% 5. Uebungsblatt ALP3 WS 2003/04
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage {ngerman}
\textwidth=16,1cm
\textheight=25cm
\hoffset = -17mm
\voffset = -30mm

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

\begin{centering}
{\large \bf Algorithmen und Programmierung 3, WS 2003/2004 ---
 6.~\"Ubungsblatt\par}
\bigskip
Abgabe bis Donnerstag, 11. Dezember 2003
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{35}

\item (7 Punkte)
Wir wollen eine Variante von $a$-$b$-Bäumen konstruieren, bei der
weniger Speicher verschwendet wird.
Es sei $b=100$. Wie groß kann man $a$ wählen, wenn man
\begin{itemize}
\item beim Entfernen bis zu \emph{zwei} Geschwisterknoten zum
  Ausborgen in Betracht zieht, und
\item beim Einfügen einen Geschwisterknoten zu Hilfe nimmt, falls
  dieser den Überlauf aufnehmen kann?
\end{itemize}


% \item (0 Punkte)
% Gegeben sei eine Funktion $f\colon
% \{0,\ldots,n-1\}\to\{0,\ldots,n-1\}$,
% die einen großen (aber endlichen) Bereich in sich selbst abbildet,
% zum Beispiel
% $$f(x) = x^3 + 2x^2 +7 \bmod 10^6.$$
% Wir betrachten die Folge $a_0=0$, $a_{i+1}=f(a_i)$.
% Da der Bereich endlich ist, muss die Folge Wiederholungen
% enthalten.
% Wie kann man in $O(n)$ Zeit mit \emph{konstantem Speicher} ein
% doppeltes Element finden?
% Wie kann man das kleinste $i$ und das kleinste $j$ finden, sodass
% $a_i=a_{i+j}$ ist?%
% \footnote{Diese Aufgabe dient nur zur Erbauung und hat mit dem
%   Stoff der Vorlesung nicht direkt etwas zu tun.
% Lösungshinweise finden Sie auf der Netzseite der Vorlesung.}

\item (9 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 den 2-3-B"aumen, wie sie in der Vorlesung besprochen wurden).

%\footnote{%
Eine Implementierung von Rot-Schwarz-B"aumen kann man % etwa %zum Beispiel
in der Klasse \texttt{TreeMap} im Paket {\tt java.util} finden,
siehe
{\tt
  http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/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.

\item (4 Punkte) Es sei $A_h$ die kleinstmögliche Anzahl von Blättern
  eines AVL-Baumes mit Höhe~$h$.  Beweisen Sie, dass die Zahlen $A_h$
%,  $h=1,2,\ldots$,
 die Fibonacci-Zahlen sind.

Was können Sie daraus für die kleinstmögliche Anzahl $n(h)$ von \emph{inneren Knoten}
  eines AVL-Baumes mit Höhe $h$ schließen?

  
\item (0 Punkte) Wir wollen die Algorithmen zum Suchen, Einf"ugen und L"oschen
  in einem bin"aren Suchbaum so erweitern, 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.

Man könnte das lösen, indem man zu jedem Knoten den \emph{Rang} speichert, das
heißt, die Position, die dieser Schlüssel in der sortierten Reihenfolge einnimmt.
Warum ist dies keine gute Idee?


\item (0 Punkte)
Schreiben Sie ein Programm, das einen (nicht zu gro"sen) bin"aren Baum
zweidimensional
in "ubersichtlicher und sch"on lesbarer Form ausdruckt.
Drei Vorschl"age\footnote
{Das dritte Beispiel ist als PostScript-Datei erstellt
worden,
siehe\\
  \texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/baum.eps}.
\\Ihr Programm kann sich an dieser Datei als Beispiel orientieren.}:

\noindent \hbox to \linewidth
{\hskip 0pt plus 0,5fil
$\vcenter{\tt \parskip0pt 
\setbox0=\hbox{ 50 \ ----------}
\hsize=\wd0
\advance\baselineskip -2,3pt \obeylines\obeyspaces
\      20  ----
\         23  -
\            30
\   40  -------
\      45
 50  ----------
\      64  -
\         65
\   70  ----}
\hfil
\vcenter{
\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
\setbox0=\hbox{\         40                70}\hsize=\wd0 %
\               50
\           /----+---------~
\         40                70
\  /-------+~           /---+
 20          45       64
\ +~                 /-+~
\   23             60    65
\   +-~
\      30}
\hfil
\vcenter{
\hbox{\includegraphics[height=7.5\baselineskip]{baum}}
}\hskip 0pt plus 0,5fil$}

\eject
\end{enumerate}
\end{document}
