Suchbaum

Grundidee und Bedeutung

Ein Suchbaum ist in der Informatik eine abstrakte Datenstruktur, die eine Menge von Elementen als Baum darstellt, damit sich darin effizient suchen lässt. Ähnlich wie ein assoziatives Datenfeld oder eine Hashtabelle kann er eine endliche Funktion (Map) verwirklichen: Ein Suchschlüssel aus einer endlichen Definitionsmenge führt zu einem zugehörigen Datenwert. Gibt es keine eigenen Datenwerte, dient der Baum als Indikatorfunktion und stellt damit eine endliche Menge (Set) dar.

Die Elemente besitzen meistens eine totale Quasiordnung oder eine Totalordnung. Bei einer Totalordnung lassen sich alle Elemente eindeutig der Größe nach vergleichen. Diese Ordnung wird durch eine Links-Rechts-Orientierung im Baum abgebildet: Links von einem Knoten liegen keine größeren Elemente, rechts davon keine kleineren. So kann die Suche nach dem Prinzip „Teile und herrsche“ immer den Teil des Baums auswählen, in dem sich der gesuchte Schlüssel befinden kann. Bei geeigneter Baumform sind dadurch Suchzeiten möglich, die logarithmisch mit der Anzahl der Schlüssel wachsen.

Suchbäume können statisch oder dynamisch sein. Ein statischer Suchbaum bleibt unverändert. In einem dynamischen Suchbaum können Elemente eingefügt und gelöscht werden; die Baumstruktur eignet sich besonders gut für solche Veränderungen.

Operationen und Balance

Die charakteristische Operation ist das Suchen. Weitere wichtige Operationen wie Einfügen, Löschen und Traversieren übernimmt der Suchbaum von der zugrunde liegenden Baumstruktur. Traversieren bedeutet, die Knoten des Baums in einer bestimmten Reihenfolge zu durchlaufen.

Eine Suche liefert ein Element mit einem übereinstimmenden Schlüssel. Kommt der Schlüssel nicht vor, kann sie das NULL-Element oder ein gemäß der Totalordnung nächstgelegenes anderes Element zurückgeben.

Der maximale Suchaufwand, also die größte erforderliche Zahl von Vergleichen, ist bei einer Totalordnung proportional zur Baumhöhe h. Ein Suchbaum heißt balanciert, wenn sichergestellt ist, dass h stets logarithmisch von der Anzahl n der Elemente abhängt. Dann liegt der Suchaufwand bei O(log n). Ohne Maßnahmen zur Balance kann ein Baum degenerieren, also beispielsweise eine kettenartige Form annehmen. Im ungünstigsten Fall wird der Suchaufwand dann proportional zu n und beträgt O(n).

Binäre Suchbäume

Ein binärer Suchbaum ist eine knotenbasierte Datenstruktur. Jeder Knoten enthält einen Schlüssel und höchstens zwei Teilbäume: einen linken und einen rechten. Alle Schlüssel im linken Teilbaum sind kleiner als der Schlüssel des Knotens, alle Schlüssel im rechten Teilbaum sind größer. Zugleich ist jeder Teilbaum selbst wieder ein binärer Suchbaum.

Für binäre Suchbäume wurden zahlreiche Varianten entwickelt, die einer Degeneration entgegenwirken. Die Zeitkomplexität der Suche entspricht im Worst Case der Baumhöhe. Bei einem Baum mit n Elementen kann diese Höhe so klein wie O(log n) sein. Bei unbalancierten binären Suchbäumen ist O(log n) jedoch nicht für jede Baumform garantiert; im ungünstigsten Fall gilt O(n). Die logarithmische Angabe gilt im Mittel über alle möglichen Baumformen hinweg.

Nicht zu den Binärbäumen gehören der Fibonacci-Heap, der 2-3-4-Baum, der B-Baum und der K-d-Baum.

Mehrweg-Suchbäume

Ein B-Baum verallgemeinert den binären Suchbaum: Ein Knoten kann eine variable Anzahl von Teilbäumen besitzen. Untergeordnete Knoten haben einen vordefinierten Kapazitätsbereich, müssen aber nicht vollständig mit Daten gefüllt sein. Deshalb können B-Bäume etwas Speicherplatz verschwenden. Dafür müssen sie weniger häufig neu balanciert werden als andere selbstbalancierende Bäume. Aufgrund der variablen Knotengröße eignen sie sich besonders für Systeme, die große Datenblöcke lesen, und werden häufig in Datenbanken verwendet. Die Suche benötigt O(log n) Zeit.

