% Dieses Dokument ist in der Zusammenarbeit von angehenden und
% ausgebildeten Informatiklehrkräften entstanden.
% Der Herausgeber dieses Dokuments ist die Fachgruppe Informatische
% Bildung in NRW der Gesellschaft für Informatik.
%
% Das Dokument steht unter der Lizenz: Creative Commons by-nc-sa Version 4.0
% https://creativecommons.org/licenses/by-nc-sa/4.0/deed.de
%
% Nach dieser Lizenz darf das Dokument beliebig kopiert und bearbeitet werden,
% sofern das Folgeprodukt wiederum unter gleichen Lizenzbedingungen vertrieben
% und auf die ursprünglichen Urheber verwiesen wird.
% Eine kommerzielle Nutzung ist ausdrücklich ausgeschlossen.
%
% Die Namensnennung durch einen Verweis und die Lizenzangabe der ursprünglichen
% Urheber auf den Materialien für Schülerinnen und Schüler ist erforderlich.
%
% Die Sammlung der Dokumente steht unter
% https://matsam.fg-ibn.gi.de
% zur Verfügung.
%
% Das LaTeX-Paket zum Setzen der Dokumente der Sammlung steht
% unter https://www.ctan.org/pkg/schule
% zur Verfügung.


\chapter{Balance ist alles}
\label{cap:balance}

\begin{uebersichtBox}
    Am Ende dieses Kapitels haben Sie gesehen, dass durch das Einfügen in einen binären Suchbaum auch Bäume entstehen können, die nicht mehr bei jedem Schritt die Anzahl der Elemente halbieren und somit nicht mehr sonderlich optimal sind. In diesem Kapitel werden Sie eine Vorgehensweise kennenlernen, die dieses Problem adressiert.
\end{uebersichtBox}

\begin{lernzieleBox}
    Nach der Bearbeitung dieses Kapitels,
    \begin{smallitemize}
        \item kennen Sie die Nachteile, die mit dem Einfügen in binäre Suchbäume verbunden sind.
        \item können Sie ein Verfahren anwenden, um einen binären Suchbaum wieder in eine \enquote{ideale Form} zu bringen.
    \end{smallitemize}
\end{lernzieleBox}

\section{Der Baum als Ideallösung?}
Nachdem Sie sich in den letzten Kapiteln näher mit dem binären Suchbaum vertraut gemacht haben, werden Sie sicherlich auch schon einen Nachteil der Baumstruktur entdeckt haben: Durch Einfüge- und auch durch Lösch-Operationen kann es schnell passieren, dass der Baum zu einer Art linearen Liste \enquote{entartet}. Fügt man die Knoten beispielsweise in aufsteigender Reihenfolge hinzu, so entsteht ein Baum, in dem jeder Knoten nur Nachfolger auf der rechten Seite hat. Beim Durchsuchen dieser Liste würde dann der gleiche Aufwand entstehen, wie beim Durchsuchen einer linearen Liste -- und alle Vorteile des binären Suchbaums wären dahin. Daher werden Lösungen für dieses Problem benötigt.

\begin{aufgabe}
    \begin{teilaufgaben}
        \teilaufgabe Formulieren Sie mit eigenen Worten: Wann bringt ein binärer Suchbaum die Vorteile mit sich, für die er von uns modelliert worden ist? Welche Eigenschaften muss der Baum erfüllen?

        \teilaufgabe Denken Sie an Kapitel \ref{cap:regal} und \ref{cap:baum} zurück -- und daran, aus welchen Überlegungen der Suchbaum entstanden ist. Welche -- zugegebenermaßen sehr aufwändige -- Möglichkeit besteht, um einen Baum wieder in \enquote{Idealform} zu bringen?
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    \begin{teilaufgaben}
        \teilaufgabe Der binäre Suchbaum muss auf beiden Seiten der Wurzel (und jedes   einzelnen Knotens) möglichst die gleiche Anzahl von Knoten als Nachfolgern besitzen. Nur so kann gewährleistet werden, dass mit jedem \enquote{Abzweigen} auch etwa die Hälfte aller anderen Elemente ausgeschlossen werden.

        \teilaufgabe Eine Möglichkeit besteht darin, den bestehenden Baum \enquote{inorder} zu durchlaufen, so dass alle Elemente als sortierte Liste vorliegen. Anschließend führt man für jedes Element in dieser Liste die binäre Suche durch und notiert sich dabei \enquote{den Suchpfad}. So entsteht   Schritt für Schritt ein Baum, bei dem gewährleistet ist, dass die Hälfte der   Knoten pro Suchschritt ausgeschlossen werden kann.
    \end{teilaufgaben}
