Hfhgf

Á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ó difere 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 é 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. Índice [esconder] * 1 Características * 1.1 Balanceamento * 2 Operações * 2.1 Inserção * 2.2 Remoção * 2.3 Pesquisa * 3 Rotação * 3.1 Rotação à esquerda * 3.2 Rotação à direita * 4 Ver também * 5 Bibliografia * 6 Ligações externas |
-------------------------------------------------
[editar]Características
[editar]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