In che modo l'esempio di Wikipedia di un albero AVL non bilanciato è davvero squilibrato?

Question

L'immagine sopra è da " La voce di Wikipedia sugli alberi AVL " che Wikipedia indica è sbilanciato. In che modo questo albero non è già bilanciato? Ecco una citazione dall'articolo:

  

Il fattore di equilibrio di un nodo è l'altezza della sua sottostruttura destra meno l'altezza della sua sottostruttura sinistra e un nodo con fattore di equilibrio 1, 0 o -1 è considerato bilanciato. Un nodo con qualsiasi altro fattore di equilibrio è considerato sbilanciato e richiede il riequilibrio dell'albero. Il fattore di equilibrio viene memorizzato direttamente su ciascun nodo o calcolato dalle altezze dei sottotitoli.

Entrambi i sottotitoli sinistro e destro hanno un'altezza di 4. Il sottotree destro dell'albero sinistro ha un'altezza di 3 che è ancora solo 1 in meno di 4. Qualcuno può spiegare cosa mi sto perdendo?

Answer 1

Per essere bilanciato, ogni nodo nella struttura deve,

• non ha figli, (essere un nodo "foglia")
• Avere due figli.

• Oppure, se ha solo un figlio, quel figlio deve essere una foglia.

  Nel grafico che hai pubblicato, 9, 54 & amp; 76 viola l'ultima regola.

Correttamente bilanciato, l'albero dovrebbe apparire come:

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

AGGIORNAMENTO: (dopo quasi 9 anni, ho creato un fantastico grafico online per il grafico a draw.io )

Answer 2

Il nodo 76 non è bilanciato, ad esempio, perché la sottostruttura destra è di altezza 0 e la sinistra è di altezza 3.

Answer 3

Intuitivamente, è perché non è il più piccolo possibile. ad esempio, 12 dovrebbe essere il genitore di 9 e 14. Così com'è, 9 non ha sottoalbero sinistro, quindi è sbilanciato. Un albero è una struttura di dati gerarchica, quindi una regola come "bilanciata" spesso si applicano a tutti i nodi e non solo al nodo principale.

Hai ragione, il nodo radice è bilanciato, ma non tutti i nodi dell'albero sono.

Answer 4

Un altro modo di vedere questo è che l'altezza h di qualsiasi nodo è data da:

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

e un nodo è sbilanciato ogni volta:

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

Guardando l'albero sopra:

- 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

Per determinare se il nodo 9 è bilanciato o no, osserviamo l'altezza dei suoi figli:

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

Ora risolvi per mostrare che il nodo 9 è sbilanciato:

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

Calcoli simili possono essere effettuati per ogni altro nodo.