% 6. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=16,1cm
\textheight=25,7cm
\hoffset = -17mm
\voffset = -25mm

\setcounter{page}{7}
\begin{document}

\begin{centering}
{\large \bf Algorithmen
und Programmieren III, WS 1999/2000 ---
 6.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Dienstag, 14. Dezember 1999

\par \medskip
\end{centering}
\hrule
\medskip

\begin{enumerate}
\setcounter{enumi}{30}

\itemsep=0,45\itemsep
\item (0 Punkte)
\emph{Rot-Schwarz-B"aume} sind bin"are B"aume mit folgenden
Eigenschaften:%
\footnote{Es gibt verschiedene andere Versionen von Rot-Schwarz-B"aumen,
bei denen zum Beispiel auch die inneren Knoten Werte enthalten
(im Gegensatz zu 2-3-B"aumen).

%\footnote{%
Eine Implementierung von Rot-Schwarz-B"aumen kann man zum Beispiel
in der Klasse \texttt{TreeMap} im Paket {\tt java.util} finden,
siehe
{\tt http://www.inf.fu-berlin.de/\char`\~rote/Lere/alp3/TreeMap.java}.}
\begin{enumerate}
\itemsep=0pt
\item Jeder innere Knoten hat zwei Kinder.
\item Jeder Knoten ist entweder als \emph{rot} oder als
\emph{schwarz} gekennzeichnet.
\item Die Wurzel und alle Bl"atter sind schwarz.
\item Die Kinder eines roten Knotens sind schwarz.
\item Ein schwarzer Knoten kann h"ochstens ein rotes Kind haben.
\item Alle Wege von der Wurzel zu den Bl"attern enthalten
gleich viele schwarzen Knoten.
\end{enumerate}
Zeichnen Sie Rot-Schwarz-B"aume mit 5, 7 und 12 Bl"attern.
Zeigen Sie, dass man aus jedem Rot-Schwarz-Baum einen 2-3-Baum
machen kann, und umgekehrt\rlap.%

\item (5 Punkte) Erweitern Sie die Algorithmen zum Suchen, Einf"ugen und
L"oschen in bin"aren Suchb"aumen so, dass man jederzeit
auch das $i$-gr"o"ste Element finden kann, und dass alle
Operationen Zeit proportional zur H"ohe des Baumes ben"otigen.

\item  (0 Punkte)
Gegeben sind $n$ G"uter (Sand, Gold, Salz, usw.). Von jedem Gut
ist eine gewisse Menge $x_i$ vorhanden; weiters ist der
Wert $w_i$ (pro Gewichtseinheit) bekannt.
Welche G"uter soll man in welcher Menge ausw"ahlen,
wenn man insgesamt nur ein Gesamtgewicht von $b$ Einheiten
nehmen kann und den gr"o"sten Wert erzielen m"ochte?
(Welche G"uter soll man zum Beispiel bei einem Feuer in Sicherheit
bringen?)
\\
Wie w"urden Sie dieses Problem (unter Zuhilfenahme
bin"arer Suchb"aume) l"osen, wenn man f"ur verschiedene
Werte von $b$ jeweils schnell eine Antwort bekommen m"ochte,
und wenn sich die Menge der G"uter m"oglicherweise "andert?

\item (5 Punkte)
Schreiben Sie ein Programm, das einen (nicht zu gro"sen) bin"aren Baum
zweidimensional
in "ubersichtlicher und sch"on lesbarer Form ausdruckt.
Zwei Vorschl"age:
$$
\vcenter{\hsize=0,3\hsize \tt \parskip0pt 
\advance\baselineskip -2,3pt \obeylines\obeyspaces
\      20  ----
\         23  -
\            30
\   40  -------
\      45
 50  ----------
\      64  -
\         65
\   70  ----}
\qquad 
\vcenter{\hsize=0,4\hsize 
\catcode`/=\active\def/{\lower0,3ex\hbox{\char`\/}}
\catcode`+=\active\def+{\rlap{-}\raise0,65ex\hbox{\char"0B}}
\def~{\lower0,3ex\hbox{\char`\\}}
\tt \parskip0pt\advance\baselineskip -2pt \obeylines\obeyspaces
\               50
\           /----+---------~
\         40                70
\  /-------+~           /---+
 20          45       64
\ +~                 /-+~
\   23             60    65
\   +-~
\      30}
$$  

\item (5 Punkte)
Implementieren Sie f"ur bin"are Suchb"aume eine Methode,
die einen \emph{Iterator} mit den Methoden
\texttt{next()} und
\texttt{hasNext()} erzeugt.
(Sie d"urfen annehmen, dass die Knoten Mutterzeiger wie in
Aufgabe 26 haben.)
Verwenden Sie dabei \emph{nicht} das Verfahren aus der Vorlesung,
das eine Kopie der Daten in einem linearen Feld anlegt,
oder eine andere Methode, die mehr als konstant viel
zus"atzlichen Speicher ben"otigt.

\item 
\begin{enumerate}
\item (0 Punkte)
In einem bin"aren Suchbaum, der ganze Zahlen speichert, sollen
die Zahlen~$x$, die im Intervall $\{\,x\mid a\le x\le b\,\}$ liegen,
ausgegeben werden. Schreiben Sie ein Programm, das diese Aufgabe in
$O(h+k)$ Zeit erledigt, wobei $h$ die H"ohe des Baumes und $k$~die L"ange
der Ausgabe ist.
\item (0 Punkte)
Wie kann man die in den Knoten des Baumes gespeicherte Informationen
so erweitern, dass man die \emph{Summe} der
Zahlen $x$ im Intervall $\{\,x\mid a\le x\le b\,\}$
in $O(h)$ Zeit bestimmen kann (und trotzdem noch in $O(h)$ Zeit
einf"ugen und entfernen kann)?
\eject
\end{enumerate}
\end{enumerate}
\end{document}

