In derInformatik ist einSuchbaum eineabstrakteDatenstruktur, bei der dieMenge von Elementen, in der gesucht werden soll, in einerBaumstruktur dargestellt wird.Wie einassoziatives Datenfeld oder eineHashtabelle realisiert er eine endlicheFunktion (englisch:map), bei der aus einemSuchschlüssel (aus der endlichenDefinitionsmenge) ein Datenwert (aus derWertemenge) gewonnen wird. Bei fehlender Wertemenge realisiert der Baum eineIndikatorfunktion, entspricht also einer endlichen Menge (englisch:set).

Aus Effizienzgründen besitzt die Menge allermeist einetotale Quasiordnung, die auch eineTotalordnung sein kann. Dieser Ordnung entspricht im Baum eine Links-Rechts-Orientierung auf folgende Weise: »links« von einem Knoten gibt es keine größeren Elemente und »rechts« keine kleineren. Dadurch wird in Form des„binären Suchens“ ein Prinzip namens„Teile und herrsche“ möglich, welches Suchzeiten erlaubt, dielogarithmisch in der Anzahl der Suchschlüssel sind.

Es gibt Suchbäume sowohl in statischer (unveränderlicher) wie in dynamischer (durch Einfügen und Löschen von Elementen veränderbarer) Ausprägung, für welche sich dieBaumstruktur besonders gut eignet.

Die charakteristischeOperation ist dasSuchen. Die meisten anderen Operationen, wieEinfügen,Löschen,Traversieren werden von der unterliegendenBaumstruktur geerbt.

Die Suchoperation gibt ein Element mit übereinstimmendem Schlüssel zurück oder, falls der Schlüssel nicht vorkommt, das NULL-Element oder ein im Sinne derTotalordnung nächstgelegenes anderes Element.

Der maximale Aufwand für das Suchen, d. h. die Maximalzahl der erforderlichen Vergleiche, ist bei vorliegenderTotalordnungproportional zurBaumhöhe${\displaystyle h}$. Ein Baum wirdbalanciert genannt, wenn dafür Sorge getragen ist, dass${\displaystyle h}$ stets logarithmisch in der Anzahl${\displaystyle n}$ der Elemente ist. Ohne solche Vorkehrung kann der Suchbaumentarten bis zum ungünstigen Fall, dass der Suchaufwand proportional wird zu${\displaystyle n}$.

Einbinärer Suchbaum ist eine knotenbasierteDatenstruktur, in der jederKnoten einen Schlüssel und maximal zweiTeilbäume enthält, den linken und den rechten. Alle Schlüssel des linken Teilbaums sind kleiner als der Schlüssel des Knotens und die des rechten Teilbaums größer. Jeder Teilbaum ist ein binärer Suchbaum. Es sind viele Varianten entwickelt worden, die der Degeneration entgegenwirken sollen.

DieZeitkomplexität für die Suche in einembinären Suchbaum ist imWorst Case die Höhe desBaums, die für einen Baum mit${\displaystyle n}$ Elementen so klein wie${\displaystyle \mathcal{O}(\log n)}$ sein kann.

KeineBinärbäume sind folgende Suchbäume:

• Fibonacci-Heap
• 2-3-4-Baum
• B-Baum
• K-d-Baum

B-Bäume sind Verallgemeinerungen vonbinären Suchbäumen, da sie an jedemKnoten eine variable Anzahl vonTeilbäumen haben können. Während untergeordnete Knoten einen vordefinierten Bereich haben, werden sie nicht unbedingt mit Daten gefüllt, was bedeutet, dass B-Bäume möglicherweise etwas Platz verschwenden können. Der Vorteil ist, dass B-Bäume nicht so häufig rebalanciert werden müssen wie andere selbst-balancierende Bäume.

Aufgrund des variablen Bereichs ihrer Knotenlänge sindB-Bäume für Systeme optimiert, die große Datenblöcke lesen. Sie werden auch häufig inDatenbanken verwendet.

DieZeitkomplexität für die Suche in einemB-Baum beträgt${\displaystyle \mathcal{O}(\log n)}$.

Ein(a, b)-Baum ist ein Suchbaum, in dem alleBlätter die gleiche Tiefe haben. JederKnoten hat mindestens einen und höchstens${\displaystyle b}$Nachfolger, während die Wurzel mindestens 2 und höchstens${\displaystyle b}$ Nachfolger hat.

${\displaystyle a}$ und${\displaystyle b}$ können mit folgender Formel bestimmt werden:^[1]

${\displaystyle 2\le a\le \frac{(b+1)}{2}}$

DieZeitkomplexität für die Suche nach einem(a, b)-Baum beträgt${\displaystyle \mathcal{O}(\log n)}$.

Ein ternärer Suchbaum ist eineDatenstruktur in Gestalt einesPräfixbaums, in der die Folgeknoten^[2] entsprechend derOrdnungsrelation geordnet sind.

Jeder Knoten in einem ternären Suchbaum enthält 3Zeiger:

1. Der mittlere Zeiger zeigt auf den Knoten, mit dessenWert, dem aktuellen, sich die Zeichenkette fortsetzt.
2. Der linke Zeiger zeigt auf einen Knoten, dessenWert kleiner ist als der aktuelleWert.
3. Der rechte Zeiger zeigt auf einen Knoten, dessenWert größer ist als der aktuelleWert.

