AVL-Baum
(mit Java-Code)

Ein AVL-Baum ist eine konkrete Implementierung eines balancierten binären Suchbaums. Er wurde 1962 von den sowjetischen Informatikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis entwickelt und nach deren Initialen benannt.

In diesem Artikel erfährst du:

• Was ist ein AVL-Baum?
• Wie berechnet man den Balance-Faktor in einem AVL-Baum?
• Wie funktioniert eine AVL-Baum-Rotation?
• Wie fügt man Elemente ein, und wie löscht man sie?
• Wie implementiert man einen AVL-Baum in Java?
• Welche Zeitkomplexität haben die Operationen des AVL-Baums?
• Was unterscheidet den AVL-Baum vom Rot-Schwarz-Baum?

Den Quellcode zum Artikel findest du in diesem GitHub-Repository.

Was ist ein AVL-Baum?

Ein AVL-Baum ist ein balancierter binärer Suchbaum – also ein binärer Suchbaum, in dem sich die Höhen der linken und rechten Teilbäume eines jeden Knotens um maximal eins unterscheiden.

Nach jeder Einfüge- und Löschoperation wird diese Eigenschaft überprüft und die Balance ggf. durch AVL-Rotation wiederhergestellt.

Höhe eines AVL-Baums

Die Höhe eines (Teil-)baums gibt an, wie weit die Wurzel vom tiefsten Knoten entfernt ist. Ein (Teil-)Baum, der nur aus einem Wurzelknoten besteht, hat demnach die Höhe 0.

AVL-Baum Balance-Faktor

Der Balance-Faktor "BF" eines Knotens "node" bezeichnet die Differenz der Höhen "H" des rechten und linken Teilbaums ("node.right" und "node.left"):

BF(node) = H(node.right) - H(node.left)

Die Höhe eines nicht vorhandenen Teilbaums ist -1 (eins weniger als die Höhe eines Teilbaums, der aus nur einem Knoten besteht).

Man unterscheidet drei Fälle:

• Bei einem Balance-Faktor von < 0 spricht man von einem linkslastigen Knoten.
• Bei einem Balance-Faktor von > 0 spricht man von einem rechtslastigen Knoten.
• Ein Balance-Faktor von 0 steht für einen höhengleichen oder ausgewogenen Knoten.

In einem AVL-Baum ist der Balance-Faktor an jedem Knoten -1, 0 oder 1.

AVL-Baum-Beispiel

Das folgende Beispiel zeigt einen AVL-Baum mit Angabe von Höhe und Balance-Faktor an jedem Knoten:

Knoten 2 und 7 sind in diesem Beispiel rechtslastig, Knoten 4 ist linkslastig. Alle anderen Knoten sind ausgewogen.

Der folgende Baum hingegen ist kein AVL-Baum, da das AVL-Kriterum (-1 ≤ BF ≤ 1) an Knoten 4 nicht erfüllt ist. Dessen linker Teilbaum hat die Höhe 1 und der rechte, leere Teilbaum die Höhe -1. Die Differenz daraus ist -2.

Implementierung eines AVL-Baums in Java

Als Basis für die Implementierung des AVL-Baums in Java verwenden wir den Java-Quellcode für den binären Suchbaum aus dem vorangegangenen Tutorial der Binärbaum-Serie.

Knoten werden durch die Klasse Node dargestellt. Für den Knotenwert data verwenden wir der Einfachheit halber int-Primitive. In height speichern wir die Höhe des Teilbaums, dessen Wurzel dieser Knoten darstellt.

public class Node {
  int data;
  Node left;
  Node right;

  int height;

  public Node(int data) {
    this.data = data;
  }
}Code-Sprache: Java (java)

Der AVL-Baum wird durch die Klasse AvlTree implementiert. Diese erweitert die im vorangegenen Teil vorgestellte Klasse BinarySearchTreeRecursive. Wir werden einen Großteil deren Funktionalität wiederverwenden.

Für die Balancierung des AVL-Baums benötigen wir folgende drei zusätzliche Methoden:

• height() liefert die in node.height hinterlegte Höhe eines Teilbaums ‒ oder -1 für einen leeren Teilbaum.
• updateHeight() setzt node.height als maximale Höhe der Kinder plus 1.
• balanceFactor() berechnet den Balance-Faktor eines Knotens.

