\begin{slide}{Balancierte Bäume: (2,3)-Bäume}

(2,3)-Baum:
\begin{itemize}
\item 
  alle \emph{Blätter} sind gleich tief

  und haben keine Schlüssel
\item 
  jeder \emph{innere Knoten} ist
  \begin{itemize}
  \item ein 2-Knoten: 2 Kinder $[l,r]$, 1 Schlüssel $x$

    jeder Schlüssel in $l$ $< x <$ jeder Schlüssel in $r$
  \item ein 3-Knoten: 3 Kinder $[l,m,r]$, 2 Schlüssel $[x,y]$

    jeder Schlüssel in $l$ $< x <$ jeder Schlüssel in $m$
    $< y <$ jeder Schlüssel in $r$
  \end{itemize}
\end{itemize}

Diese Eigeschaften (Invarianten)
müssen bei allen Operationen erhalten bleiben.

\end{slide}

\begin{slide}{Eigenschaften von (2,3)-Bäumen}
  Ein (2,3)-Baum der Höhe $n$

  hat wenigstens $1 + 2 + 2^2 + \ldots + 2^n = 2^{n+1}-1$ Knoten

  und höchstens $1 + 3 + 3^2 + \ldots + 3^n = (3^{n+1}-1)/2$ Knoten.

  Aufgabe: wieviele Knoten hat ein (2,3)-Baum der Höhe 10
  wenigstens? höchstens?

  Aufgabe: welche Höhe hat ein (2,3)-Baum mit $10^6$ Knoten
  wenigsten? höchstens?
\end{slide}

\begin{slide}{Einfügen in (2,3)-Bäume}
(Suchen funktioniert ähnlich wie bei binären Suchbäumen.)
\begin{itemize}
\item
  suchen den Knoten (direkt über Blättern),
  der neuen Schlüssel aufnehmen sollte.
\item
  aus 2-Knoten wird 3-Knoten (OK),
\item
  aus 3-Knoten wird 4-Knoten (verboten).
\item
  Lösung:
  \begin{itemize}
  \item  
    diesen 4-Knoten in zwei 2-Knoten (und einen Schlüssel) zerlegen,
  \item 
    diesen Schlüssel in Vorgänger einfügen
  \end{itemize}
\end{itemize}


\end{slide}

\begin{slide}{$(a,b)$-Bäume}

Das funktioniert statt $(2,3)$ genauso für Zahlen $(a,b)$
mit $ a \le (b+1)/2$. (Warum diese Einschränkung?)

Für große Datenbanken benutzt man z. B. $a=10,b=100$.

\end{slide}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "informatik"
%%% End: 
