Suchbaum

In der Informatik ist ein Suchbaum eine abstrakte Datenstruktur, bei der die Menge von Elementen, in der gesucht werden soll, in einer Baumstruktur dargestellt wird. Wie ein assoziatives Datenfeld oder eine Hashtabelle realisiert er eine endliche Funktion (englisch: map), bei der aus einem Suchschlüssel (aus der endlichen Definitionsmenge) ein Datenwert (aus der Wertemenge) gewonnen wird. Bei fehlender Wertemenge realisiert der Baum eine Indikatorfunktion, entspricht also einer endlichen Menge (englisch: set).

Aus Effizienzgründen besitzt die Menge allermeist eine totale Quasiordnung, die auch eine Totalordnung 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, die logarithmisch 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 die Baumstruktur besonders gut eignet.