A figura abaixo é uma árvore que não é AVL, explique por que ela está desregulada e indique a operação para regular, tornando-a uma árvore AVL.

15

------

Uma árvore AVL é uma árvore binária balanceada, no sentido em que o chamado fator de balanço, que nada mais é que a diferença entre a altura da sub-árvore da esquerda menos a altura da sub-árvore da direita:

\[f=h_L-h_R\]

deve ter módulo sempre inferior a 2.

------

Analisando a imagem é possível determinar o fator de balanço de cada vértice:

\[f_1=0-0=0\ \checkmark\]

\[f_2=1-2=-1\ \checkmark\]

\[f_3=0-0=0\ \checkmark\]

\[f_4=1-1=0\ \checkmark\]

\[f_5=0-0=0\ \checkmark\]

\[f_6=3-1=2\ \times\]

\[f_8=0-0=0\ \checkmark\]

Esses resultados nos mostram que o nó 6 deve ser balanceado.

------

Quando o fator de balanço é maior que 1, devemos rotacionar para a direita. Para tal devemos pegar o maior elemento da sub-árvore da esquerda (5), torná-lo raiz e deslocar a atual raiz (6) e seu filho da direita para a direita, de forma a termos a nova lista de fatores de balanço:

\[f_1=0-0=0\ \checkmark\]

\[f_2=1-2=-1\ \checkmark\]

\[f_3=0-0=0\ \checkmark\]

\[f_4=1-0=1\ \checkmark\]

\[f_5=3-2=1\ \checkmark\]

\[f_6=0-1=-1\ \checkmark\]

\[f_8=0-0=0\ \checkmark\]