Prüfungsfrage 07 – Binärbaum, AVL-Baum, Algorithmus, Datenstruktur

 

Gegeben ist ein Binärbaum. Nun wird der Knoten D gelöscht. Wie sieht der Baum nach Löschen des Knotens aus? Geben Sie eine Programmskizze „Löschen eines Knotens“ an“!
Wie kann die durch Löschen oder Einfügen von Knoten ausgelöste Unbalanciertheit eines Baums vermieden werden?

Lösung

Der Unterschied der Höhen hlinks und hrechts der beiden Nachfolger-Teilbäume eines Knotens soll minimiert werden.

inf-avl-tree-01

Hier ist hrechts-hlinks = -2. Dies muss verbessert werden. Die Idee hinter selbstbalancierten Binärbäumen (AVL-Bäume nach Adelson-Velsky-Landis) ist es, in jedem Knoten ein Balancekriterium zu speichern. Dieser Wert wird berechnet mit der Formel bal = hrechts-hlinks.
Zulässige Werte für bal sind nur {-1, 0, 1}, das heißt der linke und der rechte Teilbaum eines Knotens dürfen sich höchstens um 1 in der Höhe unterscheiden.

Es kann nachgewiesen werden, dass in diesem Fall der Aufwand zum Einfügen eines neuen Knotens nur O(log n) ist.

Beispiel:

1. bis 3. Knoten einfügen:

inf-avl-tree-02

inf-avl-tree-03

inf-avl-tree-04

4. und 5. Knoten einfügen:

inf-avl-tree-05

inf-avl-tree-06

Operationen in AVL-Bäumen

Einfügen neuer Knoten mit insert

Wenn wir einen neuen Knoten einfügen, gehen wir wie beim normalen Binärbaum vor. Jedoch wird rückwärts, vom neuen Knoten aus, dem vorausgehende Knoten mitgeteilt, dass der entsprechende Teilbaum gewachsen ist.
bal erhöht oder verringert sich dadurch um 1. Wenn sich bal nicht mehr im zulässigen Wertebereich befindet, muss der Baum lokal umgebaut werden. Der Funktion wird wie beim Binärbaum der Schlüssel des neuen Elementes übergeben, sowie die Stelle, an der das Element eingefügt werden soll. Beim Aufruf durch den Benutzer ist dies der Wurzelknoten. Programmintern wird die Funktion dann im weiteren Verlauf rekursiv von sich selbst mit einem anderen Parameter für t aufgerufen.
Im ersten Schritt wird geprüft, ob an der Stelle t schon ein Knoten existiert. Wenn nicht, wird an genau dieser Stelle der neue Knoten erzeugt. Wenn der Knoten t schon existiert, muss geprüft werden, ob der neue Knoten als linker oder als rechter Nachfolger in Frage kommt. Hierfür wird der übergebene Schlüssel mit dem Schlüssel des Knotens t verglichen. An dieser Stelle wollen wir nun vier verschiedene Fälle untersuchen, die beim Einfügen des Knotens auf der linken oder der rechten Seite auftreten können.

Fall 1:

Durch das Einfügen des neuen Knotens wird der linke Arm zu lang. Diese Situation ist der “Left-Left-Case”. Das Problem wird behoben durch eine einfache Rotation nach rechts:

inf-avl-tree-07

inf-avl-tree-08

Der linke Teilarm (Element 2) wird dabei einfach mitgezogen. Da auf dieses linke “Kind” geachtet werden muss, wird die Rotation “rotateWithLeftChild” genannt.

Fall 2:

Durch das Einfügen des neuen Knotens wird der linke Arm zu lang. Dieser Fall (Right-Right-Case) ist analog zu Fall 1. Hier wird also auch das Problem mit der gleichen Herangehensweise gelöst: Der Baum wird nach links rotiert mit der Funktion “rotateWithRightChild”

Fall 3:

Durch das Einfügen des neuen Knotens wird der linke Arm zu lang, allerdings ist der neue Knoten nun nicht linker Nachfolger, sondern rechter Nachfolger. Hier kann der Baum nicht einfach nach rechts rotiert werden, denn dann wäre der Knoten 3 an der Stelle der Wurzel. Sowohl Knoten 4 als auch Knoten 5 haben aber einen größeren Schlüsselwert als Knoten 3, deshalb hätte Knoten 3 zwei rechte Nachfolger. Es muss jedoch immer einen linken und einen rechten Nachfolger geben.

inf-avl-tree-11

Die Lösung des Problems ist eine doppelte Rotation. Zuerst wird eine lokale Rotation nach links durchgeführt, anschließend folgt eine Rotation nach rechts, wobei das linke “Kind” mitgezogen wird:

inf-avl-tree-12

Knoten 4 ist nun die neue Wurzel, er hat einen linken und einen rechten Nachfolger und der Baum ist wieder ausbalanciert. Die Funktion, die diesen beiden Rotationen kombiniert, ist “doubleWithLeftChild”.

Fall 4:

Durch das Einfügen des neuen Knotens wird der rechte Arm zu lang, allerdings ist der neue Knoten nun nicht rechter Nachfolger, sondern linker Nachfolger. Dies ist analog zu 3.

Löschen eines Knotens

Es gibt zwei Varianten, einen Knoten aus einem Binärbaum zu löschen.

Erste Möglichkeit:

Der linke Nachfolgerbaum wird an die Stelle des gelöschten Knotens gesetzt. Der rechte Nachfolgerbaum wird an den untersten rechten Knoten des linken angehängt. Anschließend muss mit den oben beschriebenen Rotationen die Balance des Baumes wiederhergestellt werden.

inf-avl-tree-15

Zweite Möglichkeit:

Der zu löschende Knoten wird durch das kleinste Element des rechten Nachfolgerbaumes ersetzt (im Fall oben wäre dies der Knoten F). Dieses Element lässt sich finden, indem man im rechten Baum immer dem linken Weg nach unten folgt, bis es nur noch einen Weg nach rechts oder gar keinen Weg mehr gibt. Diese Möglichkeit des Löschens verhindert, dass sich die Geometrie des Baumes stark ändern kann, es müssen daher nicht viele, sondern höchstens eine Rotation zur Balancierung durchgeführt werden.

Rechenaufwand

Die Links- und Rechtsrotationen sind alle lokale Operationen mit dem Aufwand O(1). Als obere Abschätzung kann man sagen, dass schlimmstenfalls bei jedem Einfügen eine Rotation durchgeführt werden muss. Dieser schlimmste Fall kann aber mathematisch nachweislich nicht auftreten, der Rechenaufwand zum Einfügen eines Knotens geht nicht über O(log n) hinaus.

Der Rechenaufwand, um den gesamten Baum aufzubauen ist somit O(n log n), das Optimum für einen Binärbaum.
Der fertig aufgebaute AVL-Baum ist ein perfekter Binärbaum, in dem mit minimalem Aufwand eine sortierte Traversierung durchgeführt werden kann. Zusätzlich ist der AVL-Baum eine dynamische Datenstruktur (Vorteile gegenüber statischen Feldern). Somit ist der AVL-Baum auch ein optimales Sortierverfahren.