\end{loesung}

\section{Der AVL-Baum}
Um das Problem des \enquote{unbalancierten} Baums zu lösen, benötigen wir zuerst eine Definition, was für uns ein \enquote{balancierter} Baum ist. Dazu betrachten wir den folgenden binären Suchbaum:
\begin{center}
  \footnotesize
  \begin{tikzpicture}[level distance=1.8cm,
            level/.style={sibling distance=7cm/#1},
            every node/.style={draw,ellipse,fill=white,text width=1.8cm, minimum height=.9cm, text centered},
            every label/.style={label position=above,fill=orange!40,circle,draw=none,text width=1em,minimum height=0}, every label/.prefix code={\scriptsize}]
        \node[label=0] (root) {Ivy Quainoo}
            child {node[label=-1] {David Guetta}
                child {node[label=-1] {Boy}
                    child {node[label=0] {AC/DC}}
                    child[missing] {node {x}}
                }
                child {node[label=0] {Eisblume}}
            }
            child {node[label=0] {Rihanna}
                child {node[label=-1] {Michel Telo}
                    child {node[label=0] {Lana Del Rey}}
                    child[missing] {node {x}}
                }
                child {node[label=+1] {The Overtones}
                    child[missing] {node[label=0] {Silbermond}}
                    child {node[label=0] {Xavier Naidoo}}
                }
            };
    \end{tikzpicture}
\end{center}
An jeden der Knoten $k$ ist eine Zahl geschrieben worden, die sich folgendermaßen berechnet:
\begin{center}
    Höhe des rechten Teilbaums von $k$ -- Höhe des linken Teilbaums von $k$
\end{center}
\begin{aufgabe}
    Beantworten Sie die folgenden Fragen:
    \begin{teilaufgaben}
        \teilaufgabe Blätter sind immer mit der Zahl~0 beschriftet. Warum ist das so?
        \teilaufgabe Welche Information erhalten wir durch das Vorzeichen der Zahl über die Teilbäume des Knotens?
        \teilaufgabe Welche Eigenschaft muss für die Zahlen (und damit für die Knoten) gelten, damit die Knoten im Baum möglichst gleichmäßig verteilt sind?
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    \begin{teilaufgaben}
        \teilaufgabe Da bei Blättern beide Teilbäume leer sind (also die Höhe~0 haben), ergibt sich als Wert folgerichtig die 0.

        \teilaufgabe Betrachtet man die Formel, so lässt sich folgendes ablesen: Wenn der \textbf{rechte} Teilbaum eine größere Höhe hat als der linke, so wird die Zahl positiv. Der umgekehrte Fall gilt, falls der linke Teilbaum höher ist.

        \teilaufgabe Die Zahl oberhalb des Baums darf höchstens den Betrag~1 haben -- auf diese Weise halten sich die Teilbäume gegenseitig relativ gut im Gleichgewicht.
    \end{teilaufgaben}
\end{loesung}

\begin{theorieBox}
    Ein binärer Baum heißt \emph{ausgeglichener oder AVL-Baum}, wenn sich für jeden Knoten $k$ die Höhen des linken und rechten Teilbaums höchstens um 1 unterscheiden. Der Baum im obigen Beispiel ist demnach ausgeglichen.
\end{theorieBox}

\section{Rotation zum Ausgleich}
Wir betrachten nun das Beispiel eines binären Suchbaums, der nicht ausgeglichen ist. Dazu fügen wir dem obigen Beispielbaum den neuen Knoten \enquote{Adele} nach den bekannten Regeln hinzu:
\begin{center}
    \footnotesize
    \begin{tikzpicture}[level distance=1.8cm,
            level/.style={sibling distance=7cm/#1},
            every node/.style={draw,ellipse,fill=white,text width=1.8cm, minimum height=.9cm, text centered},
            every label/.style={label position=above,fill=orange!40,circle,draw=none,text width=1em,minimum height=0}, every label/.prefix code={\scriptsize}]
        \node (root) {Ivy Quainoo}
            child {node {David Guetta}
                child {node {Boy}
                child {node {AC/DC}
                    child[missing] {node {x}}
                    child[orange,thick] {node {Adele}}
                    }
                child[missing] {node {x}}
                }
                child {node {Eisblume}}
            }
            child {node {Rihanna}
                child {node {Michel Telo}
                    child {node {Lana Del Rey}}
                    child[missing] {node {x}}
                }
                child {node {The Overtones}
                    child[missing] {node {Silbermond}}
                    child {node {Xavier Naidoo}}
                }
            };
    \end{tikzpicture}
\end{center}

\begin{aufgabe}
    Beschriften Sie die Knoten im obigen Baum mit den Werten der Höhendifferenz, wie sie im vorangehenden Abschnitt definiert wurde. \label{ex:baum_hoehendifferenz}
\end{aufgabe}
\begin{loesung}
    Mit der Beschriftung sieht der Baum dann wie folgt aus:
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.8cm,
                level/.style={sibling distance=7cm/#1},
                every node/.style={draw,ellipse,fill=white,text width=1.8cm,
                minimum height=.9cm, text centered},
                every label/.style={label position=above,fill=orange!40,
                circle,draw=none,text width=1em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[label=-1] (root) {Ivy Quainoo}
                child {node[label=-2] {David Guetta}
                    child {node[label=-2] {Boy}
                        child {node[label=+1] {AC/DC}
                            child[missing] {node {x}}
                            child {node[label=0] {Adele}}
                            }
                        child[missing] {node {x}}
                    }
                    child {node[label=0] {Eisblume}}
                }
                child {node[label=0] {Rihanna}
                    child {node[label=-1] {Michel Telo}
                        child {node[label=0] {Lana Del Rey}}
                        child[missing] {node {x}}
                    }
                    child {node[label=+1] {The Overtones}
                        child[missing] {node[label=0] {Silbermond}}
                        child {node[label=0] {Xavier Naidoo}}
                    }
                };
        \end{tikzpicture}
    \end{center}
\end{loesung}

Betrachten wir den nun entstandenen Baum und die Werte für die Höhendifferenzen, so fällt auf, dass an zwei Stellen eine Differenz von \enquote{-2} eintritt und der Baum damit nicht mehr ausgeglichen ist. Um dieses Problem zu beheben, bedient man sich des Prinzips der \enquote{Rotation}. Man \enquote{dreht} Knoten so, dass einige Knoten auf- bzw. absteigen und erhält so schrittweise wieder einen AVL-Baum.

\begin{aufgabe}[pcAufgabe]
    Besuchen Sie die Internetseite:
    \begin{center}
        \url{https://visualgo.net/en/bst?mode=AVL}
    \end{center}
    Wählen Sie auf der linken Seite Insert(y) mindestens zehn mal aus und lassen Sie so   neue Zahlen in den Baum einfügen. Beobachten Sie, was geschieht. Beschreiben Sie anschließend das Verfahren zum Ausgleich des Baums (grob) mit eigenen Worten!
    \label{ex:alv-baum}
\end{aufgabe}
\begin{loesung}
    Das Verfahren gliedert sich in folgende Schritte:
    \begin{itemize}
        \item Fügen Sie den neuen Knoten~$x$ an die passende Stelle im (bereits ausgeglichenen) Baum ein
        \item Wandern Sie von diesem Knoten den Baum nach oben entlang und aktualisieren Sie die Höhendifferenzen im \enquote{Vorbeigehen}
        \begin{itemize}
            \item Fall~1: Eine Höhendifferenz wird auf 0 geändert. Beenden Sie die Operation, der Baum ist ausgeglichen.
            \item Fall~2: Eine Höhendifferenz wird auf -2 oder +2 geändert -- führen Sie eine Ausgleichsoperation (Rotation) durch.
        \end{itemize}
    \end{itemize}
\end{loesung}

Wie Sie in der vorherigen Aufgabe festgestellt haben, wird der Baum im Falle des Ungleichgewichts rotiert. Die Schwierigkeit liegt nun darin, zu bestimmen, in welche Richtung rotiert werden muss und ob es sich um eine einfache oder doppelte Rotation handelt. Damit kommen wir zu der folgenden Aufgabe:

\begin{aufgabe}
    Wir betrachten in dieser Aufgabe immer nur Teilbäume, da es genügt, diese \textbf{beim Einfügen} eines neuen Elementes auszubalancieren.
    \begin{center}
        Baum 1:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child {node {8}
                    child {node {3}}
                    child[missing] {node{x}}
                }
                child[missing] {node {x}};
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum 2:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child[missing] {node {x}}
                child {node {18}
                    child[missing] {node {4}}
                    child {node {42}}
                };
        \end{tikzpicture}
    \end{center}
    Beide gezeigten Teilbäume befinden sich im Ungleichgewicht. Wie müssen die Knoten rotiert werden, damit beide Bäume balanciert sind? Und welcher Zusammenhang besteht zu den Höhendifferenzen (achten Sie besonders auf die Vorzeichen)?
    \begin{center}
        Baum 3:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child {node {8}
                    child[missing] {node {3}}
                    child {node{9}}
                }
                child[missing] {node {x}};
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum 4:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child[missing] {node {x}}
                child {node {18}
                    child {node {14}}
                    child[missing] {node {42}}
                };
        \end{tikzpicture}
    \end{center}
    Bearbeiten Sie nun Baum~3 und 4 auf analoge Weise.

    Beschreiben Sie abschließend, worin der Unterschied zwischen Baum~1 und 3 bzw. Baum~2 und 4 liegt. Achten Sie dabei besonders auf die Höhendifferenzen.
\end{aufgabe}
\begin{loesung}
    Baum~1 hat ein Übergewicht auf der linken Seite (der Wurzelknoten hat eine negative Höhendifferenz). Daher drehen wir den Wurzelknoten nach rechts, um dem entgegenzuwirken. Dasselbe Verfahren gilt umgekehrt für Baum~2: eine positive Höhendifferenz von  \enquote{+2} ergibt eine Drehung nach links.
    \begin{center}
        Baum~1:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child {node {8}
                    child {node {3}}
                    child[missing] {node{x}}
                }
                child[missing] {node {x}};
            \path[<-,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum~2:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {11}
                child[missing] {node {x}}
                child {node {18}
                    child[missing] {node {4}}
                    child {node {42}}
                };
            \path[->,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
    \end{center}

    Es ergeben sich daraus die folgenden neuen Bäume:
    \begin{center}
        Baum 1:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {8}
                child {node {3}}
                child {node {11}};
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum 2:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white}]
            \node (root) {18}
                child {node {11}}
                child {node {42}};
        \end{tikzpicture}
    \end{center}

    Berücksichtigt man dabei noch, dass die Knoten alle ebenfalls Wurzeln von Teilbäumen sein könnten, ergibt sich folgende Zeichnung für die Rotation nach links:

    \textbf{L-Rotation}
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.5cm,
                level/.style={sibling distance=4cm/#1},
                every node/.style={draw,fill=white, text centered},
                every label/.style={label position=above,fill=orange!40,circle,
                draw=none,text width=.8em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[draw,circle,label=+2] (root) {$k_1$}
                child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_1$}}
                child {node[draw,circle,label=+1] {$k_2$}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_2$}}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_3$}
                        child[missing] {node {x}}
                        child {node[draw,circle] {x}}
                    }
                };
            \path[->,line width=2pt,draw] (root) + (240:1cm) arc[x radius=1cm, y radius=1cm, start angle=240, delta angle=270];
        \end{tikzpicture}
        \tikz[baseline=-3cm]\draw[->,line width=2pt] (0,0) -- (1,0);
        \begin{tikzpicture}[baseline=-5cm,level distance=1.5cm,
                level/.style={sibling distance=4cm/#1},
                every node/.style={draw,fill=white, text centered},
                every label/.style={label position=above,fill=orange!40,circle,
                draw=none,text width=.8em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[draw,circle,label=0] (root) {$k_2$}
                child {node[draw,circle,label=0] {$k_1$}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_1$}}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_2$}}
                }
                child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_3$}
                    child[missing] {node {x}}
                    child {node[draw,circle] {x}}
                };

            %\path[->,line width=2pt,draw] (root) + (240:1cm) arc[x radius=1cm, y radius=1cm, start angle=240, delta angle=270];
        \end{tikzpicture}

        Die \textbf{R-Rotation} läuft auf symmetrische Art und Weise ab.
    \end{center}

    Betrachten wir nun die Bäume~3 und 4.
    \begin{center}
        Baum~3:
        \begin{tikzpicture}[baseline=0.1cm,every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=-2] (root) {11}
                child {node[label=+1] {8}
                    child[missing] {node {3}}
                    child {node[label=0]{9}}
                }
                child[missing] {node {x}};
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum~4:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=+2] (root) {11}
                child[missing] {node {x}}
                child {node[label=-1] {18}
                    child {node[label=0] {14}}
                    child[missing] {node {42}}
                };
        \end{tikzpicture}
    \end{center}
    Eine einfache Rotation um die Wurzel würde in diesem Fall keinen Erfolg bringen, da hierdurch die Eigenschaft aus \autoref{eigBinBaum} verletzt werden würde bzw. die 8 beispielsweise sowohl die 9 als auch die 11 als Nachfolger hätte und damit wiederum einen unbalancierten Baum erzeugen würde. Aus diesem Grund führt man hier eine \textbf{doppelte} Rotation durch. Ein Hinweis darauf, dass eine doppelte Rotation nötig ist, sind die verschiedenen Vorzeichen der Höhendifferenzen: So hat die 11 in Baum 3 die Differenz \enquote{-2}, die 8 aber \enquote{+1}. Man führt in diesem Fall zuerst eine Rotation der 8 nach links durch, danach dann eine Rotation der Wurzel nach rechts:
    \begin{center}
        Baum~3:
        \begin{tikzpicture}[baseline=0.1cm, every node/.style={%
                draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=-2] (root) {11}
                child {node[label=+1] {8}
                    child[missing] {node {3}}
                    child {node[label=0]{9}}
                }
                child[missing] {node {x}};
            \path[->,line width=2pt,draw] (root-1) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum 4:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=+2] (root) {11}
                child[missing] {node {x}}
                child {node[label=-1] {18}
                    child {node[label=0] {14}}
                    child[missing] {node {42}}
                };
            \path[<-,line width=2pt,draw] (root-2) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
    \end{center}

    \begin{center}
        Baum~3:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=-2] (root) {11}
                child {node[label=-1] {9}
                    child {node[label=0] {8}}
                    child[missing] {node[label=0]{9}}
                }
                child[missing] {node {x}};
            \path[<-,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum~4:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=orange!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=+2] (root) {11}
                child[missing] {node {x}}
                child {node[label=+1] {14}
                    child[missing] {node[label=0] {14}}
                    child {node[label=0] {18}}
                };
            \path[->,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
    \end{center}
    \begin{center}
        Baum~3:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=green!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=0] (root) {9}
                child {node[label=0] {8}}
                child {node[label=0] {11}};
            %\path[<-,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
        \qquad\qquad\qquad
        Baum~4:
        \begin{tikzpicture}[baseline=0.1cm,
                every node/.style={draw,circle,text width=.8em,text centered,fill=white},
                every label/.style={circle,fill=green!20,text width=1em},
                every label/.prefix code={\scriptsize}]
            \node[label=0] (root) {14}
                child {node[label=0] {11}}
                child {node[label=0] {18}};
            %\path[->,line width=2pt,draw] (root) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}
    \end{center}
    Das entsprechende Verfahren mit evtl. vorhandenen Teilbäume sieht folgendermaßen aus: \textbf{LR-Rotation:}
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.5cm,
                level/.style={sibling distance=4cm/#1},
                every node/.style={draw,fill=white, text centered},
                every label/.style={label position=above,fill=orange!40,circle, draw=none,text width=.9em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[draw,circle,label=-2] (root) {$k_1$}
                child {node[draw,circle,label=+1] {$k_2$}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_1$}}
                    child {node[draw,circle,label=+1] {$k_3$}
                        child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_2$}}
                        child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_3$}
                            child[missing] {node {x}}
                            child {node[circle] {x}}
                        }
                    }
                }
                child[level distance=3cm,child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_4$}};
             \path[->,line width=2pt,draw] (root-1) + (240:1cm) arc[x radius=1cm, y radius=1cm, start angle=240, delta angle=270];
        \end{tikzpicture}
        \tikz[baseline=-3cm]\draw[->,line width=2pt] (0,0) -- (1,0);
        \begin{tikzpicture}[level distance=1.5cm,
                level/.style={sibling distance=4cm/#1},
                every node/.style={draw,fill=white, text centered},
                every label/.style={label position=above,fill=orange!40,circle, draw=none,text width=.9em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node [draw,circle,label=-2] (root) {$k_1$}
                child {node[draw,circle,label=-1] {$k_3$}
                    child {node[draw,circle,label=-1] {$k_2$}
                        child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_1$}}
                        child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_2$}}
                    }
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_3$}
                        child[missing] {node {}}
                        child {node[circle] {x}}
                    }
                }
                child[child anchor=north,level distance=3cm] {node[draw,isosceles triangle,shape border rotate=90] {$T_4$}};
            \path[<-,line width=2pt,draw] (root-1) + (120:1cm) arc[x radius=1cm, y radius=1cm, start angle=120, delta angle=270];
        \end{tikzpicture}\\[1cm]
        \tikz[baseline=-3cm]\draw[->,line width=2pt] (0,0) -- (1,0);
        \begin{tikzpicture}[level distance=1.5cm,
                level/.style={sibling distance=4cm/#1},
                every node/.style={draw,fill=white, text centered},
                every label/.style={label position=above,fill=orange!40,circle, draw=none,text width=.9em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[draw,circle,label=0] (root) {$k_3$}
                child {node[draw,circle,label=-1] {$k_2$}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_1$}}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_2$}}
                }
                child {node[draw,circle,label=0] {$k_1$}
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_3$}
                        child[missing] {node {}}
                        child {node[draw,circle] {x}}
                    }
                    child[child anchor=north] {node[draw,isosceles triangle,shape border rotate=90] {$T_4$}}
                };
        \end{tikzpicture}\\
        Auch hier existiert ein Gegenstück, das symmetrisch abläuft: Die \textbf{RL-Rotation}.
    \end{center}
