\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {Aussage widerlegen},
  Referenz = 46115-2019-F.T2-A3,
  RelativerPfad = Examen/46115/2019/03/Thema-2/Aufgabe-3.tex,
  ZitatSchluessel = examen:46115:2019:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = korrekt und überprüft,
  Ueberprueft = {mit den Online-Tool VisuAlgo \url{https://visualgo.net/en/bst}},
  Stichwoerter = {AVL-Baum},
  EinzelpruefungsNr = 46115,
  Jahr = 2019,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 3,
}
\begin{enumerate}

%%
% (a)
%%

\item Zeigen oder widerlegen Sie die folgende Aussage: Wird ein Element
in einen AVL-Baum eingefügt und unmittelbar danach wieder gelöscht, so
befindet sich der AVL-Baum wieder in seinem
Ursprungszustand.\index{AVL-Baum}
\footcite{examen:46115:2019:03}

\begin{bAntwort}
Die Aussage ist falsch. Wir widerlegen die Aussage durch ein konkretes
Beispiel:

\begin{bBaum}{Unser Ausgangs-AVL-Baum}
\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=0]{2};
  [.\node[label=0]{1}; ]
  [.\node[label=0]{3}; ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Löschen von „3“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=-1]{2};
  [.\node[label=0]{1}; ]
  \edge[blank]; \node[blank]{};
]
\end{tikzpicture}
\end{bBaum}

\end{bAntwort}

%%
% (b)
%%

\item Fügen Sie in den gegebenen Baum den Schlüssel $11$ ein.

\begin{center}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+1]{10};
  [.\node[label=0]{5}; ]
  [.\node[label=-1]{15};
    [.\node[label=0]{12}; ]
    \edge[blank]; \node[blank]{};
  ]
]
\end{tikzpicture}
\end{center}

Rebalancieren Sie anschließend den Baum so, dass die AVL-Eigenschaft
wieder erreicht wird. Zeichnen Sie den Baum nach jeder Einfach- und
Doppelrotation und benennen Sie die Art der Rotation (Links-, Rechts-,
Links-Rechts-, oder Rechts-Links-Rotation). Argumentieren Sie jeweils
über die Höhenbalancen der Teilbäume.

Tipp: Zeichnen Sie nach jedem Schritt die Höhenbalancen in den Baum ein.

%  bschlangaul-werkzeug.java baum --avl 10 5 15 12 11 -v -t
\begin{bAntwort}
\begin{bBaum}{Nach dem Einfügen von „11“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{10};
  [.\node[label=0]{5}; ]
  [.\node[label=-2]{15};
    [.\node[label=-1]{12};
      [.\node[label=0]{11}; ]
      \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]{10};
  [.\node[label=0]{5}; ]
  [.\node[label=0]{12};
    [.\node[label=0]{11}; ]
    [.\node[label=0]{15}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}
\end{bAntwort}
\end{enumerate}
\end{document}