Was ist Binärer Suchbaum (Binary Search Tree)?
Binärbaum, in dem für jeden Knoten alle Werte im linken Teilbaum kleiner und alle Werte im rechten Teilbaum größer als der Knoten sind. Suchen, Einfügen und Löschen kosten Zeit proportional zur Höhe des Baums, und ein Durchlauf in In-Order besucht die Werte in aufsteigender Reihenfolge.
Japanische Bezeichnung: 二分探索木
„Binärer Suchbaum (Binary Search Tree)“ kommt in 3 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.
Fachgebiet: Datenstrukturen und Algorithmen
Suchen, Einfügen und Löschen
Eine Suche beginnt an der Wurzel und geht zum linken Kind, wenn der Zielwert kleiner als der Knoten ist, oder zum rechten Kind, wenn er größer ist, bis sie einen Treffer findet oder keine Kinder mehr vorhanden sind. Beim Einfügen wird gesucht und ein neuer Knoten dort angehängt, wo die Suche keine Kinder mehr fand. Beim Löschen wird ein Knoten mit null oder einem Kind entfernt und das Kind neu angeschlossen; ein Knoten mit zwei Kindern wird durch den kleinsten Wert seines rechten Teilbaums (oder den größten seines linken Teilbaums) ersetzt, und stattdessen wird jener Knoten gelöscht. Jede Operation kostet Zeit proportional zur Zahl der Ebenen von der Wurzel bis zu einem Blatt (der Höhe des Baums).
Unausgeglichene Bäume und selbstbalancierende Bäume
Ein binärer Suchbaum mit n Knoten hat, wenn er ausgeglichen ist, eine Höhe von etwa log₂ n; werden die Werte aber in sortierter Reihenfolge wie 1, 2, 3, … eingefügt, entsteht eine einzige Kette, die nur zu einer Seite wächst und die Höhe n−1 hat. Die Suche kostet dann O(n), genau wie in einer verketteten Liste. AVL-Bäume und Rot-Schwarz-Bäume sind selbstbalancierende binäre Suchbäume, die sich bei jedem Einfügen und Löschen mit sogenannten Rotationen umformen und die Höhe bei O(log n) halten; sie werden für die geordneten Dictionaries und Sets vieler Programmiersprachen verwendet.
Durchlaufreihenfolgen
Zu den Arten, alle Knoten eines Baums zu besuchen, gehören Pre-Order, die jeden Knoten zuerst besucht; In-Order, die den linken Teilbaum, den Knoten und dann den rechten Teilbaum besucht; Post-Order, die zuerst die Kinder besucht; und die Breitenreihenfolge (Level-Order), die den Baum Ebene für Ebene besucht. Ein Durchlauf eines binären Suchbaums in In-Order listet die Werte in aufsteigender Reihenfolge auf und liefert so eine sortierte Liste. Ein Durchlauf eines Ausdrucksbaums in Post-Order ergibt die umgekehrte polnische Notation.
Häufige Fragen
Wie unterscheidet sich ein binärer Suchbaum von einem Heap?
Ein binärer Suchbaum folgt der Regel „links kleiner, rechts größer“ und kann daher nach beliebigen Werten suchen und Werte geordnet auflisten. Ein binärer Heap folgt nur der Regel „ein Elternknoten ist größer (oder kleiner) als seine Kinder“; er kann das Maximum (oder Minimum) schnell entnehmen, eignet sich aber nicht für die Suche nach beliebigen Werten.
Wann verwendet man einen binären Suchbaum und wann einen B-Baum?
Im Arbeitsspeicher werden selbstbalancierende binäre Suchbäume verwendet; für Speicher, der blockweise gelesen wird, wie Festplatten und SSDs, verwendet man B-Bäume (B+-Bäume), die den Baum flach halten, indem sie viele Schlüssel in jeden Knoten legen.