WS 2002/2003                   Übung 12                          H. Schweppe
                                        

        Ausgabe: 17.1.12. 2002
        Abgabe:   28. 1. 2003  15.00

Aufgabe 12.1 (  6 P)
a) (3 P) Zeichnen Sie schrittweise den Rot-Schwarz-Baum, der bei Einfügen der Schlüssel 'A' bis 'K' in den anfangs leeren Baum entsteht.

b) (3 P) Machen Sie eine allgemeine Aussage dazu, was passiert, wenn man Rot-Schwarz-Bäume durch Einfügen von Schlüsseln in aufsteigender Reihenfolge erstellt. Geben Sie die Laufzeit für das Einfügen von n Schlüsseln in aufsteigender Reihenfolge an.

Aufgabe 12.2 (  6  P)
 Machen Sie sich für Teil a) mit Rot-Schwarz-Bäumen anhand von Animationen vertraut (z.B.    http://www.seanet.com/users/arsen/avltree.html oder  http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html). 
a) (3 P) Geben Sie die Anzahl strukturell verschiedener Rot-Schwarz-Bäume mit n=2, 3,...., 12 verschiedenen Schlüssel an.

b) (3 P) Entwerfen Sie einen Algorithmus, der in logarithmischer Zeit feststellt, ob es in einem Rot-Schwarz-Baum einen Schlüssel gibt, der zwischen den Schlüsseln x und y (Eingabeparameter) liegt: 
                interval :: Ord t -> RBTree  a -> a -> a -> Bool
        -- interval rb i j
        -- pre : i <= j
        -- result:True if( exists k, k element of rb  and i < k < j),
        --        False otherwise. 
Geben Sie eine Implementierung in Haskell an. (Code für den Rot-Schwarz-Baum hier). 

Aufgabe 12.3 (7  P)
a) (1 P) Geben Sie die Hash-Tabelle an, die sich durch Einfügen der Werte  E, A, S, Y, Q, U, E, S, T, I , O, N  in dieser Reihenfolge ergibt. Die Schlüssel sind als natürliche  Zahlen kodiert, und zwar A= 0, B = 1 usw. . Duplikate sind erlaubt.   Die Tabelle besitzt m=13 Elemente, h(x) = x mod 13. Im Fall von Kollisionen wird linear sondiert. 

b) (1 P) Wie a), aber Sondierung mit unabhängigen  Hash-Funktionen.  Die sekundäre Hash-Funktion sei  h'(x) = 1 + (x mod 11). 

c) (1 P) Welche Laufzeit hat das Einfügen eines Schlüssels in eine Hash-Tabelle bei Kollisionsbehandlung durch Verkettung  im schlechtesten Fall, wenn die Ketten sortiert gespeichert werden?

d) (2 P) Wie viele Sondierungen braucht man, um n-mal den gleichen Wert (oder: n gleiche Schlüssel)  in eine Hash-Tabelle bei Kollisionsauflösung mit  zwei unabhängigen Hash-Funktionen  einzufügen. 

e) (2 P) Zeigen Sie: Bei Kollisionsbehandlung mit zwei unabhängigen  Funktionen h(x) und h'(x) werden, falls m (die Tabellengröße) keine Primzahl ist, nicht notwendig alle leeren Tabellenelemente gefunden. 

Aufgabe 12.4  ( 11 + 6 P)
a) (3) Beweisen Sie: ((a*x mod m ) + b) mod m = (a*x + b) mod m; dabei sind a, b, x, m sind positive ganze Zahlen.

b) (4 P) Implementieren Sie eine Klasse class HashExperiment, deren Methode h Zeichenketten s durch Modulbildung in die Zahlen [0.. m-1] abbildet. Dabei ist m die Tabellengröße. Die Zeichenkette wird als Zahl zur  Basis a interpretiert. Z.B. ist   h("ava") = (97a^2 + 118*a + 97) % m. Die auf dem Typ String definierte Funktion charAt(int i) liefert das i-te Zeichen von s (Siehe Java Klassen-Dokumentation). Verwenden Sie zur Berechnung das Hornerschema. Da die Zeichenketten lang werden können, müssen Sie die in a) zu beweisende Eigenschaft nutzen. Ein einfaches Fragment für ein Rahmenprogramm finden Sie hier.

c) (4 P) Berechnen Sie die Hashwerte für die Zeilen der hier zu findenden Datei (mit 79 Zeilen), und zwar mit m=96, a= 128; m=97, a=128; m=96, a=127. Geben Sie die Hashwerte jeder Zeile aus, ferner die Kollisionsstatistik ("Wieviel Zeilen wurden auf i, 0 <= i < m abgebildet?"). Interpretieren Sie das Ergebnis.
Bemerkung: Es geht in c) nur um die Hash-Verschlüsselung von Zeichenketten, nicht um die Wirksamkeit von  Kollisionsauflösungsverfahren. Um die geht es hier.....:

d) (6 Zusatzpunkte) Untersuchen Sie experimentell für die offenen Adressierung die Verfahren lineare Sondierung, quadratische Sondierung und unabhängige Hash-Funktionen (Double hashing). Eine geeignete zweite Hashfunktion bzw. die Konstanten c1 und c2 für quadratisches Sondieren wählen Sie bitte selbst.  Vergleichen Sie die durchschnittliche Anzahl von Tests bei einer Suche mit den theoretischen Werten (lineares Sondieren, unabhängige Hash-Funktionen). Eine besonders gelungene experimentelle Untersuchung kann in der letzten Vorlesung am 13.2. vorgestellt werden.

Aufgabe 12.5  ( 2 P)
a) (2 P) Ist die Folge F = [4,7,10,9,16,12,8,13,11,20] die Felddarstellung eines binären (Min)-Heaps? Zeichnen Sie bitte den durch F angegebenen Heap. Stellen Sie gegebenenfalls die Heap-Eigenschaft her.
 

32 Punkte + 6 Sonderpunkte.