Árvore AVL

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde abril de 2011).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Uma árvore não-AVL
Mesma árvore após balanceamento por altura, agora uma árvore AVL

Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, as alturas das duas sub-árvores a partir de cada nó diferem no máximo em uma unidade. As operações de busca, inserção e remoção de elementos possuem complexidade O( log2 n ) (no qual n é o número de elementos da árvore). Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.

O nome AVL vem de seus criadores Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.

Características[editar | editar código-fonte]

Balanceamento[editar | editar código-fonte]

Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós.

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

Operações[editar | editar código-fonte]

Inserção[editar | editar código-fonte]

Inserção em uma árvore AVL deve ser dada pela inserção do nodo seguida de uma verificação na propriedade do fator de balanceamento. Caso não obedeça a essa propriedade, deve-se fazer uma rotação conveniente.

Remoção[editar | editar código-fonte]

A remoção deve ser dada por uma rotação em torno do a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.

Pesquisa[editar | editar código-fonte]

O número de comparações para localizar um elemento em AVL é aproximadamente 1.44 log2 n no pior caso.

Rotação[editar | editar código-fonte]

A operação básica em uma árvore AVL geralmente envolve os mesmos algoritmos de uma árvore de busca binária desbalanceada. A rotação na árvore AVL ocorre devido ao seu desbalanceamento, uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".

Rotação à esquerda[editar | editar código-fonte]

Em uma árvore binária, basta empurrar o nodo N para baixo e para a esquerda. O filho à direita de N o substitui, e o filho à esquerda do filho à direita vem a ser o novo filho à direita de N. Segue pseudocódigo:

  • Seja Y o filho à direita de X
  • Torne o filho à esquerda de Y o filho à direita de X.
  • Torne X filho à esquerda de Y

Rotação à direita[editar | editar código-fonte]

Numa árvore binária basta empurrar o nodo N para baixo e para a direita. O filho à esquerda de N o substitui, e o filho à direita do filho à esquerda vem a ser o novo filho à esquerda de N. Segue pseudocódigo:

  • Seja Y o filho à esquerda de X
  • Torne o filho à direita de Y o filho à esquerda de X.
  • Torne X o filho à direita de Y

É interessante observar que as rotações duplas nada mais são que duas rotações simples seguidas, independentes se à direita ou à esquerda.

Bibliografia[editar | editar código-fonte]

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.

Ver também[editar | editar código-fonte]

O Commons possui uma categoria contendo imagens e outros ficheiros sobre Árvore AVL