Árvore AVL: diferenças entre revisões

[[Imagem:Unbalanced binary tree.svg|thumb|direita|250px|Uma árvore não- 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-balanceadaautobalanceada. 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.

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.

O nome árvore AVL vêmvem 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]].

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

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvoresubá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á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>:  

Para removermos um nó de valor '''K''' na árvore, devemos buscar '''K '''nesta árvore e, caso '''K '''seja folha da arvoreárvore, apenas deletadeletá-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.

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

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