public class AvlTree extends BinarySearchTreeRecursive {

  private int height(Node node) {
    return node != null ? node.height : -1;
  }

  private void updateHeight(Node node) {
    int leftChildHeight = height(node.left);
    int rightChildHeight = height(node.right);
    node.height = max(leftChildHeight, rightChildHeight) + 1;
  }

  private int balanceFactor(Node node) {
    return height(node.right) - height(node.left);
  }

  // ...
}Code-Sprache: Java (java)

Der Code wird in den folgenden Abschnitten Schritt für Schritt erweitert.

AVL-Baum Rotation

Einfügen in und Löschen aus einem AVL-Baum funktioniert grundsätzlich so wie im Artikel über binäre Suchbäume beschrieben.

Wenn nach einer Einfüge- oder Löschoperation das AVL-Kriterium nicht mehr erfüllt ist, muss der Baum rebalanciert werden. Dies geschieht durch sogenannte Rotationen.

Man unterscheidet zwischen Rechts- und Links-Rotation.

Rechts-Rotation

Die folgende Grafik zeigt eine Rechts-Rotation. Der dargestellte (Teil-)baum enthält folgende Knoten:

• N: der Knoten, an dem ein Ungleichgewicht festgestellt wurde
• L: der linke Kind-Knoten von N
• LL: der linke Kind-Knoten von L
• LR: der rechte Kind-Knoten von L
• R: der rechte Kind-Knoten von N

Unter den Buchstaben wird jeweils in Klammern ein beispielhafter Knoten-Wert angezeigt. An diesem ist gut zu erkennen, dass vor der Rotation folgende In-Order-Reihenfolge gilt:

LL (1) < L (2) < LR (3) < N (4) < R (5)

Während der Rotation wandert Knoten L an die Wurzel, und die vorherige Wurzel N wird zum rechten Kind von L. Das vorherige rechte Kind von L, LR wird zum neuen linken Kind von N. Die zwei restlichen Knoten, LL und R bleiben unverändert relativ zu ihrem Elternknoten.

An den Beispiel-Werten in Klammern sieht man gut, dass sich durch die Rotation die In-Order-Reihenfolge der Knoten nicht verändert hat.

Der Java-Code für die Rechts-Rotation ist unkompliziert (Klasse AvlTree, ab Zeile 71).

private Node rotateRight(Node node) {
  Node leftChild = node.left;

  node.left = leftChild.right;
  leftChild.right = node;

  updateHeight(node);
  updateHeight(leftChild);

  return leftChild;
}Code-Sprache: Java (java)

Wir merken uns das linke Kind leftChild (in der Grafik L) von node (in der Grafik N), ersetzen das linke Kind von node durch das rechte Kind des linken Kindes leftChild.right (in der Grafik LR) und setzen dann node als neues rechtes Kind des linken Kindes.

Danach aktualisieren wir die Höhen der Teilbäume in der gezeigten Reihenfolge. Die updateHeight()-Methode habe ich bereits im Abschnitt Implementierung eines AVL-Baums in Java vorgestellt.

Rückgabewert ist der neue Wurzelknoten leftChild (in der Grafik L).

Links-Rotation

Die Links-Rotation funktioniert analog:

Knoten R wird zur Wurzel; die vorherige Wurzel N wird zum linken Kind von R. Das vorherige linke Kind von R, RL wird zum neuen rechten Kind von N. Die relativen Positionen der Knoten RR und L ändern sich nicht.

Auch bei der Links-Rotation bleibt die In-Order-Reihenfolge der Knoten (L < N < RL < R < RR) erhalten.

Der Java-Code sieht wie folgt aus (Klasse AvlTree, ab Zeile 83):

private Node rotateLeft(Node node) {
  Node rightChild = node.right;

  node.right = rightChild.left;
  rightChild.left = node;

  updateHeight(node);
  updateHeight(rightChild);

  return rightChild;
}Code-Sprache: Java (java)

AVL-Baum balancieren

Nach dem Einfügen in oder Löschen aus dem AVL-Baum berechnen wir die Höhe und den Balance-Faktor vom eingefügten oder gelöschten Knoten aus aufwärts bis zur Wurzel.

Wenn wir an einem Knoten feststellen, dass das AVL-Kriterium nicht mehr erfüllt ist (der Balance-Faktor also kleiner als -1 oder größer als +1 ist), müssen wir rebalancieren. Dabei unterscheiden wir vier Fälle:

