\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {AVL-Baum, Dijkstra, Tiefensuche},
  Referenz = 66115-2006-H.T1-A4,
  RelativerPfad = Examen/66115/2006/09/Thema-1/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2006:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {AVL-Baum, Algorithmus von Dijkstra, Tiefensuche, Quicksort},
  EinzelpruefungsNr = 66115,
  Jahr = 2006,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 4,
}

\begin{enumerate}
\item Gegeben sei die folgende Folge ganzer Zahlen: $6, 13, 4, 8, 11, 9,
10$.
\index{AVL-Baum}
\footcite{examen:66115:2006:09}

% bschlangaul-werkzeug.java baum --avl 6 13 4 8 11 9 10

\begin{enumerate}
\item Fügen Sie obige Zahlen der Reihe nach in einen anfangs leeren
AVL-Baum ein und stellen Sie den Baum nach jedem Einfügeschritt dar!

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

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

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

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

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

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

\begin{bBaum}{Nach der Rechtsrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{6};
  [.\node[label=0]{4}; ]
  [.\node[label=0]{11};
    [.\node[label=0]{8}; ]
    [.\node[label=0]{13}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

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

\begin{bBaum}{Nach der Rechtsrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{6};
  [.\node[label=0]{4}; ]
  [.\node[label=+2]{8};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{11};
      [.\node[label=0]{9}; ]
      [.\node[label=0]{13}; ]
    ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{8};
  [.\node[label=-1]{6};
    [.\node[label=0]{4}; ]
    \edge[blank]; \node[blank]{};
  ]
  [.\node[label=0]{11};
    [.\node[label=0]{9}; ]
    [.\node[label=0]{13}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

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

\item Löschen Sie das Wurzelelement des entstandenen AVL-Baums und
stellen Sie die AVL-Eigenschaft wieder her!

\begin{bAntwort}
\begin{bBaum}{Nach dem Löschen von „8“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{9};
  [.\node[label=-1]{6};
    [.\node[label=0]{4}; ]
    \edge[blank]; \node[blank]{};
  ]
  [.\node[label=0]{11};
    [.\node[label=0]{10}; ]
    [.\node[label=0]{13}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}
\end{bAntwort}
\end{enumerate}

%%
% b)
%%

\item Gegeben sei der folgende gerichtete und gewichtete Graph:

\begin{itemize}
\item Bestimmen Sie mit Hilfe des Algorithmus von Dijkstra die kürzesten
Wege vom Knoten A zu allen anderen Knoten! Geben Sie dabei nach jedem
Verarbeitungsschritt den Zustand der Hilfsdatenstruktur an!
\index{Algorithmus von Dijkstra}

\item Skizzieren Sie einen Algorithmus für den Tiefendurchlauf von
gerichteten Graphen, wobei jede Kante nur einmal verwendet werden darf!
\index{Tiefensuche}

\end{itemize}
%%
% c)
%%

\item Ein wesentlicher Nachteil der Standardimplementierung des
QUICKSORT Algorithmus ist dessen rekursiver Aufruf. Implementieren Sie
den Algorithmus QUICKSORT ohne den rekursiven Prozeduraufruf!
\index{Quicksort}

\end{enumerate}

\end{document}