Árvore AVL

Page 1

Árvores AVL

Estrutura criada em 1962 pelos soviético, Adelson Velsky e Landis.

" Uma árvore binária T é denominada AVL, para quando qualquer nó de T, as altura de suas subárvores, esquerda e direita, diferem um módulo de até uma unidade." ( Wikipédia ).

Temos:

| hE - hD | <= 1 ; ou seja o módulo da diferença da alturas de dois nós das subárvores esqueda e direita é igual ou menor que 1.

Esse valor é denominado fator de balanço. Cada nó possui um fator.

Caso o valor do fator de balanço seja igual a -1,0 e +1 podemos dizer que nó é um nó regulado. Para se ter um Árvore AVL temos de ter todos os nós regulados.

O fator de balanceamento é calculado a cada nó. A altura de uma árvore vazia é -1.

fonte: https://youtu.be/YkF76cOgtMQ?list=PLxI8Can9yAHf8k8LrUePyj0y3lLpigGcl

Uma inserção pode fazer com que o fator de balanceamento vire +-2. Contudo somente nós no caminho do ponto de inserção até a raiz podem ter mudado sua altura.

Então após a inserção volta-se até a raiz, nó por nó, atualizando as alturas.

Rotação

Existe dois tipo de rotação

à esquerda.

à direita