NFII, WS 1997/98: Übungsblatt 9

Ausgegeben am: 27. Januar 1998
Abzugeben bis: 3. Februar 1998
Lösungen dazu

In diesem Aufgabenblatt geht es um die Erstellung und Benutzung eines binären Suchbaumes. Ein binärer Baum ist ein Baum, bei dem jeder Knoten zwei Nachfolger hat, einen linken und einen rechten. Die einzige Ausnahme bilden die äußersten Knoten, die Blätter heißen. Ein binärer Suchbaum wird daraus, wenn man die Knoten mit Schlüsselwerten assoziiert (z.B. Namen) und fordert, daß alle Knoten auf der linken Seite eines Knotes Schlüssel mit kleinerem Wert haben, alle Knoten auf der rechten Seite jedoch Schlüssel mit größerem Wert. Ein Beispiel für einen solchen Baum ist folgender:

Man sieht, die Schlüssel sind gleichzeitig die einzige Information, die an jedem Knoten gespeichert ist.

Aufgabe 1: Repräsentation eines binären Suchbaumes

Konstruieren Sie einen binären Suchbaum. Verwenden Sie ein dreistelliges Proädikat

node( key, left, right).

zur Repräsentation. Das Prädikat sagt aus, daß der Knoten den Schlüsselwert key hat. Der linke Teilbaum ist durch left, der rechte Teilbaum durch right repräsentiert. Der oben angegebene Baum sieht also so aus:

node( stefan, node( marion, node( gustav, nil, nil), 
                            node( ortrud, node( monika, nil, nil), 
                                          nil)),
              node( viktor, node( tamara, nil, nil),
                            node( vogon, nil, nil))).

nil bezeichnet dabei den leeren Baum.

Konstruieren Sie per Hand einen binären Suchbaum aus den Vornamen von sich selber, Ihren Eltern und Großeltern. Beginnen Sie mit einem beliebigen Namen und fügen Sie manuell Knoten hinzu.

Aufgabe 2: Traversierung eines binären Suchbaumes

Entwerfen Sie ein zweistelligen Prädikat no_of_nodes( Tree, Number), das gelingt, wenn Tree Number Knoten hat. der Baum in obiger Abbildung habe acht Knoten.

Aufgabe 3: Einfügen in einen binären Suchbaum

Entwerfen Sie ein dreistelliges Prädikat insert_name( OldTree, Name, NewTree), das gelingt, wenn aus dem alten Baum OldTree durch Einfügen eines Namens Name der neue Baum NewTree wird.

Aufgabe 4: Eigenschaften binärer Suchbäume

Die Komplexität des Suchens eines Knotens in einem binären Baum ist linear in der Anzahl der Knoten. Das heißt anschaulich, daß man doppelt so lange brauchen kann, wenn doppelt so viele Namen im Baum sind.

Diese Abschätzung ist die Worst-case-Komplexität. Wann tritt dieser Fall ein?

Kann man einen Suchbaum so konstruieren, daß die Komplexität besser wird?