\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum,spalten}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2-3-4-B-Baum und AVL-Baum},
  Thematik = {2-3-4-Baum},
  Referenz = 46115-2011-F.T1-A3,
  RelativerPfad = Examen/46115/2011/03/Thema-1/Aufgabe-3.tex,
  ZitatSchluessel = aud:pu:7,
  ZitatBeschreibung = {entnommen aus Algorithmen und Datenstrukturen, Übungsblatt 6, Universität Würzburg, Aufgabe 9},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {B-Baum, AVL-Baum},
  EinzelpruefungsNr = 46115,
  Jahr = 2011,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 3,
}

\begin{enumerate}

%%
% (a)
%%

\item Fügen Sie in einen anfangs leeren 2-3-4-Baum (B-Baum der Ordnung
4)\footnote{ein Baum, für den folgendes gilt: Er besitzt in einem Knoten
max. 3 Schlüssel-Einträge und 4 Kindknoten und minimal einen Schlüssel
und 2 Nachfolger} der Reihe nach die folgenden Schlüssel ein:
\index{B-Baum}\index{AVL-Baum}
\footcite[entnommen aus Algorithmen und
Datenstrukturen, Übungsblatt 6, Universität Würzburg, Aufgabe 9]{aud:pu:7}
\index{B-Baum}

\bigskip

\centerline{$1$, $2$, $3$, $5$, $7$, $8$, $9$, $4$, $11$, $12$, $13$, $6$.}

\bigskip

Dokumentieren Sie die Zwischenschritte so,
dass die Entstehung des Baumes und nicht nur das Endergebnis
nachvollziehbar ist. \footcite[Staatsexamen Theoretische Informatik,
Algorithmen und Datenstrukturen, Realschulen, Frühjahr 2011, Thema 1
Aufgabe 3]{examen:46115:2011:03}

\begin{bAntwort}
\begin{multicols}{2}
\begin{enumerate}

%%
%
%%

\item 1, 2, 3 (Einfaches Einfügen):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
]
\node {1 \nodepart{two} 2 \nodepart{three} 3};
\end{tikzpicture}

%%
%
%%

\item 5 (Split):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=25mm},
]
\node {2} [->]
  child {node {1}}
  child {node {3 \nodepart{two} 5}}
;
\end{tikzpicture}

%%
%
%%

\item 7 (Einfaches Einfügen):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=25mm},
]
\node {2} [->]
  child {node {1}}
  child {node {3 \nodepart{two} 5 \nodepart{three} 7}}
;
\end{tikzpicture}

%%
%
%%

\item 8 (Split):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=15mm},
]
\node {2 \nodepart{two} 5} [->]
  child {node {1}}
  child {node {3}}
  child {node {7 \nodepart{two} 8}}
;
\end{tikzpicture}

%%
%
%%

\item 9, 4 (Einfaches Einfügen):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=15mm},
]
\node {2 \nodepart{two} 5} [->]
  child {node {1}}
  child {node {3 \nodepart{two} 4}}
  child {node {7 \nodepart{two} 8 \nodepart{three} 9}}
;
\end{tikzpicture}

%%
%
%%

\item 11 (Split):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=15mm},
]
\node {2 \nodepart{two} 5 \nodepart{three} 8} [->]
  child {node {1}}
  child {node {3 \nodepart{two} 4}}
  child {node {7}}
  child {node {9 \nodepart{two} 11}}
;
\end{tikzpicture}

%%
%
%%

\item 12 (Einfaches Einfügen):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=15mm},
]
\node {2 \nodepart{two} 5 \nodepart{three} 8} [->]
  child {node {1}}
  child {node {3 \nodepart{two} 4}}
  child {node {7}}
  child {node {9 \nodepart{two} 11 \nodepart{three} 12}}
;
\end{tikzpicture}

%%
%
%%

\item 13 (zwei Splits):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=31mm},
  level 2/.style={level distance=10mm,sibling distance=12mm},
]
\node {5} [->]
  child {node {2}
    child {node {1}}
    child {node {3 \nodepart{two} 4}}
  }
  child {node {8 \nodepart{two} 11}
    child {node {7}}
    child {node {9}}
    child {node {12 \nodepart{two} 13}}
  }
;
\end{tikzpicture}

%%
%
%%

\item 6 (Einfaches Einfügen):

\begin{tikzpicture}[
  scale=0.8,
  transform shape,
  b bbaum,
  level 1/.style={level distance=12mm,sibling distance=31mm},
  level 2/.style={level distance=15mm,sibling distance=12mm},
]
\node {5} [->]
  child {node {2}
    child {node {1}}
    child {node {3 \nodepart{two} 4}}
  }
  child {node {8 \nodepart{two} 11}
    child {node {6 \nodepart{two} 7}}
    child {node {9}}
    child {node {12 \nodepart{two} 13}}
  }
;
\end{tikzpicture}
\end{enumerate}
\end{multicols}
\end{bAntwort}

