Zur Themenübersicht     

Einfügen

Wenden wir uns dem unten stehenden Baum zu. Obwohl es auf den ersten Blick nicht so aussieht, gilt: bei jedem Knoten unterscheidet sich die Tiefe des linken und des rechten Teilbaumes höchstens um 1, er ist also ausgeglichen

.

Fügen wir nun wie üblich bei Suchbäumen eine 20 hinzu, so ergibt sich folgender unausgeglichener Baum:

Sowohl der Knoten mit dem Inhalt 50 wie auch die Wurzel mit dem Inhalt 60 sind linkslastig. Da eine Rotation im oberen Teil eines Baumes Unausgeglichenheiten unten im Baum im allgemeinen nicht ausgleicht, muss der Baum sukzessive von unten nach oben ausgeglichen werden. In diesem Beispiel heißt das:  Zuerst ist der Baum mit der Wurzel 50 auszugleichen!
Der linke Teilbaum von 50 , also der mit der Wurzel 40 (oben rot) ist zu lang. Bei diesem Teilbaum müssen wir nun zwei Fälle unterscheiden. Fall1: Der äußere Teilbaum dieses zu langen Teilbaumes ist zu lang. Fall2: Der innere Teilbaum dieses zu langen Teilbaumes ist zu lang. 

Zum Verständnis noch einmal ausführlich: Der rot markierte zu lange Teilbaum ist seinerseits ausgeglichen. Sonst würden wir ja diesen Baum ausgleichen! Unausgeglichen ist der darüber liegende Baum mit der Wurzel 50. Für die Art des  Ausgleichens ist aber dieser (rot markierte) zu lange Teilbaum entscheidend. Er besitzt selber zwei Teilbäume. Die Frage ist nun, ob der innere oder der äußere dieser (roten) Teilbäume zu lang ist! (Frage: Warum ist es nicht möglich, dass beide Teilbäume zu lang sind??)  

1. Fall:  der äußere Teilbaum ist zu lang: Dieser Teilbaum ist oben in etwas hellerem Rot markiert. Hier genügt nun eine einfache Rotation nach innen (hier nach rechts) um die linkslastige Wurzel (hier 50) 

und der gesamte (!!) Baum ist wieder ausgeglichen.

2. Fall: Etwas schwieriger ist die Situation, wenn der innere Teilbaum des zu langen Teilbaumes zu lang ist. Die ist in folgendem Beispiel der Fall. Wir gehen aus von folgendem ausgeglichenen Baum:

Fügen wir hier eine 48 ein, so ergibt sich folgender unausgeglichener Baum: 

Wiederum ist die 50 linkslastig. Der zu lange Teilbaum ist rot eingefärbt. In diesem roten Teilbaum ist allerdings der zu lange Teil (etwas heller rot markiert)  innen. Eine einfache Rechtsrotation um die linkslastige 50 ergäbe: 

Wiederum wäre die gleiche Stelle im Baum (hier die 40) unausgeglichen. 
Wir müssen also anders vorgehen. In dem zu langen (roten) Teilbaum ist erst eine Rotation nach außen (hier nach links) durchzuführen. 

Wir erhalten:

Jetzt haben wir wiederum die Situation des ersten Falles: Die 50 ist linkslastig, aber der zu lange Teilbaum hat seinerseits seinen längeren Teilbaum außen. Es genügt eine Rotation nach innen (hier nach rechts) um die nicht ausgeglichene Wurzel (hier also um die 50) und wir erhalten einen Baum, der interessanter Weise nicht nur unten sondern insgesamt ausgeglichen ist. 

Dies ist kein Zufall, denn es lässt sich allgemein zeigen, dass nach dem Einfügen eines Knotens in einen AVL-Baum der Ausgleich durch höchstens zwei Rotationen wieder hergestellt werden kann. 

Löschen:

Nach diesen nicht einfachen Ausführungen zum Einfügen verweisen wir zum Löschen auf den Informatiktreff der Bezirksregierung Düsseldorf. Dort findet sich eine sehr gute Erklärung zum Löschen in AVL-Bäumen unter: http://www.informatiktreff.de/materialien/sek_ii/algorithmen/avl/avlbaum.htm

Zur Themenübersicht
Zum Seitenanfang
Zur vorigen Seite	Zur nächsten Seite