Bilanciamento di un albero binario (AVL)

Question

Ok, questo è un altro nel regno della teoria per i ragazzi del CS in giro.

Negli anni '90 ho fatto abbastanza bene a implementare i BST. L'unica cosa che non sono mai riuscito a capovolgere era la complessità dell'algoritmo per bilanciare un albero binario (AVL).

Ragazzi, potete aiutarmi su questo?

Answer 1

Un albero capro espiatorio ha probabilmente l'algoritmo di determinazione dell'equilibrio più semplice da capire. Se un inserimento fa sì che il nuovo nodo sia troppo profondo, trova un nodo attorno al quale riequilibrare, osservando il bilanciamento del peso anziché il bilanciamento dell'altezza. Anche la regola per riequilibrare la cancellazione è semplice. Non memorizza alcuna informazione arcana nei nodi. È più difficile dimostrare che è corretto, ma non è necessario per capire l'algoritmo ...

Tuttavia, a differenza di un AVL, non è sempre bilanciato in altezza. Come il rosso-nero, il suo sbilanciamento è limitato, ma a differenza del rosso-nero è sintonizzabile con un parametro, quindi per la maggior parte degli scopi pratici sembra equilibrato come è necessario. Ho il sospetto che se lo sintonizzi troppo strettamente, però, finisce come cattivo o peggiore di AVL per inserimenti nel caso peggiore.

Risposta alla modifica della domanda

Fornirò il mio percorso personale per comprendere gli alberi AVL.

Per prima cosa devi capire cos'è una rotazione dell'albero, quindi ignora tutto il resto che hai mai sentito gli algoritmi AVL e capiscilo. Mettiti dritto nella tua testa che è una rotazione a destra e quale è una rotazione a sinistra, e ciò che ciascuno fa all'albero, altrimenti le descrizioni dei metodi precisi ti confonderanno e basta

Quindi, capire che il trucco per bilanciare gli alberi AVL è che ogni nodo registra in esso la differenza tra l'altezza dei suoi sottotitoli sinistro e destro. La definizione di "altezza bilanciata" è che questa è compresa tra -1 e 1 per ogni nodo dell'albero.

Quindi, comprendi che se hai aggiunto o rimosso un nodo, potresti aver sbilanciato l'albero. Ma puoi solo aver modificato il saldo dei nodi che sono antenati del nodo che hai aggiunto o rimosso. Quindi, quello che farai è tornare indietro sull'albero, usando le rotazioni per bilanciare tutti i nodi sbilanciati che trovi e aggiornando il loro punteggio di equilibrio, fino a quando l'albero non viene nuovamente bilanciato.

La parte finale della comprensione è cercare in un decente riferimento le rotazioni specifiche utilizzate per riequilibrare ogni nodo che trovi: questa è la "tecnica". di esso in contrapposizione al concetto elevato. Devi solo ricordare i dettagli durante la modifica del codice dell'albero AVL o forse durante gli esami delle strutture dati. Sono passati anni dall'ultima volta che ho avuto il codice ad albero AVL tanto quanto aperto nel debugger - le implementazioni tendono a arrivare a un punto in cui funzionano e quindi continuano a funzionare. Quindi non ricordo davvero. Puoi farlo su un tavolo usando alcune fiches da poker, ma è difficile essere sicuri di avere davvero tutti i casi (non ce ne sono molti). Meglio solo cercarlo.

Quindi c'è il compito di tradurre tutto in codice.

Non penso che guardare gli elenchi di codici sia di grande aiuto in qualsiasi fase tranne l'ultimo, quindi ignorali. Anche nel migliore dei casi, dove il codice è chiaramente scritto, sembrerà una descrizione da manuale del processo, ma senza i diagrammi. In un caso più tipico è un casino di manipolazione della struttura. Quindi attenersi ai libri.

Answer 2

Non credo sia bene pubblicare qui codici completi per algoritmi di bilanciamento dei nodi poiché diventano piuttosto grandi. Tuttavia, l'articolo di Wikipedia su alberi rosso-neri contiene un'implementazione C completa dell'algoritmo e l'articolo su alberi AVL contiene anche numerosi collegamenti a implementazioni di alta qualità.

Queste due implementazioni sono sufficienti per la maggior parte degli scenari di uso generale.

Answer 3

Ultimamente ho lavorato un po 'con gli alberi AVL.

Il miglior aiuto che sono riuscito a trovare su come bilanciarli è stato tramite la ricerca su Google.

Ho appena codificato questo pseudo codice (se capisci come fare le rotazioni è abbastanza facile da implementare).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

Answer 4

Sono d'accordo, un programma completo non sarebbe appropriato.

Mentre gli alberi AVL e RB classici usano un approccio deterministico, suggerirei di dare un'occhiata a " Alberi di ricerca binaria randomizzati " che sono meno costosi per mantenere l'equilibrio e garantire un buon bilanciamento indipendentemente dalla distribuzione statistica delle chiavi.

Answer 5

L'albero AVL è inefficiente perché è necessario eseguire potenzialmente molte rotazioni per inserimento / eliminazione.

L'albero Rosso-Nero è probabilmente un'alternativa migliore perché inserimenti / eliminazioni sono molto più efficienti. Questa struttura garantisce che il percorso più lungo verso una foglia non sia più del doppio del percorso più breve. Quindi, sebbene meno equilibrato di un albero AVL, i casi peggiori sbilanciati sono evitati.

Se il tuo albero verrà letto molte volte e non verrà modificato dopo la sua creazione, può valere la pena sovraccarico per un albero AVL completamente bilanciato. Inoltre l'albero rosso-nero richiede un ulteriore bit di memoria per ciascun nodo, che fornisce il "colore" del nodo.

Answer 6

Per bilanciare un albero AVL ho appena scritto un mucchio di funzioni che ho pensato di condividere con tutti qui. Immagino che questa implementazione sia impeccabile. Domande / domande / critiche sono ovviamente benvenute:

http://uploading.com/files/5883f1c7/AVL_Balance.cpp/

Essendo un principiante di StackOverflow, ho provato a pubblicare qui il mio codice ma ero bloccato con problemi di formattazione errati. Quindi, caricato il file sul link sopra.

Saluti.

Answer 7

esiste un'implementazione completa di un avl tree autobilanciante @ http: // code.google.com/p/self-balancing-avl-tree/ . implementa inoltre operazioni concatenate e di divisione del tempo logaritmico nonché raccolte mappe / multimap