Unsere Datenschutzrichtlinie wird in Kürze aktualisiert. Bitte sehen Sie sich die Vorschau an.

Grundlagen der Programmierung: Datenstrukturen

Binäre Suchbäume

Testen Sie unsere 2016 Kurse

10 Tage kostenlos!

Jetzt testen Alle Abonnements anzeigen
Binäre Suchbäume sind Datenstrukturen, die ihre Stärken im Zusammenhang mit sortierten Ein- und Ausgaben ausspielen können und somit einen erheblichen Performancevorteil bieten.

Transkript

Wenn wir über die spezielle Art des binären Baums, den binären Suchbaum, sprechen wollen, müssen wir uns mit weiteren Begriffen vertraut machen. Bei einem binären Baum können nicht mehr als zwei unmittelbare Kindknoten an einen Elternknoten kommen. Die können aber ihrerseits wieder Kindknoten haben und die können wieder Kindknoten haben, müssen aber nicht zwei Kindknoten haben, können auch nur einen Kindknoten haben oder ein Knoten hat gar keinen weiteren Kindknoten, dann wird er als Blatt bezeichnet. Warum es diese Einschränkungen gibt? Sie sorgt für etwas mehr Klarheit. Wir wissen, dass in einem binären Baum jedes Knotenobjekt nur zwei Links haben kann. Nur zwei Referenzen zu Kindern. Es wird kein willkürliches Büschel an Links erzeugt, also keine 14 Links weg von einem Knoten, es sind immer nur zwei. Und in einem binären Suchbaumknoten haben diese beiden Links spezielle Namen. Nämlich linkes Kind, wenn es auf der linken Seite weggeht, und rechtes Kind, wenn es auf der rechten Seite weggeht. Aber diese Links können auch den Wert Null haben. Das bedeutet, dass sie keine Kinder haben. Ein solcher Knoten ist dann einfach nur ein Blatt. Oder das linke Kind verweist auf einen anderen Knoten. Oder der Link des rechten Kinds verweist auf einen weiteren Knoten. Oder beide verweisen auf einen weiteren Knoten. Warum arbeite ich jetzt so massiv mit Verweisen? Weil in einem binären Suchbaum wichtig ist, ob ein Knoten an den linken oder an den rechten Kindknoten angefügt wird. Und es ist nicht nur – Oh, es ist der erste linke Knoten, den tun wir links hin, das ist der zweite, den tun wir rechts hin – nein. Es herrscht eine Gesetzmäßigkeit dahinter, ob ein Kindknoten links oder rechts dazugefügt werden kann. Denn ein links angefügter Kindknoten muss niedriger sein als sein Elternknoten. Und ein rechts angefügter Knoten muss höher sein als sein Elternknoten. Wenn wir einen neuen Knoten mit Werten einfügen, müssen wir also immer genau auf diese Regel achten. Bei meinem Beispiel verwende ich Integer-Zahlen als Repräsentation dessen, was im Knoten gespeichert ist. Ein binärer Suchbaum wird oft verwendet, um Schlüssel-Wert-Paare zu sortieren, wie in einem assoziativen Array. Wir sehen hier also den Schlüssel zum eigentlichen Objekt. Und der Schlüssel, der gespeichert wird, damit wir ihn reihen und sortieren können und so in diesen binären Suchbaum abspeichern. Es muss jeder Eintrag hier einzigartig sein. Sie können keine doppelten Schlüssel haben, genau so wie Sie keine doppelten Schlüssel in Hash-Tabellen oder in Arrays haben können. Wir erzeugen einen binären Suchbaum durch das Hinzufügen eines Knotens, einem Schlüssel-Wert-Paar. Sagen wir mal, der Schlüssel ist 50 und der Wert Wurzelknoten. Dann wollen wir einen neuen Knoten hinzufügen. Der hat einen Schlüssel 25. Der binäre Suchbaum evaluiert nun und sagt: Gut, das ist weniger als der Wurzelwert, das wird zum linken Kind. Dann fügen wir einen anderen Knoten hinzu. Dieser hat den Schlüssel 100. Er wird ausgewertet. Da er größer als der Wurzelwert ist, gehen wir auf der rechten Seite weiter nach unten und lagern dort unsere 100 ab. Der nächste Wert ist die 75. Die 75 ist höher als die 50, wir gehen also rechts weiter runter in Gedanken, und es ist niedriger als die 100, also wird's das linke Kind von der 100. Der nächste Knoten, eine 30. Eine 30 ist niedriger als 50, also niedriger als der Wurzelknoten. Das heißt, er kommt auf der rechten Seite weiter runter. Aber es ist höher als 25. Jetzt haben wir von der 25 also wieder einen rechten Knoten. Lassen Sie uns einen niedrigeren Wert einfügen. Der Wert 10. Der Wert ist also niedriger als 50, also kommt er auf die linke Seite, er ist auch niedriger als 25, also kommt er auch auf die linke Seite der 25. Der Wert 1000. 1000 ist höher als 50, also rechts, höher als 100, also rechts, also wandert er auf der rechten Seite weiter nach unten. 2000. Noch höher. Wieder dasselbe. Er wandert solange nach unten auf der rechten Seite. Zu guter Letzt noch die 3000. Ebenfalls. Gut! Wir haben jetzt also einen Suchbaum erzeugt. Spannend wird das Ganze ja erst, wenn ich nach einem Wert wieder suche, denn dadurch, dass alles sortiert abgelegt wird, kann ich jetzt natürlich auch ganz gezielt suchen. Ich suche den Wert 2000. Ich fange also beim Wurzelknoten an. Der Wurzelknoten sagt, ich bin 50, das ist niedriger. Jetzt weiß ich schon, dass ich einfach auf der rechten Seite weitergehen muss. 100. Mein 2000 ist auch höher als 100, das heißt, ich gehe wieder auf der rechten Seite weiter. 2000 ist auch höher als 1000. Ich gehe wieder rechts weiter, bis ich eben zu dem Wert komme, den ich suche, oder den Wert nicht finden kann, weil es ihn da drin nicht gibt. Aber dadurch, dass ich so gezielt in der Baumstruktur suchen kann, spare ich mir sehr viel zusätzliche Sucharbeit, weil ich die anderen Zweige, im wahrsten Sinne des Wortes, links liegen lassen kann. Ein weiterer Vorteil beim binären Suchbaum ist der, dass einfach immer sortiert ist. Wenn wir die Elemente in einer Reihe von links nach rechts wieder ausgeben, bekommen wir sie in der richtigen Reihenfolge wieder ausgegeben. Sie haben vielleicht noch gemerkt, dass wir auf der rechten Seite mehr Knotenpunkte haben als auf der linken. Es ist nicht unüblich, dass so was passiert. Wir können keine Garantie dafür abgeben, dass die Art, wie wir Daten hinzufügen, bis ganz nach unten zu einem perfekt symmetrischen Baum führen wird. In dem Fall sagen wir, dass es sich um einen unausgeglichenen oder auch unausbalancierten Suchbaum handelt. Es sind mehr Level auf der einen als auf der anderen Seite. Die Kehrseite davon ist, im Durchschnitt müssen wir mehr Checkdurchläufe zum Einfügen und Entfernen auf der rechten Seite machen, als wir's auf der linken machen müssen. Aber, nicht vergessen: Wir sprechen ja von einer abstrakten Idee eines binären Suchbaums als Datenstruktur. Und es ist klar, dass es verschiedene Umsetzungen der binären-Suchbaum-Idee gibt, welche selbst ausbalancierende binäre Suchbäume sind. Sie beinhalten zusätzliche Algorithmen, die dafür sorgen, falls der Baum schief zu werden beginnt, was unweigerlich passieren kann, so wird dafür gesorgt, dass es zu einer Neuorganisation mit einer gleichmäßigeren Aufteilung der Level-Anzahlen geben kann. Das kann so einfach sein, wie das Verändern der Position des Wurzelknotens, um den gesamten Baum neu auszurichten. Aber die wichtige Idee der Balance bei einem binären Suchbaum ist nicht die, dass wir immer zwei Kindknoten brauchen. Das ist völlig egal. Es ist wichtig, dass die Anzahl an Ebenen ungefähr gleich ist. Wir haben dann also nicht drei Ebenen auf der einen und 20 auf der anderen. Wenn Sie anfangen, binäre Suchbäume einzusetzen, werden Sie unterschiedlichen, selbst balancierenden, binären Suchbaum-Algorithmen begegnen, die so schöne Namen haben wie Red Black Trees oder AVL Trees oder Adison Velsky Landis Tree. Scapegoat Trees oder Splay Trees. In diesem Videotraining werde ich aber nicht tiefer in die Materie eintauchen, denn das würde uns vom Thema Datenstrukturen weg und hin zu Algorithmen führen, die eben diese Datenstrukturen managen. Das würde aber zu sehr in die Tiefe führen. Das ist wahrscheinlich ein Bereich, wo Sie noch eine ganze Menge wunderbarer PhDs ablegen könnten. Was sind also die Hauptvorteile? Nun, im binären Suchbaum ist es so, dass ich schnell einfügen und auch schnell Daten wieder ausgeben kann. Gut. Hash-Tabellen können das genauso. Das ist absolut gut und richtig so. Aber weil binäre Suchbäume immer sortiert bleiben, und Hash-Tabellen eben nicht, ist das ein Punkt, wo der binäre Suchbaum seine Vorteile sozusagen voll und ganz ausspielen kann. Und wenn wir anfangen, uns ganz bestimmte Sprachen anzusehen, werden wir feststellen, dass Bäume ein Gebiet sind, in denen Sie nicht so viel direkte Sprachunterstützung erwarten würden wie bei anderen Datenstrukturen. Typischerweise instanzieren Sie kein Objekt aus einem binären Suchbaum heraus. Denn wir kommen in ein Gebiet, in dem binäre Suchbäume zwar verwendet werden, aber hinter dem Vorhang, um andere Datenstrukturen einzusetzen. In C++ ist die Umsetzung einer Set-Datenstruktur mit Hilfe eines binären Suchbaums gestaltet. Sie müssen sich aber wie gesagt nicht weiter drum kümmern. Sie müssen nicht über linke Kindknoten und rechte Kindknoten nachdenken oder darüber, wie Sie ausbalancieren können oder nicht. Das erledigt das Programm für Sie. Sie verwenden einfach das Set. Ähnlich ist es in C# und in .NET-Umgebungen, wo es keine binären Suchbaumklassen gibt, aber wenn Sie ein sortiertes Dictionary verwenden, eine Sammlung mit Schlüssel-Wert-Paaren, mit geordneten Schlüsseln, dann kommt eine binäre Suchbaum- Variation zum Einsatz, um diese Idee umzusetzen. Und auch wenn Dictionaries oft mit Hash-Tabellen umgesetzt werden: In dem Moment, wo Schlüssel sortiert werden müssen, worin Hash-Tabellen nicht wirklich ihre Stärke haben, dann kommen ebenso binäre Suchbäume zum Einsatz. Ruby hat keinen eingebauten Suchbaum-Datenstruktur-Ansatz. Es gibt Umsetzungen von Drittanbietern. Bei Python ist es genauso. Es hat eine eigene eingebaute Baum-Datenstruktur. Mit Java haben wir Klassen wie TreeMap. Diese speichern eine Sammlung von Schlüssel-Wert-Paaren, aber wenn Sie sich dann einige von den Dokumentationen durchlesen, werden die Ihnen sagen, dass dies eben ein Red Black Tree ist. Das ist eine sich selbst ausbalancierende binäre Suchbaum-Version. So. Das ist jetzt alles, was ich über binäre Suchbäume sagen werde. Dabei ist mir aber völlig klar, dass wir gerade an der Spitze des Eisbergs gekratzt haben.

Grundlagen der Programmierung: Datenstrukturen

Erhalten Sieeinen klaren Eindruck von Datenstrukturen und deren Eigenheiten und verstehen, wie Sie diese am besten einsetzen können – ganz unabhängig von den einzelnen Programmiersprachen.

2 Std. 51 min (29 Videos)
Derzeit sind keine Feedbacks vorhanden...
 

Dieser Online-Kurs ist als Download und als Streaming-Video verfügbar. Die gute Nachricht: Sie müssen sich nicht entscheiden - sobald Sie das Training erwerben, erhalten Sie Zugang zu beiden Optionen!

Der Download ermöglicht Ihnen die Offline-Nutzung des Trainings und bietet die Vorteile einer benutzerfreundlichen Abspielumgebung. Wenn Sie an verschiedenen Computern arbeiten, oder nicht den ganzen Kurs auf einmal herunterladen möchten, loggen Sie sich auf dieser Seite ein, um alle Videos des Trainings als Streaming-Video anzusehen.

Wir hoffen, dass Sie viel Freude und Erfolg mit diesem Video-Training haben werden. Falls Sie irgendwelche Fragen haben, zögern Sie nicht uns zu kontaktieren!