Kapitel 1 *

Kapitel 2 *

Kapitel 3 *

Kapitel 4 *

Kapitel 5 *

Kapitel 6 *

Literaturverzeichnis *

Abbildung 2.1: Vom Quell- zum Maschinencode *

 

 

1. Motivation und Aufgabenstellung

 

Das Projekt TeleTeaching der Universitäten Heidelberg und Mannheim befaßt sich mit dem gegenseitigen Austausch von Vorlesungen mittels eines digitalen Hochgeschwindig-keitsnetzes. Im Sommersemester 1996 wurde erstmals die Vorlesung Rechnernetze von Prof. Dr. Effelsberg auf diese Weise nach Heidelberg übertragen. Weitere Vorlesungübertragungen werden in Zukunft in beide Richtungen folgen.

Das Tele-Teaching hat sich zum Ziel gesetzt neue Formen des Lernens und Lehrens mit Hilfe neuer Medien zu proben und einzusetzen. Als primäre Ziele gelten die Bereicherung des Lehrangebots, Verbesserung der Lehre und Entwicklung eines Tele-Learning- Gesamtkonzepts. Die vorhandenen Lehr- und Lernmethoden sollen nicht erstetzt, sondern sinnvoll ergänzt werden.

Die erziehungswissenschaftliche Begleitung und Evaluierung durch die beteiligten Lehrstühle Erziehungswissenschaft II in Mannheim und Psychologie in Heidelberg ist von zentraler Bedeutung. So können Lern- und Akzeptanzschwierigkeiten bereits während der Entwicklung entgegengesteuert werden [EEG97].

Zu den Vorlesungen wird das Unterrichtsmaterial multimedial aufbereitet (Text, Graphiken, Video, Audio, etc.) und den Studenten per WWW zur Nachbereitung und Prüfungsvorbereitung zur Verfügung gestellt. Gegenüber klassischen Medien, wie z.B. Büchern bietet der Computer die Möglichkeit, interaktiv zu lernen, statt passiv zu konsumieren. Selbstständiges Ausprobieren und Anwenden des Wissens optimiert den Lerneffekt. Basierend auf dem "Learning by doing" – Prinzip sollten daher, zusätzlich zum reinen Vorlesungsstoff, interaktive Animationen/Simulationen entwickelt werden, die über WWW abrufbar sind.

Ziel dieser Studienarbeit ist die Entwicklung eines interaktiven Animations- bzw. Simulationsprogramms zur Visualisierung des AVL-Baum-Algorithmus, welcher in der Vorlesung Programmierverfahren und Datenstrukturen abgehandelt wird. Mit diesem Programm soll der Anwender in der Lage sein, seinen eigenen AVL-Baum nach belieben aufzubauen. Auf interaktives Eingreifen seitens der Anwender wird großes Augenmerkmal bei der Umsetzung gesetzt. Alle Aktivität geht direkt vom Benutzer aus. Damit der Lerneffekt noch zusätzlich verstärkt wird, ist ein Textfenster eingebaut. In diesem wird dem Benutzer permanent das aktuelle Geschehen klar verständlich erklärt.

Da die Animation im WWW abgelegt wird, soll das Programm auf mehreren Plattformen lauffähig sein. Aus diesem Grunde fiel die Wahl auf die an C++ angelehnte plattenformunabhängige Programmiersprache Java.

Besonderer Wert wird hierbei auf eine objektorientierte Entwicklung gelegt. Die entwickelten Basisklassen sollen so flexibel gestaltet werden, daß sie sich ohne signifikante Änderungen auch für Animationen in anderen Bereichen eignen.

Wie oben bereits erwähnt, wurde die Implemenitierung mit der Programmiersprache Java vorgenommen. Im folgenden Kapitel wird daher auf Java eingegangen. Ein wichtiger Bestandteil dieser Studienarbeit stellen AVL-Bäume dar. Sie werden im Kapitel 3 erklärt. Alle wichtige theoretische Hintegründe zu AVL-Bäumen wird in diesem Kapitel abgehandelt. Ferner wird speziell auf das Einfügen und Löschen von Knoten eingegangen. Im Kapitel 4 wird die Benutzerführung für das Programm erläutert. Alle Bedienungsmöglichkeiten werden explizit dargelegt, so daß beim Umgehen mit dem Programm keine Bedienungsfragen entstehen. Im letzten Kapitel wird das Thema Interner Programmaufbau aufgegriffen. In diesem werden Analyse und Design behandelt. Zudem wird zum Schluß auf Erweiterbarkeit und Verbesserungsvorschläge eingegangen.

 

 

1. Die Programmiersprache Java

 

Offenkundig ist Java derzeit die Programmiersprache fürs Internet. Sie bietet interessante Möglichkeiten, mit dynamischen HTML-Dokumenten Bewegung ins Web zu bringen, ohne für jede Änderung den HTTP-Server zu konsulitieren.

Java ist objektorientiert und vergleichbar mit C++, ist aber um einige Möglichkeiten ärmer. Sie ist so konzipiert, daß sie portabel ist. Die Portabilität reicht über verschiedene Plattformen und Betriebssysteme.

Normalerweise übersetzt ein Compiler Programme, die etwa in C++ geschrieben sind, in Maschinencode für einen speziellen Prozessor. Wenn das Programm auf einem anderen Rechner ablaufen soll, muß es ausgehend vom Quellcode neu kompiliert werden.

