Árvore AVL

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes fiáveis e independentes. (desde abril de 2011). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
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)[1] . 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 soviéticos Adelson Velsky e Landis, e sua primeira referência encontra-se no documento "Algoritmos para organização da informação" de 1962.

Nessa estrutura de dados cada elemento é chamado de nó. Um nó contém um valor próprio, um valor de altura, e dois filhos que são outros nós. A partir desta estrutura é possível montar um algoritmo eficiente para armazenar, buscar e deletar informações.

Terminologia[editar | editar código-fonte]

O nome árvore AVL vêm do nome do tipo de estrutura de dados em que se baseia (arvores binárias de busca) e do nome de seus criadores Adelson Velsky e Landis.

História[editar | editar código-fonte]

Esta estrutura foi criada em 1962 pelos soviéticos Adelson Velsky e Landis que a criaram para que fosse possível inserir e buscar um elemento em tempo C log (n) operações, onde n é o número de elementos contido na árvore. Tal estrutura foi a primeira árvore binaria balanceada criada[2] .

Estrutura e Propriedades[editar | editar código-fonte]

A árvore é na verdade um conjunto de nós interligados. Cada nó pode ter até duas ligações: uma com seu filho da esquerda e outra com seu filho da direita.

Cada nó contém as seguintes informações:

Altura h: Número inteiro que determina a altura do nó. O número zero representa a raiz da árvore.

Valor v: Valor da chave do nó

Filho da esquerda: Pode existir ou não. Caso exista o valor da chave do filho da esquerda deve obrigatoriamente ser menor que o valor da chave do pai.

Filho da direita: Pode existir ou não. Caso exista o valor da chave do filho da direita deve obrigatoriamente ser maior que o valor da chave do pai.

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. Para garantirmos essa propriedade a cada inserção ou remoção a diferença de altura dos nós afetados e dos nós superiores deve ser recalculada de modo que a altura do nó que está sendo recalculado seja igual a altura do nó esquerdo menos a altura do nó direito.

Uma arvore AVL sempre terá um tamanho menor que[3] :  

\log _\varphi(\sqrt{5}(n+2))-2 = \frac{{\log _2(\sqrt{5}(n+2))}} {{\log_2(\varphi)}} -2 = \log _\varphi (2) \cdot \log _2(\sqrt{5}(n+2)) - 2 \approx 1.44\log_2(n+2)-0.328

Complexidade da árvore AVL em notação O.

  Onde n é o número de elementos da árvore e \varphi é a proporção áurea. 

Complexidade[editar | editar código-fonte]

A árvore AVL tem complexidade O(log n) para todas operações e ocupa espaço n, onde n é o numero de nós pertencentes à arvore.

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

Busca[editar | editar código-fonte]

Para buscarmos um nó basta comparar o seu valor com o valor do nó que está sendo analisado (raiz no caso da primeira iteração). Se o valor buscado for menor que o valor do nó que está sendo analisado devemos efetuar a busca no filho da esquerda do nó atual, caso contrário deveremos efetuar a busca no filho da direita do nó atual.  Se o nó não for encontrado com essa busca podemos ter certeza que ele não existe dentro da árvore.

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

Para inserirmos um novo nó de valor K em uma árvore AVL é necessária uma busca por K nesta mesma árvore. Após a busca o local correto para a inserção do nó K será encontrado. Depois de inserido o nó a altura do nó pai e de todos os nós acima deve ser atualizada. Em seguida o algoritmo de rotação deve ser acionado para o nó pai e depois para todos os nós superiores caso um desses nós caia em uma das condições de rotação.

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

Para removermos um nó de valor K na árvore devemos buscar K nesta árvore e, caso K seja folha da arvore, apenas deleta-lo. Caso K pertença à árvore, mas não seja uma folha da árvore devemos substituir o valor de K com o valor mais próximo possível menor ou igual a K pertencente à árvore.

