Como o exemplo da Wikipedia de uma árvore AVL desequilibrada é realmente desequilibrada?

Question

A imagem acima é de "Entrada da Wikipedia em árvores AVL" que a Wikipedia indica que está desequilibrado. Como essa árvore ainda não está equilibrada? Aqui está uma cotação do artigo:

O fator de equilíbrio de um nó é a altura de sua subárvore direita menos a altura da subárvore esquerda e um nó com fator de equilíbrio 1, 0 ou -1 é considerado equilibrado. Um nó com qualquer outro fator de equilíbrio é considerado desequilibrado e requer reequilíbrio da árvore. O fator de equilíbrio é armazenado diretamente em cada nó ou calculado a partir das alturas das subárvores.

As subárvores esquerda e direita têm uma altura de 4. A subárvore direita da árvore esquerda tem uma altura de 3, que ainda é apenas 1 menor que 4. Alguém pode explicar o que estou perdendo?

Answer 1

Para ser equilibrado, todo nó na árvore deve, também, deve

• não tem filhos, (seja um nó "folha")
• Tem dois filhos.

• Ou, se tiver apenas um filho, essa criança deve ser uma folha.

  No gráfico que você postou, 9, 54 e 76 violam a última regra.

Adequadamente equilibrado, a árvore seria:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

ATUALIZAÇÃO: (Depois de quase 9 anos, criei um gráfico online legal para o gráfico em draw.io)

Answer 2

O nó 76 é desequilibrado, por exemplo, porque sua subárvore direita é da altura 0 e a esquerda é da altura 3.

Answer 3

Intuitivamente, é porque não é o menor possível. Por exemplo, 12 deve ser o pai de 9 e 14. Como é, 9 não tem sub-árvore de esquerda, por isso está desequilibrado. Uma árvore é uma estrutura de dados hierárquicos, portanto, uma regra como "equilibrada" geralmente se aplica a todos os nós e não apenas ao nó raiz.

Você está correto, o nó raiz é equilibrado, mas não todos os nós da árvore são.

Answer 4

Outra maneira de olhar para isso é que a altura h de qualquer nó é dado por:

h = 1 + max( left.height, right.height )

e um nó está desequilibrado sempre que:

abs( left.height - right.height ) > 1

Olhando para a árvore acima:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

Para determinar se o nó 9 é equilibrado ou não, olhamos para o auge de seus filhos:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

Agora resolva para mostrar que o nó 9 está desequilibrado:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

Cálculos semelhantes podem ser feitos para todos os outros nó.