Come fai a sapere dove eseguire le rotazioni in un albero AVL?

Question

Quindi sono auto alberi insegnamento AVL e capisco l'idea di base dietro di esso, ma voglio solo per assicurarsi che la mia intuizione di effettiva attuazione è valida:

ho esamineremo con la sinistra rotation-

Quindi, la seguente situazione è semplice:

 8 
    /\ 
    7 10 
/
    6 
/
3 

Quando aggiungiamo il 3, l'albero si riequilibra a:

8 
/\ 
    6 10 
/\ 
3 7 

Ma la rotazione si basa sull'aggiunta del 3 o dello squilibrio del sottoalbero radicato in 7? È anche basato sullo squilibrio dell'albero radicato a 8?

L'esempio seguente è dove le cose si fanno un po 'peloso, a mio parere:

 9 
    /\ 
    7 10 
/\ 
    6 8 
/
3 

Quindi, in questo caso, la sottostruttura alle 7 va bene quando è aggiunto il 3, in modo che non lo fa sottostruttura bisogno di ruotare. Tuttavia, l'albero a 9 è squilibrata con l'aggiunta di 3, quindi abbiamo basare la rotazione alle 9. Otteniamo:

 7 
    /\ 
    6 9 
//\ 
    3 8 10 

per iscritto il mio codice, che io ben presto, sarebbe il seguente codice, a partire da piccoli sottoalberi che lavorano a sottostrutture più grandi fanno il trucco?

pseudocodice:

function balanceTree(Node n){ 

    if (n is not null){ 

    balanceTree(n.rightchild); 
    balanceTree(n.leftchild); 
    } 

    if (abs(balanceFactor(n))>1){ 

    rotateAsNeeded(n);// rotate based on balance factor 

    } 

} 

Grazie in anticipo!

Answer 1

Lo pseudocodice che hai postato bilancia correttamente un albero. Detto questo, è troppo inefficiente per essere pratico: notate che state esplorando ricorsivamente l'intero albero cercando di eseguire operazioni di riequilibrio, il che renderà tutti gli inserimenti e le eliminazioni in O (n), eliminando tutti i guadagni in termini di efficienza di avere un albero equilibrato.

L'idea alla base di alberi AVL è che globalmente riequilibrare l'albero può essere fatto applicando iterativamente locali rotazioni. In altre parole, quando fai un inserimento o una cancellazione e devi fare rotazioni dell'albero, quelle rotazioni non appariranno in punti casuali nell'albero. Verranno sempre visualizzati lungo il percorso di accesso che hai preso durante l'inserimento o l'eliminazione del nodo.

Ad esempio, si erano curiosi sull'inserimento il valore 3 in questo albero:

 9 
    /\ 
    7 10 
/\ 
    6 8 

Iniziamo scrivendo la differenza nei fattori di equilibrio associate a ciascun nodo (è fondamentale che AVL nodi dell'albero negozio di questo informazioni, dal momento che è ciò che rende possibile fare inserimenti e cancellazioni in modo efficiente):

  9(+1) 
     /  \ 
     7 (0) 10 (0) 
    /\ 
    6(0) 8(0) 

Così ora vediamo cosa succede quando inseriamo 3. Ciò pone il 3 qui:

0.123.

  9(+1?) 
     /  \ 
     7 (0?) 10 (0) 
    / \ 
    6(0?) 8(0) 
/
3(0) 

Si noti che ho contrassegnato tutti i nodi sul percorso di accesso con un?, Poiché non siamo più sicuri di quali siano i loro fattori di bilanciamento.Poiché abbiamo inserito un nuovo bambino per 6, questo cambia il fattore di equilibrio per il nodo 6 a +1:

  9(+1?) 
     /  \ 
     7 (0?) 10 (0) 
    / \ 
    6(+1) 8(0) 
/
3(0) 

Analogamente, il sottoalbero sinistro 7 crebbe in altezza, per cui il suo fattore di equilibrio dovrebbe essere incrementato:

  9(+1?) 
     /  \ 
     7 (+1) 10 (0) 
    / \ 
    6(+1) 8(0) 
/
3(0) 

Infine, sotto-albero sinistro 9 è cresciuta per uno, che conferisce a questo:

  9(+2!) 
     /  \ 
     7 (+1) 10 (0) 
    / \ 
    6(+1) 8(0) 
/
3(0) 

E qui troviamo che 9 ha un fattore di equilibrio di due, il che significa che abbiamo bisogno di fare una rotazione. Consultando Wikipedia's great table of all AVL tree rotations, possiamo vedere che siamo nel caso in cui abbiamo un fattore di equilibrio di +2, dove il bambino sinistro ha un fattore di equilibrio di +1. Ciò significa che facciamo una rotazione a destra e tirare il 7 sopra il 9, come illustrato di seguito:

 7(0) 
    / \ 
    6(+1)  9(0) 
/ / \ 
3(0) 8(0) 10 (0) 

Et voil & agrave ;! L'albero è ora bilanciato.

Si noti che quando abbiamo eseguito questa procedura di correzione, non è stato necessario esaminare l'intero albero. Invece, tutto ciò che dovevamo fare era guardare lungo il percorso di accesso e controllare lì ogni nodo. In genere, quando l'attuazione di un albero AVL, la vostra procedura di inserimento farà il seguente:

• Se l'albero è nullo:
  • Inserire il nodo con fattore di equilibrio 0.
  • di ritorno che l'altezza albero ha aumentata di 1.
• Altrimenti:
  • Se il valore da inserire corrisponde alla corrente nodo, non fare nulla.
  • In caso contrario, inserire ricorsivamente il nodo nella sottostruttura appropriata e ottenere l'importo da cui è stata modificata l'altezza dell'albero.
  • Aggiornare il fattore di equilibrio di questo nodo in base all'importo modificato dall'altezza del sottostrato.
  • Se ciò richiede una serie di rotazioni, eseguirle.
  • Restituisce la modifica risultante nell'altezza di questo albero.

Poiché tutte queste operazioni sono locali, il lavoro totale svolto si basa unicamente sulla lunghezza del percorso di accesso, che in questo caso è O (log n) per alberi AVL sono sempre equilibrata.

Spero che questo aiuti!

---

PS: Il vostro esempio iniziale era questo albero:

 8 
    /\ 
    7 10 
/
    6 
/
3 

Si noti che questo albero non è in realtà un albero legale AVL, dal momento che il fattore di equilibrio del nodo principale è +2. Se si mantiene costantemente il bilancio dell'albero utilizzando l'algoritmo AVL, non si incontrerà mai questo caso.