AVL-Baum: Vollständiger Guide mit Python-Implementierung

Ungleichgewicht in binären Suchbäumen

Binäre Suchbäume (BSTs) sind eine Form binärer Bäume als Datenstruktur, die Daten in einer festen Ordnung organisiert. Jeder Knoten enthält einen Wert und zeigt auf bis zu zwei weitere Knoten: das linke und das rechte Kind. In einem BST gilt: Der Wert des linken Kindes ist kleiner als der des Elternknotens, der des rechten größer.

BSTs sind beim Finden bestimmter Werte sehr effizient, weil sie während der Suche große Teile des Baums ausschließen. Suchen wir im obigen Baum beispielsweise die 1, können wir alle Knoten rechts von 6 ignorieren. Die Ordnungsregel garantiert, dass dort nur Werte größer als 6 liegen.

Ideal ist, wenn jeder Knoten die Daten halbiert, sodass bei jedem Schritt die Hälfte der Werte entfällt. So entstehen extrem schnelle Lookups. Je nach Einfügereihenfolge kann der Baum aber aus dem Gleichgewicht geraten und die Daten nicht mehr effektiv teilen. Fügt man etwa Werte strikt aufsteigend ein, entsteht ein linearer Baum, der nicht besser als eine Liste performt.

Was ist ein AVL-Baum?

Ein AVL-Baum ist ein binärer Suchbaum mit folgender Zusatz-Eigenschaft:

Für jeden Knoten unterscheiden sich die Höhen von linkem und rechtem Teilbaum um höchstens eins.

Zur Einordnung: Der linke Teilbaum eines Knotens umfasst alle Knoten links von ihm, der rechte Teilbaum alle Knoten rechts. Die Höhe eines Baums ist die Länge des längsten Pfads von der Wurzel (oberster Knoten) zu einem Blatt (Knoten ohne Kinder).

Der Balancefaktor eines Knotens ist die Höhendifferenz zwischen linkem und rechtem Teilbaum:

balance(N) = height(linker Teilbaum von N) - height(rechter Teilbaum von N)

Zum Beispiel gilt: balance(6) = 1 - 3 = -2.

Im Diagramm hat der Knoten 6 einen Balancefaktor von -2 und erfüllt damit nicht die AVL-Kriterien. Für einen AVL-Baum muss der Balancefaktor jedes Knotens -1, 0 oder 1 betragen.

Warum AVL-Bäume verwenden?

Die Effizienz von Anfragen in einem binären Suchbaum hängt von seiner Höhe ab. Im schlechtesten Fall entspricht die Zahl der zu prüfenden Knoten der Baumhöhe. Ein zentrales Problem von BSTs ist, dass die Höhe der Knotenanzahl entsprechen kann – dann muss eine Anfrage im Extremfall jeden Knoten prüfen.

Bezeichne M(h) als die minimale Anzahl Knoten, die nötig ist, um einen binären Suchbaum der Höhe h zu erreichen. Für einfache BSTs gilt beobachtbar M(h) = h, d. h. wir können mit h Knoten Höhe h erreichen. Die Höhe kann also linear mit der Knotenanzahl wachsen – die Abfragezeit ist proportional zur Datensatzgröße.

Beweis: AVL-Bäume haben logarithmische Höhe

Betrachten wir die minimale Knotenanzahl M(h), die für einen AVL-Baum der Höhe h erforderlich ist. In einem AVL-Baum kann der Balancefaktor jedes Knotens nur -1, 0 oder 1 sein.

Angenommen, der Baum hat so wenig Knoten wie möglich, um die Höhe h zu erreichen. Dann kann die Wurzel nicht Balance 0 haben. Wäre sie 0, könnten wir links oder rechts einen Knoten entfernen und Balance -1 oder 1 erhalten – immer noch ein gültiger AVL-Baum.

Nehmen wir an, die Balance der Wurzel ist 1 (für -1 ist das Argument analog). Dann ist der Baum wie folgt aufgebaut:

Beide Teilbäume müssen ebenfalls AVL-Bäume mit der jeweils minimalen Knotenanzahl für ihre Höhen sein (sonst ließen sich weitere Knoten entfernen). Die Gesamtknotenanzahl ist 1 (für die Wurzel) plus die Knoten im linken plus die im rechten Teilbaum.

