% 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{Additum -- Ein paar Schritte weiter} \begin{uebersichtBox} Dieses Kapitels gibt einen kleinen Ausblick in weitere Bereiche. Die einzelnen Punkte sind exemplarisch und gehen nicht in die Tiefe. \end{uebersichtBox} \section{Eine Effizienzanalyse} Als Informatiker ist man immer sehr daran interessiert zu erfahren, wie aufwändig ein neues Verfahren ist. Gerade im Zusammenhang mit großen Datenmengen ist die Effizienz eines Algorithmus überaus wichtig. Wir wollen in diesem Abschnitt eine Effizienzanalyse für die binäre Suche durchführen. Vom intuitiven Verständnis her ist Ihnen sicher schon klar, dass die binäre gegenüber der linearen Suche schneller zu Ergebnissen führt. Generell kann man sagen, dass bei man bei der linearen Suche in $n$ verschiedenen Elementen im Schnitt ca. $n/2$ Elemente betrachten muss, im schlimmsten Fall (\emph{worst case}) sogar $n$ Elemente. \begin{aufgabe} Wir wollen folgende Frage beantworten: Wie viele Versuche benötigt man im Schnitt bei der binären Suche in einer Menge mit $n$ Elementen? Gehen Sie zur Beantwortung dieser Frage folgendermaßen vor: \begin{itemize} \item Wie viele Elemente können Sie mit einem einzigen Vergleich durchsuchen? \\ Wir gehen ab jetzt übrigens immer davon aus, dass das gesuchte Element auch tatsächlich in der Menge vorhanden ist! \item Verdopplen nun die Anzahl der Vergleiche: \\Wie viele Elemente können Sie mit zwei Vergleichen durchsuchen? \item Dieses Spiel setzen Sie nun fort. \\Wie viele Elemente können mit drei, vier, fünf, \ldots Ver\-gleichen durchsucht werden? Untersuchen Sie, ob Sie einen mathematischen Zusammenhang finden. \item Nun nehmen Sie, dass Sie eine Menge mit $n$ Elementen durchsuchen möchten. Setzen Sie jetzt das Ergebnis aus der vorherigen Aufgabe in Zusammenhang mit der Zahl $n$. Beantworten Sie anschließend die folgende Frage: \\ Wie viele Vergleiche benötigt man, um $10.000$~CDs zu durchsuchen? \end{itemize} \end{aufgabe} \begin{loesung} Angenommen, unsere Liste besteht aus zwei Elementen, A und B. Mit einem einzigen Vergleich kann man nun eines dieser beiden Elemente finden: Betrachtet man zuerst Element~B und vergleicht es mit dem gesuchten Element, so gibt es zwei Möglichkeiten: \begin{enumerate}[label=\bfseries{Fall ~\arabic*:}, left= 0pt] \item B ist das gesuchte Element, unsere Suche endet hier. \item B ist nicht das gesucht Element. Da wir vorausgesetzt haben, dass das gesuchte Element in der Liste vorhanden sein \textbf{muss}, ist das andere Element der Liste das gesuchte. \end{enumerate} Nun gehen wir den umgekehrten Weg und fragen uns: Wie viele Elemente kann ich mit $x$ Vergleichen durchsuchen? Nehmen wir nun zwei Vergleiche: Es ist bekannt, dass man mit einem Vergleich zwei Elemente durchsuchen kann. Da sich mit jedem Vergleich die Menge der noch zu durchsuchenden Elemente halbiert, muss man demnach mit zwei Vergleichen vier Elemente durchsuchen können. Veranschaulichen wir dies: \begin{center} \begin{tikzpicture}[every node/.style={text centered, text width=1.5em, minimum height=2em,draw,rectangle}] \node (A) {A}; \node[right=0cm of A] (B) {B}; \node[right=0cm of B] (C) {C}; \node[right=0cm of C] (D) {D}; \end{tikzpicture} \end{center} Angenommen, wir suchen nach Element~A. Wir beginnen unsere Suche bei Element~C: \begin{center} \begin{tikzpicture}[every node/.style={text centered, text width=1.5em, minimum height=2em,draw,rectangle}] \node (A) {A}; \node[right=0cm of A] (B) {B}; \node[right=0cm of B,fill=green] (C) {C}; \node[right=0cm of C] (D) {D}; \end{tikzpicture} \end{center} Wir wissen nun, dass das gesuchte Element im linken Teil der Liste liegen muss. Demnach schließen wir C und D aus und betrachten nun B: \begin{center} \begin{tikzpicture}[every node/.style={text centered, text width=1.5em, minimum height=2em,draw,rectangle}] \node (A) {A}; \node[right=0cm of A,fill=green] (B) {B}; \node[right=0cm of B,black!40] (C) {C}; \node[right=0cm of C,black!40] (D) {D}; \end{tikzpicture} \end{center} Dieses schließen wir ebenfalls aus, da es nicht das gesuchte Element ist und wissen demnach, dass das gesuchte A links vom B stehen muss. Man sieht also: Mit zwei Vergleichen kann man vier Elemente durchsuchen -- immer vorausgesetzt, dass das Element auch in der Liste vorhanden ist. Dies kann man nun fortsetzen: \begin{center} \begin{tabular}{r|l} \bfseries Vergleiche & \bfseries Anzahl Elemente\\\hline 1 & 2\\ 2 & 4\\ 3 & 8\\ 4 & 16\\ \vdots & \vdots\\ $x$ & $2^x$ \end{tabular} \end{center} Da sich die Anzahl der durchsuchbaren Elemente mit jedem Schritt verdoppelt, ergibt sich die Anzahl der durchsuchbaren Elemente für $x$ Vergleiche somit als $2^x$. Kehren wir nun zu unserer Frage aus der Aufgabenstellung zurück: \textbf{Wie viele Vergleiche braucht man maximal für $10.000$~Elemente?} Wir können dies nun in Form einer mathematischen Gleichung ausdrücken: \[ 2^x = 10.000\] Um diese Gleichung lösen zu können, brauchen wir den \emph{Logarithmus} als Hilfsmittel. Dann können wir die Gleichung schreiben als: \[ \log_210.000 = x\] Oder, um es besser in den Taschenrechner eingeben zu können: \[ \frac{\log 10.000}{\log 2}=x,\] wobei $\log$ der Logarithmus zur Basis~10 ist. Damit ergibt sich $x\approx 13,288$. Da wir immer nur ganz Vergleiche betrachten können, runden wir das Ganze somit zu 14 Vergleichen auf. Diese 14~Vergleiche müssen nun im Kontrast gesehen werden zur linearen Suche, die für 10.000~Elemente im Schnitt 5.000~Schritte benötigen würde. \end{loesung} \section{Rückwärts durch den Baum} Sie haben in Kapitel~2 den \enquote{in order}-Durchlauf durch einen Baum kennen gelernt. An dieser Stelle können Sie Ihr Wissen erneut überprüfen: \begin{aufgabe} Entwickeln Sie einen Algorithmus, um einen Baum in umgekehrter Reihenfolge ausgeben zu lassen. \end{aufgabe} \begin{loesung} Der Algorithmus basiert auf dem Wissen, dass das größte Element in einem binären Suchbaum immer ganz rechts außen platziert ist. Bedenkt man dies und die Vorgehensweise beim \enquote{in order}-Durchlauf, so ergibt sich der folgende Algorithmus: \begin{itemize} \item Steige an der Wurzel in den Baum ein. \item Mache für jeden Knoten von der Wurzel aus folgende Schritte: \begin{itemize} \item Steige in den \textbf{rechten} Teilbaum ein und beginne für jeden Knoten diese Abfolge von Schritten. Ist der rechte Teilbaum leer, gehe zum nächsten Schritt. \item Gib den Knoten aus. \item Steige in den \textbf{linken} Teilbaum ein und beginne für jeden Knoten diese Abfolge von Schritten erneut. \end{itemize} \end{itemize} \end{loesung} Diesen Algorithmus nennt man den \enquote{reverse in-order}-Durchlauf. \section{Knoten löschen} Den Algorithmus zum Einfügen von Knoten haben Sie bereits in Kapitel~3 erarbeitet. Da der binäre Suchbaum als dynamische Datenstruktur fungieren soll, die sich regelmäßig verändert, wird natürlich ebenfalls eine Operation zum Löschen von Knoten benötigt. Diese erarbeiten Sie sich in der folgenden Aufgabe. \begin{aufgabe} Machen Sie sich Gedanken, wie das Löschen eines Knotens in einem binären Suchbaums zu bewerkstelligen ist. Unterscheiden Sie dabei zwischen verschiedenen Fällen, die auftreten können: \begin{itemize} \item Der Knoten hat keine Nachfolger. \item Der Knoten hat nur einen linken oder rechten Teilbaum. \item Der Knoten hat sowohl einen linken als auch einen rechten Teilbaum. \end{itemize} Es geht in dieser Aufgabe nicht darum, dass die Bäume nach den Löschoperationen wieder ausgeglichen werden (da es passieren kann, dass die Balance verletzt wird), sondern wirklich nur um den Löschvorgang an sich! \end{aufgabe} \begin{loesung} Wir überlegen uns unser Vorgehen am Beispiel des folgenden Suchbaums: \begin{center} \begin{tikzpicture}[level distance=1cm, every node/.style={draw,circle,text width=1.1em,text centered}, level 1/.style={sibling distance=8cm,nodes={}}, level 2/.style={sibling distance=4cm,nodes={}}, level 3/.style={sibling distance=2cm,nodes={}}] \node[circle, draw] (root) {42} child {node {25} child {node {9} child {node {2}} child {node {12}} } child {node {29}} } child {node {64} child {node {50} child[missing] {node {44}} child {node {53}} } child {node {72} child {node {70}} child {node {82}} } }; \end{tikzpicture} \end{center} \begin{description} \item[Fall~1:] Wir löschen den Knoten mit dem Wert~70. Da dieser Knoten ein Blatt ist, müssen wir nichts weiter beachten und können den Knoten einfach aus dem Baum entfernen. Daraus entsteht der folgende Baum: \begin{center} \begin{tikzpicture}[level distance=1cm, every node/.style={draw,circle,text width=1.1em,text centered}, level 1/.style={sibling distance=8cm,nodes={}}, level 2/.style={sibling distance=4cm,nodes={}}, level 3/.style={sibling distance=2cm,nodes={}}] \node[circle, draw] (root) {42} child {node {25} child {node {9} child {node {2}} child {node {12}} } child {node {29}} } child {node {64} child {node {50} child[missing] {node {44}} child {node {53}} } child {node {72} child[black!30] {node {70}} child {node {82}} } }; \end{tikzpicture} \end{center} \item[Fall~2:] Wir löschen den Knoten mit dem Wert~50. Dieser Knoten hat nur einen rechten Teilbaum. Wir können den Teilbaum somit einfach \enquote{umhängen}, indem wir an die Stelle der 50 die Wurzel des rechten Teilbaums setzen (in diesem Fall nur ein Knoten). Es entsteht der folgende Baum: \begin{center} \begin{tikzpicture}[level distance=1cm, every node/.style={draw,circle,text width=1.1em,text centered}, level 1/.style={sibling distance=8cm,nodes={}}, level 2/.style={sibling distance=4cm,nodes={}}, level 3/.style={sibling distance=2cm,nodes={}}] \node[circle, draw] (root) {42} child {node {25} child {node {9} child {node {2}} child {node {12}} } child {node {29}} } child {node {64} child {node {53} child[missing] {node {44}} child[black!20] {node {53}} } child {node {72} child[missing] {node {70}} child {node {82}} } }; \end{tikzpicture} \end{center} \item[Fall~3:] Der komplexeste Fall tritt ein, wenn ein Knoten gelöscht werden soll, der sowohl einen linken als auch rechten Teilbaum hat. In diesem Fall stellt sich die Frage, welche Knoten aus den Teilbäumen den gelöschten ersetzen soll. Betrachten wir nochmals den Baum: \begin{center} \begin{tikzpicture}[level distance=1cm, every node/.style={draw,circle,text width=1.1em,text centered}, level 1/.style={sibling distance=8cm,nodes={}}, level 2/.style={sibling distance=4cm,nodes={}}, level 3/.style={sibling distance=2cm,nodes={}}] \node[circle, draw] (root) {42} child {node {25} child {node {9} child {node {2}} child {node {12}} } child[green,thick] {node {29}} } child {node {64} child[thick,green] {node {53} child[missing] {node {44}} child[missing] {node {53}} } child {node {72} child[missing] {node {70}} child {node {82}} } }; \end{tikzpicture} \end{center} Es wurden die beiden Knoten markiert, die als potentielle Ersatzknoten in Frage kommen: Entweder der größte Knoten aus dem linken Teilbaum (da alle Knoten links der Wurzel kleiner sein müssen als diese) oder der kleinste Knoten rechts im Teilbaum (da alle Knoten rechts der Wurzel größer sein müssen als diese). Hätte man beispielsweise den Knoten~12 als Ersatz für die Wurzel genommen, wäre diese Eigenschaft unmittelbar verletzt worden, da der linke Nachfolger~25 größer ist als die 12. Es gibt somit zwei Möglichkeiten, den Wurzelknoten zu ersetzen. \textbf{Achtung:} Die Knoten, die aus dem Baum entfernt werden, haben möglicherweise noch einen anhängenden Teilbaum. Dieser muss dann wiederum -- entsprechend Fall~2 -- gelöscht werden. \end{description} \end{loesung} \newpage \begin{loesungenBox} \end{loesungenBox} \printsolutionstype[chapter=\thechapter]{aufgabe}