Binärbäume werden benutzt da sie ein sehr effizientes Suchen mit einem Aufwand von O(logN) erlauben solange sie balanciert sind. In extremen Fällen kann die Suche nach Knoten jedoch zu einem Aufwand von O(N) führen falls der Baum degeneriert ist.

Die im vorhergehenden Abschnitt vorgestellten Bäume verwenden in ihren Implementierungen der Einfüge- und Entferneoperation naive Verfahren. Diese naive Verfahren können dazu führen, dass ein Baum sehr unbalanciert werden kann.

Erste Vorschläge zur Vermeidung dieses Problems gehen auf die 1962 gemachten Vorschläge von Adelson-Velskij und Landis zurück. Sie schlugen höhenbalancierte AVL Bäume vor.

AVL Bäume

 Beispiele von AVL Bäumen die der obigen Definition genügen sind im folgenden Diagramm zu sehen

 Der nachfolgende Baum ist kein AVL Baum. Der rechte Knoten in der zweiten Ebene von oben hat einen linken Unterbaum der Höhe 1 und einen rechten Unterbaum der Höhe 3.

Dieser Baum müsste umorganisiert werden um ein AVL Baum zu werden.

Zum Verwalten von AVL Bäumen berechet man jedoch nicht immer wieder die Höhe der Teilbäume.

Es ist einfacher einen Balanchefaktor zu jedem inneren Knoten mitzuführen der die Differenz der Höhe vom linken und rechtem Teilbaum verwaltet.

Im folgenden Beispiel sind die Balancefaktoren für die inneren Knoten eingetragen:

 AVL Bäume müssen beim Einfügen und Entfernen von Knoten unter Umständen neu balanciert werden. Der Vorteil besteht jedoch in dem sehr vorhersagbaren Verhalten mit dem Aufwand von O(logN) bei Operationen auf dem Baum.

Tipp: Bauen Sie sich Ihren eigen AVL Baum. Die Universität hat eine web basierte Visualisierung von AVL Bäumen.