Arvores binarias c

ÁRVORE AVL
ÁRVORE BALANCEADA Sucessivas inserções e remoções de nós em uma árvore binária de pesquisa fazem com que existam diferenças entre os níveis das suas folhas, o que acarreta grandes diferenças de performance no acesso a seus nós. No pior caso, se os dados já estão ordenados, a árvore será uma lista, perdendo toda a eficiência da busca. Nesses casos, diz-se que a árvore ficou degenerada. Uma árvore é dita balanceada quando, para qualquer nó, as suas sub-árvores à esquerda e à direita possuem a mesma altura. Isso equivale a dizer que todos os ponteiros nulos estão no mesmo nível, ou seja, que a árvore está completa. Isso nem sempre é possível, por conta do número de nós da árvore. Um critério mais simplificado seria considerar uma árvore balanceada se o número máximo de nós da sub -árvore esquerda diferencie no máximo 1 da sub-árvore direita.

BALANCEAMENTO ESTÁTICO Consiste em construir uma nova versão de uma árvore binária de pesquisa, reorganizando-a. Essa reorganização possui duas etapas: 1. Percurso in-ordem sobre a árvore, para gerar um vetor ordenado com o conteúdo de todos os seus nós. 2. Criação de uma ABP a partir desse vetor, da seguinte forma: a) Identifica-se o nó médio do vetor, que passa a ser considerado a raiz da ABP que está sendo criada. b) Cada uma das metades do vetor é tratada analogamente, de modo que cada nó intermediário será a raiz de uma sub-árvore.

BALANCEAMENTO DINÂMICO: AVL Em 1962, dois matemáticos russos (Adelson-Velskii e Landis) definiram uma nova estrutura para balanceamento de árvores ABP e deram o nome de AVL. Esta nova estrutura permite o balanceamento dinâmico da árvore e com boa performance. Fator de Balanceamento (FB) de um nó É a altura da subárvore direita do nó menos a altura da subárvore esquerda do nó. Inserção AVL: O que pode acontecer quando um novo nó é inserido numa árvore balanceada? Na árvore abaixo:

-

Nós 9 ou 11 podem ser inseridos sem balanceamento. Subárvore com raiz 10 passa a ter uma