Árvore AVL

I - Apresentação

Como descrito anteriormente, busca binária em arvores trabalham bem somente quando a árvore está balanceada. Infelizmente, manter uma árvore de busca binária balanceada é um problema mais complicado do que parece inicialmente. Não obstante, existem algumas abordagens inteligentes que podem ser usadas para se criar ou manter uma arvore balanceada.

Por exemplo, sabendo de antemão os itens que serão utilizados na arvore, colocamos os itens mais frequentemente acessados na parte alta da arvore, criando assim uma arvore balanceada por peso.

Ao generalizar a utilidade assumi-se que todos os itens utilizados na árvore tem a mesma frequência. Como consequência desta ação a árvore terá balanceamento de altura, ou seja, nenhuma subárvore terá permissão de ser maior que seu irmão.

Uma formulação especifica desta ideia foi introduzida por dois matemáticos soviéticos, Georgii Maximovich Adelson-Velsky e  Evgenii Mikhailovich Landis. As árvores que seguem o modelo de programação são conhecidas como arvores AVL. Uma árvore AVL é uma árvore de busca binária que obedece a seguinte regra: A altura das árvores filhas de um nó tem apenas a diferença de um.

Árvore AVL

Esta regra requer que a árvore seja vista como uma floresta de subárvores e imponha a regra através da árvore, como mostrado na figura acima. Note que a regra aplica-se tanto para pequenas subárvore (círculos vermelho e amarelo) como também para as duas subárvores da raiz (círculos verde e azul). Enquanto a regra parece pesada em sua execução, é possível perceber que uma árvore pode ser mantida balanceada realizando apenas manipulações locais na mesma.

  

II - Fator de balanço

Para isso a árvore AVL armazena um pedaço extra de informação em cada nó: fator de balanço. O fator de balanço de um nó é a altura da subárvore enraizada em seu filho esquerdo menos a altura da subárvore enraizada em seu filho direito.

            A altura de cada subárvore será definida pelo filho de maior altura somado de um, ao pegar o exemplo da figura 1 e incluir os valores de altura temos que cada folha terá o valor zero.

            A partir das folhas, a altura da subárvore pai irá escolher sempre a subrvore filha de maior altura e somar 1.

Como se observa, a altura da arvore utilizara como referencia sempre a altura do maior filho.

Possuindo a altura de cada nó que se encontra na árvore, basta fazer altura do filho esquerdo menos a altura do filho direito para obter o fator de balanço.

Após adicionar ou apagar nós, se deve rebalancear a árvore caso um desbalanceamento tenha sido introduzido, ajustando para que todos os fatores de balanço fiquem +1, -1 ou 0.   

Uma subárvore com o fator de balanço +1 é dita como esquerda pesada. Uma subárvore com fator de balanço -1 é dita como direito-pesada. Uma subárvore cujo nó tem o fator de balanço 0 é considerada balanceada. Por manter suas subárvores balanceadas, uma árvore AVL se mantém de forma geral aproximadamente balanceada.

III - Rotação

A rotação faz o rebalanceamento de uma parte da árvore AVL ao rearranjar nós enquanto preserva a relação aonde o esquerdo é menor que o pai e o pai é menor que o da direita, que deve ser mantida para que árvore permaneça uma árvore de busca binária. Após a rotação, o fator de balanço entre todos os nós na subárvore que girou em volta são +1, -1 ou 0.

Na figura abaixo vemos as duas operações básicas de rotação para rebalancear a arvore sem violar a propriedade de busca binária com filho esquerdo menor que pai menor que filho direito, aonde T1, T2 e T3 são subárvores com raiz em y (lado esquerdo) ou em x (lado direito).

   

Operações básicas de rotação

  

Existem somente quatro casos em que as rotações podem ser aplicadas. Estes são as sequencias EE (Esquerda Esquerda), ED (Esquerda Direita), DD (Direita Direita) e DE (Direita Esquerda).

1.            Caso EE (Esquerda Esquerda):

2.            Caso ED (Esquerda Direita):

3.            Caso DD (Direita Direita):

4.            Caso DE (Direita Esquerda):

Todos os ajustes de rotação para DD e DE são simétricos de EE e ED.

O efeito da regra AVL é assegurar que árvore nunca fique substancialmente desbalanceada, e pode ser mostrado que a altura de uma árvore AVL com N nós será proporcional à lg N. De qualquer maneira, realmente programar uma árvore AVL é problemático devido ao numero de casos especiais que devem ser considerados, como também a possibilidade de que a árvore exija múltiplas rotações para consertar os novos desbalanceamentos gerados pelas rotações anteriores.

Isto implica em atravessar de volta o caminho de acesso tomado durante a inserção ou exclusão, recorrendo à recursividade, entretanto existem soluções mais simples, que embora não obtenham um balanceamento tão eficiente como o AVL, mas que permitem rotações ocorrerem enquanto a busca segue direção abaixo como a árvore Rubro negra.