\documentclass[12pt, oneside]{article}

\usepackage{a4, latexsym}
\usepackage{fullpage}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{german}
\usepackage{nopageno}

\date{}

\begin{document}
\noindent
\textsl{Vorlesung Algorithmen, D.~Huson und R.~Rupp, Universit\"at T\"ubingen, WS07/08}

\bigskip


\begin{center}
\LARGE{Aufgabenblatt 9}
\end{center}

\medskip


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Implementierung eines Suchbaumes (6 P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Implementieren Sie einen bin"aren Suchbaum, genauso, wie in der Vorlesung diskutiert.
Benutzen Sie dazu bitte die Datei\\
{\tt http://www-ab.informatik.uni-tuebingen.de/teaching/ws07/algo/BinarySearchTree.java}.

Schreiben Sie die folgenden Methoden:
{\sf insert}, {\sf delete}, {\sf search}, {\sf getSuccessor}, {\sf getPredecessor},
{\sf getMinimum}, {\sf getMaximum} und {\sf print}.

In dem Baum sollen verschiedene Elemente mit demselben {\it key} vorkommen d"urfen.
Die Methoden {\sf search} und {\sf delete} sollen jeweils ein Element mit
dem gegebenen  {\it key} finden oder l"oschen.
Die Methode {\sf print} soll den aktuellen Baum m"oglichst "ubersichtlich ausdrucken.

Ein- und Ausgabe sind in der {\sf main} Methode bereits implementiert und es werden dort
die folgenden Kommandos unterst"utzt:
\begin{verbatim}
	Insert: insert <key>*
	Delete: delete <key>*
	Search: search <key>*
	Search for all occurrences: all <key>* (siehe Aufgabe 2)
	Successor: succ <key>*
	Predecessor: pred <key>*
	Minimum: min
	Maximum: max
	Print tree: print
	Quit: quit
\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, Alle Elemente finden  (2 P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Implementieren Sie zus"atzlich eine Methode {\sf searchAll},
die mit Hilfe der Methoden {\sf getSuccessor} und {\sf getPredecessor} rekursiv
{\em alle} Vorkommnisse eines Sch"ussels als Java Liste zur"uck gibt.

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, Beispiel (2 P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Zeigen Sie bitte an Hand eines Beispiels, dass die verschiedenen Funktionalit"aten Ihres Programmes korrekt zu funktionieren scheinen.

\bigskip
\bigskip

\noindent
Bitte senden Sie die L"osungen per Email an Daniel Huson mit Subject: {\tt Aufgabenblatt 9}.
\end{document}