M(h) = 1 + (Knoten in L) + (Knoten in R) = 1 + M(h - 1) + M(h - 2)

Mit wachsender Höhe müssen mehr Knoten hinzugefügt werden. Daher gilt:

M(h - 1) > M(h - 2)

Kombiniert erhalten wir:

M(h) = 1 + M(h - 1) + M(h - 2) > 1 + 2 × M(h - 2) > 2 × M(h - 2)

Das können wir h/2-mal anwenden, bis wir entweder M(1) = 1 oder M(2) = 2 erreichen:

M(h) > 2 × M(h - 2) > 2 × 2 × M(h - 4) > 2 × 2 × 2 × M(h - 6) > … > 2(h/2)

Zur Veranschaulichung zeigt das folgende Bild die konkreten Beispiele für h = 7 und h = 6:

Damit ist die minimale Knotenanzahl in einem AVL-Baum der Höhe h mindestens 2(h/2):

M(h) > 2(h/2)

Wenden wir auf beide Seiten den Logarithmus zur Basis zwei an, erhalten wir:

log2(M(h)) > log2(2(h/2)) = h/2

Multiplizieren wir beide Seiten mit zwei, folgt: Die Höhe ist höchstens das Doppelte des Logarithmus zur Basis 2 der Knotenanzahl:

2 × log2(M(h)) > h

Wir haben gezeigt:

Die Höhe eines AVL-Baums mit N Knoten ist höchstens 2 × log2(N).

Das bedeutet: Abfragen in einem AVL-Baum müssen nur einen kleinen Teil des Datensatzes prüfen. Bei einer Milliarde Einträgen liegt der Logarithmus etwa bei 30 – selbst dann sind für eine Suche nur rund 60 Werte zu betrachten. Im Vergleich zu BSTs, die im Worst Case alle eine Milliarde Einträge prüfen müssten, ist das ein gewaltiger Vorteil.

Wenn du algorithmische Zeitkomplexität und den Unterschied zwischen linearer und logarithmischer Komplexität vertiefen möchtest, lies diesen Blogpost zur Big-O-Notation und Zeitkomplexität.

Balance mit AVL-Bäumen erhalten

AVL-Bäume garantieren schnelle Abfragen, indem der Balancefaktor jedes Knotens auf -1, 0 oder 1 beschränkt wird. Damit das so bleibt, müssen wir den Baum nach jeder Einfügung ggf. neu ausbalancieren.

Das Einfügen in BSTs folgt dem Pfad von der Wurzel nach unten: Ist der einzufügende Wert kleiner, gehen wir links, sonst rechts.

Eine Einfügung erhöht die Höhe um höchstens eins. Wenn danach die Balance verletzt ist, gab es zuvor entweder einen Knoten mit Balance -1, der nun -2 hat, oder einen mit Balance 1, der nun 2 hat. Ersteres passiert im obigen Beispiel.

Einfache Rotationen

Zum Wiederherstellen der Balance verwenden wir Rotationen. Eine Linksrotation an Knoten A rotiert A nach links, wie unten gezeigt:

Im Diagramm gilt:

• BL ist der linke Teilbaum von B
• BR ist der rechte Teilbaum
• AL ist der linke Teilbaum von A

Nach der Rotation ist die Knotenordnung weiterhin gültig:

1. Knoten A ist kleiner als B, da B zuvor sein rechtes Kind war.
2. Knoten in BL sind größer als A, denn sie lagen rechts von A.
3. Knoten in AL sind kleiner als B, da sie kleiner als A sind.

Eine Rechtsrotation funktioniert symmetrisch, indem A nach rechts rotiert wird.

Schauen wir uns ein konkretes Beispiel an und beheben das Ungleichgewicht nach dem Einfügen von 19 mit einer Linksrotation an Knoten 6.

Nach dem Einfügen beheben wir das Ungleichgewicht, indem wir einen Knoten mit Balance -2 oder 2 rotieren. Hier hatte Knoten 6 den Balancefaktor -2 – der Baum neigte nach rechts –, daher die Linksrotation (entgegen der Neigung). Bei Balance 2 würden wir entsprechend rechts rotieren.

Doppelte Rotationen

Im vorherigen Beispiel kippte der Baum vollständig nach rechts, sodass eine einfache Linksrotation genügte. In manchen Fällen gibt es jedoch ein Zickzack-Ungleichgewicht: Der Gesamtbaum neigt zur einen Seite, der Teilbaum zur anderen. Kehren wir zum Ausgangsbaum vor dem Einfügen von 19 zurück und fügen stattdessen 7 ein:

