\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{ngerman}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 12. Dezember 2013 vor der Vorlesung in 
                          die jeweiligen Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen und Programmierung III} \\[0.5ex]
\normalsize
Wolfgang Mulzer \hfill WiSe 2013/14

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Bin\"are Suchb\"aume}{10 Punkte}

\begin{enumerate}
  \item F\"ugen Sie die Schl\"ussel A, L, P, D, R, E, I, X, Y, Z in dieser
       Reihenfolge in einen anfangs leeren bin\"aren Suchbaum ein. 
       L\"oschen Sie sodann die Schl\"ussel
       Z, A, L. Zeichnen Sie
       den Baum nach jedem Einf\"uge- und L\"oschvorgang.
  \item Seien $T_1$ und $T_2$ zwei bin\"are Suchb\"aume, in
    denen jeweils die gleiche Menge $S$ von Eintr\"agen gespeichert
    ist, mit $|S|=n$. Zeigen Sie: Es gibt eine Folge von h\"ochstens
    $2n$ einfachen Rotationen, die $T_1$ nach $T_2$ \"uberf\"uhrt.
\end{enumerate} 

\AUFGABE{AVL-B\"aume}{10 Punkte}
  
  \begin{enumerate}
    \item F\"ugen Sie die Schl\"ussel A, L, P, D, R, E, I, F, O, M, N in dieser
       Reihenfolge in einen anfangs leeren AVL-Baum ein. 
       L\"oschen Sie sodann die Schl\"ussel
       A, M, R. Zeichnen Sie den Baum nach jedem Einf\"uge- und
       L\"oschvorgang, und zeigen Sie die Rotationen, welche durchgef\"uhrt
       werden. Annotieren Sie dabei auch die Knoten mit
       ihrer jeweiligen H\"ohe.
     \item
        Beweisen Sie: Beim Einf\"ugen in einen AVL-Baum wird h\"ochstens
	    eine (Einfach- oder Doppel-)Rotation ausgef\"uhrt.
	    Gilt das auch beim L\"oschen (Begr\"undung)? 
  \end{enumerate}


\AUFGABE{Treaps/Balden/Baufen}{10 Punkte}

Ein Treap/eine Balde/ein Baufen ist eine Kreuzung aus einem
\textbf{Tr}ee (bzw. \textbf{B}aum) und einem H\textbf{eap}
(bzw. einer H\textbf{alde}/einem H\textbf{aufen}). Die Knoten
eines Treaps $T$ speichern (neben den Werten) zwei Felder: einen
\emph{Schl\"ussel} und eine \emph{Priorit\"at}. Bez\"uglich der Schl\"ussel
hat $T$ die bin\"are Suchbaumeigenschaft, bez\"uglich der
Priorit\"aten die Min-Heap-Eigenschaft. Das hei\ss{}t,
f\"ur jeden inneren Knoten $v$ von $T$ gilt:
(i) alle Knoten im linken Unterbaum von $v$ haben Schl\"ussel 
kleiner als der Schl\"ussel von $v$;
(ii) alle Knoten im rechten Unterbaum von $v$ haben Schl\"ussel gr\"o\ss{}er
als der Schl\"ussel von $v$; 
(iii) die Priorit\"aten der Kinder von $v$ sind gr\"o\ss{}er als die
Priorit\"at von $v$.
\begin{enumerate}
  \item Zeichnen Sie einen Treap f\"ur die folgende Menge von
        Schl\"ussel-Priorit\"ats-Paaren: 
	(E, 23), (K, 65), (H, 5), (B, 7), (I, 73), (A, 10), (G, 4).
  \item Zeigen Sie: Wenn in einer Menge von Schl\"ussel-Priorit\"ats-Paaren 
       alle Schl\"ussel und Priorit\"aten paarweise verschieden sind, so 
       gibt es genau einen Treap f\"ur diese Menge.
  \item  Geben Sie Pseudocode f\"ur Algorithmen zum Einf\"ugen und
      L\"oschen in einen Treap.

      \emph{Hinweis:} F\"uhren Sie zun\"achst die Operation genauso durch
         wie in einem herk\"ommlichen bin\"aren Suchbaum. Verwenden
	 Sie dann Einfachrotationen, um die Heapeigenschaft
	 wieder herzustellen. Pseudocode f\"ur bin\"are Suchb\"aume finden
	 Sie auf der Veranstaltungsseite.
\end{enumerate}
\emph{Bemerkung:} Man kann zeigen, dass Treaps erwartete H\"ohe 
 $O(\log n)$ haben, wenn die Priorit\"aten zuf\"allig
 aus dem Intervall $(0,1)$ gew\"ahlt werden.

\end{description}
\end{document}