Ein (a, b)-Baum ist ein Suchbaum, bei dem alle Blätter dieselbe Tiefe haben. Jeder Knoten hat mindestens a und höchstens b Nachfolger; die Wurzel besitzt mindestens 2 und höchstens b Nachfolger. Für die Parameter gilt die Bedingung 2 ≤ a ≤ (b + 1) / 2. Auch die Suche in einem (a, b)-Baum hat die Zeitkomplexität O(log n).

Ternäre Suchbäume und Zeichenketten

Ein ternärer Suchbaum ist ein Präfixbaum, dessen Folgeknoten gemäß einer Ordnungsrelation angeordnet sind. Er eignet sich zur Suche nach Zeichenketten. Jeder Knoten besitzt drei Zeiger:

• Der mittlere Zeiger führt zu dem Knoten, mit dessen Wert die Zeichenkette nach dem aktuellen Wert fortgesetzt wird.
• Der linke Zeiger führt zu einem Knoten mit einem kleineren Wert.
• Der rechte Zeiger führt zu einem Knoten mit einem größeren Wert.

Zusätzlich enthält jeder Knoten ein Feld, das gegebenenfalls das Ende einer Zeichenkette markiert, sowie möglicherweise ein Feld für weitere Benutzerdaten. Bei der Suche wird der Suchschlüssel als Zeichenkette übergeben und geprüft, ob ein entsprechender Pfad im Baum vorhanden ist.

Als Beispiel zeigt der Artikel einen ternären Suchbaum für die Zeichenketten „cute“, „cup“, „at“, „as“, „he“, „us“ und „v“. Das jeweilige Ende einer Zeichenkette wird am letzten Zeichen markiert. In einem ausgeglichenen ternären Suchbaum beträgt die Zeitkomplexität der Suche O(log n).

Laufzeit, Speicher und praktische Umgebung

Der zusätzliche Speicherverbrauch eines Suchbaums ist im Allgemeinen linear zur Anzahl n der Elemente und beträgt damit O(n). Die eigentlichen Nutzdaten sind dabei nicht eingerechnet.

Bei der Laufzeit werden Suchen, Traversieren zum Nachbarknoten, Einfügen und Löschen unterschieden. Die Suchzeit entspricht der Baumhöhe. Bei den Angaben für Einfügen und Löschen ist die Zeit zum Positionieren nicht enthalten, weil die Position außer durch Suchen beispielsweise auch durch Traversieren gefunden werden kann. Angaben wie „mittlere Laufzeit < maximale Laufzeit“ unterscheiden den durchschnittlichen vom ungünstigsten Fall.

Für AVL-Bäume und Rot-Schwarz-Bäume gilt für die Suche O(log n). Das Traversieren zum Nachbarknoten sowie Einfügen und Löschen benötigen im Mittel O(1) und maximal O(log n). Bei 2-3-4-Bäumen und B-Bäumen liegen Suchen, Einfügen und Löschen jeweils in O(log n).

Bei Splay-Bäumen beträgt die Suche ebenso wie Einfügen und Löschen im Mittel O(log n), im Worst Case aber O(n). Abhängig vom Zugriffsmuster einer Anwendung können auch unterlogarithmische mittlere Laufzeiten auftreten. Das Traversieren zum Nachbarknoten reicht dort von einer mittleren Laufzeit O(1) bis zu einer maximalen Laufzeit O(n).

Beim gewöhnlichen binären Suchbaum liegt die Suche im Mittel bei O(log n), kann aber O(n) erreichen. Das Traversieren zum Nachbarknoten reicht von O(1) im Mittel bis O(n) im Worst Case. Das Einfügen selbst benötigt O(1), wenn die Positionierungszeit nicht mitgerechnet wird. Für das Löschen werden im Mittel O(log n) und maximal O(n) angegeben. Weitere mögliche Operationen sind der Zugriff auf besondere Elemente, etwa das kleinste Element, und das Verschmelzen mehrerer Suchbäume.

Komplexitätsangaben sind asymptotisch, beschreiben also vor allem das Wachstum des Aufwands bei zunehmendem n. Sie lassen sich besonders unmittelbar auf die Praxis übertragen, wenn die gesamte Datenstruktur in einem gleichförmigen Medium wie dem Arbeitsspeicher liegt. Bei Zugriffen auf externe Medien sind zusätzliche Überlegungen nötig; dafür sind insbesondere B-Bäume und Indexstrukturen relevant.