AVL Tree ist ein ausgewogener binärer Suchbaum. Der Beitrag führte binäre Suchbäume ein. Die Such-, Einfüge- und Löschzeiten für einen Binärbaum hängen von der Höhe des Baums ab. Im schlimmsten Fall beträgt die Höhe O(n). Wenn ein Baum perfekt ausbalanciert ist, also ein vollständiger Binärbaum, beträgt seine Höhe log n. Können wir einen perfekt ausgeglichenen Baum erhalten? Ja, aber dies wird kostspielig sein. Der Kompromiss besteht darin, einen ausgewogenen Baum beizubehalten – das heißt, die Höhen der beiden Teilbäume jedes Knotens sind ungefähr gleich.

AVL-Bäume sind gut ausbalanciert. AVL-Bäume wurden 1962 von zwei russischen Informatikern, G. M. Adelson-Velsky und E. M. Landis, erfunden (daher der Name AVL). In einem AVL-Baum beträgt der Unterschied zwischen den Höhen der beiden Teilbäume jedes Knotens 0 oder 1. Es kann gezeigt werden, dass die maximale Höhe eines AVL-Baums O(log n) beträgt.

Der Vorgang zum Einfügen oder Löschen eines Elements in einen AVL-Baum ist derselbe wie in einem regulären binären Suchbaum, mit der Ausnahme, dass Sie den Baum nach einem Einfüge- oder Löschvorgang möglicherweise neu ausbalancieren müssen. Der Balancefaktor eines Knotens ist die Höhe seines rechten Teilbaums minus der Höhe seines linken Teilbaums. Ein Knoten gilt als ausgeglichen, wenn sein Ausgleichsfaktor -1, 0 oder 1 ist. Ein Knoten gilt als linkslastig, wenn sein Balancefaktor -1 ist, und als rechtslastig, wenn sein Balancefaktor 1 ist.