Im Gegensatz dazu enthält das Java Developers Kit (kurz JDK) zwei Arten von Übersetzern: den Java-Interpreter und den Java-Compiler. Letzterer generiert den maschinenunabhängigen Bytecode, der von ersterem und Interpretern aller anderen Plattformen abgearbeitet werden (siehe Abbildung 2.1).

---

---

---

 

Abbildung 2.1

Die Entwickler von Java haben ihre Ziele stichwortartig wie folgt zusammengefaßt:

Einfach, Objektorientiert, Verteilt, Robust, Sicher, Architekturneutral, Portabel, Interpretiert, Hohe Leistung, Multithreading und Dynamisch.

Nähere Erläuterungen zu obigen Schlägwörten findet man im Internet unter der URL-Adresse http://java.sun.com oder in den Büchern [F96] und [CH97].

Vielmehr soll es von Interesse sein, auf erste Erfahrungenswerte einzugehen, die bei dieser neuen Programmiersprache gesammelt wurden. Die Studienarbeit wurde mit der Version 1.0 von Java erstellt.

Keine Programmiersprache, die so viele Möglichkeiten bietet wie Java, ist leicht erlernbar. Man muß dabei zwischen kleinen Applets und größeren anspruchsvollen Programmen unterscheiden. Viele Java-Bücher widmen nur einen kleinen Teil ihres Inhalts der Sprache und den größten Umfang der Java-Bibliothek, welche über 150 Klassen und Schnittstellen beinhaltet. Man muß nicht alle davon für einen Programmierauftrag kennen, aber man braucht für jedes Projekt einige davon.

Etwas unübersichtlich ist der Aufbau der AWT-Bibliothek, verglichen beispielsweise mit Delphi. Auch könnte die Ereignisstruktur etwas ausgefeilter sein. Windows besitzt Hunderte von Ereignissen, Java dagegen nur knapp zwei Dutzend.

Viele Entwickler schreiben Programme am liebsten mit Hilfe spezieller Editoren. Aber PC-Programmierer, die "drag and drop" Systeme oder integrierte Entwicklungsplattformen, wie moderne C++ Compiler gewohnt sind, werden bestürzt sein. In diesem Punkt ist Besserung in Sicht, wodurch sich die Entwicklungszeit mit Java erheblich verkürzen wird.

Viele glauben, daß Java die universelle Programmiersprache für alle Programmiersprachen wird. Dies ist theoretisch möglich. Ob man sich auf den kleinsten gemeinsamen Nenner einigen wird, steht noch offen. Ein Beispiel: Man wird vergeblich versuchen die rechte Maustaste als Event aufzufangen, denn Java soll auch auf Plattformen benutzbar sein, bei denen die Mäuse nur eine Taste haben, wie dies beim Macintosh der Fall ist.

Java-Anwendungen sehen nicht so gut aus, wie etwa solche, die unter Windows-Anwendungen entwickelt wurden. Auf jeden Fall sind die mit Java 1.0 gelieferten Grafikwerkzeuge zu primitiv, um ein ansprechendes Design zu gestalten.

Die größten Probleme bei der Implementierung entstanden in der zum Teil noch fehlenden Kompatibilität. Ein fehlerloses Ablaufen unter dem Appletviewer bedeutet jedoch nicht, daß dies genauso unter einem Browser geschieht. Oft traten Securityfehler beim Ablauf des Programms unter einem Browser auf. So war es z.B. ein lang ungelöstes Rätsel, warum Securtity-Fehler beim Stoppen von Threads unter Netscape auftraten. Netscape erlaubt keine Threads, die in einer Klasse gestartet wurden, in einer anderen zu beeinflußen.

Mit Threads besteht auch das Problem der Zusammenarbeit zwischen Thread-Package und Betriebssystem. Wie ein Thread abläuft ist Sache des Betriebssystems. Nur das Betriebssystem kann die CPU-Zyklen zur Verfügung stellen. Es gibt Betriebssysteme, die einen laufenden Thread solange aktiv halten, bis ein höherwertiger Thread aktiviert wird und die Steuerung übernimmt. Andere Thread-Systeme weisen jedem laufenden Thread einen Zeitabschnitt zu, um seine Aufgabe zu erledigen. So ist es wohl auch zu erklären, weshalb das Applet unter manchen Betriebssystemen ruckartig und nicht flüssig abläuft.

Die Euphorie hinsichtlich Java ist ungebremst und wird voraussichtlich noch lange anhalten, da Java noch in seiner Entwicklungsphase steckt und noch viel Reden von sich machen wird. So kommt mit Java-Office, das in Kürze erscheinen soll, ein Produkt auf den Markt, das weitere Brücken zwischen verschiedenen Plattformen schlagen wird.

 

 

 

 

 

1. AVL-Bäume

 

Bäume gehören zu der wichtigsten in der Informatik auftretende Datenstruktur. Insbesonders kommen Binärbäume häufig vor. Mit ihnen können die Operationen Suchen, Einfügen und Entfernen effizient implementiert werden.

