% 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{Die Modellierung des binären Suchbaums}
\begin{uebersichtBox}
    Im vorherigen Kapitel haben wir den binären Suchbaum als Produkt der binären Suche für eine Menge von sortierbaren Elementen kennengelernt. Unser Ziel ist es jedoch, den binären Suchbaum als eigenständige und unabhängige Datenstruktur verwenden zu können und die Vorteile, die uns die binäre Suche bietet, in diese Datenstruktur einzuarbeiten.

    In diesem Kapitel werden die Grundlagen für eine mögliche spätere Implementierung des Baums gelegt, indem wir den Baum mit Hilfe von Objekten modellieren. Anschließend verdeutlichen wir uns die Abläufe, die beim Einfügen von neuen Knoten in den Baum vorgehen, indem wir unser objektorientiertes Modell zugrunde legen.
\end{uebersichtBox}

\begin{lernzieleBox}
    Nach der Bearbeitung dieses Kapitels,
    \begin{smallitemize}
         \item kennen Sie ein Modell für den binären Suchbaum.
        \item kennen Sie den Algorithmus zum Einfügen neuer Knoten.
    \end{smallitemize}
\end{lernzieleBox}

\section{Modellierung}
Um uns der Modellierung eines binären Suchbaums stückweise zu nähern, beginnen wir wiederum mit einem Beispiel eines bereits bestehenden Baums:
\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}]
        \node (root) {Ivy Quainoo}
            child {node {David Guetta}
                child {node {Boy}
                    child {node {AC/DC}}
                    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 {node {Silbermond}}
                    child[missing] {node {x}}
                }
            };
        \begin{pgfonlayer}{background}
            \node[draw=none,rectangle,rounded corners,fill=orange!50, fit=(root) (root-1) (root-2)] {};
            \node[draw=none,rectangle,rounded corners,fill=orange!50, fit=(root-1) (root-1-1) (root-1-2)] {};
        \end{pgfonlayer}
    \end{tikzpicture}
\end{center}
Um uns ein wenig Arbeit vorweg abzunehmen, beschäftigen wir uns bei der objektorientierten Modellierung vorerst nur mit den markierten fünf Elementen.

