alberi AVL

[71104]

ho sentito che si chiamano così gli alberi binari di ricerca che si possono bilanciare per ottimizzare le ricerche... qualcuno può spiegarmi sinteticamente come funzionano? so che devo mettere un campo intero in ciascun nodo che indica se l'albero "pende" più verso destra o sinistra (tipo -1 vuol dire che il sottoalbero sinistro ha un nodo in più del destro), e che quando il modulo di questo campo supera il valore 1 bisogna bilanciarlo, ma non so come.

[maxithron]

è un link puramente indicativo, in basso ci sono anche i sorgenti di esempio:

http://www.dis.uniroma1.it/~fbenedet/f22/f2211.htm

[51078]

Ho trovato qualcosa QUI ...

E' abbastanza semplice, ma non spiega bene le procedure. Se trovi i miei appunti di algoritmi ti scrivo qualcosa.


Cmq sono noiosi da implementare, dato che ogni volta che inserisci un nodo devi aggiornare ogni nodo (l'inserimento è sempre in foglia) e quando, inevitabilmente l'albero si sbilancia per più devi mettere in atto le procedure di bilanciamento che consistono per lo + nel "tirare su" uno dei due nodi figli della radice, che diventa a sua volta la radice.
E' una procedura ricorsiva che parte dal nodo al quale è stata attaccata la foglia fino ad arrivare nel peggiore dei casi alla radice.

Naturalmente la struttura più indicata è la lista, ma la parte noiosa del bilanciamento è l'aggiornamento dei campi che indicano il peso dell'albero sotto di essi...

[71104]

grazie a entrambi per i link, ottimi: me li studierò