Die Operationen Suchen, Einfügen und Entfernen eines Schlüssels in einem zufällig erzeugten Binärbaum mit n Knoten ist zwar im Mittel mit der Komplexität O (log₂n) durchführbar, im worst-case kann jedoch ein entarteter Binärbaum entstehen. Dieser gleicht dann einer linearen Liste, wobei zur Durchführung einer Operation ein Aufwand von O(n) entsteht.

Durch zusätzliche Bedingungen an die Struktur des Baumes kann dies verhindert werden. In der Literatur [OW96] wird eine Vielfalt von Möglichkeiten beschrieben, die die Struktur eines Baumes mit n Knoten und einer Höhe von O(log₂n) zusichern und somit die Durchführung aller Baumoperationen in logarithmischer Zeit ermöglichen.

Der erste historische Vorschlag stammt von Adelson-Velskij und Landis. Eine entartete Struktur eines Binärbaumes wird durch die Forderungen an die Höhendifferenz der beiden Teilbäume eines jedes Knotens verhindert. Sie gehören deshalb auch der Klasse der höhenbalancierten Bäume an.

Bäume, die diese Bedingungen erfüllen, heißen nach ihren Schöpfern AVL-Bäume.

Im folgenden Kapitel wird zuerst die Definition von AVL-Bäumen wiedergegeben. Danach wird mit dieser der Zusammenhang zwischen Knotenzahl und Baumhöhe untersucht. Damit kann gezeigt werden, daß AVL-Bäume nie entarten. Im Anschluß werden die Operationen Einfügen eines Schlüssels in einen AVL-Baum und Entfernen eines Schlüssels aus einem AVL-Baum erläutert.

 

1. 3.1 Definition

Ein binärer Suchbaum T ist AVL-ausgeglichen oder höhenbalanciert, kurz: ein AVL-Baum, wenn für jeden Knoten p des Baumes gilt, daß sich die Höhe des rechten Teilbaumes von der des linken Teilbaumes höchstens um eins unterscheidet [OW96].

| Höhe(linker Teilbaum(p)) – Höhe(rechter Teilbaum(p)) | £ 1 " p Î T



Abbildung 3.1

In Abbildung 3.1 sind (a) und (c) Beispiele für AVL-Bäume, (b) ist dagegen kein AVL-Baum.

Die Motivation ist, entartete Binärbaume zu verhindern. AVL-Bäume können nie zu linearen Listen entarten. Folgende Überlegung zeigt, daß AVL-Bäume mit n Knoten eine Höhe von O(log₂n) haben.

 

2. 3.2 Zusamennhang zwischen Knotenzahl und Baumhöhe

a) Die maximale Höhe h für einen völlig ausgeglichenen Baum wird mit n = 2^h – 1 erreicht Daraus folgt für h unmittelbar log₂(n+1) –1 £ h.

b) Um die minimale Knotenzahl zu ermitteln, formuliert man folgenden induktiven Ansatz:

Ein AVL-Baum T₀ mit der Höhe 0 hat mindestens ein Blatt, ein AVL-Baum T₁ der Höhe 1 mindestens 2 Knoten. Um den Baum mit der Mindestknotenzahl T_h h>1 zu konstruieren, müssen wir die Wurzel mit zwei Teilbäumen versehen, die wiederum eine minimale Anzahl von Knoten haben. Natürlich muß ein Teilbaum die Höhe h-1 haben, der andere kann dann eine, um eins kleinere Höhe, nämlich h-2 haben, damit die AVL-Ausgeglichenheit weitherin gegeben ist.

Da dieses Prinzip sehr stark dem der Fibanocci-Zahlen gleicht, heißen sie Fibanocci-Bäume (siehe Abbildung 3.2).

Abbildung 3.2

Þ T_h = T_h-1 + 1 + T_h-2 (linker Teilbaum + Wurzel + rechter Teilbaum)

Þ (T_h +1) = (T_h-1 + 1) + (T_h-2 + 1)

Setze nun f_h º T_h + 1 mit f_h = f_h-1 + f_h-2 (Fibanocci-Zahlen).

Die minimale Knotenzahl n von Fibonacci-Bäumen beträgt damit f_h-1. Durch vollständige Induktion kann man beweisen, daß f_h-1 » 1.17 * 1.618^h - 1 ist [OW96].

Þ n + 1 ³ 1.17 * 1.618^h

Þ log₂(n+1) ³ log₂(1.17) + h * log₂(1.618)

Þ log₂(n+1) – log₂(1.17) ³ h * log₂(1.618)

Þ h £ (log₂(n+1) – log₂(1.17)) / log₂(1.618) £ 1.44 * log₂(n+1)

 

Aus a) und b) folgt: log₂(n+1) –1 £ h £ 1.44 * log₂(n+1) Þ AVL-Baum hat Höhe von O(log₂n).

 

 

 

Ein AVL-Baum ist dadurch charakterisiert, daß jeder Knoten p einen Balancefaktor bal(p) mitführt, der wie folgt definiert ist:

bal(p) = Höhe rechter Teilbaum(p) – Höhe linker Teilbaum(p)

Aus der Definition eines AVL-Baums folgt: bal(p) Î {-1, 0, 1}" p Î T.

Wie später noch zu sehen ist, muß man nicht die Höhen der Teilbäume jedes Knoten kennen.

 

3. 3.3 Einfügen in einen AVL-Baum