\begin{aufgabe}
    \begin{teilaufgaben}
        \teilaufgabe Geben Sie die Objektkarten für die markierten fünf Knoten des Baums an. Beachten Sie bei der Modellierung, dass die Knoten im restlichen Baum trotzdem als existent angesehen werden sollen. Denken Sie an Methoden, mit denen die Attribute ausgelesen werden können.

        \teilaufgabe Kennzeichnen Sie die Beziehungen zwischen den Objekten. Falls Beziehungen zu Objekten aufgebaut werden sollen, die außerhalb des markierten Bereichs liegen, so genügt es, wenn Sie einen stellvertretenden Text an die passende Stelle schreiben.
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    Wir beschränken uns bei der Modellierung an dieser Stelle auf die Interpreten der einzelnen Alben. Natürlich bräuchten wir für eine vollständige Implementierung noch weitere Attribute wie z.\,B. den Albumtitel.
    \begin{center}
        \scriptsize
        \begin{tikzpicture}[objektdiagramm]
            \node (wurzel) [objekt,text width=4cm] {
                \bfseries wurzel
                \nodepart[align=left]{two}
                interpret = \diastring{Ivy Quainoo}\\
                \attribut{kenntDavid}linkerNachfolger\\
                rechterNachfolger\attribut{kenntRihanna}
                \nodepart[align=left]{three}
                gibInterpret()\\
                gibLinkerNachfolger()\\
                gibRechterNachfolger()
            };

            \node (david) [objekt,text width=4cm, below left=1cm and -.7cm of wurzel] {
                \bfseries davidGuetta
                \nodepart[align=left]{two}
                interpret = \diastring{David Guetta}\\
                \attribut{kenntBoy}linkerNachfolger\\
                rechterNachfolger\attribut{kenntEisblume}
                \nodepart[align=left]{three}
                gibInterpret()\\
                gibLinkerNachfolger()\\
                gibRechterNachfolger()
            };

            \node (rihanna) [objekt,text width=4cm, below right=1cm and -.7cm of wurzel] {
                \bfseries rihanna
                \nodepart[align=left]{two}
                interpret = \diastring{Rihanna}\\
                linkerNachfolger\attribut{kenntMichel}\\
                rechterNachfolger\attribut{kenntOvertones}
                \nodepart[align=left]{three}
                gibInterpret()\\
                gibLinkerNachfolger()\\
                gibRechterNachfolger()
            };

            \node (boy) [objekt,text width=4cm, below left=1cm and -.7cm of david] {
                \bfseries boy
                \nodepart[align=left]{two}
                interpret = \diastring{Boy}\\
                \attribut{kenntACDC}linkerNachfolger
                \nodepart[align=left]{three}
                gibInterpret()\\
                gibLinkerNachfolger()
            };

            \node (eisblume) [objekt,text width=4cm, below right=1cm and -.7cm of david] {
                \bfseries eisblume
                \nodepart[align=left]{two}
                interpret = \diastring{Eisblume}\\
                \nodepart[align=left]{three}
                gibInterpret()
            };

            \node (acdc) [below=1cm of boy] {AC/DC};
            \node (michel) [below right=1cm and -1.7cm of rihanna] {Michel Telo};
            \node (overtones) [below right=2cm and -.4cm of rihanna] {The Overtones};

            \draw[-angle 60,thick] (kenntDavid) -| (david);
            \draw[-angle 60,thick] (kenntRihanna) -| (rihanna);
            \draw[-angle 60,thick] (kenntBoy) -| (boy);
            \draw[-angle 60,thick] (kenntEisblume) -| (eisblume);
            \draw[-angle 60,thick] (kenntACDC) -- ++ (-.3,0)  |- (acdc);
            \draw[-angle 60,thick] (kenntMichel) -| (michel);
            \draw[-angle 60,thick] (kenntOvertones) -| (overtones);
        \end{tikzpicture}
    \end{center}
\end{loesung}

Nachdem Sie sich klar gemacht haben, welche Attribute und Methoden die einzelnen Objekte benötigen, sollte es Ihnen möglich sein, daraus eine Klasse für die Knoten abzuleiten.

\begin{aufgabe}
    \begin{teilaufgaben}
        \teilaufgabe Entwerfen Sie eine Klasse für die Knoten des binären Suchbaums. Geben Sie lediglich an, über welche Attribute und Methoden die Klasse verfügen soll -- es geht hierbei \textbf{nicht} um eine konkrete Implementierung!

        \teilaufgabe Geben Sie nun den Aufbau für eine Klasse \lstinline!BinaererSuchbaum! an. Welche Methoden sollten für einen binären Suchbaum zur Verfügung stehen, damit er sinnvoll als Datenstruktur genutzt werden kann?
    \end{teilaufgaben}
\end{aufgabe}
\begin{loesung}
    Eine Lösung aus den Klassen Knoten und BinaererSuchbaum ist folgend dargestellt.
    \begin{center}
        \begin{tikzpicture}
            \footnotesize
            \node (knoten) [rectangle split, rectangle split parts=3, draw, align=center,text width=6cm] {
                \bfseries Knoten
                \nodepart[align=left]{two}
                interpret: Zeichenkette\\
                linkerNachfolger: Knoten\\
                rechterNachfolger: Knoten
                \nodepart[align=left]{three}
                Knoten(Zeichenkette interpret)\\
                gibInterpret(): Zeichenkette\\
                gibLinkenNachfolger(): Knoten\\
                gibRechtenNachfolger(): Knoten\\
                setzeLinkenNachfolger(Knoten k)\\
                setzeRechtenNachfolger(Knoten k)
            };
            \node (baum) [rectangle split, rectangle split parts=3, draw, align=center,text width=6cm,below=1cm of knoten] {
                \bfseries BinaererSuchbaum
                \nodepart[align=left]{two}
                wurzel: Knoten
                \nodepart[align=left]{three}
                fuegeKnotenEin(Knoten k)\\
                inOrderDurchlauf()\\
                gibWurzel()\\
            };
        \end{tikzpicture}
    \end{center}
