22.04.2025Balancierte Suchbäume sind eine Verbesserung von binären Suchbäumen (BSB). Wenn man meine Seite zu binären Suchbäumen betrachtet, kann man sehen das solche Bäume unbalanciert sein können, z.B. mit den meisten Knoten auf einer Seite der Wurzel. Suchbäume funktionieren am besten, wenn jeder Knoten eine ähnliche Tiefe unter der Wurzel hat, dies ist dann ein balancierter Suchbaum. Eine einfache Art Balance zu erreichen ist der 2-3-Baum, von dem ein Beispiel oben zu sehen ist. Der Name kommt von der Tatsache, dass interne Knoten 2 oder 3 Kinder haben, wohingegen Knoten in einem BSB 0 bis 2 haben. In einem 2-3-Baum ist die Höhe über jedem Endknoten gleich, im Baum oben sind es 2 Knoten bis zur Wurzel.
Eine wesentliche Funktion von 2-3-Bäumen ist es, Werte in logarithmischer Zeit zu finden. Dies wird in der Animation oben gezeigt. Mit Hilfe der Werte in den Knoten, durchläuft ein Algorithmus den Baum bis er entweder den richtigen Knoten findet (grün) oder zum Schluss kommt, dass die Zahl nicht vorhanden ist (rot). Die dafür gebrauchte Zeit ist proportional zur Höhe des Baums and somit auch zum Logarithmus der Anzahl der Werte im Baum.
Werte sind im 2-3-Baum in einer Ordnung vorhanden, von kleinen Zahlen (links) zu größeren (rechts). Hier wird gezeigt, wie der Baum durchlaufen werden kann um alle Werte der Reihe nach auszulesen.
Hier sehen wir einen 2-3-Baum mit umgekehrter Sortierung zum vorherigen Baum. Größere Werte sind links und kleinere rechts. Die Invariante des Baumes wird auf gleiche Weise hier illustriert. Für den Rest dieser Seite nehmen wir wieder die vorherige Sortierung her.
Hier verzichten wir auf die Zahlen in den Knoten, um einen größeren 2-3-Baum darzustellen. Man beachte, wie Knoten mit 2 oder 3 Kinderknoten durch den Baum verteilt sind. Mit nur 4 Ebenen unter der Wurzel, kann dieser Baum 90 Zahlen aufnehmen. Wie also erhält der Baum seinen Mix aus 2 und 3-Knoten? Während die Werte eingefügt werden, hält der Algorithmus die ausgewogene Tiefe aufrecht, indem Werte entweder in kleinere Knoten aufgenommen werden oder ein größerer Knoten in drei 2-Knoten aufgespalten wird.
Eine weitere Form von balancierten Bäumen sind sogenannte Rot-Schwarz-Bäume, die aus einem 2-3-Baum entstehen, wenn man alle 3-Knoten in zwei 2-Knoten aufteilt indem man eine rote Kante zwischen ihnen einfügt. Alle anderen, vorher vorhandenen Kanten sind schwarze Kanten. Knoten erhalten dieselbe Farbe wie die Kante, die zu ihnen hinführt. Auf diese Weise erhält man eine Art binären Suchbaum in dem die Tiefe unter der Wurzel bis auf einen Faktor von höchstens 2 ausbalanciert ist. Im obigen Diagram ist der 2-3-Baum von der ersten Abbildung auf dieser Seite in einen äquivalenten Rot-Schwarz-Baum umgewandelt, mit genau denselben Zahlen.
Hier haben wir wieder den größeren 2-3-Baum von oben in einen Rot-Schwarz-Baum umgewandelt. Die Operationen auf diesen Baum werden wir hier nicht behandeln, aber sie erhalten die Balance in so einem Baum. Es gibt leicht unterschiedliche Varianten des Rot-Schwarz-Baumes, diese Version findet sich um unten angegebenen Buch wieder.
Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken.