Home

Árvores AVL (Inserção)

(aula 12)

 

As árvores AVL, propostas por Adel’son, Vel’skii e Landis em 1962, foram historicamente a primeira estrutura de dados a oferecer operações de inserção, remoção e busca em tempo logarítmico.

Uma árvore binária de busca A é uma árvore AVL, ou tem a propriedade AVL, tal que, para qualquer nó n de A, as alturas de suas subárvores (fe, fd) diferem no máximo de 1:

|h(fe) – h(fd) | <= k  : k = 0, 1

. Na figura  estão representadas duas árvores binárias de busca. A da esquerda (a) não é AVL, pois a altura da subárvore direita da raiz é 1 e a da esquerda é 3.

Inserção:

Seja c uma nova chave a inserir numa arvore AVL A. Primeiro, c é inserido como folha de A, seguindo o algoritmo de inserção numa Árvore Binaria Ordenada. Se depois da inserção a árvore fica AVL, então nada há a fazer, senão é necessário tornar AVL.

Para que uma inserção resulte imediatamente numa árvore AVL, é preciso ter pelo menos um nó da árvore inicial tal que uma subárvore tem altura estritamente superior à da outra, e que a inserção seja realizada na outra subárvore. Seja n o nó de maior nível que enraíza uma subárvore S que não tem propriedade AVL depois da inserção. Em consequência, essa subárvore S tem uma altura estritamente superior a 0, e não é vazia. Supondo que E é a subárvore esquerda de S e tem altura maior que D, a subárvore direita de S. Seja a a altura de D, logo a+1 é a altura de E. Seja n_e a raiz de E, EE e ED são as subárvores à esquerda e à direita de n_e . Necessariamente, a é a altura da mais alta das subárvores de n_e . Há assim dois casos possíveis:

. Inserções à esquerda resultando em árvores não AVL

Caso (a) – A inserção ocorre em EE. Como, por hipótese o resultado da inserção não é AVL, as alturas de EE antes e depois da inserção devem ser a e a+1. Neste caso qual é altura de ED? Como a árvore era inicialmente balanceada, a altura de EE é a ou a-1. Mas não pode ser a-1, pois, neste caso n_e é um nó que enraíza uma subárvore que não é AVL e o seu nível é superior ao de n. O novo nó é inserido na subárvore esquerda de n_e . Depois desta inserção, a altura da subárvore esquerda de n é a+2 e a altura da subárvore direita é a. Para corrigir esse desequilibro, a subárvore é rearranjada usando uma rotação simples à direita.

Caso(b) – A inserção ocorre em ED. Como, por hipótese o resultado da inserção não é AVL, as alturas de ED antes e depois da inserção devem ser a e a+1. Para as mesmas razões apresentadas no ponto anterior a altura de EE é a. Como o novo nó é inserido em ED, a altura de E torna-se igual a a+2, enquanto que a altura de D permaneceu igual a a. O equilíbrio é restabelecido usando uma rotação dupla à direita.

No caso simétrico, onde é a subárvore direita da raiz que está inicialmente mais alta que a subárvore esquerda:

. Inserções à direita resultando em arvores não AVL.

Caso(c) – A inserção à direita, simétrica do caso(a).

Caso(d) – A inserção à direita, simétrica do caso(b).

Uma vez transformada a árvore por rotação simples ou dupla, de tal maneira a reequilibrar a subárvore enraizada no nó de maior nível, o algoritmo de inserção procede, procurando o segundo de maior nível que enraíza uma subárvore que não tem propriedade AVL, até que todas as subárvores estejam equilibradas.

Rotação Simples:

Para explicar a rotação simples, tratemos do caso particular da rotação simples a direita, sendo a rotação simples à esquerda a operação simétrica.

A operação de rotação simples à direita segue os seguintes passos:

1.      n_e é colocado na raiz

_2.        EE permanece a subárvore esquerda de n_e

_3.        n torna-se a raiz da subárvore direita de n_e

4.      ED é a nova subárvore esquerda de n

5.      D permanece a subárvore direita de n

. Rotação simples à direita.

A operação simétrica é a rotação simples à esquerda que corresponde ao caso(c). É de notar que, em todos os casos, depois de inserir e rearranjar, a altura da subárvore volta ao seu valor inicial a+2, A tinha propriedade AVL, depois da inserção, A permanece AVL.

. Rotação simples à esquerda.

Rotação Dupla:

No caso(b), uma rotação dupla à direita é necessária. Observar que ED tem altura a+1, onde a>0. Consequentemente, ED tem pelo menos um nó. Assim a rotação dupla à direita é formada pelas seguintes etapas:

1.      O nó n_ed é a nova raiz, n_e é sua filha direita, e n sua filha esquerda

2.      As subárvores esquerda e direita de n_e são respectivamente EE e EDE

3.      As subárvores esquerda e direita de n_ed são respectivamente EDD e D

. Rotação dupla à direita.

Por hipótese EE, EDE, EDD e D têm a propriedade AVL e são de altura a. Em consequência, as subárvores enraizadas em n_e e n tem a propriedade AVL e altura a+1. Em conclusão a arvore enraizada em n_ed tem a propriedade AVL. Assim, depois de inserir e rodar, a altura da subárvore S é de novo o seu valor inicial a+2, portanto A permanece AVL.

O algoritmo implementando estas operações é baseado no facto que uma rotação dupla é equivalente a duas rotações simples consecutivas.

 

Paulo Renato nº 8503 – Ensino Informática

Rui Rodrigues nº13607 –Engª Sistemas e Computação