\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\ph} {\varphi}
\newcommand {\wph} {\widehat{\varphi}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Bin\"are Suchb\"aume}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle
\section{Einfache Bin\"are Suchb\"aume}
\subsection{Darstellung}

Ein bin\"arer Suchbaum besteht aus
Knoten.
Ein Knoten \texttt{n} hat folgende 
Felder:
\begin{itemize}
  \item \texttt{k}, \texttt{v}: Schl\"ussel und Wert
  \item \texttt{parent}: Elternknoten
  \item \texttt{left}, \texttt{right}: linkes und rechtes Kind
\end{itemize}

\subsection{Nachschlagen}

\begin{verbatim}
get(k)
  n <- root
  while n != NULL do
    if n.k == k then
      return n.v
    if k < n.k then
      n <- n.left
    else
      n <- n.right
  throw NoSuchElementException
\end{verbatim}

\subsection{Einf\"ugen}

\begin{verbatim}
put(k,v)
  if root == NULL then
    root <- new node for (k,v)
    return
  n <- root
  while true do
    if n.k == k then
      n.v <- v
      return
    if k < n.k then
      if n.left != NULL then
        n <- n.left
      else
        n.left <- new node for (k,v)
        return
    else
      if n.right != NULL then
        n <- n.right
      else
        n.right <- new node for (k,v)
        return
\end{verbatim}

\subsection{L\"oschen}

\begin{verbatim}
remove(k)
  // lokalisiere den Knoten fuer k
  n <- root
  while n != NULL && n.k != k do
    if k < n.k then
      n <- n.left
    else
      n <- n.right
  if n == NULL then
    throw NoSuchElementException
  // wenn der Knoten n kein linkes oder kein rechtes Kind hat, loesche ihn direkt
  if n.left == NULL then
    // ersetze n durch das rechte Kind. Wir zeigen die noetigen Zeigeroperationen
    // nur einmal 
    if n.right != NULL then
      n.right.parent <- n.parent
    if n.parent != NULL then
      if n.parent.left == n then
        n.parent.left <- n.right
      else
        n.parent.right <- n.right
    return
  else if n.right == NULL then
    replace n by its left child
    return
  // n hat beide Kinder -> finde den Vorgaenger von n
  m <- n.left
  while m.right != NULL do
    m <- m.right
  // nun ist m der Vorgaenger von n, m hat kein rechtes Kind
  replace m by its left child
  replace n by m  
\end{verbatim}

\section{AVL-B\"aume}

Ein \emph{AVL-Baum} ist ein \emph{h\"ohen-balancierter} bin\"arer Suchbaum.
Das bedeutet, dass sich an jedem Knoten $v$ des AVL-Baums die
H\"ohen des linken und des rechten Teilbaums h\"ochstens um
$1$ unterscheiden. Wir wollen nun sehen, dass diese
Eigenschaft einen fast perfekten Baum garantiert.

\subsection{Die H\"ohe von AVL-B\"aumen}
\begin{theorem}
\label{thm:shannon}
  Ein AVL-Baum mit $n$ Knoten hat H\"ohe $O(\log n)$.
\end{theorem}

\begin{proof}
F\"ur $h \in \{0, 1, \dots, \}$ sei $F_h$ definiert
als die \emph{minimale} Anzahl von Knoten, die ein
AVL-Baum der H\"ohe $h$ besitzen kann.
Dann gilt
\begin{equation}\label{eq:monotone}
  F_h > F_{h-1}\qquad \text{f\"ur alle } h \in \{1, \dots \},
\end{equation}
da ein Baum der H\"ohe $h$ immer einen echten Teilbaum der H\"ohe
$h-1$ enth\"alt. Au\ss{}erdem ist
\begin{equation}\label{eq:base1}
F_0 = 1,
\end{equation} 
denn es gibt nur
einen Baum der H\"ohe $0$: der Baum der nur aus
der Wurzel besteht. Au\ss{}erdem haben wir
\begin{equation}\label{eq:base2}
F_1 = 2,
\end{equation}
den von den drei m\"oglichen bin\"aren Baumen der H\"ohe $1$ sind
die beiden B\"aume mit zwei Knoten AVL-B\"aume. Schlie\ss{}lich
gilt f\"ur $h \geq 2$:
\begin{equation}\label{eq:rek}
  F_h = F_{h-2} + F_{h-1} + 1,
\end{equation}
denn ein AVL-Baum der H\"ohe $h$ besteht aus einer Wurzel und 
zwei Teilb\"aumen, deren H\"ohen sich um h\"ochstens $1$ unterscheiden.
Da die Teilb\"aume unabh\"angig sind, muss die
Anzahl der Knoten in den Teilb\"aumen minimal sein, damit die Anzahl
der Knoten im gesamten Baum minimal ist. Wegen (\ref{eq:monotone})
muss einer der Teilb\"aume H\"ohe $h-2$ haben.

Wir beweisen durch Induktion: F\"ur alle $h \in \{0, 1,  \dots, \}$
gilt
\begin{equation}\label{eq:Fh}
  F_h \geq \left(\frac{3}{2}\right)^{h}.
\end{equation}
Die Aussage ist klar f\"ur $h \in \{0, 1\}$, denn nach
(\ref{eq:base1}, \ref{eq:base2}) haben wir
\[
F_0 = 1  \geq \left(\frac{3}{2}\right)^0 \text{ und }
F_1 = 2 \geq \left(\frac{3}{2}\right)^1.
\]

Sei nun $h \geq 2$. Nach Induktionsannahme und (\ref{eq:rek}) gilt:
\begin{align*}
F_h = F_{h-2} + F_{h-1} + 1
&\geq \left(\frac{3}{2}\right)^{h-2}
+ \left(\frac{3}{2}\right)^{h-1}
+1\\
&=
\left(\frac{3}{2}\right)^{h-2} \left(1 + \frac{3}{2}\right) + 1\\
&> 
\left(\frac{3}{2}\right)^{h-2}\cdot \frac{9}{4}  \\
&= \left(\frac{3}{2}\right)^{h}.
\end{align*}
Damit ist (\ref{eq:Fh}) bewiesen. 

Betrachte nun einen AVL-Baum $T$ mit $n$ Knoten, und
nimm an, dass $T$ die H\"ohe $h$ besitzt. Dann gilt
nach Definition von $F_h$, dass $n \geq F_h$ ist.
Nach (\ref{eq:Fh}) ist au\ss{}erdem $F_h \geq (3/2)^h$.
Also gilt $n \geq (3/2)^h$, oder \"aquivalent 
$h \leq \log_{3/2} n \approx 1.71 \log_2 n = O(\log n)$, wie
behauptet.
\end{proof}

\textbf{Anmerkung}. Durch exaktes L\"osen der Rekursionsgleichung
(\ref{eq:base1}, \ref{eq:base2}, \ref{eq:rek}) erh\"alt man 
sogar,
dass $h \leq \log_\ph (n+2) \approx 1.44 \log (n+2)$ ist, 
wobei $\ph = (1 + \sqrt{5})/2$
den goldenen Schnitt bezeichnet.

Das wollen wir nun beweisen. Dazu verwenden wir
die Technik der \emph{erzeugenden Funktionen}.
Wir stellen die Folge $F_h$ als Funktion dar, und
benutzen algebraische Manipulationen, um eine
explizite Darstellung der Folgenglieder zu erhalten.
Wir schreiben also
\[
F(x) = \sum_{h=0}^\infty F_h x^h.
\]
Dann gilt:
\begin{align*}
F(x) &=  1 + 2x + \sum_{h = 2}^\infty F_h x^h & 
\text{(nach (\ref{eq:base1}, \ref{eq:base2}))}\\
     &=  1 + 2x + \sum_{h = 2}^\infty (F_{h-2}+F_{h-1}+1) x^h &
\text{(nach (\ref{eq:rek}))}\\
     &=  1 + 2x + \sum_{h = 2}^\infty F_{h-2}x^h + 
         \sum_{h=2}^\infty F_{h-1}x^h + \sum_{h=2}^\infty x^h
	 & \text{(Aufteilen der Summanden)}\\
     &=  1 + 2x + x^2 \left(\sum_{h = 0}^\infty F_{h}x^h\right) + 
         x \left(\sum_{h=1}^\infty F_{h}x^h\right) + 
         \left(\sum_{h=0}^\infty x^h\right) - 1 - x
	 & \text{(Indexverschiebung)}\\
     &=  1 + 2x + x^2 F(x) + 
         x \left(F(x) - 1\right) + \left(\sum_{h=0}^\infty x^h\right) - 1 - x
	 & \text{(Definition von $F(x)$)}\\
         &=  x^2 F(x) + x F(x) + \frac{1}{1-x}.
	 & \text{(Vereinfachen, geometrische Reihe)}\\
\end{align*}
Aufl\"osen nach $F(x)$ ergibt die folgende Funktionalgleichung:
\[
  F(x) = \frac{1}{(x^2 + x - 1)(x - 1)}.
\]
Schreibe nun $\ph = (1+\sqrt{5})/2$ und 
$\wph = (1-\sqrt{5})/2$. Wie man schnell nachrechnet, haben
die beiden Zahlen $\ph$ und $\wph$
die folgenden Eigenschaften:
\[
\text{(i) } \ph + \wph = 1; \quad \text{(ii) } \ph - \wph = \sqrt{5}; \quad
\text{(iii) } \ph\cdot \wph = -1; \quad
\text{(iv) } \ph^2 = \ph + 1; \,
\text{ und (v) } \wph^2 = \wph + 1. 
\]
Aus (i, iii) folgt, dass $(x+\wph)(x+\ph) = x^2 + x - 1$ ist. Also:
\[
  F(x) = \frac{1}{(x+\wph)(x+\ph)(x - 1)}.
\]
Das Ziel ist nun, aus der Funktionalgleichung f\"ur 
$F(x)$ eine explizite Darstellung der Folgenglieder $F_h$
zu gewinnen. Dazu wollen wir die Funktionalgleichung
auf die geometrische Reihe $1/(1-ax) = \sum_{h=0}^\infty a^hx^h$
zur\"uckf\"uhren. Das geeignete Werkzeug zu diesem 
Zweck ist die bekannte \emph{Partialbruchzerlegung}.
Wir machen den Ansatz
\[
F(x) =  \frac{1}{(x+\wph)(x+\ph)(x - 1)} = 
\frac{\alpha}{x + \wph} + \frac{\beta}{x + \ph} + \frac{\gamma}{x - 1},
\]
wobei $\alpha, \beta, \gamma$ gesucht sind. Wenn wir
diese Gleichung mit $x+\wph$ multiplizieren und $x = -\wph$
setzen,
so erhalten wir wegen (ii, v, iii)
\[
\alpha = \frac{1}{(-\wph + \ph)(-\wph - 1)}
       = \frac{1}{\sqrt{5}(-\wph^2)}
       = -\frac{\ph^2}{\sqrt{5}}.
\]
Analog sehen wir mit (ii, iv, iii), dass
\[
\beta = \frac{1}{(-\ph + \wph)(-\ph - 1)}
       = \frac{1}{-\sqrt{5}(-\ph^2)}
       = \frac{\wph^2}{\sqrt{5}}
\]
und mit (iv, v, iii), dass
\[
\gamma = \frac{1}{(1+\ph)(1+\wph)}
       = \frac{1}{(\ph\wph)^2}
       = 1
\]
ist. Nun k\"onnen wir mit der Partialbruchzerlegung f\"ur $F(x)$ 
wie geplant arbeiten.
\begin{align*}
  F(x) &= 
  - \frac{\ph^2}{\sqrt{5}}\cdot\frac{1}{x + \wph}
  + \frac{\wph^2}{\sqrt{5}}\cdot\frac{1}{x + \ph} 
  + \frac{1}{x-1} \\
&= 
  - \frac{\ph^2}{\sqrt{5}}\cdot\frac{1}{\wph(1+ x/\wph)}
  + \frac{\wph^2}{\sqrt{5}}\cdot\frac{1}{\ph(1+x/\ph)} 
  -\frac{1}{1-x} & \text{(Ausklammern)}\\
&= 
  \frac{\ph^2}{\sqrt{5}}\cdot\frac{\ph}{1- \ph x}
  - \frac{\wph^2}{\sqrt{5}}\cdot\frac{\wph}{1-\wph x} 
  -\frac{1}{1-x} & \text{(wegen (iii))}\\
  &=
  \frac{\ph^3}{\sqrt{5}}\cdot \sum_{h=0}^\infty \ph^hx^h 
  - \frac{\wph^3}{\sqrt{5}}\cdot \sum_{h=0}^\infty \wph^hx^h 
  -\sum_{h=0}^\infty x^h 
  -\frac{1}{1-x} & \text{(geometrische Reihe)}\\
&=
  \sum_{h=0}^\infty \left(
  \frac{\ph^{h+3}-\wph^{h+3}}{\sqrt{5}}
 -1 \right)x^h. & \text{(Zusammenfassen)}
\end{align*}
Durch Koeffizientenvergleich k\"onnen wir nun die
Formel
\[
F_h = \frac{1}{\sqrt{5}}\left(\ph^{h+3} - \wph^{h+3}\right) - 1,
\]
f\"ur alle $h \geq 0$, ableiten. Es gilt also
\[
  n \geq F_h \geq \frac{1}{\sqrt{5}}\ph^{h+3} - 2
\]
und somit
\[
h \leq \log_{\ph}(n+2) + \log_{\ph}(\sqrt{5})-3,
\]
wie behauptet.
\end{document}