Hier neigt der Baum weiterhin nach rechts, der bei 10 verwurzelte Teilbaum jedoch nach links. Zuerst rotieren wir daher Knoten 10 nach rechts:

Beachte, dass Knoten B kein rechtes Kind hat. Im Diagramm ist es zur Verdeutlichung dennoch blau markiert.

Nach der Rechtsrotation sind wir wieder im Fall, in dem eine Linksrotation an 6 die Balance wiederherstellt:

So implementierst du einen AVL-Baum in Python

Beginnen wir mit der Knoten-Implementierung.

Knoten-Implementierung

Jeder Knoten besitzt fünf Attribute:

• Den gespeicherten Wert (self.value)
• Den Elternknoten (self.parent)
• Das linke Kind (self.left)
• Das rechte Kind (self.right)
• Die Höhe des an diesem Knoten verwurzelten Teilbaums (self.height)

class Node:
  def __init__(self, value, parent = None):
    self.value = value
    self.parent = parent
    self.left = None
    self.right = None
    self.height = 1

Fehlende Knoten repräsentieren wir mit None. Der Standardwert für height ist 1, denn ein Baum aus genau einem Knoten hat die Höhe 1.

Zur Erleichterung der Baum-Implementierung fügen wir der Klasse Node einige Methoden hinzu.

# Inside the Node class
  def left_height(self):
    # Get the heigth of the left subtree
    return 0 if self.left is None else self.left.height
  
  def right_height(self):
    # Get the height of the right subtree
    return 0 if self.right is None else self.right.height
  def balance_factor(self):
    # Get the balance factor
    return self.left_height() - self.right_height()
  def update_heigth(self):
    # Update the heigth of this node
    self.height = 1 + max(self.left_height(),self.right_height())
    
  def set_left(self, node):
    # Set the left child
    self.left = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  
  def set_right(self, node):
    # Set the right child
    self.right = node
    if node is not None:
      node.parent = self
    self.update_heigth()
  def is_left_child(self):
    # Check whether this node is a left child
    return self.parent is not None and self.parent.left == self
  
  def is_right_child(self):
    # Check whether this node is a right child
    return self.parent is not None and self.parent.right == self

Beachte: Wir verwenden .set_left() und .set_right(), um linkes und rechtes Kind zu setzen. Der Grund: Bei jeder Änderung eines Kindes müssen wir auch dessen Elternzeiger aktualisieren und die Höhe des Knotens neu berechnen.

AVL-Baum-Implementierung

Der AVL-Baum verwaltet einen Parameter: die Wurzel, also den obersten Knoten.

class AVLTree:
  def __init__(self):
    self.root = None

Um die Balance zu halten, implementieren wir Links- und Rechtsrotationen. So ist die Linksrotation im Diagramm dargestellt:

# Inside the AVLTree class
  
  def rotate_left(self, a):
    b = a.right
    # 1. The new right child of A becomes the left child of B
    a.set_right(b.left)
    # 2. The new left child of B becomes A
    b.set_left(a)
    return b # 3. Return B to replace A with it

Rechtsrotationen implementieren wir symmetrisch:

# Inside the AVLTree class
  
  def rotate_right(self, a):
    b = a.left
    a.set_left(b.right)
    b.set_right(a)
    return b

Mit diesen Rotationen können wir den Baum ausbalancieren. Ein Knoten benötigt Rebalancing, wenn sein Balancefaktor 2 (Neigung nach links) oder -2 (Neigung nach rechts) erreicht. Insgesamt unterscheiden wir vier Fälle:

Diese vier Fälle implementieren wir in der Methode .rebalance().

# Inside the AVLTree class
  
  def rebalance(self, node):
    if node is None:
      # Empty tree, no rebalancing needed
      return None
    balance = node.balance_factor()
    if abs(balance) <= 1:
      # The node is already balanced, no rebalancing needed
      return node
    if balance == 2: 
      # Cases 1 and 2, the tree is leaning to the left
      if node.left.balance_factor() == -1: 
        # Case 2, we first do a left rotation
        node.set_left(self.rotate_left(node.left))
      return self.rotate_right(node)
    # Balance must be -2
    # Cases 3 and 4, the tree is leaning to the left
    if node.right.balance_factor() == 1:
      # Case 4, we first do a right rotation
      node.set_right(self.rotate_right(node.right)) 
    return self.rotate_left(node)

