Prendi il seguente albero:
50
40
30
20
10
Quale nodo sarà prima bilanciato? 50 o 30
Caso 1: 50
L'albero è
30
20 40
10 50
Caso 2: 30
L'albero è
40
/ \
20 50
10 30
Bene, entrambi sono alberi AVL, quindi entrambi sono corretti?
Il tuo primo albero non è un albero AVL. Anche meno un elemento non è un albero AVL (quindi non possiamo nemmeno considerarlo come un albero AVL in equilibrio).
Le operazioni AVL sono definite sugli alberi AVL per produrre un nuovo albero AVL. Sono definiti in termini di nodo che è stato inserito o eliminato.
Quindi, non abbiamo un albero AVL da avviare, e non abbiamo informazioni su come abbiamo ottenuto quell'albero (era qualcosa appena inserito o cancellato, e se sì, cosa?). In breve, penso che la questione debba essere chiarita.
È più facile pensare al problema in modo ricorsivo bilanciando 30 prima di 50. Poiché i nodi foglia (senza nodi figli) sono già bilanciati, è possibile bilanciare l'albero in modo bottom-up, sapendo che tutti i nodi sotto il nodo corrente sono alberi equilibrati.
z5h ha ragione. Se vuoi un albero AVL devi costruirlo, aggiungendo gli elementi uno per uno e bilanciamento se necessario.
Leggi altre domande sui tag data-structures binary-tree