Hfhgf

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (273 palavras )
  • Download(s) : 0
  • Publicado : 24 de outubro de 2012
Ler documento completo
Amostra do texto
Á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 apartir 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 elementosda á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 balanceadaquando, 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 obalanceamento é 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...
tracking img