888565856585

Árvores AVL, Multidirecionais, B e B+*

2.1 Árvores Balanceadas (AVL)

Definições:

Altura (profundidade) de uma árvore: nível máximo das folhas da árvore
Por conveniência, a altura de uma árvore vazia é definida como sendo –1
Árvore binária perfeitamente balanceada: os números de nós de quaisquer duas sub-árvores de um nó nunca diferem em mais de 1
Árvore binária balanceada AVL: árvore binária na qual as alturas de quaisquer duas sub-árvores nunca diferem em mais de 1
AVL: homenagem a Adelson-Velskii e Landis que demonstraram várias propriedades interessantes dessas árvores
Note que toda árvore perfeitamente balanceada também é uma árvore AVL, mas a recíproca não é verdadeira; i.e., a árvore perfeitamente balanceada tem critério de balanceamento mais rígido do que árvores AVL
Exemplo: a árvore binária a seguir é AVL, mas não é perfeitamente balanceada:

Balanceamento de um nó: a altura de sua sub-árvore esquerda menos a altura de sua sub-árvore direita
Conclusão: cada nó de uma árvore AVL tem balanceamento -1, 0 ou 1, conforme sua sub-árvore esquerda tem altura menor, igual ou maior do que a altura de sua sub-árvore direita

Exemplo: a figura a seguir representa uma árvore AVL (o número no interior de cada nó é o balanceamento do nó)

Se todas as chaves tiverem a mesma probabilidade de serem pesquisadas, a busca numa árvore binária balanceada será mais eficiente do que numa árvore binária não-balanceada
Conforme foi visto, o grau de balanceamento depende da ordem na qual a chave é inserida na árvore
A função que faz busca e inserção apresentada na seção anterior, quanto aplicada a uma árvore balanceada, não garante que a árvore permanecerá balanceada
Restabelecer o balanceamento de uma árvore perfeitamente balanceada após inserção ou remoção de um nó não é trivial, mas, no caso de árvores AVL, essa tarefa é relativamente fácil

A figura a seguir ilustra todas as inserções possíveis que podem ser