\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Übungsaufgabe B-Bäume},
  Thematik = {B-Baum m=2},
  Referenz = 66112-2005-H.T2-A6,
  RelativerPfad = Examen/66112/2005/09/Thema-2/Aufgabe-6.tex,
  ZitatSchluessel = 66112:2005:09,
  ZitatBeschreibung = {Thema 2 Aufgabe 6
(Adaptiert)},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {B-Baum},
  EinzelpruefungsNr = 66112,
  Jahr = 2005,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 6,
}

\begin{enumerate}

%%
% a)
%%

\item Erzeugen\index{B-Baum} \footcite[Thema 2 Aufgabe 6
(Adaptiert)]{66112:2005:09} Sie aus der gegebenen Folge einen B-Baum der
Ordnung $m=2$:\footcite[Seite 34-37(PDF 28-31)]{aud:fs:5}

$22,10,19,20,1,13,11,12,7,8,5,42,33,21,52,48,50$

Fügen Sie dazu die einzelnen Elemente in gegebener Reihenfolge in einen
anfangs leeren B-Baum ein. Stellen Sie für jeden Wert die entsprechenden
Zwischenergebnisse und die angewendeten Operationen als Bäume dar!

\begin{bAntwort}
\begin{itemize}

%%
%
%%

\item \fbox{+22} \fbox{+10} \fbox{+19} \fbox{+20} Einfügen der ersten
Zahlen bis zur kompletten Füllung der Wurzel:

\begin{tikzpicture}[b bbaum]
\node {10 \nodepart{two} 19 \nodepart{three} 20 \nodepart{four} 22};
\end{tikzpicture}

%%
%
%%

\item \fbox{+1} Einfügen der 1 führt zum Überlauf, deshalb Aufspaltung:

\begin{tikzpicture}[b bbaum]
\node {1 \nodepart{two} 10 \nodepart{three} 19 \nodepart{four} 20 \nodepart{five} 22};
\end{tikzpicture}

%%
%
%%

\item Übernahme des mittleren Elements (19) in die Wurzel:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=15mm},
]
\node {19}[->]
  child{node {1 \nodepart{two} 10}}
  child{node {20 \nodepart{two} 22}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+13} Einfügen der 13:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=20mm},
]
\node {19}[->]
  child{node {1 \nodepart{two} 10 \nodepart{three} 11 \nodepart{four} 13}}
  child{node {20 \nodepart{two} 22}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+12} Einfügen der 12 nicht möglich, also wieder Aufspaltung.
11 als mittleres Element wird nach oben geschrieben:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=15mm},
]
\node {11 \nodepart{two} 19}[->]
  child{node {1 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 22}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+7} \fbox{+8} Einfügen von 7 und 8:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=20mm},
]
\node {11 \nodepart{two} 19}[->]
  child{node {1 \nodepart{two} 7 \nodepart{three} 8 \nodepart{four} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 22}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+5} Einfügen von 5 nicht möglich, deshalb Aufspaltung, 7 als
mittleres Element wird nach oben geschrieben:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=15mm},
]
\node {7 \nodepart{two} 11 \nodepart{three} 19}[->]
  child{node {1 \nodepart{two} 5}}
  child{node {8 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 22}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+42} \fbox{+33} Einfügen von 42 und 33:

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=20mm},
]
\node {7 \nodepart{two} 11 \nodepart{three} 19}[->]
  child{node {1 \nodepart{two} 5}}
  child{node {8 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 22 \nodepart{three} 33 \nodepart{four} 42}}
;
\end{tikzpicture}

%%
%
%%

\item \fbox{+21} Einfügen von 21 nicht möglich, also Aufspaltung, 22
nach oben schieben

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=15mm},
]
\node {7 \nodepart{two} 11 \nodepart{three} 19 \nodepart{four} 22}[->]
  child{node {1 \nodepart{two} 5}}
  child{node {8 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 21}}
  child{node {33 \nodepart{two} 42}}
;
\end{tikzpicture}

\item \fbox{+52} \fbox{+48} Einfügen von 52 und 48

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=20mm},
]
\node {7 \nodepart{two} 11 \nodepart{three} 19 \nodepart{four} 22}[->]
  child{node {1 \nodepart{two} 5}}
  child{node {8 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 21}}
  child{node {33 \nodepart{two} 42 \nodepart{three} 48 \nodepart{four} 52}}
;
\end{tikzpicture}

\item \fbox{+50} Einfügen von 50 nicht möglich, daher splitten und 48 eine Ebene
nach oben schieben

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={sibling distance=15mm},
]
\node {7 \nodepart{two} 11 \nodepart{three} 19 \nodepart{four} 22 \nodepart{five} 48}[->]
  child{node {1 \nodepart{two} 5}}
  child{node {8 \nodepart{two} 10}}
  child{node {12 \nodepart{two} 13}}
  child{node {20 \nodepart{two} 21}}
  child{node {33 \nodepart{two} 42}}
  child{node {48 \nodepart{two} 52}}
;
\end{tikzpicture}

\item Einfügen von 48 oben nicht möglich, da Knoten ebenfalls voll! ->
weiterer Splitt notwendig, der neue Ebene erzeugt!

\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={level distance=5mm,sibling distance=60mm},
  level 2/.append style={sibling distance=20mm}
]
\node{19}[->]
  child{node{7 \nodepart{two} 11}
      child{node {1 \nodepart{two} 5}}
      child{node {8 \nodepart{two} 10}}
      child{node {12 \nodepart{two} 13}}
  }
  child{node{22 \nodepart{two} 48}
    child{node {20 \nodepart{two} 21}}
    child{node {33 \nodepart{two} 42}}
    child{node {48 \nodepart{two} 52}}
  }
;
\end{tikzpicture}
\end{itemize}
\end{bAntwort}

%%
% b)
%%

\item In dem Ergebnisbaum suchen wir nun den Wert 17. Stellen Sie den
Ablauf des Suchalgorithmus an einer Zeichnung graphisch dar!

\begin{bAntwort}
\begin{tikzpicture}[
  b bbaum,
  level 1/.append style={level distance=5mm,sibling distance=60mm},
  level 2/.append style={sibling distance=20mm}
]
\node[name=eins]{19}[->]
  child{node[name=zwei]{7 \nodepart{two} 11}
      child{node {1 \nodepart{two} 5}}
      child{node {8 \nodepart{two} 10}}
      child{node[name=drei]{12 \nodepart{two} 13}}
  }
  child{node{22 \nodepart{two} 48}
    child{node {20 \nodepart{two} 21}}
    child{node {33 \nodepart{two} 42}}
    child{node {48 \nodepart{two} 52}}
  }
;
\end{tikzpicture}
\end{bAntwort}
\end{enumerate}
\end{document}