In che modo l'esempio di Wikipedia di un albero AVL non bilanciato è davvero squilibrato?
-
04-07-2019 - |
Domanda
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?
Soluzione
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 )
Altri suggerimenti
Il nodo 76 non è bilanciato, ad esempio, perché la sottostruttura destra è di altezza 0 e la sinistra è di altezza 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.
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.