
\begin{slide}{Suchbäume}

Ein Suchbaum ist ein binärer Baum,
bei dem \emph{für jeden inneren Knoten} gilt:

\begin{itemize}
\item
  jeder Schlüssel im Teilbaum \verb|t.links|
  ist kleiner als \verb|t.key|
\item
  und \verb|t.key| ist kleiner 
  als jeder Schlüssel im Teilbaum \verb|t.rechts|
\end{itemize}
D. h. inorder-Reihenfolge ist eine monoton
steigende Liste.

Suchbäume benutzt man, 
um Schlüssel schnell wiederzufinden.


\end{slide}

\begin{slide}{Suchen}

gesuchten Schlüssel mit Schlüssel der Wurzel vergleichen,
nach links oder rechts absteigen und weitersuchen.

\begin{verbatim}
search (Knoten t, Key k) {
  if ( t.key == k ) { return t; }
  else { 
    if t ist kein Blatt { 
      if ( k < t.key ) { 
        return search (t.left, k);
      } else {
        return search (t.right, k);
      } } } }
\end{verbatim}
  
\end{slide}


\begin{slide}{Laufzeiten für Suchbäume}

\begin{itemize}
\item
  Laufzeit für Suchen ist proportional
  zur Höhe des Baumes ($=$ längster Weg von Wurzel zu Blatt).
\item
  wenn der Baum gut \emph{balanciert} ist,
  dann enthält er bei Höhe $h$ ungefähr $n=2^h$ Knoten
\item
  Laufzeit ist $\sim h \sim \log_2 n$
\item
  Beispiel: wenn Suchen in 1000 Knoten 1 Sekunden dauert,
  dann für 1000000 Knoten 2 Sekunden,
  1000000000 Knoten 3 Sekunden usw.
\end{itemize}

\end{slide}

\begin{slide}{Einfügen}
\begin{verbatim}
insert (Knoten t, Key k) {
  if t ist kein Blatt { 
    if ( k < t.key ) { 
      insert (t.left, k);
    } else {
      insert (t.right, k);
    } 
  } else {
    if ( k < t.key ) {
      t.left = new Blatt (k);
    } else {
      t.right = new Blatt (k);
    } 
} }
\end{verbatim}

\end{slide}

\begin{slide}{weitere Operationen, Diskussion}

Löschen:
\begin{itemize}
\item
  Blatt löschen ist einfach.
\item
  Wie löscht man einen inneren Knoten (Übung)?
\item
  beachte für Einfügen und Löschen:
  es entstehen auch innere Knoten ohne linkes
  bzw. ohne rechtes Kind.
\end{itemize}

Balance:
\begin{itemize}
\item
  bei dieser Art des Einfügens/Löschens
  können stark unbalancierte Bäume entstehen
\item
  reale Algorithmen enthalten deswegen
  Arbeitsschritte, die den Baum \emph{rebalancieren}
\end{itemize}

\end{slide}


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