\end{loesung}

\section{Neue Elemente braucht der Baum}
Kommen wir nun zurück zu unserer CD-Sammlung:
\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}]
        \node (root) {Ivy Quainoo}
            child {node {David Guetta}
                child {node {Boy}
                    child {node {AC/DC}}
                    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 {node {Silbermond}}
                    child[missing] {node {x}}
                }
            };
    \end{tikzpicture}
\end{center}
Da wir hier nur einen kleinen Ausschnitt unserer Sammlung betrachten, möchten wir nachträglich weitere Elemente zu dem gegebenen Baum hinzufügen können. Weil Sie sich gerade das neue Album von \enquote{Die Ärzte} gekauft haben, soll uns dieses hier als Beispiel dienen.

Wenn wir neue Elemente zu unserem Baum hinzufügen, ist es natürlich wichtig, dass die grundlegende Eigenschaft aus \autoref{eigBinBaum} dabei erhalten bleibt. Bevor wir -- Schritt für Schritt -- einen Algorithmus zum Einfügen neuer Elemente entwickeln, überlegen wir uns, an welcher Stelle das Element eingefügt werden muss.

\begin{aufgabe}
    Wir gehen davon aus, dass die bestehende Struktur des Baums so erhalten bleiben soll, wie sie ist. Überlegen Sie sich, wie das Einfügen eines neuen Knotens in einen binären Suchbaum abläuft. Greifen Sie im Zweifelsfall auf die Fragen im Nothelfer zurück!