Um einen Schlüssel in einen AVL-Baum einzufügen, sucht man zunächst nach dem Schlüssel im Baum. Wenn der einzufügende Schlüssel noch nicht existiert endet die Suche in dem Blatt, an dem er angehängt wird. Nun kann es aber sein, daß dadurch keine AVL-Ausgeglichenheit mehr vorliegt.



Abbildung 3.3

Liegt ein Fall wie in Abbildung 3.3 vor, muß die Ausgeglichenheit wieder durch eine sogenannte Rotation oder Doppelrotation hergestellt werden.

 

Beim Einfügen eines neuen Knoten x können die folgenden Fälle unterschieden werden:

a) Der Elternknoten von x besitzt bereits einen Sohn (siehe Abbildung 3.4).

Abbildung 3.4

Der Schlüssel x wird links von Elternknoten p eingefügt (siehe Abbildung 3.4). In diesem Fall verschiebt sich die Balance des Elternknotens auf 0. Da sich die Höhe des Baumes durch die Operation nicht verändert hat, muß keine Operation durchgeführt werden. Analog verhält es sich, wenn Elternknoten p bereits einen linken Sohn hat und rechts von p der neue Schlüssel x angehängt wird.

b) Der Elternknoten war vorher ein Blatt (siehe Abbildung 3.5).



Abbildung 3.5

War vor dem Einfügen des Schlüssel x der Elternknoten p von x ein Blatt, so verschiebt sich die Balance des Teilbaumes mit Wurzel p in eine Richtung. Der Teilbaum mit Wurzel p ist in der Höhe um eins gewachsen. Da sich dadurch auch andere Balancefaktoren von Knoten verändern können, muß eine Prozdur upin(p) aufgerufen werden, die im folgenden erläutert wird.

c) Wenn upin(p) aufgerufen wird, so ist bal(p) Î {+1, -1} und die Höhe des Teilbaumes mit Wurzel p ist in der Höhe um eins gewachsen. Man muß darauf achten, daß vor jedem Aufruf von upin(p) diese Invariante gilt. Die Prozedur upin(p) bricht ab, falls p keinen Vater hat, d.h. wenn p die Wurzel des Baumes ist.

Man unterscheidet zwei Fälle, je nachdem ob p linker oder rechter Sohn seines Elternkotens j p ist.

Fall 1 [p ist linker Sohn seines Elternknotens j p]

Fall 1.1 [bal(j p) = +1]



Abbildung 3.6

Wie in Abbildung 3.6 ersichtlich ist, hat sich Gesamthöhe des Teilbaums von j p nicht verändert. Der rechte Teilbaum von j p war bisher um eins höher als der linke. Durch den neuen Knoten im linken Teilbaum ist dieser in der Höhen um eins gewachsen. Dadurch ist der Baum mit Wurzel j p nun ausbalanciert. Weitere Untersuchungen sind nicht mehr notwendig. Alle Balancefaktoren der Knoten, die sich noch auf dem Suchpfad zur Wurzel befinden, können sich nun nicht mehr verändern, weil alle Teilbaumhöhen dieser Knoten gleich geblieben sind.

Fall 1.2 [bal(j p) = 0]

Abbildung 3.7

In diesem Fall verschiebt sich die Balance des Elternknotens j p auf -1 (siehe Abbildung 3.7). Vor dem Einfügevorgang war der Teilbaum mit Wurzel j p ausgeglichen. Durch das Einfügen hat sich die linke Teilbaumhöhe um eins erhöht. Es gilt die Invariante, deshalb wird die Prozedur upin(j p) aufgerufen.

Fall 1.3 [bal(j p) = -1]

Abbildung 3.8

Die Invariante sagt, daß der Teilbaum mit der Wurzel p in der Höhe um eins gewachsen ist. Aus der Voraussetzung bal(j p) = -1 kann man in diesem Fall schließen, daß bereits vor dem Einfügen des neuen Schlüssels in den linken Teilbaum von j p mit Wurzel p dieser Teilbaum eine um eins größere Höhe hatte als der rechte Teilbaum von j p. Da der Teilbaum mit der Wurzel p in der Höhe um eins gewachsen ist, ist die AVL-Ausgeglichenheit bei j p verletzt (siehe Abbildung 3.8). Wir müssen also umstrukturieren und unterscheiden dazu zwei Fälle, je nachdem ob bal(p) = +1 oder bal(j p) = -1 ist. Wegen der Invariante ist bal(p) = 0 nicht möglich.

Fall 1.3.1 [bal(p)=-1]



Abbildung 3.9

Man beachte: Nach Voraussetzung ist die Höhe des Teilbaum p um eins gewachsen und der linke Teilbaum von p um eins höher als der rechte. Eine Rotation nach rechts bringt den Baum bei j p wieder in die Balance (siehe Abbildung 3.10). Es ist keine weitere Umstrukturierung nötig, weil der durch die Rotation entstehende Teilbaum mit Wurzel j p in der Höhe nicht mehr gewachsen ist. An der Höhe der Teilbäume 1 bis 3 kann man erkennen, daß der entstandene Teilbaum nach der Umstrukturierung wieder ausgeglichen ist.

 

 

 

 

 

Fall 1.3.2 [bal(p) = +1]



Abbildung 3.10

