Praktikum Algorithmische Anwendungen

Wintersemester 2003/04

Praktikum 2

 

Gruppe AI A1
M. Serhat Çinar 11030409 ai440
Michael Boiman 11027800 ai320
Mustafa Ekit 11027589 ai336

 

Index

  • Aufgabe 1: Implementierung des ADTDictionary mit einem RedBlack-Tree
  • Implementierung der Methoden Predecessor und Successor
  • Dateien
  • Aufgabe 2: Erläuterung des RedBlack Tree
  •  


    Aufgabe 1: Implementierung des ADTDictionary mit einem RedBlack-Tree     top

    Zuerst wurde eine Aufteilung der Aufgaben erstellt:
    Michael Boiman: Speichern / laden des Dictionaries, Dokumentation (Aufgabenteil 2)
    Mustafa Ekit: Implementierung der Methoden predecessor und successor, Dokumentation (Aufgabenteil 2)
    M. Serhat Cinar: Erstellung der GUI, Projektmanagement

      Als Grundlage diente die Klasse RedBlackTree.java aus der API &structure& von Duane A. Bailey, Avan S. Sandhaus.

     

    UML-Diagramme

     

    Das Dictionary



    Generiert von Eclipse 2.1.1 und EclipseUML

     

    Die GUI



    Generiert von Eclipse 2.1.1 und EclipseUML

     

    Implementierung der Methoden Predecessor und Successor

     

    Successor

    Der Wert von Successor(k) ist das Element mit dem kleinsten Schlüssel größer als k.

    Code

    Grafik

    Der Rückgabe- und Eingabetyp ist Comparable, damit der ADT nicht eingeschränkt wird.
    Da es ein Comparable ist, müssen wir es aus diesem einen RedBlackTree erzeugen, weil wir ja mittels left und right den Baum travesieren müssen (s. Zeile 2).
    Dazu müssen wir leider die Funktion locate benutzen, um an die richtige Position zu gelangen.

    Erster Fall

    Der Successor vom root ist gesucht.

    Grafik

    Wir wissen ja, dass der Successor der kleinste Schlüssel im rechten Teilbaum vom root ist. Also wird zuerst geprüft, ob der root ein rechtes Kind hat (s. Zeile 6). In dem Fall stimmt die Bedingung (Zeile 7-11).
    Zuerst gelangt man zum rechten Kind (s. Zeile 7).

    Grafik

    Jetzt wird mittels einer while Schleifes solange zum linken Kind bewegt, bis man zum letzten Knoten angekommen ist (s. Zeilen 8 und 9).

    Grafik

    Und dieser wird zurückgegeben (s. Zeile 11).

    Zweiter Fall

    Der Successor wird für einen Knoten aufgerufen, der kein rechtes Kind hat.

    Grafik

    Die Bedingung für rechtes Kind (Zeilen 7-11) trifft hier nicht zu und deshalb gelangt es jetzt in den else-Block (Zeile 14-25).

    Grafik

    Geht zum Vater (s. Zeile 15).

    Grafik

    Wenn das Kind das rechte Kind von seinem Vater war, wird er nochmals zum Vater gehen (s. Zeile 19).

    Dritter Fall

    Der Successor wird für den grössten Schlüssel aufgerufen.

    Grafik

    Man geht solange zum Vater bis der Vater ein linkes Kind von seinem Vater ist (s.Zeile 16).
    Da das nie vorkommen wird, gelangt man am Ende zur der Wurzel und null wird zurückgeben (s.Zeile 22).

     

    Predecessor

    Der Wert von Predecessor(k) ist das Element mit dem grössten Schlüssel kleiner als k.

    Code

    Grafik

    Der Rückgabe- und Eingabetyp ist Comparable, damit der ADT nicht eingeschränkt wird.
    Da es ein Comparable ist, müssen wir es aus diesem einen RedBlackTree erzeugen, weil wir ja mittels left und right den Baum travesieren müssen (s. Zeile 2).
    Dazu müssen wir leider die Funktion locate benutzen, um an die richtige Position zu gelangen.

    Erster Fall

    Der Predecessor vom root ist gesucht.

    Grafik

    Wir wissen ja, dass der Predecessor der grösste Schlüssel im linken Teilbaum vom root ist. Also wird zuerst geprüft, ob der root ein linkes Kind hat (s. Zeile 6). In dem Fall stimmt die Bedingung (Zeile 7-11).
    Zuerst gelangt man zum linken Kind (s. Zeile 7).

    Grafik

    Jetzt wird mittels einer while Schleifes solange zum rechten Kind bewegt, bis man zum letzten Knoten angekommen ist (s. Zeilen 8 und 9).

    Grafik

    Und dieser wird zurückgegeben (s. Zeile 11).

    Zweiter Fall

    Der Predecessor wird für einen Knoten aufgerufen, der kein linkes Kind hat.

    Grafik

    Die Bedingung für linkes Kind (Zeilen 7-11) trifft hier nicht zu und deshalb gelangt es jetzt in den else-Block (Zeile 14-25).

    Grafik

    Geht zum Vater (s. Zeile 15).
    Wäre das Kind das linke Kind von seinem Vater, dann hätten man nochmals zum Vater gehen müssen, aber es ist nicht hier der Fall.

    Dritter Fall

    Der Predecessor wird für den kleinsten Schlüssel aufgerufen.

    Grafik

    Man geht solange zum Vater bis der Vater ein rechtes Kind von seinem Vater ist (s.Zeile 16).
    Da das nie vorkommen wird, gelangt man am Ende zur der Wurzel und null wird zurückgeben (s.Zeile 22).

     

    Dateien

      Klassen, Quellcode und Javadoc
    Javadoc online

     


    Aufgabe 2: Erläuterung des RedBlack Tree     top

    Hier geht es weiter