Binäre Bäume - Suchverfahren 1
Was ist ein Binärbaum?
Zu Beginn erst mal: Was ist ein Binärbaum?
Ein Binärbaum ist grob gesagt eine Datenstruktur, also ein Objekt zur Organisation und Speicherung
von Daten.
Wie sieht ein Binärbaum aus?
So warum heißt das ganze jetzt Binärbaum?
Weil er grün ist oder Sauerstoff produziert?
Nope!
Erstmal weil der Aufbau stark an den eines Baum erinnert.
Es gibt immer einen Wurzelknoten.
Der besteht wiederum aus weiteren Nachkommen.
Diese Nachkommen haben dann wieder Nachkommen und so weiter.
Wat ne endless Story.
Wäre jetzt ja ziemlich langweilig wenn die Knoten da so leer rumstehen würden.
Deswegen enthält jeder Knoten nen Wert der gepseichert werden soll.
Was hat jetzt das Binär im Namen zu suchen?
Binär kennen wir ja schon vom Binärsystem.
Das bedeutet jetzt nix anderes, als dass der Vaterknoten höchstens zwei Nachkommen haben
kann.
Zu verwirrend?
Machen wirs einfach!
Stellt euch einen Vater ,oder auch ne Mama,vor.
Der hat jetzt wiederum zwei Kinder.
Von diesen Kinder haben beide wieder zwei Kinder und so weiter...
Das ganze erinnert also stark an den Stammbau einer großen Familie.
Gut, jeweils nur mit zwei Kindern aber hey, reicht doch.
Wie ist ein Binärbaum aufgebaut?
So da wir jetzt wissen was ein Binärbaum genau ist, können wir uns jetzt anschauen
wie er aufgebaut ist.
Wie schon gesagt gibt es immer einen Wurzelknoten, worauf der Baum aufbaut.
Dieser ist durch sogenannte Kanten mit höchstens zwei Kindsknoten verbunden.
Diese Kindsknoten können jetzt wieder durch Kanten mit anderen Knoten verbunden sein.
Natürlich dürfen es wieder höchstens zwei sein.
Diese Knoten mit einem Vorfahren und weiteren Kindsknoten nennt man auch innere Knoten oder
Elternknoten.
Alles hat ein Ende nur die Wurst hat zwei... so auch der Binärbaum.
Wenn keine Werte mehr vorhanden sind, gibt es irgendwann Knoten ohne Nachkommen.
Die werden genauso bezeichnet wie beim Baum, nämlich Blätter.
Auf der anderen Seite werden Knoten die nur ein Blatt als Kind haben, Halbblatt genannt.
Heißt also quasi, dass der Elternknoten nur ein Kind hat und das Kind als Einzelkind aufwächst.
Außerdem kann unser Baum jetzt noch aus mehreren Teilbäumen bestehen.
Zum Beispiel aus einem Linken und einem Rechten.
Genauso wie im richtigen Leben können diese Bäume jetzt auch eine unterschiedliche Höhe
besitzen.
Wenn ein Baum leer ist, hat er eine Höhe von 0.
Die Wurzel liegt dabei immer auf Höhe 1.
Wie langweilig wäre es denn wenn jeder Baum gleich aussehen würde?
Damit das nicht passiert gibt es jetzt noch unterschiedliche Binärbäume.
Ein Binärbaum heißt zum Beispiel geordnet, wenn der linke Kindsknoten kleiner und der
rechte Kindsknoten größer als der Elternknoten ist.
So zum Beispiel.
Ihr seht hier, dass alles was kleiner als 5 ist links steht.
Die Werte die größer als 5 sind, stehen in dem Fall rechts davon.
Genauso funktioniert es bei der 8.
Da die 7 kleiner ist, steht sie links.
Die 10 steht dagegen rechts von der 8, da sie größer ist.
Das heißt also geordnet.
Eigentlich ganz logisch oder?
Außerdem muss gelten, dass jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes
Kind besitzt.
Ein Binärbaum kann außerdem voll sein.
Nein, nicht betrunken!
Ein Binärbaum ist voll, wenn er maximal besetzt ist.
Also wenn jeder Knoten entweder ein Blatt oder zwei Kinder besitzt.
Zuletzt kann ein Baum noch vollständig sein.
Das heißt nix anderes ,als dass jedes Blatt sich auf der gleichen Höhe befindet.
Bei so einem Baum kann die Anzahl der Knoten auch ganz einfach durch die Höhe abgeleitet
werden.
Nämlich mit der Formel 2^h – 1.
Wie man im Beispiel sieht, ist die Höhe 3.
Somit kommt man mit der Formel auf 7 Knoten.
So damit das Ganze jetzt noch ein bisschen verständlicher wird machen wir nochmal ein
kleines Beispiel.
Wir haben jetzt unsere Werte [5,3,1,6,8,10].
Unsere Aufgabe ist daraus einen Binärbaum zu machen.
Ein beliebiger Binärbaum dazu, könnte also so aussehen.
Natürlich gibt es dazu noch andere Lösungen.
Wenn wir jetzt einen geordneten Baum dazu aufbauen wollen, müssen wir uns an die Regeln
halten, die wir vorher schon gelernt haben.
Dies sieht wiederum so aus.
Ihr seht das die Werte links von der 6 alle kleiner und die Werte rechts davon alle größer
sind.
Genauso sieht es in den Teilbäumen aus.
Die 1 ist beispielsweise kleiner als 3 und die 5 ist größer.
Also steht die 1 links von der 3 und die 5 rechts.
Alles klar soweit?
Natürlich waren das jetzt nur die Grundlagen.
Mit Binärbäumen lässt sich noch viel mehr anfangen, aber das schauen wir uns in den
nächsten Videos noch genauer an.
So was solltet ihr jetzt auf jeden Fall zu Binärbäumen wissen?
Ein Binärbaum ist grob gesagt eine Datenstruktur, also ein Objekt zur Organisation und Speicherung
von Daten.
Sie setzen sich aus Knoten zusammen, die wiederum Werte enthalten.
Ein Knoten kann maximal zwei Nachkommen haben.
Es gibt Wurzelknoten, Elternknoten, Blätter und Halbblätter.
Ein Binärbaum kann wieder aus mehreren Teilbäumen bestehen.
Binärbäume können geordnet, voll und vollständig sein.
Wollt ihr jetzt noch wissen was man alles mit Binärbäumen machen kann und wie das
genau mit dem Einfügen und Löschen von Knoten funktioniert,
schaut euch doch gleich das nächste Video dazu an!
Ich geh mir jetzt nochmal richtige Bäume anschauen!
Macht es gut!