Wie in Abbildung 3.11 ersichtlich ist, sind die einzig möglichen Höhenkombinationen für die Teilbäume 2 und 3 (h-1, h-2) und (h-2, h-1). Sie können nicht die gleiche Höhe haben. Denn auf Grund der Invariante ist der Teilbaum mit Wurzel p in der Höhe um 1 gewachsen und wegen Annahme von Fall 1.3.2 ist der rechte Teilbaum von p um 1 höher als sein linker. Eine Doppelrotation nach rechts, d.h. zunächst eine Rotation nach links bei p und dann eine Rotation nach rechts bei j p, stellt die AVL-Ausgeglichenheit bei j p wieder her. Eine weitere Umstrukturierung ist nicht nötig, da der Teilbaum mit Wurzel j p in der Höhe nicht gewachsen ist.

 

Fall 2 [p ist rechter Sohn seines Elternknotens j p]

In diesem Fall geht man völlig analog vor und gleicht den Baum, wenn nötig, durch eine Rotation nach links bzw. eine Doppelrotation rechts-links bei j p wieder aus.

 

Beim Verfahren Einfügen kann im worst-case für das sukzessives Zurückgehen auf dem Suchpfad von der Einfügestelle zur Wurzel der Besuch aller Knoten erforderlich sein. Daraus folgt, daß O(log₂n) Schritte, wegen logarithmischer Höhe des AVL-Baums. Dabei wird noch höchstens ein weiterer Schritt für eine Rotation oder Doppelrotation ausgeführt. Damit ist klar, daß das Einfügen eines neuen Schlüssels in einen AVL-Baum mit n Schlüsseln in O(log₂n) Schritten ausführbar ist.

 

4. 3.4 Löschen eines Schlüssels aus einem AVL-Baum

Um einen Schlüssel aus einen AVL-Baum zu entfernen, sucht man zunächst nach dem Schlüssel im Baum. Wenn dieser Schlüssel nicht existiert, ist das Löschen bereits beendet. Andernfalls wird der Schlüssel wie in einem Suchbaum entfernt. Nun kann es aber sein, daß anschließend keine AVL-Ausgeglichenheit mehr gegeben ist.

Beim Löschen eines Kotens können folgende Falle unterschieden werden:

Fall 1: Der zu entfernende Schlüssel ist der Schlüssel eines Knotens, dessen beide Söhne Blätter sind. Dann entfernt man den Knoten und ersetzt ihn durch ein Blatt. Falls der Baum nunmehr nicht der leere Baum geworden ist, muß für den Elternknoten p des neuen Blattes mindestens der Balancefaktor geändert werden. Falls die Balance auf bal(p) = 0 geändert werden muß, ist der Teilbaum mit Wurzel p auch in der Höhe um eins gefallen. Damit können sich auch für alle Knoten auf dem Suchpfad nach p die Balancefaktoren und die Höhen der Teilbäume verändert haben. Wir rufen daher eine Prozedur output(p) auf, die die AVL-Ausgeglichenheit wiederherstellt.

Fall 2: Der zu entfernende Schlüssel ist der Schlüssel eines Knotens p, der nur einen inneren Knoten q als Sohn hat. Dann müssen beide Söhne von q Blätter sein. Man ersetzt also den Schlüssel von p durch den Schlüssel von q und q durch ein Blatt. Damit ist nunmehr p ein Knoten mit pal(p) = 0 und die Höhe des Teilbaums mit der Wurzel p um eins gesunken. Auch in diesem Fall ruft man output(p) auf, um die AVL-Ausgeglichenheit wiederherzustellen.

Fall 3: Liegt der Fall vor, daß der zu entfernende Knoten p zwei Söhne hat, geht man wie bei natürlichen Suchbäumen vor und ersetzt den Schlüssel p durch den Schlüssel des symmetrischen Nachfolgers (oder Vorgängers), d.h. man sucht im linken (rechten) Teilbaum mit Wurzel p das größtes Element s_max (kleinstes Element s_min). Vertausche die Schlüssel p und s_max (s_min). Der Schlüssel p muß dann ein Knoten sein, dessen Schlüssel wie in Fall 1 und 2 beschrieben entfernt wird.

In jedem Fall hat man das Löschen auf die Ausführung der Prozedur output(p) für einen Knoten p mit bal(p) = 0 reduziert, dessen Teilbaum in der Höhe um eins gesunken ist.

Die Prozedur output(p) wird längs des Suchpfades rekursiv aufgerufen. Sie adjustiert die Höhenbalancen und führt gegebenfalls Rotationen oder Doppelrotationen durch. Wenn output(p) aufgerufen wird, gilt bal(p) = 0 und der Teilbaum it Wurzel p ist in der Höhe um eins gefallen. Man muß darauf achten, daß vor jedem Aufruf diese Invariante gilt. Man unterscheidet wieder zwei Fälle, je nachdem ob p linker oder rechter Sohn eines Elternknotens j p ist.

Fall 1 [p ist linker Sohn seines Elternknotens j p]

Fall 1.1 [bal(j p) = -1 ]



Abbildung 3.11

Die Höhe des Teilbaums mit der Wurzel j p hat sich um 1 verringert (siehe Abbildung 3.12). Damit können sich für alle Knoten auf dem Suchpfad nach die Balancefaktoren und die Höhen der Teilbäume verändert haben. Infolgedessen ruft output(j p) auf.

 