\end{loesung}

\begin{nothelferBox}
    Verwenden Sie das Applet der oben gezeigten Seite, um die Lösungen nachvollziehen zu können. Versuchen Sie anschließend, die Vorgehensweise zu begründen.
\end{nothelferBox}

\begin{aufgabe}
    Wenden Sie das Verfahren nun auf unseren Baum aus Aufgabe \ref{ex:baum_hoehendifferenz} an.
\end{aufgabe}
\begin{loesung}
    Beim Eintragen der Höhendifferenzen fällt auf, dass zuerst die Differenz im Knoten \enquote{Boy} auf \enquote{-2} verändert wird. Dieser Knoten muss demnach rotiert werden. Da die Höhendifferenz des Nachfolgeknotens \enquote{AC/DC} ein anderes Vorzeichen hat als das \enquote{Boy}, muss eine Doppelrotation durchgeführt werden. Zudem handelt es sich um ein linksseitiges Übergewicht, demnach muss eine LR-Rotation durchgeführt werden:
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.8cm,
                level/.style={sibling distance=7cm/#1},
                every node/.style={draw,ellipse,fill=white,text width=1.8cm,
                minimum height=.9cm, text centered},
                every label/.style={label position=above,fill=orange!40,circle,
                draw=none,text width=1em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[label=-1] (root) {Ivy Quainoo}
                child {node[label=-2] {David Guetta}
                    child {node[label=-2] {Boy}
                        child {node[label=+1] {AC/DC}
                            child[missing] {node {x}}
                            child {node[label=0] {Adele}}
                        }
                        child[missing] {node {x}}
                    }
                    child {node[label=0] {Eisblume}}
                }
                child {node[label=0] {Rihanna}
                    child {node[label=-1] {Michel Telo}
                        child {node[label=0] {Lana Del Rey}}
                        child[missing] {node {x}}
                    }
                    child {node[label=+1] {The Overtones}
                        child[missing] {node[label=0] {Silbermond}}
                        child {node[label=0] {Xavier Naidoo}}
                    }
                };
            \path[->,line width=2pt,draw] (root-1-1-1) + (120:1cm) arc[x radius=1.5cm, y radius=1cm, start angle=120, delta angle=270];
            \node[left=4cm of root,fill=green!30] {1. Schritt: L-Rotation};
        \end{tikzpicture}
    \end{center}
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.8cm,
                level/.style={sibling distance=7cm/#1},
                every node/.style={draw,ellipse,fill=white,text width=1.8cm, minimum height=.9cm, text centered},
                every label/.style={label position=above,fill=orange!40,circle, draw=none,text width=1em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[label=-1] (root) {Ivy Quainoo}
                child {node[label=-2] {David Guetta}
                    child {node[label=-2] {Boy}
                        child {node[label=+1] {Adele}
                            child {node[label=0] {AC/DC}}
                            child[missing] {node[label=0] {x}}
                        }
                        child[missing] {node {x}}
                    }
                    child {node[label=0] {Eisblume}}
                }
                child {node[label=0] {Rihanna}
                    child {node[label=-1] {Michel Telo}
                        child {node[label=0] {Lana Del Rey}}
                        child[missing] {node {x}}
                    }
                    child {node[label=+1] {The Overtones}
                        child[missing] {node[label=0] {Silbermond}}
                        child {node[label=0] {Xavier Naidoo}}
                    }
                };
            \path[<-,line width=2pt,draw] (root-1-1) + (120:1cm) arc[x radius=1.5cm, y radius=1cm, start angle=120, delta angle=270];
            \node[left=4cm of root,fill=green!30] {2. Schritt: R-Rotation};
        \end{tikzpicture}
    \end{center}
    \begin{center}
        \footnotesize
        \begin{tikzpicture}[level distance=1.8cm,
                level/.style={sibling distance=7.8cm/#1},
                every node/.style={draw,ellipse,fill=white,text width=1.8cm, minimum height=.9cm, text centered},
                every label/.style={label position=above,fill=orange!40,circle, draw=none,text width=1em,minimum height=0},
                every label/.prefix code={\scriptsize}]
            \node[label=0] (root) {Ivy Quainoo}
                child {node[label=-1] {David Guetta}
                    child {node[label=0] {Adele}
                        child {node[label=0] {AC/DC}}
                        child {node[label=0] {Boy}}
                    }
                    child {node[label=0] {Eisblume}}
                }
                child {node[label=0] {Rihanna}
                    child {node[label=-1] {Michel Telo}
                        child {node[label=0] {Lana Del Rey}}
                        child[missing] {node {x}}
                    }
                    child {node[label=+1] {The Overtones}
                        child[missing] {node[label=0] {Silbermond}}
                        child {node[label=0] {Xavier Naidoo}}
                    }
                };
            %\path[<-,line width=2pt,draw] (root-1-1) + (120:1cm) arc[x radius=1.5cm, y radius=1cm, start angle=120, delta angle=270];
            \node[text width=2.8cm,left=3cm of root,fill=green!30] {3. Schritt: Höhendifferenzen aktualisieren};
        \end{tikzpicture}
    \end{center}
    Damit ist der Baum ausgeglichen.
\end{loesung}

\begin{lernkontrolleBox}
    \begin{kontrollaufgabe}
        Ein binärer Suchbaum ist ausgeglichen, wenn die Höhendifferenz in allen Knoten~0 beträgt.
        \begin{mcumgebung}
            \choice[\mcrichtig] Falsch
            \choice Richtig
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Eine positive Höhendifferenz deutet darauf hin, dass der rechte Teilbaum eines Knotens größer ist als der linke.
        \begin{mcumgebung}
            \choice Falsch
            \choice[\mcrichtig] Richtig
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Bauen Sie einen neuen binären Suchbaum aus folgenden Zahlen auf:
        \begin{center}
            83, 13, 25, 42, 19, 22, 49, 12
        \end{center}
        Achten Sie nach jedem Einfügen darauf, dass der Baum wieder ausgeglichen ist. Kontrollieren Sie Ihre Lösung anschließend mit der Internetseite aus Aufgabe \ref{ex:alv-baum}.
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        Der Baum wird drei Male rotiert und sieht am Ende so aus:
        \begin{center}
            \begin{tikzpicture}[level distance=10mm, level/.style={sibling distance=59mm/#1}, every node/.style={draw,circle,fill=white,text width=1em,text centered}]
                    \node (root) {25}
                        child {node {19}
                            child {node {13}
                                child {node {12}}
                                child[missing] {}
                            }
                            child{node {22}}
                        }
                        child {node {49}
                            child {node {42}}
                            child {node {83}}
                        };
            \end{tikzpicture}
        \end{center}
    \end{kontrollloesung}
\end{lernkontrolleBox}

\newpage

\begin{loesungenBox}
\end{loesungenBox}
\printsolutionstype[chapter=\thechapter]{aufgabe}

\paragraph{Lernkontrolle}$~$\\

\printsolutionstype[chapter=\thechapter]{kontrollaufgabe}