Árvore AVL
Origem: Wikipédia, a enciclopédia livre.
Árvore AVL (ou árvore balanceada pela altura), em Ciência da Computação, é uma árvore de busca binária auto-balanceada. Em tal árvore, a altura de dois nós folha difere no máximo em uma unidade. As operações de busca, inserção e eliminação de elementos possuem complexidade O(logn) (no qual n é o número de elementos da árvore). Inserções e eliminaçõ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, cuja primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.
Índice |
[editar] Características
[editar] Balanceamento
Uma árvore AVL é dita balanceada quando a diferença entre as alturas das sub-árvores não é maior do que um. Caso a árvore não estiver balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de adição e exclusã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 -2 ou 2 é considerado um árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.
[editar] Operações
[editar] Inserção
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.
[editar] Remoção
A remoção deve ser dada por uma rotação em torno do nó 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.
[editar] Pesquisa
O número de comparações para localizar um elemento em AVL é aproximadamente 1.44 log2 n no pior caso.
[editar] Rotação
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. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai.
[editar] Rotação à esquerda
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
- Troque X por Y
- Torne o filho à esquerda de Y o filho à direita de X.
[editar] Rotação à direita
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
- Troque X por Y
- Torne o filho à direita de Y o filho à esquerda de X.
É interessante observar que as rotações duplas nada mais são que duas rotações simples seguidas, independentes se à direita ou à esquerda.
[editar] Ver também
[editar] Bibliografia
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.
