Hast Du bei sehr starkem Wind einen Baum schon mal biegen sehen? Oder hast Du Dich schon einmal gewundert, wie ein Baum mit vielen Früchten nicht aus der Balance kommt? In der Informatik gibt es eine besondere Baumdatenstruktur, die dafür sorgt, dass ein Baum niemals aus der Balance kommt!
Hier erfährst Du wie das ganze eigentlich möglich ist und warum dieser Baum beim Suchen von Daten so effizient ist.
AVL Baum Bedeutung
Binäre Suchbäume gibt es viele. Allerdings ist der AVL-Baum die älteste Datenstruktur für binäre Suchbäume und wurde im Jahr 1962 von den sowjetischen Mathematikern Georgi Maximowitsch Adelson-Velski und Jewgeni Michailowitsch Landis vorgestellt.
Den AVL Baum kannst Du auch als AVL-Baum schreiben!
Ein AVL Baum ist ein ausgeglichener binärer Suchbaum, wobei sich für jeden Knoten die Höhen seines linken und rechten Teilbaumes um maximal eins unterscheiden.
Dabei hat ein AVL-Baum modifizierte Einfügen und Entfernen Operationen, die dafür sorgen, dass die Balance aufrechterhalten bleibt. Das bedeutet, dass nach jeder Operation, die Struktur überprüft wird und je nach Bedürfnis durch sogenannte Rebalancierungs-Operationen, auch Rotationen genannt, der Baum wieder ausgeglichen wird.
Mehr über Suchbäume und seine Variationen findest Du in eigenständigen Erklärungen auf StudySmarter!
Was es mit dem Balancieren und der Rotation auf sich hat, wirst Du in den folgenden Abschnitten erfahren. Zunächst erfährst Du aber etwas über die Struktur eines AVL Baum!
Höhe eines AVL-Baums
Die Ausgeglichenheit eines AVL-Baums sorgt dafür, dass die Höhe des Suchbaumes stets O (log n) ist. Damit sind auch alle anderen Operationen mit O (log n) ausführbar.
Eine Eigenschaft des AVL Baumes ist, dass jeder Knoten einen Balance-Faktor besitzt. Dieser ergibt sich aus folgende Formel:
Höhe (rechter Teilbaum) - Höhe (linker Teilbaum) ∈ {-1, 0, 1}
Es ist wichtig, drei Fälle zu unterscheiden:
- Rechtslastiger Knoten bei einem Balance-Faktor von > 0
- Linkslastigen Knoten bei einem Balance-Faktor von < 0
- Ausgeglichener Knoten bei einem Balance-Faktor von 0
Ein Teilbaum, der nur aus einem Wurzelknoten besteht, hat auch eine Höhe von 1! Hierbei handelt es sich um einen ausgeglichenen Knoten.
AVL Baum Beispiel
Anhand eines bildlichen AVL Baum Beispiels kannst Du Dir die Datenstruktur etwas deutlicher vorstellen:
In Abb. 1 siehst Du, wie die Balance an jedem Knoten vorgemerkt ist. Beim rechten Baum ist das AVL-Kriterium von (-1 ≤ BF ≤ 1) an Knoten 4 verletzt, weshalb es sich hier nur um einen binären Suchbaum handelt. Der Suchbaum ist nicht balanciert, da die Differenz der Höhe vom rechten und linken Teilbaum größer als eins ist. Die absolute Höhe ist dabei nicht interessant.
Es ist wichtig zu erwähnen, dass Eigenschaften wie Suchen, Vorgänger, Nachfolger oder Maximum/Minimum nicht von den modifizierten Einfügen und Entfernen Operationen betroffen sind, wenn die allgemeine Suchbaumeigenschaft weiterhin erhalten bleiben soll.
AVL Baum Rotation
"Rebalancierungs-Operationen" sind spezielle Rotationen, welche die Balance eines AVL Baumes gewährleisten.
Insgesamt gibt es vier Rotationen, Du Dir merken musst:
- Rechts Rotation um vO (R-Rotation)
- Links Rotation um vO (L-Rotation)
- Links-Rechts-Rotation; Links Rotation um vU, dann R-Rot um vO (L-R-Rotation)
- Rechts-links-Rotation; R-Rot um vU; dann L-Rot um vO (R-L-Rotation)
Außerdem kannst Du Dir noch merken, dass Rotationen, bei denen nur einmal rotiert wird, Einfachrotationen heißen. Wenn zweimal rotiert wird, heißt dies dementsprechend auch Doppelrotation.
vO beschreibt den oberen Knoten und vU steht für den unteren Knoten. Es wird also stets um den nicht balancierten Knoten rotiert.
Bei den Rotationen ist es wichtig den Balance-Faktor (BF) zu beachten, damit Du weißt, welche Rotation Du anwenden musst.
Folgende Tabelle kann Dir dabei einen Überblick verschaffen:
| BF von vO oberer Knoten | BF von vU unterer Knoten | Rotation |
| -2 | -1 | R-Rotation |
| 2 | 1 | L-Rotation |
| 2 | -1 | R-L-Rotation |
| -2 | 1 | L-R-Rotation |
AVL Baum Einfügen
Das Einfügen in einem AVL-Baum geschieht wie in einem normalen binären Suchbaum. Die Zahl 13 ist der Startknoten und daraufhin werden die Zahlen 6 und 5 eingefügt. Da die Zahl 6 kleiner als 13 ist, wird sie links von 13 eingefügt. Dasselbe passiert auch mit der Zahl 5. Zudem werden auch die Balance-Faktoren mit notiert.
Wenn Du jetzt jeden Knoten einzeln betrachtest, dann kannst Du Dir Folgendes notieren:
- Knoten 15 hat einen Balance-Faktor von 0.
- Knoten 6 hat einen Balance-Faktor von -1; Knoten 6 ist also linkslastig. Das AVL-Kriterium (-1 ≤ BF ≤ 1) ist allerdings erfüllt.
- Der Balance-Faktor an Knoten 13 beträgt -2; das AVL-Kriterium ist nicht erfüllt und es muss rotiert werden.
Mithilfe der oberen Tabelle siehst Du, dass eine Rechts-Rotation angewendet werden muss. Der Knoten 6 (vU) muss um 13 (vO) rotiert werden.
Knoten 6 ist aktuell die neue Wurzel und wenn Du jetzt die einzelnen Balance-Faktoren notierst, merkst Du, dass der Baum sowohl balanciert als auch ausgeglichen ist.
Also eigentlich ganz einfach, nicht wahr?
Bei den anderen Rotationen geschieht es ähnlich.
Links Rotation
In diesem Baum siehst Du anhand der Balance-Faktoren, dass sowohl Knoten 5 als auch 6 rechtslastig sind. Bei Knoten 5 ist allerdings das AVL-Kriterium nicht erfüllt. Hier muss eine Links-Rotation angewendet werden:
Nach der Rotation ist der Baum wieder balanciert und das AVL-Kriterium ist an jedem Knoten erfüllt.
Rechts-Links-Rotation
Knoten 5 ist hier rechtslastig und Knoten 13 dafür linkslastig. Anhand der Balance-Faktoren weißt Du, dass Du hier die Rechts-Links-Rotation (R-L-Rotation) anwenden musst.
Zuerst wird um Knoten 13 (vU) rechts rotiert. Daraufhin entsteht erneut ein unbalancierter Baum, weshalb wieder rotiert werden muss. Diesmal aber links um Knoten 5 (vO)
Es entsteht wieder ein balancierter, ausgeglichener Baum.
Links-Rechts-Rotation
Zuerst wird um Knoten 5 (vU) nach links rotiert. Daraufhin wird um Knoten 13 (vO) nach rechts rotiert.
AVL Baum Löschen
Sicherlich möchtest Du auch wissen, wie ein Knoten aus einem AVL-Baum gelöscht werden kann. Auch dies läuft nach dem gleichen Prinzip wie das Einfügen ab.
Zuerst löschst Du Deinen Knoten und danach musst Du rebalancieren. Außerdem musst Du darauf achten, dass Du eventuell Knoten evtl. neu einordnen musst, wenn Du rotierst.
Gegeben ist ein AVL-Baum
Wenn hier der Knoten 16 gelöscht wird, ist der Baum unbalanciert und es muss rotiert werden. Nach dem Löschen beträgt der Balance-Faktor von Knoten 8 (vO) -2 und der von Knoten 4 (vU) 1. Daher muss eine Links-Rechts-Rotation durchgeführt werden.
Bei der Links-Rotation rutscht der Knoten 4 links von Knoten 6 und tauscht mit Knoten 5 die Plätze. Da aber 5 größer als 4 ist und wieder einen Platz braucht, wird er rechts von Knoten 4 eingefügt. Dementsprechend erfolgt die Rechts-Rotation um Knoten 8.
Wieder rutscht Knoten 8 rechts von Knoten 6 und tauscht mit Knoten 7 die Plätze. Da 7 aber kleiner als 8 ist und einen Platz benötigt, wird er an die linke Stelle von Knoten 8 eingefügt.
AVL Baum erstellen
Du hast eben gelernt, wie ein AVL-Baum erstellt wird. Du folgst den Prinzipen eines Suchbaumes und balancierst je nach Bedarf. Wie diese Datenstruktur aber implementiert wird, siehst Du im folgenden Abschnitt.
AVL Baum Java
Die Basis Implementierung von einem AVL Baum in Java unterscheidet sich kaum von dem eines normalen binären Suchbaumes. Allerdings müssen die Operationen später modifiziert werden.
Zu Beginn wird der Startknoten (Wurzel), hier auch „Node“ genannt, implementiert:
class Node {
int data;
Node left;
Node right;
int height;
public Node(int data) {
this.data = data;
}
}Der AVL-Baum wird durch die Klasse AvlTree implementiert:
class Node {
int data;
int height; //speichern der Höhe
Node left;
Node right;
public Node (int data) {
this.data = data
}
}
// 3 Methoden für das Balancieren der AVL-Bäume
class AVLTree {
private Node root;
int height(Node node) {
return node != null ? node.height : -1;
}
void updateHeight(Node node) {
int leftChild = height(node.left);
int rightChild = height(node.right);
node.height = max(leftChild, rightChild) +1;
}
int balanceFactor(Node node) {
return height(node.right) - height(node.left);
}
// RechtsRotation
Node rotateRight (Node node) {
Node leftChild = node.left; // Merken des Linken Knotens/Kind LeftChild von node
node.left = leftChild.right;
leftChild.right = node;
// ersetzen des linken Kindes von node durch das rechte Kind des linken Kindes leftChild.right
// node wird danach als das neue rechte Kind von dem linken Kind gesetzt
updateHeight(node);
updateHeight(leftChild);
return leftChild;
}
// LinksRotation
Node rotateLeft (Node node) {
Node rightChild = node.left;
node.right = rightChild.left;
rightChild.left = node;
updateHeight(node);
updateHeight(rightChild);
return rightChild;
}
// Implementierung der Rebalance Operationen durch das Betrachten der einzelnen Fälle:
Node rebalance(Noded node) {
updateHeight(node);
int balance = BalanceFactor(node);
if (balance < -1) {
if (balanceFactor(node.left) <= 0) {
// RechtsRotation:
node.rotateRight(node);
} else {
// Links-Rechts-Rotation:
node.left = rotateLeft(node.left);
node = rotateRight(node);
}
}
// Überprüfen, ob der Teilbaum rechtslastig ist
if (balance > 1) {
if (balanceFactor(node.right) >= 0) {
//LinksRotation
node = rotateLeft(node);
} else {
// Rechts-Links-Rotation:
node.right = rotateRight(node.right);
node = rotateLeft(node);
}
}
return node;
}
// Einfügen funktioniert so ähnlich wie bei einem B-Baum
Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
} else if (node.key > key) {
node.left = insert(node.left, key);
} else if (node.key < key){
node.right = insert(node.right, key);
} else {
throw new Runtime Exception("duplicate Key!");
}
return rebalance(node);
}
Noide delete(Node node, int key) {
if (node == null) {
return node;
} else if (node.key > key) {
node.left = delete(node.left, key);
} else if (node.key < key) {
node.right = delete(node.right, key);
} else {
if (node.left == null || node.right == null) {
node = (node.left == null) ? node.right : node.left;
} else {
Node mostLeftChild = mostLeftChild(node.right);
node.key = mostLeftChild.key;
node.right = delete(node.right, node.key);
}
}
if (node != null) {
node = rebalance(node);
}
return node;
Node find(int key) {
Node current = root;
while (current != null) {
if (current.key == key) {
break;
}
cuurent = current.key < key ? current.right : current.left;
}
return current;
}
}
}AVL Baum – Vergleich zu anderen Suchbäumen
In der Informatik ist der Suchbaum eine abstrakte Datenstruktur, dessen Elemente in der Form von geordneten Bäumen gespeichert sind. Dabei heißt ein (Binär) Baum ausgeglichen oder balanciert, wenn er bei n Knoten eine Höhe in der Größenordnung von O (log n) hat.
Dir sollten die Unterschiede der jeweiligen Suchbäume bewusst sein, weshalb in den folgenden Abschnitten die Differenzen noch einmal dargestellt werden.
Du findest zu den verschiedenen Bäumen, wie B-Baum oder dem Rot Schwarz Baum jeweils eine eigenständige Erklärung auf StudySmarter!
AVL-Baum vs. Rot Schwarz Baum
Ein Rot Schwarz Baum ist ein selbst balancierender binärer Suchbaum, dem jedem Knoten anhand von bestimmten Regeln eine Farbe zugeordnet ist.
| AVL-Baum | Rot Schwarz Baum |
| Sehr strenge Balancierungregeln, die eine schnellere Suche ermöglichen | Weniger strenge Balancierungsregeln |
| Komplex zu implementieren in der Praxis | Einfach zu implementieren |
| Jeder Knoten hat ein Balance-Faktor | Jedem Knoten ist eine Farbe (rot oder schwarz) zugeordnet |
| Einfügen und Entfernen erfolgen relativ langsam | Einfügen und Entfernen erfolgen zügig |
| Die Tiefe zweier Teilbäume unterscheidet sich nie um mehr als 1 | Längster Pfad ist maximal doppelt so lang wie der kürzeste, nie länger |
Das Suchen liegt in beiden Bäumen im Bereich von O (log n), allerdings ist die Suche in der Praxis bei AVL-Bäumen schneller. Das Einfügen liegt ebenfalls im Bereich von O (log n), da aber der Rot Schwarz Baum seltener balanciert wird, erfolgt das Einfügen und Entfernen schneller.
AVL-Baum vs. Binärer Suchbaum
Ein Binärer Suchbaum (BST) ist ein binärer Baum (B-Baum), dessen Elemente im Linken Teilbaum kleiner als seine Wurzel sind und alle Elemente im rechten Teilbaum größer als seine Wurzel sind. Damit ist auch jeder AVL-Baum gleichzeitig ein BST Baum. Umgekehrt ist dies aber nicht der Fall.
Weitere Unterschiede zwischen einem Binären Suchbaum und einem AVL-Baum siehst Du in folgender Tabelle.
| Binärer Suchbaum (BST) | AVL-Baum |
| Höhe und Tiefe liegen im Bereich von O (n), mit n Knoten | Höhe und Tiefe liegen im Bereich von O (log n) |
| Suche in einem BST ist ineffizient, da der Baum nicht balanciert ist | Suche erfolgt aufgrund der Balance effizient |
| Beim Einfügen und Entfernen wird das Element nur mit der Wurzel verglichen – es gibt keine Rebalancierungs-Operationen | Nach jedem Einfügen und Löschen muss die Balance überprüft und eine AVL Rotation durchgeführt werden |
| Kein hoher Speicherverbrauch bei den einzelnen Operationen | Höherer Speicherverbrauch als bei einem BST, da für jeden Knoten der Balance-Faktor mitgespeichert werden muss |
Das Einfügen in einem BST ist weniger effizient, da ein BST zu einer linearen Liste degenerieren kann.
AVL Baum – Das Wichtigste
- Ein AVL-Baum ist ein ausgeglichener binärer Suchbaum, wobei sich für jeden Knoten die Höhen seines linken und rechten Teilbaumes um maximal eins unterscheiden.
- AVL Baum erstellen: Die Erstellung eines AVL-Baums erfolgt genauso wie bei anderen Suchbäume, allerdings muss die Balance mit beachtet werden.
- Der Balance-Faktor errechnet sich durch die Höhe (rechten Teilbaumes) - Höhe (linken Teilbaumes) und wird an jedem Knoten vermerkt.
- AVL Baum Rotation: Es gibt vier Rotationen, die für die Balancierung eines AVL-Baums zuständig sind: Rechts-Rotation, Links-Rotation, Rechts-Links-Rotation, Links-Rechts-Rotation
- Eine AVL Rotation erfolgt nach dem Einfügen und Löschen.
- Die Suche innerhalb eines AVL Baum, erfolgt schnell und liegt im Bereich von O (log n).
- AVL Baum Java: Einen AVL Baum in Java zu implementieren, erfolgt so ähnlich wie bei einem B-Baum, allerdings müssen die Rotationen mit einbezogenen werden, die wiederum etwas komplexer sind.
- Der Aufwand für das Ausgleichen in einem AVL-Baum ist aufgrund der geringeren Umsortierung deutlich weniger als bei anderen Suchbäumen.
Nachweise
- Ralf Hartmut Güting; Stefan Dieker (2018). Datenstrukturen und Algorithmen. Springer
- Prof. Dr.-Ing. Matthias Teschner (2012). Algorithmen und Datenstrukturen Balancierte Suchbäume. cg.informatik.uni-freiburg.de (25.10.2022)
- happycoders.eu: AVL-Baum (mit Java-Code). (28.10.2022)
Erklärungen 
Magazine 
