\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 7},
  Thematik = {3,5,1,2,4 in leerer Suchbaum und Heap},
  Referenz = 66115-2012-H.T2-A7,
  RelativerPfad = Examen/66115/2012/09/Thema-2/Aufgabe-7.tex,
  ZitatSchluessel = examen:66115:2012:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Halde (Heap)},
  EinzelpruefungsNr = 66115,
  Jahr = 2012,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 7,
}

\begin{enumerate}

%%
% a)
%%

\item Fügen Sie nacheinander die Zahlen
$3,5,1,2,4$\footcite{examen:66115:2012:09}

\begin{enumerate}

%%
% (i)
%%

\item in einen leeren binären Suchbaum ein

\begin{bAntwort}
\begin{bBaum}{Nach dem Einfügen von „3“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.3 ]
\end{tikzpicture}
\end{bBaum}

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

\begin{bBaum}{Nach dem Einfügen von „1“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.3
  [.1 ]
  [.5 ]
]
\end{tikzpicture}
\end{bBaum}

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

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

%%
% (ii)
%%

\item in einen leeren Heap ein
\index{Halde (Heap)}

\begin{bAntwort}
\begin{bBaum}{Erstellen einer Max.-Halde, einfügen von 3 und 5, Versickern notwendig}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node(3){3};
      [.\node(5){5}; ]
      \edge[blank]; \node[blank]{};
]
\draw[dotted,<->] (3) .. controls +(west:1) .. (5);
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Einfügen von 1 und 2 ohne Änderungen, Einfügen von 4, versickern notwendig}
\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.\node(3){3};
    [.2 ]
    [.\node(4){4}; ]
  ]
  [.1 ]
]
\draw[dotted,<->] (3) .. controls +(east:0.5) .. (4);
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Fertiger Heap}
\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.4
    [.2 ]
    [.3 ]
  ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}
\footcite[Zeichnen der Heap)]{aud:ab:7}

%%
%
%%

\bPseudoUeberschrift{Ausführlicher als Max-Halde}

\begin{bBaum}{Nach dem Einfügen von „3“}
\begin{tabular}{l}
\bf{0} \\
\hline
3      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.3 ]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „5“}
\begin{tabular}{ll}
\bf{0} & \bf{1} \\
\hline
3      & 5      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.3
  [.5 ]
  \edge[blank]; \node[blank]{};
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „5“ und „3“}
\begin{tabular}{ll}
\bf{0} & \bf{1} \\
\hline
5      & 3      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.3 ]
  \edge[blank]; \node[blank]{};
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „1“}
\begin{tabular}{lll}
\bf{0} & \bf{1} & \bf{2} \\
\hline
5      & 3      & 1      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.3 ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „2“}
\begin{tabular}{llll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} \\
\hline
5      & 3      & 1      & 2      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.3
    [.2 ]
    \edge[blank]; \node[blank]{};
  ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „4“}
\begin{tabular}{lllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} \\
\hline
5      & 3      & 1      & 2      & 4      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.3
    [.2 ]
    [.4 ]
  ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „4“ und „3“}
\begin{tabular}{lllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} \\
\hline
5      & 4      & 1      & 2      & 3      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.5
  [.4
    [.2 ]
    [.3 ]
  ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}

%%
%
%%

\bPseudoUeberschrift{Ausführlicher als Min-Halde}

\begin{bBaum}{Nach dem Einfügen von „3“}
\begin{tabular}{l}
\bf{0} \\
\hline
3      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.3 ]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „5“}
\begin{tabular}{ll}
\bf{0} & \bf{1} \\
\hline
3      & 5      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.3
  [.5 ]
  \edge[blank]; \node[blank]{};
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „1“}
\begin{tabular}{lll}
\bf{0} & \bf{1} & \bf{2} \\
\hline
3      & 5      & 1      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.3
  [.5 ]
  [.1 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „1“ und „3“}
\begin{tabular}{lll}
\bf{0} & \bf{1} & \bf{2} \\
\hline
1      & 5      & 3      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.1
  [.5 ]
  [.3 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „2“}
\begin{tabular}{llll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} \\
\hline
1      & 5      & 3      & 2      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.1
  [.5
    [.2 ]
    \edge[blank]; \node[blank]{};
  ]
  [.3 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Vertauschen von „2“ und „5“}
\begin{tabular}{llll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} \\
\hline
1      & 2      & 3      & 5      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.1
  [.2
    [.5 ]
    \edge[blank]; \node[blank]{};
  ]
  [.3 ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Einfügen von „4“}
\begin{tabular}{lllll}
\bf{0} & \bf{1} & \bf{2} & \bf{3} & \bf{4} \\
\hline
1      & 2      & 3      & 5      & 4      \\
\end{tabular}

\begin{tikzpicture}[b binaer baum]
\Tree
[.1
  [.2
    [.5 ]
    [.4 ]
  ]
  [.3 ]
]
\end{tikzpicture}
\end{bBaum}
\end{bAntwort}

\end{enumerate}

Geben Sie die Ergebnisse an (Zeichnung)

%%
% b)
%%

\item Geben Sie zwei Merkmale an, bei denen sich Heaps und binäre
Suchbäume wesentlich unterscheiden. Ein wesentlicher Unterschied
zwischen Bubblesort und Mergesort ist \zB die \emph{worst case} Laufzeit
mit $\mathcal{O}(n^2)$ für Bubblesort und $\mathcal{O}(n \log n)$ für
Mergesort.

\begin{bAntwort}
\begin{tabular}{lll}
& Binärer Suchbaum & Heap \\\hline
Suchen beliebiger Wert (worst case) &
$\mathcal{O}(\log(n))$ &
$\mathcal{O}(n)$ \\

Suchen Min-Max (average case) &
$\mathcal{O}(\log(n))$ &
$\mathcal{O}(1)$ \\
\end{tabular}

\bFussnoteUrl{https://cs.stackexchange.com/q/27860}
\end{bAntwort}

\end{enumerate}
\end{document}