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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{am 22. Dezember~2017 bis 10 Uhr 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}}
\newcommand{\N}{\mathbb{N}}

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


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

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\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{Gewichtsbalancierte B\"aume}{10 Punkte}

Sei $T$ ein bin\"arer Suchbaum mit $n$ Knoten. 
Wir definieren eine \emph{Gewichtsfunktion} auf
$T$. Es ist $w(\perp) = 1$. Sei $v$ ein Knoten von
$T$, mit linkem Kind $v_l$ und rechtem Kind $v_r$
(es ist $v_l = \perp$ oder $v_r = \perp$, falls das
jeweilige Kind nicht vorhanden ist).
Dann ist $w(v) = 1 + w(v_l) + w(v_r)$.

Wir nennen $T$ \emph{gewichtsbalanciert}, 
falls f\"ur alle Knoten $v$ in $T$ gilt:
Seien $v_l$ und $v_r$ das linke und das rechte Kind von
$v$. Dann ist $w(v_l) \geq w(v)/10$ und 
$w(v_r) \geq w(v)/10$. 

Zeigen Sie: Wenn $T$ gewichtsbalanciert ist, dann hat 
$T$ H\"ohe $O(\log n)$.

\emph{Hinweis}: Verwenden Sie Induktion.
Argumentieren Sie zun\"achst, dass
$w(v_l) \leq \frac{9}{10} w(v)$ und $w(v_r) \leq \frac{9}{10} w(v)$ sind.

\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}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.



\end{document}