%%
% (b)
%%

\item Zeichnen Sie einen Rot-Schwarz-Baum oder einen AVL-Baum, der
dieselben Einträge enthält.
\index{AVL-Baum}

\begin{bAntwort}
\begin{bBaum}{Nach dem Einfügen von „1“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{1}; ]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „2“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{1};
  \edge[blank]; \node[blank]{};
  [.\node[label=0]{2}; ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „3“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{1};
  \edge[blank]; \node[blank]{};
  [.\node[label=+1]{2};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{3}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=0]{3}; ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „5“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=+1]{3};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{5}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „7“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=+2]{3};
    \edge[blank]; \node[blank]{};
    [.\node[label=+1]{5};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{7}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=0]{5};
    [.\node[label=0]{3}; ]
    [.\node[label=0]{7}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „8“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=+1]{5};
    [.\node[label=0]{3}; ]
    [.\node[label=+1]{7};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{8}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=0]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=0]{3}; ]
  ]
  [.\node[label=+1]{7};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{8}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „9“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{5};
  [.\node[label=0]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=0]{3}; ]
  ]
  [.\node[label=+2]{7};
    \edge[blank]; \node[blank]{};
    [.\node[label=+1]{8};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{9}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=0]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=0]{3}; ]
  ]
  [.\node[label=0]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=0]{9}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „4“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=-1]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=0]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=0]{9}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „11“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=+1]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=+1]{9};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{11}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „12“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=+2]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=+2]{9};
      \edge[blank]; \node[blank]{};
      [.\node[label=+1]{11};
        \edge[blank]; \node[blank]{};
        [.\node[label=0]{12}; ]
      ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=+1]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=0]{11};
      [.\node[label=0]{9}; ]
      [.\node[label=0]{12}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „13“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=+2]{8};
    [.\node[label=0]{7}; ]
    [.\node[label=+1]{11};
      [.\node[label=0]{9}; ]
      [.\node[label=+1]{12};
        \edge[blank]; \node[blank]{};
        [.\node[label=0]{13}; ]
      ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=0]{11};
    [.\node[label=0]{8};
      [.\node[label=0]{7}; ]
      [.\node[label=0]{9}; ]
    ]
    [.\node[label=+1]{12};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{13}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „6“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{5};
  [.\node[label=+1]{2};
    [.\node[label=0]{1}; ]
    [.\node[label=+1]{3};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{4}; ]
    ]
  ]
  [.\node[label=-1]{11};
    [.\node[label=-1]{8};
      [.\node[label=-1]{7};
        [.\node[label=0]{6}; ]
        \edge[blank]; \node[blank]{};
      ]
      [.\node[label=0]{9}; ]
    ]
    [.\node[label=+1]{12};
      \edge[blank]; \node[blank]{};
      [.\node[label=0]{13}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}
\end{bAntwort}

%%
% (c)
%%

\item Geben Sie eine möglichst gute untere Schranke (in
$\Omega$-Notation) für die Anzahl der Schlüssel in einem 2-3-4-Baum der
Höhe $h$ an.

Hinweis: Überlegen Sie sich, wie ein 2-3-4-Baum mit Höhe $h$ und
möglichst wenigen Schlüsseln aussieht.

\begin{bAntwort}
Ein 2-3-4-Baum mit möglichst wenigen Schlüsseln sieht aus wie ein
Binärbaum:

\begin{itemize}
\item Ein Baum der Höhe $1$ hat $1$ Schlüssel.
\item Ein Baum der Höhe $2$ hat $3$ Schlüssel.
\item Ein Baum der Höhe $3$ hat $7$ Schlüssel.
\item $\cdots$
\item Ein Baum der Höhe $h$ hat $2^h - 1$ Schlüssel.
\end{itemize}

Also liegt die Untergrenze für die Anzahl der Schlüssel in
$\Omega(2^h)$.
\end{bAntwort}

%%
% (d)
%%

\item Geben Sie eine möglichst gute obere Schranke (in
$\mathcal{O}$-Notation) für die Anzahl der Schlüssel in einem 2-3-4-Baum
der Höhe h an.

\begin{bAntwort}
Ein 2-3-4-Baum mit möglichst vielen Schlüsseln hat in jedem Knoten drei
Schlüssel. Und jeder Knoten, der kein Blatt ist, hat vier Kinder:

\begin{itemize}
\item Ein Baum der Höhe $1$ hat $3$ Schlüssel.
\item Ein Baum der Höhe $2$ hat $15$ Schlüssel.
\item Ein Baum der Höhe $3$ hat $63$ Schlüssel.
\item $\cdots$
\item Ein Baum der Höhe $h$ hat $4^h - 1$ Schlüssel.
\end{itemize}

Also liegt die Obergrenze für die Anzahl der Schlüssel in
$\mathcal{O}(4^h)$.
\end{bAntwort}

\end{enumerate}
\end{document}