Im Rahmen der Vorlesung "Objektorientierte Programmierung" an der Fachhochschule Regensburg wurde im WS 2000/2001 unter der Leitung von Prof. Juergen Sauer oben ersichtliches Java-Applet erstellt. Es dient zur Simulation von AVL Bäumen.

Was ist ein AVL Baum?
Benannt nach den Anfangsbuchstaben seiner Entdecker (Adelson, Velskii und Landis) gehört der AVL Baum zu der Gruppe der dynamisch ausgeglichenen Binärbäume. Ein Baum hat die AVL-Eigenschaft, wenn in jedem Knoten sich die Höhen der beiden Unterbäume höchstens um 1 unterscheiden. Diese Eigenschaft stellt sicher, daß ein Baum nicht in eine lineare Liste entartet.

Was ist so kompliziert an AVL Bäumen?
Damit die AVL-Eigenschaft erhalten bleibt, muß nach jedem Einfügen oder Löschen geprüft werden ob in jedem Knoten die Eigenschaft erfüllt ist. Ist dies nicht der Fall, sind komplizierte Rotationen bzw. Doppelrotationen notwendig. Um den Einstieg in diese Thematik zu erleichtern, wurde dieses Applet konzipiert. Es ermöglicht das Einfügen, Suchen und Löschen von Baumknoten und zeigt die erforderlichen Schritte und Rotationen in grafischer Form.

Wie ist das Applet aufgebaut? Wie funktioniert es?
Die GUI des Applets teilt sich in folgende drei Bereiche: (auch in obiger Abbildung ersichtlich)

• Viewer mit Viewer-Control
• History
• Control

Im Viewer sind alle Animationen grafisch ersichtlich. Die Zoomfunktionen im Viewer-Control ermöglichen eine optimale Größenanpassung und gewährleisten somit eine übersichtliche Darstellung auch bei einer großen Anzahl von Baumknoten.

Die eigentliche Bedienung und Steuerung des Applets erfolgt über die ihm Control platzierten Eingabefelder, Buttons und Auswahlboxen. Diese stellen folgende Funktionalität zur Verfügung:

• Eingabefeld: Erlaubt die Eingabe von Knotendaten. Eingaben zwischen 1 und 999 sind zulässig. Falsche Eingaben werden in der History bemängelt.
   
• Einfügen: Fügt einen neuen Knoten im Baum ein. Der Knotenwert muß im Eingabefeld spezifiziert sein. Ist dies nicht der Fall, erfolgt eine entsprechende Fehlermeldung in der History.
   
• Random: Erzeugt zehn Zufallszahlen und fügt diese als Knoten in einen leeren Baum ein. Ist der Baum nicht leer, wird ein einziger Zufallsknoten erzeugt und an der entsprechenden Stelle im Baum eingefügt.
   
• Suchen: Sucht einen Knoten im Baum. Der Knotenwert muß im Eingabefeld spezifiziert sein. Ist dies nicht der Fall, erfolgt eine entsprechende Fehlermeldung in der History.
   
• Löschen: Löscht einen Knoten im Baum. Der Knotenwert muß im Eingabefeld spezifiziert sein. Ist dies nicht der Fall, erfolgt eine entsprechende Fehlermeldung in der History.
   
• Neu: Erzeugt einen leeren Baum, löscht die History und den Viewer und ermöglicht somit den Start einer neuen Simulation.
   

Um die Standardsituationen "Einfachrotation" und Doppelrotation" zu erzwingen, ist das Einfügen der Knoten in einer bestimmten Reihenfolge erforderlich. Die folgenden Schaltflächen entbinden den Anwender von dieser Aufgabe:

• Einfachrotation: Simulation einer Einfachrotation.
   
• Doppelrotation: Simulation einer Doppelrotation.
   

Die auf dem Viewer ersichtliche Animation kann jederzeit angehalten, weitergeführt und abgebrochen werden. Dies erfolgt mit den entsprechenden Buttons:

• Pause: Stopt die Animation sofort. Im Viewer erscheint ein rotes "PAUSE". (Kann bei breiten Bämen auch mal rechts außerhalb des sichtbaren Bereichs stehen :-/ Auf jeden Fall kann man den Zustand des Animators an den Buttons Pause und weiter erkennen.)
   
• Weiter: Beendet die Pause und führt die Animation fort.
   
• Abbrechen: Bricht die Animation ab und führt den Baum in den Endzustand über. Bei Random, Einfach- und Doppelrotation werden trotzdem alle Knoten eingefügt.
   

Darüberhinaus kann die Animation im Einzelschrittmodus erfolgen. Wird diese Option gewählt, so wird die Animation nach allen signifikanten Ereignissen (Einfügen, Rotieren, Balanceänderungen) angehalten. Die Animation wird dann mit dem Button weiter fortgesetzt.

• Animation: Schaltet Animationssequenzen ein bzw. aus. Ist diese Option deaktiviert, springen die Knoten direkt in ihre Zielposition. Dies ist hilfreich, wenn man die Animationssequenzen nicht immer ansehen will und spart auch Zeit. Die Umschaltung kann auch während einer laufenden Animation erfolgen.
   
• immer warten: Mit dieser Option wird der Einzelschrittmodus noch weiter verschärft. Ist diese Option aktiviert, so wird nach jedem Einzelschrift eine Pause gemacht.
   

Release-Note:
Das Applet wurde von uns mit diversen Browsern auf verschiedenen Plattformen getestet. Dabei sind uns einige Dinge aufgefallen, die ihr auf der FAQ-Seite nachlesen koennt. Soviel sei aber bereits hier gesagt: Das Applet läuft mit dem Microsoft Internet Explorer 5.x am schnellsten (dank JIT-Compiler). Am saubersten läuft es allerdings im AppletViewer oder Netscape unter Linux. Allgemein gilt: Um das Applet ausführen zu können ist mindestens ein Browser mit Unterstützung für JDK1.1.x notwendig. (z.B. Netscape Communicator 4.x oder Internet Explorer 5.x)


Das Autorenteam wünscht viel Spaß :-))