Wichtig: In jedem Fall gibt die Methode die Wurzel des soeben ausbalancierten Teilbaums zurück. Diese neue Teilwurzel verwenden wir später, um beim Hochlaufen im Baum die Kinder zu aktualisieren.

Das Hinzufügen eines Knotens zu einem AVL-Baum ähnelt dem Vorgehen in einem regulären BST, ergänzt um das Rebalancing nach der Einfügung. Wir starten an der Wurzel, gehen schrittweise nach unten und vergleichen den einzufügenden Wert mit dem aktuellen Knotenwert. Ist er kleiner, gehen wir links, sonst rechts. Dabei merken wir uns den Elternknoten, um den neuen Knoten als dessen Kind einzuhängen.

Erreichen wir einen leeren Platz, gibt es zwei Fälle:

1. Der Elternknoten ist None – der Baum ist leer, der neue Knoten wird die Wurzel.
2. Wir haben den Elternknoten gefunden und setzen den neuen Knoten je nach Werten als linkes oder rechtes Kind.

# Inside the AVLTree class
  def add(self, value):
    self.size += 1
    parent = None
    current = self.root
    while current is not None:
      parent = current
      if value < current.value:
        # Value to insert is smaller than node value, go left
        current = current.left
      else:
        # Value to insert is larger than node value, go right
        current = current.right
    # We found the parent, create the new node
    new_node = Node(value, parent)
    # Case 1: The parent is None so the new node is the root
    if parent is None:
      self.root = new_node
    else:
      # Case 2: Set the new node as a child of the parent
      if value < parent.value:
        parent.left = new_node
      else:
        parent.right = new_node
    # After a new node is added, we need to restore balance
    self.restore_balance(new_node)

Der einzige Unterschied zur .add()-Methode eines BST liegt im letzten Schritt: Wir laufen den Baum wieder nach oben und balancieren von dort jeden Knoten mithilfe von .rebalance() aus.

# Inside the AVLTree class
  def restore_balance(self, node):
    current = node
    # Go up the tree and rebalance left and right children
    while current is not None:
      current.set_left(self.rebalance(current.left))
      current.set_right(self.rebalance(current.right))
      current.update_heigth()
      current = current.parent
    self.root = self.rebalance(self.root)
    self.root.parent = None

Beachte: .rebalance() macht nichts, wenn der Knoten bereits balanciert ist – es gibt ihn unverändert zurück. Daher können wir beim Hochlaufen auf beiden Seiten aufrufen; nur eine Seite ist unbalanciert, die andere bleibt unverändert.

Zur Erinnerung: .rebalance() gibt die (möglicherweise neue) Wurzel des Teilbaums zurück. So können wir beim Wiederherstellen der Balance die linken und rechten Kinder der aktuellen Knoten korrekt aktualisieren.

Das folgende Diagramm zeigt die Schritte von .restore_balance() beim Hochlaufen im Baum.

Im Beispiel fügen wir zuerst den Knoten 8 hinzu. Dann startet die Balance-Wiederherstellung bei diesem Knoten und arbeitet sich nach oben, prüft und balanciert jeweils linke und rechte Kinder. Das setzt sich fort, bis Knoten 10 erreicht ist. Bis dahin haben die Aufrufe von .rebalance() keine Wirkung, da die Knoten balanciert sind.

Erst bei Knoten 10 zeigt sich: Sein linkes Kind 7 hat Balance -2 und muss ausbalanciert werden. Also rufen wir .rebalance(7) auf. Das ersetzt das linke Kind von 10 durch die neue Wurzel des linken Teilbaums, den Knoten 8, und stellt so die Balance wieder her.

Weitere Operationen für AVL-Bäume

Neben dem Einfügen und Löschen bei erhaltener Balance unterstützen AVL-Bäume weitere wichtige Operationen.

Minimum und Maximum

Durch die Ordnung in BSTs steht der Minimalwert im ganz linken, der Maximalwert im ganz rechten Knoten.

Wir implementieren zwei Hilfsfunktionen, die vom Startknoten aus den ganz linken bzw. ganz rechten Knoten finden. Das erleichtert das Löschen von Knoten.