• Linkslastigen Knoten ausgleichen:
  • Rechts-Rotation
  • Links-Rechts-Rotation
• Rechtslastigen Knoten ausgleichen:
  • Links-Rotation
  • Rechts-Links-Rotation

Im folgenden beschreibe ich die vier Fälle an verschiedenen Beispielen.

Rebalancieren durch Rechts-Rotation

Wir fügen in einen leeren Baum die Knoten 3, 2 und 1 ein. Ohne Rebalancierung sieht der Baum dann wie folgt aus:

Wir prüfen den Balance-Faktor vom zuletzt eingefügten Knoten 1 aus aufwärts:

• Der Balance-Faktor an Knoten 1 beträgt 0.
• Der Balance-Faktor an Knoten 2 beträgt -1; Knoten 2 ist also linkslastig. Das AVL-Kriterium (-1 ≤ BF ≤ 1) ist aber noch erfüllt.
• Der Balance-Faktor an Knoten 3 beträgt -2; hier ist das AVL-Kriterium nicht mehr erfüllt.

In diesem Fall müssen wir eine Rechts-Rotation um Knoten 3 ausführen:

Die neue Wurzel ist Knoten 2, und dessen Balance-Faktor ist 0. Der AVL-Baum ist wieder balanciert.

Rebalancieren durch Links-Rechts-Rotation

In folgendem Beispiel haben wir ebenfalls eine linkslastige Wurzel, allerdings sieht die Situation etwas anders aus. Dieses mal fügen wir die Knoten in der Reihenfolge 3, 1, 2 ein:

Wir stellen fest, dass an der Wurzel (mit einem Balance-Faktor von -2) das AVL-Kriterium nicht erfüllt ist. Würden wir jetzt – wie im vorangegangenen Beispiel – eine Rechts-Rotation ausführen, sähe der Baum danach wie folgt aus:

Das rechte Kind der 1 – die 2 – wurde zum linken Kind der 3. Anstatt einer linkslastigen Wurzel mit BF -2 haben wir nun eine rechtslastige Wurzel mit BF +2. Wir sind am Ziel vorbeigeschossen.

Was können wir stattdessen tun?

Die korrekte Vorgehensweise für diesen Fall (linkes Kind der Wurzel ist rechtslastig) ist eine sogenannte Links-Rechts-Rotation. Zuerst rotieren wir nach links um Knoten 1 und danach nach rechts um Knoten 3:

Mit einem Balance-Faktor von 0 an der neuen Wurzel 2 ist der AVL-Baum wieder balanciert.

Rebalancieren durch Links-Rotation

Für rechtslastige Knoten gehen wir analog vor. Wir fügen zunächst Knoten in der Reihenfolge 1, 2, 3 ein und erhalten den folgenden unbalancierten Baum:

Der Balance-Faktor an der Wurzel beträgt +2. Wir können die Balance durch einfache Links-Rotation wiederherstellen:

Rebalancieren durch Rechts-Links-Rotation

Das vierte und letzte Beispiel zeigt einen AVL-Baum, in den die Knoten in der Reihenfolge 1, 3, 2 eingefügt wurden:

Der Balance-Faktor an der Wurzel beträgt auch hier +2. Doch bei einer Links-Rotation wie im vorangegangenen Beispiel würde folgendes passieren:

Das linke Kind der 3 – die 2 – wurde zum rechten Kind der 1. Statt einer rechtslastigen haben wir jetzt eine linkslastige Wurzel mit dem Balance-Faktor -2.

Analog zum zweiten Fall ist die korrekte Vorgehensweise in diesem Fall (rechts Kind der Wurzel ist linkslastig) eine Rechts-Links-Rotation. Wir rotieren nach rechts um Knoten 3 und dann nach links um Knoten 1:

Damit hast du alle Varianten der Balancierung des AVL-Baums kennengelernt.

Java-Code für die Rebalancierung

Die vier vorangegangenen Abschnitte zusammengefasst ergeben folgende Rebalancierungs-Vorschrift. BF steht dabei für Balance-Funktion, N für den betrachteten Knoten, und L und R für dessen linkes bzw. rechtes Kind.

