AVL-Baum
Beschreibung des Applet
Dieses Applet dient zur Darstellung eines AVL-Baumes. Über das obere Textfeld werden die Werte eingegeben, welche
in den Baum eingefügt, aus dem Baum gelöscht oder einfach nur im Baum gesucht werden können. Dabei sind nur ganzzahlige Werte
erlaubt, welche zwischen 1 und 999 liegen.
Es folgt ein kurze Beschreibung der Buttons
Add Node : Der eingegeben Wert wird gemäß der Binärbaumregeln in den Baum eingefügt und gelb markiert.
Tritt eine Unbalance auf, dann wird im unteren Textfeld mitgeteilt, an welchem Knoten die Ursache hierfür ist.
Nach einem Klick auf den Next-Button, wird mittels Pfeilen dargestellt, welche Knoten miteinander vertauscht werden.
Dabei zeigt die Spitze eines aufsteigenden Pfeiles immer auf das Astende, an welchem der Knoten, der Ursprung der Pfeiles ist,
platziert werden wird. Während die Spitze eines absteigenden Pfeiles immer auf den Ursprung des Astes zeigt, an dem der Knoten,
welcher Ursprung dieses Pfeiles ist, angehängt wird. Bei einer Doppelrotation deutet ein roter Pfeil an, daß diese Rotation
zuerst durchgeführt wird. Danach wird die Rotation durchgeführt, welche durch die blauen Pfeile angedeutet wird.
Delete Node : Ist der Wert im Baum enthalten, dann wird der entsprechende Knoten schwarz eingefärbt.
Gleichzeitig wird der Knoten ermittelt, welcher den zu löschenden Knoten, falls notwendig, ersetzen wird und gelb eingefärbt.
Nach Drücken des Next-Button werden die eventuell verletzten Balancen wiederhergestellt und der Baum im ausbalancierten
Zustand dargestellt.
Search Node : Hier wird lediglich der eingegebene Wert im Baum gesucht. Ist dieser dort vorhanden, dann wird der dazugehörende
Knoten gelb eingefärbt. Diese Funktion wird bei relativ großen Bäumen sinnvoll werden.
Next : Dient zur Schritt für Schritt Verfolgung von Rotations- und Löschvorgängen. Zur Betätigung wird explizit hingewiesen.
Reset : Wird dieser Button gedrückt, dann wird der bisher erstellt Baum gelöscht und ein neuer, leerer Baum erzeugt. Diese Funktion
kann jederzeit durchgeführt werden.
Einige Anmerkungen
- Die Ziffernliste am des linken Rand dient als Höhenskala
- Da der Baum in der Lage ist die Äste bei zunehmender Größe zu spreizen, kann mittels der Scrollbars der gesamte Baum eingesehen werden.
- Balancekorrekturen nach Löschvorgängen werden nicht angezeigt. Der Umstand ist dadurch zu erklären, daß nach dem Löschen mehr als eine
Einzel- oder Doppelrotation folgen kann. Dies würde zu langwierigen Klickereien führen.
- Beim Einfügen erfolgen die Balanceüberprüfungen immer von dem frisch eingefügten Knoten beginnend aufsteigend in Richtung Wurzel. Die erste auftretende Unbalance wird korrigiert.
Mit dieser Korrektur, werden implizit auch höherliegende Unbalancen berichtigt.
- Wird beim Löschen der zu löschenden Knoten nicht oder durch seinen Sohn ersetzt, dann erfolgt die Balanceüberprüfung vom zu löschenden
Knoten aus. Ansonsten erfolgt die Überprüfung ab dem Knoten, welcher zum Ersetzen dient.
- Soll ein Knoten gelöscht werden, dann wird immer zuerst überprüft, ob dieser Knoten selbst Blattknoten ist oder nur einen Nachfolger hat.
Dies sind die trivialen Fälle. Ist dem nicht so, dann wird nach dem größten Knoten, welcher kleiner als der zu löschende Knoten ist, gesucht.
Ist dieser Knoten ein Blatt, dann wird ersetzt. Andernfalls wird der kleinste Knoten gesucht, der größer als der zu löschende Knoten ist. Ist auch
der kein Blattknoten, dann wird im tiefern der beiden Unterbäume (bei gleichtiefen Unterbäumen im linken) des Löschknoten der größte (kleinste) Knoten
kleiner (größer) als der zu entfernende Knoten, trotz eines Sohnes, genommen.
- Je nach Literatur wird eine größere Tiefe eines linken Unterbaums zum korrespondierenden rechten Unterbaum mit positiver oder mit negativer
Balance beschrieben. Bei diesem Applet wird die negative Balance verwendet.
_____________________________________________________________
Applet by Marco Huber, based on a Framework by Jan Sauerwein.