Portale:Informatica/Voce della settimana/Settimana 12

Nell'informatica l'albero AVL è un Albero binario di ricerca bilanciato. La condizione per tenerlo bilanciato è semplice: per ogni nodo dell'albero, la differenza di altezza dei suoi sottoalberi figli, deve differire al massimo di uno.

Il nome AVL viene dai suoi inventori G.M. Adelson-Velsky e E.M. Landis, che pubblicarono il loro algoritmo nel saggio "An algorithm for the organization of information" del 1962.

Per evitare di dover contare ogni volta l'altezza di un sottoalbero, si salva nel nodo il coefficiente di bilanciamento, che è definito come l'altezza del sottoalbero destro meno quella del sottoalbero sinistro.

continua...