# Inside the AVLTree class
  
  def leftmost(self, starting_node):
    # Find the leftmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.left
    return previous
  def minimum(self):
    # Return the minimum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.leftmost(self.root).value

# Inside the AVLTree class
 
  def rightmost(self, starting_node):
    # Find the rightmost node from a given starting node
    previous = None
    current = starting_node
    while current is not None:
      previous = current
      current = current.right
    return previous
  
  def maximum(self):
    # Fidn the maximum value in the tree
    if self.root is None:
      raise Exception("Empty tree")
    return self.rightmost(self.root).value

Contains

Um festzustellen, ob ein Baum einen bestimmten Wert enthält, nutzen wir die Ordnung des Baums für die Suche: Von der Wurzel aus gehen wir nach links, wenn der gesuchte Wert kleiner ist, und nach rechts, wenn er größer ist. Erreichen wir das Ende, ohne den Wert zu finden, ist er nicht im Baum vorhanden.

Dafür implementieren wir die Hilfsmethode .locate_node(). Sie hilft nicht nur bei Suchen, sondern auch beim Löschen. Zusätzlich nutzen wir .__contains__(), um per in-Operator bequem zu prüfen, ob ein Wert enthalten ist.

# Inside the AVLTree class

  def locate_node(self, value):

    # Returns the node containing a given value or None if no

    # such node exists

    current = self.root

    while current is not None:

      if value == current.value:

        return current

      if value < current.value:

        current = current.left

      else:

        current = current.right

    return None

  def __contains__(self, value):

    node = self.locate_node(value)

    return node is not None

Löschen

Das Löschen eines Knotens in einem AVL-Baum kann knifflig sein, wenn der Knoten in der Mitte des Baums liegt. Ist der Knoten ein Blatt, also ohne Kinder, können wir ihn einfach entfernen, indem wir beim Elternknoten das linke oder rechte Kind je nach Position auf None setzen.

Ein Sonderfall ist das Löschen der Wurzel. In diesem Fall können wir den Knoten entfernen, indem wir die Wurzel auf None setzen.

# Inside the AVLTree class

  def delete_leaf(self, node):

    if node.parent is None:

      self.root = None

    elif node.is_left_child():

      node.parent.left = None

      node.parent = None

    else:

      node.parent.right = None

      node.parent = None

Um einen Wert zu löschen, finden wir zunächst mit .locate_node() den entsprechenden Knoten. Ist er ein Blatt, löschen wir ihn mit .delete_leaf(). Andernfalls würde direktes Entfernen die Struktur zerstören. Dann suchen wir einen passenden Ersatzknoten. Hat der zu löschende Knoten ein linkes Kind, wählen wir den ganz rechten Knoten seines linken Teilbaums. So bleibt die Ordnung gewahrt.

Das folgende Diagramm zeigt das Entfernen des Knotens 10. Da er ein linkes Kind hat, ersetzen wir ihn durch den ganz rechten Knoten im linken Teilbaum. Nach dem Ersetzen ist es wichtig, den Baum ab dem Elternknoten des ersetzten Knotens wieder auszubalancieren.

Im Beispiel ist der Ersatzknoten ein Blatt. Hat der Ersatzknoten Kinder, müssen sie dem Elternknoten des Ersatzknotens neu zugewiesen werden. Da es sich beim Ersatzknoten um einen Extremknoten handelt (ganz links oder ganz rechts), kann er nur ein Kind haben – das Umhängen ist also stets möglich.

# Inside the AVLTree class

  def delete(self, value):

    # Delete a value from the tree

    node = self.locate_node(value)

    if node is None:

      raise Exception("Value not stored in tree")

    replacement = None

    rebalance_node = node.parent

    if node.left is not None:

      # There's a left child so we replace with rightmost node

      replacement = self.rightmost(node.left)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.left)

      else:

        replacement.parent.set_right(replacement.left)

    elif node.right is not None:

      # There's a right child so we replace with the leftmost node

      replacement = self.leftmost(node.right)

      # Check if reparenting is needed

      if replacement.is_left_child():

        replacement.parent.set_left(replacement.right)

      else:

        replacement.parent.set_right(replacement.right)

    if replacement:

      # We found a replacement so replace the value

      node.value = replacement.value

      rebalance_node = replacement.parent

    else:

      # No replacement so it means the node to delete is a leaf

      self.delete_leaf(node)

    if rebalance_node is not None:

      self.restore_balance(rebalance_node)

