Árvore AVL: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 20h25min de 5 de julho de 2015

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 autobalanceada. 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(\log 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

O nome árvore AVL vem 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

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

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

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 árvore 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$

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

Complexidade

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

Busca

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

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

Para removermos um nó de valor K na árvore, devemos buscar K nesta árvore e, caso K seja folha da árvore, apenas deletá-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, K será deletado da árvore e caso M tenha um filho à esquerda esse filho ocupará sua antiga posição na árvore.

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, 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

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

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

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.

Rotação dupla à esquerda

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.

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

Aplicações

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

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

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

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.

Referências

↑ [1]
↑ 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.
↑ 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

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

[1] [1]

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

[1]

[2]

[3]

@@ Linha 1: / Linha 1: @@
 {{Sem-fontes|data=abril de 2011| angola=| arte=| Brasil=| ciência=| geografia=| música=| Portugal=| sociedade=|1=|2=|3=|4=|5=|6=}}
-[[Imagem:Unbalanced binary tree.svg|thumb|direita|250px|Uma árvore não-AVL]]
+[[Imagem:Unbalanced binary tree.svg|thumb|250px|Uma árvore não AVL]]
 [[Imagem:AVLtreef.svg|thumb|direita|250px|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 (estrutura de dados)|á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 <math>O( \log n )</math> (no qual <math>n</math> é o número de elementos da árvore)<ref>[http://xlinux.nist.gov/dads/HTML/avltree.html]</ref>. Inserções e remoções podem também requerer o rebalanceamento da árvore, exigindo uma ou mais rotações.
+'''Árvore AVL''' (ou '''árvore balanceada pela altura'''), em [[Ciência da Computação]], é uma [[árvore (estrutura de dados)|árvore]] de busca binária autobalanceada. 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 <math>O( \log n )</math> (no qual <math>n</math> é o número de elementos da árvore)<ref>[http://xlinux.nist.gov/dads/HTML/avltree.html]</ref>. 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 [[Georgii Adelson Velsky|Adelson Velsky]] e [[Yevgeniy Landis|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.
+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 ==
-O nome árvore AVL vêm do nome do tipo de estrutura de dados em que se baseia ([[Árvore binária de busca|arvores binárias de busca]]) e do nome de seus criadores [[Adelson Velsky]] e [[Yevgeniy Landis|Landis]].
+O nome árvore AVL vem do nome do tipo de estrutura de dados em que se baseia ([[Árvore binária de busca|arvores binárias de busca]]) e do nome de seus criadores [[Adelson Velsky]] e [[Yevgeniy Landis|Landis]].
 == História ==
-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<ref>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.</ref>.
+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<ref>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.</ref>.
 == Estrutura e Propriedades ==
@@ Linha 30: / Linha 30: @@
 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.
+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<ref>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.</ref>:
+Uma árvore AVL sempre terá um tamanho menor que<ref>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.</ref>:
 <math>\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</math>
@@ Linha 50: / Linha 50: @@
 === Remoção ===
-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 removermos um nó de valor '''K''' na árvore, devemos buscar '''K '''nesta árvore e, caso '''K '''seja folha da árvore, apenas deletá-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''', '''K ''' será deletado da árvore e caso '''M '''tenha um filho à esquerda esse filho ocupará sua antiga posição na árvore.
@@ Linha 92: / Linha 92: @@
 === Dicionários ===
-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]].
+Árvores 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 ===
-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.
+Árvores 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 ==