Fall 1.2 [bal(j p) = 0]

Abbildung 3.12

Der linke Teilbaum von Knoten j p hat sich in der Höhe um 1 verringert (siehe Abbildung 3.13). Die Höhe des Teilbaums mit Wurzel j p bleibt aber unverändert. Damit sind keine weitere Umtstrukturierungen notwendig.

Fall 1.3: [bal(j p) = +1]



Abbildung 3.13

Der rechte Teilbaum von j p mit Wurzel q ist höher als der linke mit Wurzel p, der darüber hinaus noch in der Höhe um eins gefallen ist (siehe Abbildung 3.14). Wir machen eine Fallunterscheidung nach dem Balancefaktor von q.

Fall 1.3.1 [bal(q) = 0]

Abbildung 3.14

Durch Rotation nach links kann der Baum wieder ausgeglichen werden (siehe Abbildung 3.15). Zwar ist der linke Teilbaum von w nun um eins höher als der rechte, allerdings hat sich dadurch die Teilbaumhöhe nicht verändert. Alle Balancefaktoren der Knoten, die sich noch auf dem Suchpfad zur Wurzel befinden, können sich nun nicht mehr verändern, weil alle Teilbaumhöhen dieser Knoten gleich geblieben sind.

 

Fall 1.3.2 [bal(q) = +1]



Abbildung 3.15

Es muß eine Rotation nach links durchgeführt werden, wie in Abbildung 3.16 dargestellt ist, um die AVL-Ausgeglichenheit wieder herzustellen. Nach der Voraussetzung hat der linke Teilbaum von q die Höhe h und ist damit um eins kleiner als der rechte. Durch die Rotation hat nun Teilbaum v einen linken und rechten Teilbaum mit Höhe h. Der Teilbaum mit Wurzel r besteht aus Teilbäumen mit den Höhen h+1 und ist damit auch ausgeglichen. Es gilt die Invariante bal(r) = 0, d.h. der linke Teilbaum hat sich in der Höhe um eins veringert. Infolgedessen wird die Prozedur output(r) aufgerufen.

Fall 1.3.3 [bal(q) = -1]



Abbildung 3.16

Weil der Teilbaum mit Wurzel p in der Höhe um 1 gefallen ist und der rechte Teilbaum von j p vor dem Entfernen eines Schlüssels aus dem Teilbaum mit Wurzel p um 1 höher war als der linke, folgt, daß der Teilbaum Wurzel q die Höhe h+2 haben muß. Wegen bal(q) = -1 hat der linke Teilbaum von q mit Wurzel z die Höhe h+1 und der rechte die Höhe h. Die Teilbäume von z können entweder beide Höhe h oder höchstens einer von ihnen die Höhe h-1 haben. In jedem Fall gleicht die angegebene Umstrukturierung (siehe Abbildung 3.17) den Baum wieder aus. Dabei hängen die Balancefaktoren der Knoten v und w vom Balancefaktor z ab. Auf jeden Fall hat der Teilbaum mit Wurzel r den Balancefaktor 0 und seine Höhe ist um eins gefallen. Es gilt also die Invariante für den Aufruf von output(r).

Fall 2 [p ist rechter Sohn seines Elternknotens j p]

Fall 2 ist völlig symmetrisch zum Fall 1 und wird daher nicht näher behandelt.

 

Ein wesentlicher Unterschied zwischen Einfügen und Löschen darf nicht übersehen werden. Während das Einfügen eines Schlüssels höchstens eine Rotation (von zwei oder drei Knoten) erfordert, kann das Löschen eine Rotation für jeden Knoten entlang des Suchpfads verursachen. Man betrachte z.B. das Löschen des Knotens mit größtem Schlüssel in einem Fibonacci-Baum. Da jedoch der Aufwand zum Ausführen einer einzelnen Rotation oder Doppelrotation konstant ist, und die Höhe h von AVL-Bäumen mit n Schlüsseln durch 1.44log₂n beschränkt ist, folgt unmittelbar: Das Entfernen ist in O(log₂n) Schritten möglich.

 

Die drei Operationen Suchen, Einfügen und Löschen sind somit im worst case in O(log₂n) Schritten ausführbar. Damit sind AVL-Bäume also eine worst-case-effiziente Implementation im Gegensatz zu natürlichen Binärbäumen, die im average-case zwar genauso effizient sind, im worst case aber W (n) Schritte zum Ausführen der drei Grundoperationen benötigen.

 

 

 

 

 

 

 

1. Benutzerführung für das Programm

 

Da es sich bei dem Programm um eine interaktive AVL-Baum-Animation handelt, müssen dementsprechende Steuerungselemente vorhanden sein. In der Menüleiste werden Optionen angeboten, die das Programm allgemein betreffen. Die Baumoperationen Einfügen und Löschen werden im Panel Baumoperationen, rechts oben im Hauptfenster, abgehandelt. Damit die Animation besser verfolgbar ist, befindet sich unter dem Animationsfenster ein Steuerungspanel, mit dem der Animationsablauf besser verfolgbar ist. Zudem gibt es noch zwei Bedienungsvereinfachungen, die im Animationsfenster anwenbar sind und im Folgenden noch erläutert werden.

 