Range Query

Bereichsabfragen ermitteln alle Werte zwischen zwei Grenzen. Dank der Ordnung in AVL-Bäumen können wir das sehr effizient durchführen.

Um alle Werte im Bereich zwischen Untergrenze lb und Obergrenze ub zu finden, durchsuchen wir den Baum rekursiv. Liegt der Knotenwert im Bereich, nehmen wir ihn ins Ergebnis auf und gehen anschließend in beide Teilbäume.

Den linken Teilbaum ignorieren wir, wenn der Knotenwert kleiner als die Untergrenze ist, da dort alle Werte noch kleiner sind. Entsprechend ignorieren wir den rechten Teilbaum, wenn der Knotenwert größer als die Obergrenze ist.

  def search(self, node, lb, ub, results):

    # Search for values between lower bound and upper bound

    if node is None:

      return

    if lb <= node.value and node.value <= ub:

      results.append(node.value)

    if node.value >= lb:

      self.search(node.left, lb, ub, results)

    if node.value <= ub:

      self.search(node.right, lb, ub, results)

  def range_query(self, lb, ub):

    # Search for values between lower bound and upper bound

    results = []

    self.search(self.root, lb, ub, results)

    return results

Weitere selbstbalancierende Bäume

Wir haben einen AVL-Baum implementiert, der folgende Operationen unterstützt:

• Werte hinzufügen
• Werte löschen
• Werte nachschlagen
• Minimum und Maximum abfragen
• Alle Werte zwischen zwei Grenzen abfragen

Das avltree-Paket bietet eine Python-Implementierung mit diesen Funktionen.

Andere selbstbalancierende binäre Suchbäume wie Rot-Schwarz-Bäume, Splay-Bäume und B-Bäume bieten ähnliche Funktionalitäten. In der Praxis ist ihre Performance meist vergleichbar, da alle eine garantiert logarithmische Höhe sicherstellen. AVL-Bäume sind feiner ausbalanciert und optimieren damit Suchen – Einfügungen können dafür durch häufigeres Rebalancing etwas langsamer sein.

Splay-Bäume eignen sich besonders, wenn zuletzt abgefragte Elemente häufig erneut genutzt werden – ideal z. B. für Caches.

B-Bäume sind speziell für effiziente Arbeit auf Festplatten statt im Arbeitsspeicher konzipiert und damit wertvoll, wenn Datenmengen den Speicher übersteigen – etwa bei Datenbankindizes.

Mögliche Erweiterungen

Unsere Implementierung lässt sich auf verschiedene Arten verbessern. Hier ein paar Übungsideen, um dein Verständnis von AVL-Bäumen zu vertiefen:

• Aktuell speichern Knoten nur einen einzelnen Wert. Für Datenbankindizes müssen komplette Zeilen abgelegt werden, da der Wert einer Spalte entspricht. Erweitere die Implementierung so, dass der AVL-Baum wie ein Dictionary Werte auf zugehörige Zeilen abbildet.
• Momentan erlaubt die Implementierung keine Duplikate. Du kannst sie so anpassen, dass mehrere Knoten denselben Wert teilen dürfen.
• Typischerweise werden AVL-Bäume rekursiv implementiert. Wir haben darauf verzichtet, um Rekursionswissen nicht vorauszusetzen. Rekursive Implementierungen sind meist eleganter und kürzer, erfordern aber ein gutes Verständnis des Konzepts.

Fazit

BSTs sind eine binäre Datenstruktur, die Werte in einer festen Ordnung organisiert. Dadurch entfällt beim Suchen die vollständige Durchsicht des Datensatzes. Allerdings können BSTs aus dem Gleichgewicht geraten und so an Leistung verlieren – im Extremfall muss dann doch der gesamte Datensatz geprüft werden.

AVL-Bäume beheben das mit zusätzlichen Balance-Eigenschaften mittels Rotationen. Dadurch bleibt die Höhe des Baums logarithmisch in Bezug auf die Datensatzgröße – ein deutlicher Gewinn.

Logarithmische Zeitkomplexität ist ein großer Vorteil gegenüber linearer Zeit. AVL-Bäume sind daher extrem effizient für Abfragen: Selbst bei Milliarden Einträgen müssen nur wenige Werte geprüft werden.