26.08.2019
Binäre Suchbäume (BSB - engl. ‘binary search tree’) sind eine typische Baumstruktur und werden für schnelle Datenzugriffe für viele verschiedene Operationen genutzt. Sie bestehen aus Knoten mit jeweils null bis zwei Kinderknoten und einen festen Wurzelknoten, ganz oben wie hier gezeigt. Neue Knoten können laufend eingefügt werden, und auch wieder entfernt werden, während die guten Performanzeigenschaften gewart werden. Gelegentlich ist eine Ausbalancierung des Baumes notwendig, mehr dazu später. Die hier gezeigten Bäume speichern ganze Zahlen bis 200. Tatsächlich können jede Art Daten durch Referenz im BSB gespeichert werden, und die Reihenfolge ist durch einen Schlüssel gegeben: eine ganze Zahl wird jedem Objekt zugeordnet.
Die auf dieser Seite gezeigten Bäume sind zur besseren Darstellung in ihrer Höhe begrenzt. Die Höhe ist definiert als die maximale Anzahl an Kanten zwische dem Wurzelknoten und den Knoten der untersten Ebene. In der Praxis können Bäume beliebig wachsen.
Der erste Schritt im Verständnis einer neuen Datenstruktur ist es, die Invariante zu kennen, die zwischen den Operationen erhalten werden muss. Für den binären Suchbaum ist sie für jeden Knoten definiert: alle Schlüssel im linken Unterbaum müssen kleiner oder gleich dem des Elternknotens sein, und alle Schlüssel im rechten Unterbaum müssen größer oder gleich dem des Elternknotens sein. Dies muss für alle Knoten gelten, mit Ausnahmen nur für leere Unterbäume. Im obigen Diagramm durchlaufen wir den Baum in richtiger Ordnung: zuerst wird der linke Unterbaum durchlaufen, dann wird der Elternknoten besucht und anschliessend ist der rechte Unterbaum dran. Dies ermöglicht es die Schlüssel im Baum in richtiger Reihenfolge auszugeben.
Die einfachste Operation an einem BSB ist es, den kleinsten oder größten Wert zu finden. Im ersten Fall folgt man wiederholt ganz einfach den Zeiger zum linken Unterknoten, bis es kein linkes Kind mehr gibt, was bedeutet das der kleinste Wert gefunden ist. Um den Knoten mit dem größten Wert zu finden, geht man ganz ähnlich vor, und folgt stets dem Zeiger zum rechten Unterknoten. Dies wird oben gezeigt, sowohl für die Suche nach dem Minimum und auch nach dem Maximum.
Einen beliebigen Schlüssel zu suchen ist fast so einfach wie die letzte Operation, den minimalen Schlüssel zu finden. Statt immer den linken Zeiger in die nächste Ebene zu wählen, muss die Suche sich jetzt zwischen dem linken und rechten Kindknoten entscheiden. Falls der gesuchte Wert kleiner ist als der des aktuellen Knotens, wird entsprechend der linke Unterknoten gewählt. Falls umgekehrt der Wert größer ist, wird beim rechten Unterknoten weitergemacht. Falls der gesuchte Wert gleich dem aktuellen Knoten ist, ist die Suche erfolgreich beendet. Falls die Suche an einem Knoten ohne passenden Kindknoten ankommt, ist die Suche erfolglos terminiert.
Um einen neuen Wert in den Binärbaum einzufügen, muss man erst die richtige Stelle dafür finden. Dies verläuft im Prinzip wie die Suche nach einem Schlüssel weiter oben. Wenn an richtiger Stelle ein fehlender Kindknoten festgestellt wird, wird einfach ein neuer Knoten angehängt. Wir erlauben mehrfach gleiche Einträge indem der neue Schlüssel z.B. im linken Unterbaum nicht streng kleiner als sein Elternknoten sein muss, sondern auch gleich sein darf.
Um einen Knoten aus dem Baum zu löschen, gehen wir wie obig vor und finden ihn erst mal im Baum. Falls er keine Kinderknoten hat, als sogenanntes Blatt, kann er ganz einfach ohne weitere Mühe gelöscht werden. Falls der zu entfernende Knoten ein Kind hat, ersetzen wir den gelöschten Knoten einfach durch das Kind und der Baum passt wieder. Der schwierige Fall ist der in dem der zu löschende Knoten zwei Kinderknoten hat. Hier ist die Prozedur folgende: tausche den Knoten mit seinem Vorgänger nach Maßgabe der Bauminvariante. Der Vorgänger wird keine zwei Kinder haben, somit kann an dieser Stelle der zu löschende Knoten wie in den obigen Fällen entfernt werden. Sie können jeden dieser Fälle ausprobieren indem Sie auf einen Knoten klicken um ihn zu löschen. Danach muss die Bauminvariante erhalten werden.
Wie Sie vielleicht schon bemerkt haben, bekommen diese Bäume mit der Zeit manchmal etwas Schlagseite, so wie oben gezeigt, wenn alle Knoten im linken oder rechten Unterbaum der Wurzel sind. Was dann gemacht werden kann heißt Rebalancieren (engl. ‘rebalancing’). Ein Knoten unter der Wurzel wird ausgewählt um die neue, bessere Wurzel zu sein. Hierauf folgt einen Rotation der Unterbäume wie gezeigt. Wir zeigen sowohl linke als auch rechte Rotationen in diesem Panel, führen aber nur eine Rotation jeweils aus. In der Praxis könnte man auch mehrere Rotationen nacheinander durchführen.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken. Insbesondere nutzt der Heap eine ähnliche Baumstruktur wie der BSB.