Alberi AVL 19 Febbraio 2008
Posted by fripp in Algoritmi, C, C++, Informatica, Programmazione.Tags: AVL tree, binary tree, C, data structure, dictionary, graphviz, tree, void
1 comment so far
Gli alberi AVL sono degli alberi binari bilanciati in altezza. Un albero binario si dice bilanciato in altezza se, per ciascun nodo dell’albero, l’altezza del sottoalbero sinistro differisce dall’altezza del sottoalbero destro al più di una unità.
Per gli alberi AVL si parla anche di fattore di sbilanciamento di un nodo e lo si definisce come la differenza tra l’altezza del sottoalbero sinistro e l’altezza del sottoalbero destro. Banalmente, in un albero AVL il fattore di sbilanciamento di ciascun nodo è, in valore assoluto, 
A differenza di un albero binario “tradizionale”, un albero AVL mantiene la proprietà di bilanciamento in qualsiasi circostanza, sia dopo un inserimento di un nuovo valore che dopo la cancellazione.
Si può dimostrare che l’altezza di un albero AVL di n nodi è sempre 
(more…)