Fall	Bedingung	Rebalancierung
1.	BF(N) < -1 und BF(L) ≤ 0	Rechts-Rotation um N
2.	BF(N) < -1 und BF(L) > 0	Links-Rotation um L gefolgt von Rechts-Rotation um N
3.	BF(N) > 1 und BF(R) ≥ 0	Links-Rotation um N
4.	BF(N) > 1 und BF(R) < 0	Rechts-Rotation um R gefolgt von Links-Rotation um N

Im Java-Code implementieren wir den Rebalancierungs-Algorithmus in der folgenden rebalance()-Methode (Klasse AvlTree, ab Zeile 41):

private Node rebalance(Node node) {
  int balanceFactor = balanceFactor(node);

  // Left-heavy?
  if (balanceFactor < -1) {
    if (balanceFactor(node.left) <= 0) {    // Case 1
      // Rotate right
      node = rotateRight(node);
    } else {                                // Case 2
      // Rotate left-right
      node.left = rotateLeft(node.left);
      node = rotateRight(node);
    }
  }

  // Right-heavy?
  if (balanceFactor > 1) {
    if (balanceFactor(node.right) >= 0) {    // Case 3
      // Rotate left
      node = rotateLeft(node);
    } else {                                 // Case 4
      // Rotate right-left
      node.right = rotateRight(node.right);
      node = rotateLeft(node);
    }
  }

  return node;
}Code-Sprache: Java (java)

Der Code entspricht dem oben beschriebenen Algorithmus; die vier Fälle sind jeweils als Kommentar im Code referenziert. Die Methode liefert den neuen Wurzelknoten des (Teil-)baums zurück.

Operationen im AVL-Baum

Da wir nun das Werkzeug für die Rebalancierung des Baums haben (die rebalance()-Methode aus dem vorherigen Abschnitt), können wir die Methoden zum Einfügen und Löschen zusammenbauen.

Einfügen in einen AVL-Baum

Um einen Knoten in den AVL-Baum einzufügen, gehen wir zunächst so vor, wie im Abschnitt "Einfügen im binären Suchbaum" des vorangegangenen Tutorials beschrieben. Im Anschluss rufen wir updateHeight() und rebalance() auf.

Da unsere AvlTree-Klasse von BinarySearchTreeRecursive erbt, erfolgt der Aufruf der Einfüge-Methode über super.insertNode() (definiert in BinarySearchTreeRecursive ab Zeile 34):

@Override
Node insertNode(int key, Node node) {
  node = super.insertNode(key, node);

  updateHeight(node);

  return rebalance(node);
}Code-Sprache: Java (java)

Löschen aus einem AVL-Baum

Zum Löschen eines Knotens gehen wir vor wie im Abschnitt "Löschen im binären Suchbaum" des vorangegangenen Tutorials beschrieben. Im Anschluss rufen wir – wie beim Einfügen – updateHeight() und rebalance() auf:

Die mit super.deleteNode() aufgerufene Methode findest du in BinarySearchTreeRecursive ab Zeile 57.

@Override
Node deleteNode(int key, Node node) {
  node = super.deleteNode(key, node);

  // Node is null if the tree doesn't contain the key
  if (node == null) {
    return null;
  }

  updateHeight(node);

  return rebalance(node);
}Code-Sprache: Java (java)

Navigation im AVL-Baum

Die Suche im AVL-Baum funktioniert exakt wie die Suche im binären Suchbaum. Die searchNode()-Methode aus BinarySearchTreeRecursive muss daher nicht überschrieben werden.

Die Traversierung in Pre-order-, Post-order-, In-order-, Reverse-in-order- und Level-order-Reihenfolge wird für Binärbäume im Allgemeinen definiert. Du findest die Definitionen im Abschnitt "Binärbaum-Traversierung" des Artikels über Binärbäume.

Die in dem Artikel vorgestellten Traversierungsklassen DepthFirstTraversal, DepthFirstTraversalIterative und DepthFirstTraversalRecursive können auch auf den AvlTree angewendet werden, da dieser indirekt das Interface BinaryTree implementiert, auf dem die Traversierungsfunktionen definiert sind.

Zeitkomplexität des AVL-Baums

(Eine Erklärung der Zeitkomplexität und von Komplexitätsklassen wie O(log n) findest du im Artikel "O-Notation und Zeitkomplexität – anschaulich erklärt".)

