StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
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!
Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenHast 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.
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!
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:
Ein Teilbaum, der nur aus einem Wurzelknoten besteht, hat auch eine Höhe von 1! Hierbei handelt es sich um einen ausgeglichenen Knoten.
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.
"Rebalancierungs-Operationen" sind spezielle Rotationen, welche die Balance eines AVL Baumes gewährleisten.
Insgesamt gibt es vier Rotationen, Du Dir merken musst:
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 |
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:
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.
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.
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.
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; } } }
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!
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.
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.
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.
Der Balance-Faktor ergibt sich aus der Höhe vom rechten Teilbaum - der Höhe vom linken Teilbaum.
Das Rotrieren sorgt dafür, dass ein AVL-Baum stets balanciert ist. Dadurch erfolgt das Suchen innerhalb von AVL Bäumen deutlich schneller als bei anderen Suchbäumen.
Karteikarten in AVL Baum16
Lerne jetztWas ist ein AVL Baum?
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.
Die Höhe eines AVL Baumes beträgt O (log n)
Wahr
Aus welcher Formel ergibt sich der Balancefaktor?
Höhe (rechter Teilbaum) - Höhe (linker Teilbaum) ∈ {-1, 0, 1}
Bei welchem Balancefaktor hat man einen ausgeglichenen Baum?
0
Welche Rotation wendest Du an wenn vO gleich -2 und vU gleich 1 ist?
L-R-Rotation
Welche Rotation wendest Du an wenn vO gleich 2 und vU gleich 1 ist?
L-Rotation
Du hast bereits ein Konto? Anmelden
Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.
Melde dich an für Notizen & Bearbeitung. 100% for free.
Speichere Erklärungen in deinem persönlichen Bereich und greife jederzeit und überall auf sie zu!
Mit E-Mail registrieren Mit Apple registrierenDurch deine Registrierung stimmst du den AGBs und der Datenschutzerklärung von StudySmarter zu.
Du hast schon einen Account? Anmelden