Árvore AVL

Á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