Para encontrar este valor basta percorrer a subárvore da direita do filho da esquerda de K, até encontrarmos o maior valor M desta subárvore. O valor de K será substituído por M, M será deletado da árvore e caso M tenha um filho à esquerda esse filho ocupará sua antiga posição na árvore.

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

Para garantirmos as propriedades da árvore AVL rotações devem ser feitas conforme necessário após operações de remoção ou inserção. Seja P o nó pai, FE o filho da esquerda de P e FD o filho da direita de P podemos definir 4 tipos diferentes de rotação:

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

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a 1. O nó FE deve tornar o novo pai e o nó P deve se tornar o filho da direita de FE. 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
A árvore da esquerda ficou desbalanceada após a inserção do nó 2, necessitando assim de uma rotação a direita. Após a rotação o nó 3 virou o pai dos nós 2 e 5.

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

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a -2 e a diferença das alturas h dos filhos de FD é igual a -1. O nó FD deve tornar o novo pai e o nó P deve se tornar o filho da esquerda de FD. 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
    A árvore da esquerda ficou desbalanceada após a inserção do nó 7, necessitando assim de uma rotação a esquerda. Após a rotação o nó 5 virou o pai dos nós 3 e 7.

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

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a 2 e a diferença das alturas h dos filhos de FE é igual a -1. Nesse caso devemos aplicar uma rotação à esquerda no nó FE e, em seguida, uma rotação à direita no nó P.

A árvore da primeira figura ficou desbalanceada após a inserção do nó 4. Para balanceá-la foi executada uma rotação dupla à direita, ou seja, primeiro foi executada uma rotação à esquerda no nó 3 (segunda figura) e depois foi executada uma rotação à direita no nó 4 (terceira figura).

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

Deve ser efetuada quando a diferença das alturas h dos filhos de P é igual a -2 e a diferença das alturas h dos filhos de FD é igual a 1. Nesse caso devemos aplicar uma rotação à direita no nó FD e, em seguida, uma rotação à esquerda no nó P.

A árvore da primeira figura ficou desbalanceada após a inserção do nó 4. Para balanceá-la foi executada uma rotação dupla à esquerda, ou seja, primeiro foi executada uma rotação à direita no nó 5 (segunda figura) e depois foi executada uma rotação à esquerda no nó 3 (terceira figura).

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

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

A árvore AVL é muito útil pois executa as operações de inserção, busca e remoção em tempo O(log n), sendo inclusive mais rápida que a árvore rubro-negra para aplicações que fazem uma quantidade excessiva de buscas, porém esta estrutura é um pouco mais lentas para inserção e remoção. Isso se deve ao fato de as árvores AVL serem mais rigidamente balanceadas.

Dicionários[editar | editar código-fonte]

Arvores AVL são usadas as vezes para formar um dicionário de uma linguagem ou de programas, como os opcodes de um assembler ou um interpretador.

Geometria Computacional[editar | editar código-fonte]

Arvores AVL podem ser usadas também na geometria computacional por ser uma estrutura muito rápida. Sem uma estrutura com complexidade O(log n) alguns algoritmos da geometria computacional poderiam demorar dias para serem executados.

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.
  • Adelson-Velskii, G.; E. M. Landis (1962). "An algorithm for the organization of information". Proceedings of the USSR Academy of Sciences 146: 263–266. (Russian) English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.

Referencias[editar | editar código-fonte]

  1. http://xlinux.nist.gov/dads/HTML/avltree.html
  2. Kent, Allen; Williams, James G. (1993), Encyclopedia of Computer Science and Technology: Volume 28 - Supplement 13: AerosPate Applications of Artificial Intelligence to Tree Structures, CRC Press, p. 373, ISBN 9780824722814.
  3. Knuth, Donald E. (2000). Sorting and searching (2. ed., 6. printing, newly updated and rev. ed.). Boston [u.a.]: Addison-Wesley. p. 460. ISBN 0-201-89685-0.

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

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