AVL-Baumeinfügungs-, Rotations- und Ausgleichsfaktor erklärt

Was ist ein AVL-Baum?

Ein AVL-Baum ist ein Subtyp eines binären Suchbaums. AVL-Bäume, benannt nach den Erfindern Adelson, Velskii und Landis, haben zusätzlich zu allen Eigenschaften, die binäre Suchbäume aufweisen, die Eigenschaft eines dynamischen Selbstausgleichs.

Eine BST ist eine Datenstruktur, die aus Knoten besteht. Es hat folgende Garantien:

  1. Jeder Baum hat einen Wurzelknoten (oben).
  2. Der Wurzelknoten hat null, einen oder zwei untergeordnete Knoten.
  3. Jeder untergeordnete Knoten hat null, einen oder zwei untergeordnete Knoten usw.
  4. Jeder Knoten hat bis zu zwei Kinder.
  5. Für jeden Knoten sind seine linken Nachkommen kleiner als der aktuelle Knoten, was weniger als die rechten Nachkommen ist.

AVL-Bäume haben eine zusätzliche Garantie:

  1. Der Unterschied zwischen der Tiefe der rechten und linken Teilbäume kann nicht mehr als eins betragen. Um diese Garantie aufrechtzuerhalten, enthält eine Implementierung einer AVL einen Algorithmus zum Neuausgleichen des Baums, wenn das Hinzufügen eines zusätzlichen Elements diese Garantie stören würde.

AVL-Bäume haben eine Worst-Case-Such-, Einfüge- und Löschzeit von O (log n).

Rechtsdrehung

AVL-Baum rechts drehen

Linksdrehung

Linksdrehung des AVL-Baums

AVL-Einfügungsprozess

Sie führen eine Einfügung ähnlich einer normalen Einfügung in einen binären Suchbaum durch. Nach dem Einfügen korrigieren Sie die AVL-Eigenschaft mit Links- oder Rechtsdrehungen.

  • Wenn das linke Kind des rechten Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rotation von links nach rechts durch.
  • Wenn das linke Kind des linken Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rechtsdrehung durch.
  • Wenn das rechte Kind des rechten Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Linksdrehung durch.
  • Wenn das rechte Kind des linken Teilbaums ein Ungleichgewicht aufweist, führen Sie eine Rotation von rechts nach links durch.

Ein AVL-Baum ist ein selbstausgleichender binärer Suchbaum. Ein AVL-Baum ist ein binärer Suchbaum mit den folgenden Eigenschaften: -> Die Unterbäume jedes Knotens unterscheiden sich in der Höhe um höchstens einen. -> Jeder Unterbaum ist ein AVL-Baum.

Der AVL-Baum überprüft die Höhe der linken und rechten Unterbäume und stellt sicher, dass die Differenz nicht mehr als 1 beträgt. Diese Differenz wird als Ausgleichsfaktor bezeichnet. Die Höhe eines AVL-Baums ist immer O (Logn), wobei n die Anzahl der Knoten im Baum ist.

AVL-Baumrotationen

Im AVL-Baum müssen wir nach jeder Operation wie Einfügen und Löschen den Ausgleichsfaktor jedes Knotens im Baum überprüfen. Wenn jeder Knoten die Ausgleichsfaktorbedingung erfüllt, schließen wir die Operation ab, andernfalls müssen wir sie ausgleichen. Wir verwenden Rotationsoperationen, um den Baum auszugleichen, wenn der Baum aufgrund einer Operation aus dem Gleichgewicht gerät.

Rotationsoperationen werden verwendet, um einen Baum auszugleichen. Es gibt vier Rotationen und sie werden in zwei Typen eingeteilt:

Einzelne Linksdrehung (LL-Drehung)

Bei der LL-Drehung bewegt sich jeder Knoten von der aktuellen Position um eine Position nach links.

Einzelne Rechtsdrehung (RR-Drehung)

Bei der RR-Drehung bewegt sich jeder Knoten von der aktuellen Position um eine Position nach rechts.

Links-Rechts-Drehung (LR-Drehung)

Die LR-Drehung ist eine Kombination aus einer einzelnen Linksdrehung, gefolgt von einer einzelnen Rechtsdrehung. Bei der LR-Drehung bewegt sich zuerst jeder Knoten um eine Position nach links und dann um eine Position nach rechts von der aktuellen Position.

Rechts-Links-Drehung (RL-Drehung)

Die RL-Drehung ist eine Kombination aus einer einzelnen Rechtsdrehung, gefolgt von einer einzelnen Linksdrehung. Bei der RL-Drehung bewegt sich zuerst jeder Knoten um eine Position nach rechts und dann um eine Position nach links von der aktuellen Position.

Zeitanalyse von AVL-Bäumen

Der AVL-Baum ist ein binärer Suchbaum mit der zusätzlichen Eigenschaft, dass der Unterschied zwischen der Höhe des linken Teilbaums und des rechten Teilbaums eines Knotens nicht mehr als 1 betragen darf.

Algorithmus Durchschnitt Schlimmster Fall: Raum : O(n), Zeit:O(n)

Anwendung von AVL-Bäumen

AVL-Bäume sind in Fällen von Vorteil, in denen Sie eine Datenbank entwerfen, in der Einfügungen und Löschungen nicht so häufig sind, Sie jedoch häufig nach den dort vorhandenen Elementen suchen müssen.