Zusätzlich zu den drei Zeigern hat jeder Knoten ein Feld zum Markieren des Endes einerZeichenkette und ggf. ein Feld für weitere Benutzerdaten.

Die untenstehende Grafik zeigt einen ternären Suchbaum, der die Zeichenketten „cute“, „cup“, „at“, „as“, „he“, „us“ und „v“ enthält. Dabei ist das Ende einer Zeichenkette durch Unterstreichung des letzten Zeichens markiert:

          c        / | \       a  u  h       |  |  | \t  te  u     /  / |     | \spesv

Beim Suchen in einem ternären Suchbaum wird der Suchschlüssel als eine Zeichenkette übergeben, für die getestet wird, ob einPfad sie enthält.

DieZeitkomplexität für die Suche in einem ausgeglichenen ternären Suchbaum beträgt${\displaystyle \mathcal{O}(\log n)}$.^[3]

Obwohlkomplexitätstheoretische Angabenasymptotisch zu verstehen sind, lassen sie sich am ehesten in die Praxis übertragen, wenn die gesamte Datenstruktur in einem gleichförmigen Medium, z. B. demArbeitsspeicher (Hauptspeicher), untergebracht werden soll.

Spielen dagegen Zugriffe zu externenMedien eine Rolle, kommen weitergehende Überlegungen ins Spiel. Im Kontext der Suchbäume sei verwiesen auf die Artikel:

• B-Baum
• Indexstruktur

Der Speicherverbrauch eines Suchbaums ist – zusätzlich zu den Nutzdaten – im Allgemeinen linear in der Anzahl${\displaystyle n}$ der Elemente, also in${\displaystyle \mathcal{O}(n)}$.

Bei derLaufzeit unterscheidet manOperationen zum Suchen, Einfügen und Löschen. Bei den letzteren beiden ist in der Tabelle die Laufzeit für das Positionierennicht mit eingerechnet, da dies nicht nur über das Suchen, sondern z. B. auch über dasTraversieren geschehen kann. Abhängig von der Art des Suchbaums werdenasymptotischemittlere maximale (worst case) Laufzeiten gegenübergestellt, wobei die maximale weggelassen ist, wenn sie mit der mittleren übereinstimmt.

Laufzeitkomplexitäten

Suchbaum	Suchen (=Baumhöhe)	Traversieren zum Nachbarknoten	Einfügen	Löschen
AVL-Baum	${\displaystyle \mathcal{O}(\log n)}$
Rot-Schwarz-Baum	${\displaystyle \mathcal{O}(\log n)}$
2-3-4-Baum	${\displaystyle \mathcal{O}(\log n)}$		${\displaystyle \mathcal{O}(\log n)}$	${\displaystyle \mathcal{O}(\log n)}$
B-Baum	${\displaystyle \mathcal{O}(\log n)}$		${\displaystyle \mathcal{O}(\log n)}$	${\displaystyle \mathcal{O}(\log n)}$
Splay-Baum	${\displaystyle \mathcal{O}(\log n)}$ 1		${\displaystyle \mathcal{O}(\log n)}$ 1	${\displaystyle \mathcal{O}(\log n)}$ 1
binärer Suchbaum	${\displaystyle \mathcal{O}(\log n)}$ 2		${\displaystyle \mathcal{O}(1)}$	${\displaystyle \mathcal{O}(\log n)}$ 2
1 Abhängig vom Zugriffsmuster der Anwendung können bei Splay-Bäumen auch unterlogarihmische mittlereLaufzeiten vorkommen. 2 Unter den unbalanciertenbinären Suchbäumen gibt esBäume, bei denen${\displaystyle \mathcal{O}(\log n)}$ nicht garantiert werden kann. Die Angabe${\displaystyle \mathcal{O}(\log n)}$ gilt jedoch im Mittel über alle möglichen Baumformen hinweg.

Neben den vorgenanntenOperationen kommen weitere in Betracht:

• Zugriff auf spezielle Elemente, wie z. B. das kleinste Element
• Verschmelzen von Suchbäumen

Laufzeitmessungen einigerSuchalgorithmen anhand realistischer Beispiele sind zu finden beiBen Pfaff.

• Effizienz (Informatik)

• Alexander Reinefeld:Spielbaum-Suchverfahren. (=Subreihe Künstliche Intelligenz. Band 200). Springer, 1989,ISBN 3-540-50742-6.
• A. Banzhaf, U. Boes, M. Kramer:Steuerung von Erkennungsprozessen durch Baumsuchverfahren. In: H. Burkhardt, K. H. Höhne, B. Neumann (Hrsg.):Mustererkennung. (=Informatik-Fachberichte. Band 219). Springer, Berlin/ Heidelberg 1989,ISBN 3-540-51748-0.

• Ben Pfaff:Performance Analysis of BSTs in System Software. (PDF; 309 kB).Stanford University, 2004. (englisch)

1. ↑Toal, Ray."(a,b) Trees"
2. ↑Der in den Knoten gespeicherteWert fungiert als Teilstück des Suchschlüssels.
3. ↑GeeksforGeeks:Ternary Search Tree

• Suchbaum
• Komplexitätstheorie