1. 4.1 Menüleiste

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Abbildung 4.1: Menüleiste

 

Mit dem Menü Bearbeiten sind folgende Optionen gegeben:

· Ungeschehen

Die letzte Baumoperation (Löschen oder Einfügen), die durchgeführt wurde, kann rückgängig gemacht werden. Alle Aktionen des aktuellen AVL-Baums werden gespeichert. So ist es auch möglich, alle durchgeführten Ereignisse ungeschehen zu machen. Diese Option ist nur wählbar, wenn ein Baum im Animationsfenster vorhanden ist.

· Geschwindigkeit

Da das Programm auf verschiedenen Plattformen funktioniert, läuft es zwangsläufig auf Computern mit stark unterschiedlicher Performance ab. Aus diesem Grund wurde diese Option eingefügt. Dadurch ist gewährleistet, daß die Animation einerseits nicht ruckartig und andererseits viel zu schnell abläuft. Bei einer Animationsbewegung wird zwischen jeder Bewegung eine Pause gemacht, in der das Programm ruht. Nach Wahl dieser Option wird ein Fenster geöffnet, in welchem diese Pause reguliert werden kann. Je kürzer die Pause gewählt wird, desto schneller läuft die Animation.

 

· AVL-Baum

w Demo starten

Dem Anwender wird die Animation vorgeführt. Dabei werden automatisch vom Programm in einen AVL-Baum bestimmte Schlüssel eingefügt und gelöscht. Die Schlüssel wurden so gewählt, daß interessante Fälle dem Anwender veranschaulicht werden können. Im Eingabefenster wird dabei angegeben, welche Zahl im Baum eingefügt bzw. gelöscht wird. Die Simulation kann während des Ablaufs nicht unterbrochen werden.

w Neu

Der aktuelle AVL-Baum im Animationsfenster wird gelöscht und ein leerer AVL-Baum neu angelegt. Danach ist das Animationsfenster leer. Diese Option ist endgültig, kann also nicht mehr ungeschehen gemacht werden.

 

Im Menü Hilfe werden, wie im diesem Abschnitt, alle Menü- und Steuerungsoptionen erläutert. Nach Wahl einer der oben genannten Optionen, wird das Hilfe-Fenster geöffnet. Dieses Fenster ist in drei horizontale Panel (Auswahl, Infofenster und Button) eingeteilt. Im Panel Auswahl steht die ausgewählte Menü- oder Steuerungsoption, welche im Infofenster erklärt wird. Beim Aufruf der Option Hilfe, werden alle Erläuterungen im Infofenster angezeigt.

Im Panel Auswahl können auch alle Hilfe-Optionen ausgewählt werden.

Das Menü Fenster enthält nur die Option Schliessen, mit der das Hauptfenster geschlossen wird. Bei allen Fenstern, die vom Programm geöffnet werden, stehen selbstverständlich die gewohnten Bedienungstechniken für Fenster, wie z.B. vergrößern, zu Verfügung.

 

2. 4.2 Baumoperationen

Im Hauptfenster befindet sich das Panel Baumoperationen. Es gibt dem Anwender die Kontrolle über den AVL-Baum. Die Operationen Schlüssel in einen AVL-Baum einfügen und löschen können hier durchgeführt werden. Dadurch ist der Anwender in der Lage, seinen eigenen AVL-Baum nach belieben aufzubauen.

Der Wertebereich der Schlüssel, die eingefügt werden können, ist beschränkt. Natürliche Zahlen zwischen 0 und 999 können sich im Binärbaum befinden. Gelöscht werden können nur solche Zahlen, die sich im aktuellen Binärbaum befinden.

Bevor eine Baumoperation durchgeführt werden kann, muß im Textfeld eine Zahl angegeben werden. Dies kann durch Benutzung des Ziffernblocks über dem Textfeld mit der Maus geschehen.

Die Eingabe kann auch über die Tastatur erfolgen. Anschließend muß diejenige Operation gewählt werden, die erfolgen soll. Wieder kann sie auf zweierlei Weise geschehen. Zum einen kann durch Anklicken der Buttons ‘Schluessel einfuegen’ und ‘Schluessel loeschen’ die gewünschte Aktion gestartet werden, zum anderen durch Drücken der Tasten ‘Enter’ (Þ Einfügen) und ‘Entf’ (Þ Löschen). Es gibt noch eine dritte Möglichkeit einen Schlüssel aus einem Binärbaum zu entfernen (siehe Bedienungsvereinfachungen).

Editieren ist im Textfeld nicht möglich. Dafür besteht die Möglichkeit, durch Aktivieren des Buttons ‘Clear’, das Textfeld nach einer Falscheingabe zu löschen

Alle Eingaben werden überprüft. Wird versucht, ein Element in den AVL-Baum einzugfügen, welches bereits im Baum existiert, wird dies ignoriert. Zusätzlich wird im Infofenster des Hauptfensters eine entsprechende Meldung ausgegeben. Analoges geschieht beim Versuch, einen Schlüssel aus dem Baum zu löschen, der sich nicht im AVL-Baum befindet.

 

3. 4.3 Steuerungspanel

Dieses Panel befindet sich unter dem Animationsfenster des Hauptfensters und umfaßt die Buttons ‘Stop‘, ‘Run‘ und ‘Next Step‘.