\end{aufgabe}
\begin{loesung}
    Die Antworten beziehen sich auf die Fragen des Nothelfers, damit Sie die Lösung Stück für Stück nachvollziehen können.
    \begin{enumerate}
        \item + 2. Es gibt insgesamt 11~Möglichkeiten, den neuen Knoten einzufügen, ohne dabei die Eigenschaft aus \autoref{eigBinBaum} zu berücksichtigen. Der einzige passende Knoten ist jedoch der grün markierte.
        \begin{center}
            \scriptsize
            \begin{tikzpicture}[level distance=1.4cm,
                    level/.style={sibling distance=7cm/#1},
                    every node/.style={draw,ellipse,fill=white,text width=1.6cm, minimum height=.9cm, text centered},
                    leaf/.style={circle,fill=red,text width=.3cm,minimum height=0cm}]
                \node (root) {Ivy Quainoo}
                    child {node {David Guetta}
                        child {node {Boy}
                            child {node {AC/DC}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                        child {node {Eisblume}
                            child[level distance=1cm, sibling distance=1cm] {node[leaf,fill=green] {}}
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                    }
                    child {node {Rihanna}
                        child {node {Michel Telo}
                            child {node {Lana Del Rey}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                        child {node {The Overtones}
                            child {node {Silbermond}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                    };
            \end{tikzpicture}
        \end{center}

        \stepcounter{enumi}
        \item Die einzige richtige Möglichkeit ist als rechter Nachfolger von \enquote{Michel Telo}:
        \begin{center}
            \scriptsize
            \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},
                    leaf/.style={circle,fill=red,text width=.3cm,minimum height=0cm}]
                \node (root) {Ivy Quainoo}
                    child {node {David Guetta}
                        child {node {Boy}
                            child {node {AC/DC}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                        child {node {Eisblume}
                            child {node {Die Ärzte}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                    }
                    child {node {Rihanna}
                        child {node {Michel Telo}
                            child {node {Lana Del Rey}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf,fill=green] {}}
                        }
                        child {node {The Overtones}
                            child {node {Silbermond}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                                child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                            }
                            child[level distance=1cm, sibling distance=1cm] {node[leaf] {}}
                        }
                    };
            \end{tikzpicture}
        \end{center}
    \end{enumerate}
\end{loesung}

\begin{nothelferBox}
    \begin{enumerate}
        \item Wie viele Knoten kommen überhaupt als Vorgänger unseres Knotens \enquote{Die Ärzte} in Betracht, wenn wir dabei die Eigenschaft aus \ref{eigBinBaum} außer Acht lassen?

        \item Ordnen Sie den Knoten nun an der richtigen Stelle ein. \textbf{Tipp}: Überlegen Sie sich beispielsweise, ob der Knoten \enquote{Die Ärzte} im rechten oder linken Teilbaum der Wurzel untergebracht werden muss. Gehen Sie so schrittweise jeden weiteren Knoten ab, bis Sie an die Stelle gelangen, die die Eigenschaft aus \autoref{eigBinBaum} erfüllt.

        \item Gehen Sie nun erneut auf diese Weise vor und fügen Sie einen Knoten für \enquote{Nickelback} an der richtigen Stelle ein.

        \item Durchlaufen Sie die Knoten nach der \enquote{inorder}-Methode, um sicherzustellen, dass die richtige Reihenfolge bewahrt worden ist.
    \end{enumerate}
\end{nothelferBox}

Um hieraus nun einen allgemeingültigen Algorithmus zu entwickeln, gehen wir vorerst davon aus, dass der Baum \textbf{nicht leer} ist, so dass wir diesen Sonderfall ausschließen können. Betrachten Sie dazu folgenden Baum:
\begin{center}
    \footnotesize
    \begin{tikzpicture}[level distance=1cm,
            level/.style={sibling distance=5cm/#1},
            every node/.style={draw,circle,fill=white,text centered,text width=1em}]
        \node (root) {9}
            child {node {4}
                child {node {2}
                    child {node {1}}
                    child[missing] {node {x}}
                }
                child {node {5}}
            }
            child {node {18}
                child {node {13}
                    child {node {12}}
                    child {node[fill=blue!20,draw=black,dashed] {15} edge from parent[dashed]}
                }
                child {node {20}
                    child {node {19}}
                    child[missing] {node {x}}
                }
            };

        \node[above=.8cm of root,fill=blue!20] (fuenfzehn) {15};
        \draw[->,thick,dashed] (fuenfzehn) -- (root);
        \draw[->,thick,dashed,red,shorten >= 1cm] (root) ++ (.4,.4) -- +($(root-2) - (root)$);
        \draw[->,thick,dashed,green,shorten >= 1cm] (root) ++ (-.4,.4) -- +($(root-1) - (root)$);
  \end{tikzpicture}
\end{center}

\begin{aufgabe}
    In obigen Baum soll die Zahl~15 eingefügt werden. Die dafür vorgesehene Stelle ist bereits markiert. Da auf die Knoten im Baum (wie bei der linearen Liste) nur über die Wurzel zugegriffen werden kann, sollte das Einfügen eines neues Elementes dort beginnen. Stellen Sie sich vor, der Knoten~15 wird \enquote{von oben} auf die Wurzel geworfen und rollt dann -- je nach Knoten, die er währenddessen passiert -- nach links oder rechts.

    Zeichnen Sie anschließend ein Struktogramm (oder einen Programmablaufplan) für das Einfügen eines neuen Knotens. Es geht dabei \textbf{nicht} darum, dass Sie sich den konkreten Code überlegen.

    (Falls möglich: Nutzen Sie zur Erzeugung des Diagramms eine Werkzeug wie dia, LibreOffice Draw o.\,ä.)
\end{aufgabe}
\begin{loesung}
    Es ist möglich, die Methode rekursiv oder iterativ anzugehen.

    Zuerst wird die \textbf{rekursive Variante} vorgestellt:

    \begin{struktogramm}(155,55)[einfuegen(baum, eintrag)]
        \ifthenelse{7}{7}{eintrag kleiner als Eintrag in baum}{ja}{nein}
            \ifthenelse{2}{2}{hat baum einen linken Teilbaum}{ja}{nein}
                \sub{einfuegen(linker Teilbaum von baum, eintrag)}
            \change
                \assign{fuege einen neuen Knoten mit eintrag als linker Nachfolger von baum ein}
            \ifend
        \change
            \ifthenelse{2}{2}{hat baum einen rechten Teilbaum}{ja}{nein}
                \sub{einfuegen(rechter Teilbaum von baum, eintrag)}
            \change
                \assign{fuege einen neuen Knoten mit eintrag als rechten Nachfolger von baum ein}
            \ifend
        \ifend
    \end{struktogramm}

    \pagebreak
    Die \textbf{iterative Variante}:

    \begin{struktogramm}(155,80)[einfuegen(baum, eintrag)]
        \assign{setze tmp auf baum}
        \assign{setze gefunden auf falsch}
        \while{solange nicht gefunden}
            \ifthenelse{7}{7}{eintrag kleiner als Eintrag von tmp}{ja}{nein}
                \ifthenelse{2}{2}{hat tmp einen linken Teilbaum}{ja}{nein}
                    \assign{setze tmp auf linken Teilbaum von tmp}
                \change
                    \assign{fuege einen neuen Knoten mit eintrag als linker Nachfolger von tmp ein}
                    \assign{setze gefunden auf wahr}
                \ifend
            \change
                \ifthenelse{2}{2}{hat tmp einen rechten Teilbaum}{ja}{nein}
                    \assign{setze tmp auf rechten Teilbaum von tmp}
                \change
                    \assign{fuege einen neuen Knoten mit eintrag als rechten Nachfolger von tmp ein}
                    \assign{setze gefunden auf wahr}
                \ifend
            \ifend
        \whileend
    \end{struktogramm}

%     \begin{center}
%         \footnotesize
%         \begin{tikzpicture}[node distance=3cm, auto,every node/.style={scale=.8}]
%             \tikzstyle{block} = [rectangle, draw, fill=blue!20,text width=8.5em, text centered, minimum height=4em]
%             \node[startstop] (start) {Start};
%             \node[left of=start, node distance=4cm] (neu) {neuer Eintrag};
%             \node[block, below of=start] (anw1) {setze tmp auf Wurzel};
%             \node[decision, below of=anw1, node distance=8cm] (dec1) {neuer Eintrag kleiner als Eintrag in tmp?};
%
%             \node[decision, left of=dec1, node distance=6cm] (dec2) {hat tmp einen linken Nachfolger?};
%             \node[block, above of=dec2, node distance=4cm] (anw2) {setze tmp auf tmps linken Nachfolger};
%             \node[block, below of=dec2, node distance=5cm] (anw3) {fuege einen neuen Knoten als linken Nachfolger von tmp ein};
%
%             \node[decision, right of=dec1, node distance=6cm] (dec3) {hat tmp einen rechten Nachfolger?};
%             \node[block, above of=dec3, node distance=4cm] (anw4) {setze tmp auf tmps rechten Nachfolger};
%             \node[block, below of=dec3, node distance=5cm] (anw5) {fuege einen neuen Knoten als rechten Nachfolger von tmp ein};
%
%             % \node[startstop, right of=anw3, node distance=6cm] (stop) {Stop};
%
%             \path (anw3.east) --node[anchor=mid,startstop] (stop) {Stop} (anw5.west);
%
%             \path[line] (neu) -- (start);
%
%             \path[line] (start) -- (anw1);
%             \path[line] (anw1) -- node[near start,anchor=mid] (anker) {} (dec1);
%
%             \path[line] (dec1) -- node {ja} (dec2);
%             \path[line] (dec2) -- node[near start] {ja} (anw2);
%             \path[line] (dec2) -- node[near start] {nein} (anw3);
%
%             \path[line] (dec1) -- node {nein} (dec3);
%             \path[line] (dec3) -- node[near start] {ja} (anw4);
%             \path[line] (dec3) -- node[near start] {nein} (anw5);
%
%             \path[line] (anw2) |- (anker);
%             \path[line] (anw4) |- (anker);
%
%             \path[line] (anw3) -- (stop);
%             \path[line] (anw5) -- (stop);
%         \end{tikzpicture}
%     \end{center}
\end{loesung}

\section{Neue Elemente und die Folgen}
Nachdem wir nun in der Lage sind, neue Knoten zu einem binären Suchbaum hinzuzufügen, sollten wir uns Gedanken darum machen, welche Auswirkungen das Einfügen neuer Knoten auf einen binären Suchbaum haben kann.

\begin{aufgabe}[pcAufgabe]
    Experimentieren Sie mit der Darstellung eines binären Suchbaumes unter \url{https://visualgo.net/en/bst?mode=BST}. Erzeugen Sie Bäume mit verschiedenem Aussehen und überlegen sich, welche Auswirkungen das Aussehen der Bäume auf die Sucheigenschaft des Baums haben kann.
\end{aufgabe}
\begin{loesung}
    Das Einfügen bereits vorsortierter Knoten sorgt dafür, dass aus einem binären Suchbaum schnell annähernd eine lineare Liste wird. Dadurch verliert der Baum seinen Geschwindigkeitsvorteil beim Durchsuchen.
\end{loesung}

Wie Sie festgestellt haben, lassen sich relativ leicht Bäume erzeugen, die nicht mehr viel von den Vorteilen bieten, die unserer eigentlichen Idee des Binären Suchbaums zugrunde liegen. Im letzten Kapitel werden wir uns hierzu einige Möglichkeiten anschauen, wie dieses Problem angegangen werden kann.
% \newpage

\begin{lernkontrolleBox}
    \begin{kontrollaufgabe}
        Das Einfügen eines neuen Knotens kann die Eigenschaft des binären Suchbaums zerstören, dass alle Werte der Knoten im linken Teilbaum kleiner sind als der Wert der Wurzel.
        \begin{mcumgebung}
            \choice Richtig
            \choice[\mcrichtig] Falsch
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Ein binärer Suchbaum kann zu einer linearen Liste werden, je nachdem, in welcher Reihenfolge die Knoten eingefügt werden.
        \begin{mcumgebung}
            \choice[\mcrichtig] Richtig
            \choice Falsch
        \end{mcumgebung}
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \mcloesung
    \end{kontrollloesung}

    \begin{kontrollaufgabe}
        Gegeben ist der folgende binäre Suchbaum:
        \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) {12}
                    child {node {8}
                        child {node {5}
                            child {node {4}}
                            child[missing] {node {x}}
                        }
                        child[missing] {node {14}}
                    }
                    child {node {27}
                        child {node {14}
                            child[missing] {node {x}}
                            child {node {21}}
                        }
                        child {node {42}
                            child {node {29}}
                            child[missing] {node {x}}
                        }
                    };
            \end{tikzpicture}
        \end{center}
        Fügen Sie diesem Baum folgende Zahlen hinzu: 10; 6; 38; 49
    \end{kontrollaufgabe}
    \begin{kontrollloesung}
        \begin{center}
            \begin{tikzpicture}[level distance=10mm,
                    level/.style={sibling distance=55mm/#1},
                    every node/.style={draw,circle,fill=white,text width=1em,text centered},
                    level 1/.style={sibling distance=60mm},
                    level 2/.style={sibling distance=30mm},
                    level 3/.style={sibling distance=15mm}]
                \node (root) {12}
                    child {node {8}
                        child {node {5}
                            child {node {4}}
                            child[green,thick] {node {6}}
                        }
                        child[green,thick] {node {10}}
                    }
                    child {node {27}
                        child {node {14}
                            child[missing] {node {x}}
                            child {node {21}}
                        }
                        child {node {42}
                            child {node {29}
                                child[missing] {node{x}}
                                child[green,thick] {node {38}}
                            }
                            child[green,thick] {node {49}}
                        }
                    };
            \end{tikzpicture}
        \end{center}
    \end{kontrollloesung}
\end{lernkontrolleBox}

\newpage

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

\paragraph{Lernkontrolle}$~$\\

\printsolutionstype[chapter=\thechapter]{kontrollaufgabe}