Beim Suchen, Einfügen und Löschen fallen folgende Operationen an:

• Die maximale Anzahl an Knoten-Vergleichsoperationen entspricht der Höhe des AVL-Baumes.
• Die maximale Anzahl an Berechnungen des Balance-Faktors ist doppelt so hoch, da auch immer der Balance-Faktor eines Kindes mit berücksichtigt werden muss.
• Die maximale Anzahl an Rotationen entspricht ebenfalls der doppelten Höhe des AVL-Baumes, da pro Ebene keine, eine oder zwei Rotationen durchgeführt werden.
• Pro Rotation wird für zwei Knoten die Höhe neu berechnet. Die maximale Anzahl an Höhen-Berechnungen beträgt also das Vierfache der Baumhöhe.

Da es sich bei einem AVL-Baum um einen balancierten Binärbaum handelt – bei Verdoppelung der Knotenzahl also lediglich eine Ebene hinzukommt – liegt die Höhe des AVL-Baumes in der Größenordnung O(log n).

Da die Kosten aller oben genannten Operationen konstant sind und die Anzahl ihrer Ausführungen jeweils proportional zur Baumhöhe ist, beträgt auch die Zeitkomplexität für das Suchen, Einfügen und Löschen jeweils O(log n).

AVL-Baum im Vergleich mit anderen Datenstrukturen

In den folgenden Abschnitten findest du die Vor- und Nachteile des AVL-Baums gegenüber vergleichbaren Datenstrukturen.

AVL-Baum vs. Rot-Schwarz-Baum

Sowohl der AVL-Baum als auch der Rot-Schwarz-Baum sind selbst-balancierende binäre Suchbäume.

Beim AVL-Baum erfolgt die Rebalancierung durch Berechnung von Balance-Faktoren und nachfolgenden Rotationen. Die absolute Höhendifferenz ist an keinem Knoten größer als 1.

Im Rot-Schwarz-Baum werden die Knoten durch Farben (rot / schwarz) gekennzeichnet. Rotationen erfolgen, wenn bestimmte Kriterien für Farbfolgen nicht mehr eingehalten sind. Die absolute Höhendifferenz an einem Knoten kann auch größer als 1 sein. Genauer gesagt: das tiefste Blatt kann von der Wurzel bis zu doppelt so weit entfernt sein wie das höchste Blatt.

Diese Eigenschaften führen zu folgenden Unterschieden:

• Die Suche im AVL-Baum ist in der Regel schneller als im Rot-Schwarz-Baum, da der AVL-Baum besser balanciert ist.
• Das Einfügen und Löschen ist hingegen im Rot-Schwarz-Baum schneller, da dieser seltener rebalanciert wird.
• AVL-Bäume benötigen ein Extra-Byte pro Knoten für das Speichern der jeweiligen Höhe. Rot-Schwarz-Bäume benötigen lediglich ein Bit pro Knoten für die Farb-Information. In der Java-Praxis macht dies keinen Unterschied, da für das Bit mindestens ein Byte belegt wird.

AVL-Baum vs. Binärer Suchbaum

Ein AVL-Baum ist ein binärer Suchbaum, der nach jeder Einfüge- und Lösch-Operation durch Rotation das AVL-Kriterium wiederherstellt.

Ein binärer Suchbaum muss nicht zwingend balanciert sein. Ebenso kann die Balancierung durch andere Algorithmen als beim AVL-Baum erreicht werden.

Jeder AVL-Baum ist also ein binärer Suchbaum. Aber nicht jeder binäre Suchbaum ist ein AVL-Baum.

Fazit

In diesem Tutorial hast du erfahren, was ein AVL-Baum ist und wie dieser nach Einfüge- oder Löschoperationen durch Einfach- oder Doppelrotation rebalanciert wird. Außerdem hast du gelernt, wie man einen AVL-Baum in Java implementiert.

Im nächsten Teil wird es um eine weitere konkrete Art des binären Suchbaums gehen: den Rot-Schwarz-Baum. Möchtest du eine E-Mail erhalten, wenn der Artikel veröffentlicht wird? Dann klicke hier, um dich in den HappyCoders-Verteiler einzutragen.

Wenn dir der Artikel gefallen hat, teile ihn gerne über einen der Share-Buttons am Ende oder schreibe mir einen Kommentar.