Besonderes Merkmal jeder Animation bzw. Simulation ist es, einen Sachverhalt zu visualisieren.. Nachteil ist dabei oft, daß keine Möglichkeit besteht, Einfluß auf den Ablauf zu nehmen, z.B. die Animation zu stoppen. Dem galt es entgegenzuwirken. Die Motivation war dabei hauptsächlich, dem Anwender ein Instrument in die Hand zu geben, um interessante Stellen der Animation, z.B. Rechts/Linksrotation, genau verfolgen zu können. So ist ein besserer Lerneffekt gegeben.

Beim Start einer Animation sind immer die Buttons ‘Stop‘ und ‘Next Step‘ aktiv und ‘Run‘ inaktiv. Dieser Zustand (Run) der Animation bedeutet, daß sukzessive Grafiken im Animationfenster aufgebaut werden. So entsteht der Eindruck einer Bewegung.

Wird ‘Stop‘ oder ‘Next Step‘ angeklickt, so hat dies auf die Animation die gleiche Wirkung. Die Animation wird angehalten und ruht, d.h. es werden keine weiteren Grafiken im Animationsfenster aufgebaut. Die letzte Grafik, die im Animationsfenster vor dem Stop aufgebaut war, ist sichtbar.

Nun sind die Buttons ‘Run‘ und ‘Next Step‘ aktiv und ‘Stop‘ inaktiv. Dies ist der zweite mögliche Zustand eines Animationsablaufs (Sleep).

‘Run‘ bewirkt nun, daß die Animation wieder in den Zustand Run zurückkehrt und die Animation weiterläuft. Wird dagegen ‘Next Step‘ angeglickt, wird die nächste Grafik der Bewegung im Animationsfenster aufgebaut und die Animation verweilt wieder in dem Zustand Sleep.

So kann jeder Schritt der Animation exakt verfolgt werden. Dies ist deshalb so wichtig, weil neben der Bewegung im Animationfenster gleichzeitig ausführliche Erläuterungen im Infofenster angegeben werden, welche beschreiben, was im Animationsfenster geschieht. So sind alle Aktionen für den Benutzer leicht nachvollziehbar.

 

4. 4.4 Bedienungsvereinfachungen

Es gibt noch zwei weitere Bedienungsmöglichkeiten, um die Anwendung zu vereinfachen.

Immer wenn sich der Mauszeiger im Animationsfenster über einen Knoten im AVL-Baum befindet, wird dieser durch die Farbe Blau hervorgehoben. Dies zeigt an, daß folgende zwei Optionen ausgeführt werden können.

Es ist oft für den Benutzer von Interesse zu wissen, welche Aktionen durchgeführt werden, wenn ein neuer Knoten an einer bestimmten Stelle des Baumes neu eingefügt wird. Besteht dieser Wunsch kann dies zwar durch "Nachrechnen" herausgefunden werden. Einfacher geschieht dies jedoch durch einfaches Anklicken des Knoten (kein innerer Knoten), an dem das neue Blatt angehängt werden soll. Im Infofenster werden daraufhin potentielle Kandidaten angezeigt, die dort im Falle eines Einfügens hinwandern und links oder rechts angehängt werden.

Nicht immer kann diese Option wahrgenommen werden, weil der Wertebereich auf die natürlichen Zahlen zwischen 0 und 999 begrenzt ist, so kann z. B. kein neues Blatt links vom Knoten mit Schlüssel 0 eingefügt werden.

Vereinfacht wurde auch der Vorgang Löschen eines Knotens aus dem Binärbaum. Dem Benutzer wird die Eingabe des Schlüssels abgenommen. Wenn der gewünschte Knoten mit Doppelklick markiert wird, erscheint im Infofenster die Warnung: "Loesche Schluessel x. Bestätigung mit <Schluessel loeschen>." Wird die Meldung mit entsprechendem Button bestätigt, wird der Löschvorgang gestartet. Andernfalls kann der Vorgang durch Anklicken von ‘Clear‘ abgebrochen werden.

 

 

 

 

 

1. Interner Programmaufbau

 

Nach dem klassischen ‘Wasserfallmodell‘ von Boehm [KS96] wird der Prozeß der Softwareentwicklung in die Phasen Analyse, Design, Implementierung, Test und Wartung unterteilt. Ziel der Analyse ist es, ein vollständiges, konsistentes und logisches Ist-Modell des für die Softwareentwicklung relevanten Realweltausschnittes zu erstellen. Zu diesem Zweck existieren in der Literatur diverse Modelle, die unabhängig von der später verwendeten Programmiersprache Notationen zur Verfügung stellen. Bei dieser Studienarbeit wurde die objektorientierte Methode von Coad und Yourdon [CY92] gewählt, um Analyse und Design durchzuführen. Das Design ist dabei die Erweiterung der Analyse um lösungsspezifische Komponenten und ist nicht mehr von der Programmiersprache unabhängig. In der Implementierungsphase werden die Ergebnisse aus Analyse und Design in die Konstrukte der verwendeten Programmiersprache umgesetzt. Als Test wird die Überprüfung der Korrektheit und Funktionalität des Programms bezeichnet. Die Wartung steht für alle Änderungen am Programm, die nach Fertigstellung notwendig werden.

 

1. 5.1 Analyse und Design

 

 

1. Ausblick