\documentclass{bschlangaul-aufgabe}
\bLadePakete{baum}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 7},
  Thematik = {AVL-Baum 10,5,25,14 erweitern und Knoten entfernen},
  Referenz = 66115-2019-H.T2-A7,
  RelativerPfad = Examen/66115/2019/09/Thema-2/Aufgabe-7.tex,
  ZitatSchluessel = examen:66115:2019:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = korrekt und überprüft,
  Ueberprueft = {https://visualgo.net/en/bst},
  Stichwoerter = {AVL-Baum},
  EinzelpruefungsNr = 66115,
  Jahr = 2019,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 7,
}

%  bschlangaul-werkzeug.java baum --avl 10 5 25 14 20 31 2 17 7 lösche 14 25

% 10, 5, 25, 14, 20, 31, 2, 17, 7
Fügen Sie (manuell) nacheinander die Zahlen $20, 31, 2, 17, 7$ in
folgenden AVL-Baum ein. Löschen Sie anschließend aus dem entstandenen
Baum nacheinander $14$ und $25$.\index{AVL-Baum}
\footcite{examen:66115:2019:09}

\begin{center}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node{10};
  [.\node{5}; ]
  [.\node{25};
    [.\node{14}; ]
    \edge[blank]; \node[blank]{};
  ]
]
\end{tikzpicture}
\end{center}

\noindent
Zeichnen Sie jeweils direkt nach jeder einzelnen Operation zum Einfügen
oder Löschen eines Knotens, sowie nach jeder elementaren Rotation den
entstehenden Baum. Insbesondere sind evtl. anfallende Doppelrotationen
in zwei Schritten darzustellen. Geben Sie zudem an jedem Knoten die
Balancewerte an.

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

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=+2]{10};
  [.\node[label=0]{5}; ]
  [.\node[label=-2]{25};
    [.\node[label=-1]{20};
      [.\node[label=0]{14}; ]
      \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]{20};
    [.\node[label=0]{14}; ]
    [.\node[label=0]{25}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

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

\begin{bBaum}{Nach der Linksrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{20};
  [.\node[label=0]{10};
    [.\node[label=0]{5}; ]
    [.\node[label=0]{14}; ]
  ]
  [.\node[label=+1]{25};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{31}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

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

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

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

\bPseudoUeberschrift{Löschen}

\begin{bBaum}{Nach dem Löschen von „14“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=-1]{20};
  [.\node[label=-1]{10};
    [.\node[label=0]{5};
      [.\node[label=0]{2}; ]
      [.\node[label=0]{7}; ]
    ]
    [.\node[label=0]{17}; ]
  ]
  [.\node[label=+1]{25};
    \edge[blank]; \node[blank]{};
    [.\node[label=0]{31}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach dem Löschen von „25“}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=-2]{20};
  [.\node[label=-1]{10};
    [.\node[label=0]{5};
      [.\node[label=0]{2}; ]
      [.\node[label=0]{7}; ]
    ]
    [.\node[label=0]{17}; ]
  ]
  [.\node[label=0]{31}; ]
]
\end{tikzpicture}
\end{bBaum}

\begin{bBaum}{Nach der Rechtsrotation}
\begin{tikzpicture}[b binaer baum]
\Tree
[.\node[label=0]{10};
  [.\node[label=0]{5};
    [.\node[label=0]{2}; ]
    [.\node[label=0]{7}; ]
  ]
  [.\node[label=0]{20};
    [.\node[label=0]{17}; ]
    [.\node[label=0]{31}; ]
  ]
]
\end{tikzpicture}
\end{bBaum}
\end{bAntwort}

\end{document}