Á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.

Árvore de Busca Binária

                Uma árvore de busca binária nada mais é do que uma arvore binária organizada especificamente para procuras, a busca de um nó dentro arvore se inicia pela raiz da arvore e desce de nível a nível até encontrar o nó desejado, utilizando a seguinte escolha, encontrou um nó maior que o desejado segue o ponteiro esquerdo, encontrou nó menor que o desejado segue o ponteiro direito, caso a procura alcance uma folha antes de encontrar um equivalente, o mesmo não existe na árvore.

                A eficiência de uma busca binária em árvores é excelente, uma vez que o pior caso, basta procurar a informação em apenas uma ramificação, ao invés de percorrer cada um de todos os dados, se uma arvore tem N nós distribuídos aleatoriamente, deverá ter uma altura media de lg N de nós. Por exemplo, se inserir em uma arvore os números 7, 3, 9, 2, 6,  11, 1, 5, 4 e 10, teremos como resultado a árvore da figura 1 com três níveis e razoavelmente bem balanceada. Se iniciar uma busca pelo numero 6, começa seguindo pelo ponteiro esquerdo na raiz 7, seguido do ponteiro direito na subárvore de árvore de valor 3 e já terá encontrado o equivalente.

Figura 1

               

                Pode ser melhorado? Certamente, a árvore da figura 1 precisa apenas de dois níveis de altura,lembre que uma árvore balanceada consiste em manter a mesma com a menor altura possível para um dado numero de nós, com o balanceamento correto na árvore, acaba eliminando o surgimento de uma ramificação demasiadamente longa que precise ser percorrida.

Entretanto  o formato desta árvore binária depende de em qual ordem o conjunto de itens foi carregado, os exemplos de árvores vistos anteriormente não possuem nenhum mecanismo interno que impeça o desbalanceamento entre subárvores.

Para melhor compreender a importância do balanceamento de uma arvore de busca binária, considere o pior caso ocorre quando toda a informação de entrada se encontra ordenada, na figura 2 temos o exemplo do que acontece na arvore quando recebe os números em ordem crescente, com cada elemento sendo sempre inserido a direita, que resulta em uma arvore desbalanceada a tal ponto que se assemelha a uma lista encadeada.

Figura 2

Em situações como esta, altura da arvore não é lg N e sim N, devido a péssima eficiência do pior caso que acaba tornando inaceitável o uso da árvore, de imediato duas soluções para o problema ocorrem, primeira alternativa aonde garante-se uma ordem aleatória de dados como no exemplo da figura 1 resultando num balanceamento ou a segunda opção em que todos os dados são analisados antes de adiciona-los.

Caso se conheça de antemão os itens que serão carregados, é possível construída uma arvore binária completa ou quase completa, mas como é de praxe na programação pratica, a ordem pela qual os nós são adicionados e excluídos não pode ser antecipada, o que irá requerer uma abordagem mais proativa utilizando algoritmos que forçam a arvore a se balancear sempre que executa uma ação de adição ou exclusão.

Nas próximas postagens veremos mais sobre o assunto através das analises das árvores AVL, Splay e Rubro-negra.