Á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 …exibir mais conteúdo…

Sejam hE(p) e hD(p) as alturas das sub-árvores esquerda e direita de p, respectivamente. Naturalmente, |hE(p)hD(p)| > 1. Então, conclui-se que |hE(p)-hD(p)| = 2, pois T era uma árvore AVL e a inserção de um único nó não pode aumentar a altura de qualquer sub-árvore em mais do que 1. As 4 situações possíveis a serem analisadas são: Caso 1: hE(p) > hD(p) Seja q o nó que foi inserido na sub-árvore esquerda de p. Além disso, sabe-se que p possui um filho esquerdo u diferente de q (caso contrário, p não teria ficado desbalanceado). Finalmente, por esse mesmo motivo, sabe-se que hE(u) é diferente de hD(u). Neste caso, são duas situações possíveis: Caso 1.1: hE(u) > hD(u) Esta situação está ilustrada na fig 1(a), sendo q um nó pertencente a T1. Observe que h(T1) - h(T2) = 1 e h(T2) = h(T3).

fig.1: rotação para a direita

3 void rot_dir (tavl *T) { tavl u; u = (*T)->esq; (*T)->esq = u->dir; u->dir = *T; (*T)->bal = 0; *T = u; } Conseqüentemente, uma rotação direita da árvore com raiz p transforma a sub-árvore considerada na árvore da fig.1(b), o que restabelece o balanceamento da sub-árvore em p e, conseqüentemente, da sub-árvore T.

Caso 1.2: hD(u) > hE(u) Neste caso, u possui um filho direito v, e a situação é ilustrada na fig.2(a), sendo que o modulo de h(T2)- h(T3) é menor que 1 e o máximo de h(T2) e h(T3) = h(T1)=h(T4).

fig.2: rotação para a esquerda e em seguida para a direita void rot_esq_dir (tavl *T) { tavl u,v; u = (*T)->esq; v = u->dir; u->dir =