My IT Utilities

AVL-Baum

Von einem zufälligen AVL-Baum ausgehen und Werte Schritt für Schritt einfügen, suchen oder löschen: Balancefaktor jedes Knotens, LL-, RR-, LR- und RL-Rotationen, Array-Form und hervorgehobener C++-Code.

Alles wird in diesem Browser simuliert; nichts wird an einen Server gesendet.

Keine Schritte

Keine Schritte

AVL-Baum

Array-Index · Balancefaktor

60[0]+145[1]+185[2]+167[5]018[3]-153[4]028[8]0

Array-Form

Die Kinder von Index i liegen bei 2i+1 und 2i+2.

  • Unbeteiligt
  • Bereits passiert
  • Wird verglichen
  • Gefunden
  • Neu
  • Zu löschen
  • Nachfolger
  • Unausgeglichen
  • Pivot

Keine Schritte

Code

#include <iostream>
#include <algorithm>
using namespace std;
class Node { // Ein Knoten enthält seinen Wert und Zeiger auf seine beiden Kinder
private: // Private Attribute: nur die Methoden greifen darauf zu
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Höhe: ein Blatt ist 1 und eine freie Stelle (nullptr) ist 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Balancefaktor: linke Höhe minus rechte Höhe
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Einfache Rechtsrotation: das linke Kind x steigt auf und y steigt ab
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Einfache Linksrotation: das rechte Kind y steigt auf und x steigt ab
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Gibt die Wurzel des Teilbaums zurück, balanciert
int bf = balanceFactor(n); // Der Balancefaktor des Knotens wird berechnet
if (bf > 1) { // Linkslastig. Ist das linke Kind nicht rechtslastig, liegt der LL-Fall vor
if (balanceFactor(n->getLeft()) < 0) // Das linke Kind ist rechtslastig: LR-Fall, zuerst links rotieren
n->setLeft(rotateLeft(n->getLeft())); // Erste Rotation des LR-Falls
return rotateRight(n); // Rechtsrotation: löst LL und die zweite Hälfte von LR
}
if (bf < -1) { // Rechtslastig. Ist das rechte Kind nicht linkslastig, liegt der RR-Fall vor
if (balanceFactor(n->getRight()) > 0) // Das rechte Kind ist linkslastig: RL-Fall, zuerst rechts rotieren
n->setRight(rotateRight(n->getRight())); // Erste Rotation des RL-Falls
return rotateLeft(n); // Linksrotation: löst RR und die zweite Hälfte von RL
}
return n; // Der Faktor liegt zwischen -1 und 1: keine Rotation nötig
}
Node* insert(Node* root, int v) { // Fügt v in den AVL-Baum ein und gibt die Wurzel zurück
if (root == nullptr) // Freie Stelle: hier kommt der neue Knoten hin
return new Node(v); // Erzeugt den neuen Knoten
if (v < root->getValue()) // Kleinere Werte gehen nach links, größere nach rechts
root->setLeft(insert(root->getLeft(), v)); // Steigt in den linken Teilbaum ab
else
root->setRight(insert(root->getRight(), v)); // Steigt in den rechten Teilbaum ab
return rebalance(root); // Beim Rückweg aus jedem Aufruf wird die Balance des Knotens geprüft
}
int main() {
Node* root = buildTree(); // Der angezeigte Baum, bereits aufgebaut
root = insert(root, v); // Erster Aufruf, aus main
return 0; // Ende der Operation
}

Dieses Tool startet mit einem zufälligen AVL-Baum, einem binären Suchbaum, der balanciert bleibt, und lässt Sie ihn von Hand verändern: Geben Sie einen Wert von 1 bis 99 ein und drücken Sie Einfügen, Suchen oder Löschen. Jeder Knoten zeigt seinen Balancefaktor, die Höhendifferenz seiner Teilbäume, und seinen Index im Array. Erreicht ein Knoten den Faktor 2 oder -2, markiert die Animation ihn und wendet die passende Rotation an: LL, RR, LR oder RL. Darunter erscheint derselbe Baum als Array, und der C++-Code hebt die ausgeführte Zeile hervor. Alles wird in Ihrem Browser simuliert.

So funktioniert es

  1. Passen Sie die Baumgröße mit dem Schieberegler an oder drücken Sie Neuen Baum erzeugen, um den Ausgangspunkt zu ändern.
  2. Geben Sie einen Wert von 1 bis 99 ein und drücken Sie Einfügen, Suchen oder Löschen. Die Animation startet von selbst.
  3. Beobachten Sie den Balancefaktor unter jedem Knoten und die Rotation, die bei 2 oder -2 angewendet wird.
  4. Gehen Sie vor und zurück und vergleichen Sie den Baum mit seiner Array-Form und der hervorgehobenen C++-Zeile.

Häufig gestellte Fragen

Was ist ein AVL-Baum und was garantiert er?
Ein binärer Suchbaum, der sich selbst neu balanciert: An jedem Knoten beträgt der Höhenunterschied zwischen linkem und rechtem Teilbaum höchstens 1. Diese Differenz heißt Balancefaktor und ist in einem gültigen AVL-Baum -1, 0 oder 1. Deshalb wächst die Höhe logarithmisch mit der Knotenzahl.
Was sind die vier Rotationsfälle und wann wird welcher genutzt?
Hat ein Knoten den Faktor 2 und sein linkes Kind ist linkslastig, liegt der Fall LL vor, und eine einfache Rechtsrotation genügt. Ist das Kind rechtslastig, ist es LR: Das Kind wird nach links, dann der Knoten nach rechts rotiert. Bei Faktor -2 ist es symmetrisch: RR löst eine einfache Linksrotation, RL eine Rechtsrotation des Kindes gefolgt von einer Linksrotation.
Was kosten Einfügen, Suchen und Löschen im Vergleich zum BST?
Im AVL-Baum brauchen alle drei Operationen im schlechtesten Fall logarithmische Zeit, weil die Höhe nie ausufert. Im einfachen BST hängt der Aufwand von der Höhe ab, die linear werden kann, wenn Werte sortiert eingefügt werden und der Baum zur Liste entartet. Dafür führt der AVL-Baum beim Einfügen oder Löschen einige Rotationen aus.
Wie wird ein AVL-Baum in einem Array gespeichert und was ist der Index über jedem Knoten?
In Heap-Form: Die Wurzel liegt bei Index 0 und die Kinder von Index i bei 2i+1 und 2i+2. Die Zahl in Klammern über jedem Knoten ist diese Position und entspricht der Array-Zelle, in der sein Wert steht. Fehlen Kinder, bleiben die Positionen dazwischen leer.

Verwandte Tools