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.

Operationen

Die charakteristische Operation ist das Suchen. Die meisten anderen Operationen, wie Einfügen, Löschen, Traversieren werden von der unterliegenden Baumstruktur 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 der Totalordnung nächstgelegenes anderes Element.

Der maximale Aufwand für das Suchen, d. h. die Maximalzahl der erforderlichen Vergleiche, ist bei vorliegender Totalordnung proportional zur Baumhöhe $h$ . Ein Baum wird balanciert genannt, wenn dafür Sorge getragen ist, dass $h$ stets logarithmisch in der Anzahl $n$ der Elemente ist. Ohne solche Vorkehrung kann der Suchbaum entarten bis zum ungünstigen Fall, dass der Suchaufwand proportional wird zu $n$ .

Spezielle Suchbäume

Binärer Suchbaum

Ein binärer Suchbaum ist eine knotenbasierte Datenstruktur, in der jeder Knoten einen Schlüssel und maximal zwei Teilbä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.

Die Zeitkomplexität für die Suche in einem binären Suchbaum ist im Worst Case die Höhe des Baums, die für einen Baum mit $n$ Elementen so klein wie ${\mathcal {O}}(\log \ n)$ sein kann.

Keine Binärbäume sind folgende Suchbäume:

B-Baum

B-Bäume sind Verallgemeinerungen von binären Suchbäumen, da sie an jedem Knoten eine variable Anzahl von Teilbä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 sind B-Bäume für Systeme optimiert, die große Datenblöcke lesen. Sie werden auch häufig in Datenbanken verwendet.

Die Zeitkomplexität für die Suche in einem B-Baum beträgt ${\mathcal {O}}(\log \ n)$ .

(a, b)-Baum

Ein (a, b)-Baum ist ein Suchbaum, in dem alle Blätter die gleiche Tiefe haben. Jeder Knoten hat mindestens einen und höchstens $b$ Nachfolger, während die Wurzel mindestens 2 und höchstens $b$ Nachfolger hat.

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

2\leq a\leq {\frac {(b+1)}{2}}

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

Ternärer Suchbaum

Ein ternärer Suchbaum ist eine Datenstruktur in Gestalt eines Präfixbaums, in der die Folgeknoten^[2] entsprechend der Ordnungsrelation geordnet sind.

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

Der mittlere Zeiger zeigt auf den Knoten, mit dessen Wert, dem aktuellen, sich die Zeichenkette fortsetzt.
Der linke Zeiger zeigt auf einen Knoten, dessen Wert kleiner ist als der aktuelle Wert.
Der rechte Zeiger zeigt auf einen Knoten, dessen Wert größer ist als der aktuelle Wert.

Zusätzlich zu den drei Zeigern hat jeder Knoten ein Feld zum Markieren des Endes einer Zeichenkette 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  t  e  u
     /  / |     | \
    s  p  e     s  v

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

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

Weitere auf Bäumen basierende Suchstrukturen

Obwohl komplexitätstheoretische Angaben asymptotisch zu verstehen sind, lassen sie sich am ehesten in die Praxis übertragen, wenn die gesamte Datenstruktur in einem gleichförmigen Medium, z. B. dem Arbeitsspeicher (Hauptspeicher), untergebracht werden soll.

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

Speicherkomplexität

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

Laufzeitkomplexität

Bei der Laufzeit unterscheidet man Operationen zum Suchen, Einfügen und Löschen. Bei den letzteren beiden ist in der Tabelle die Laufzeit für das Positionieren nicht mit eingerechnet, da dies nicht nur über das Suchen, sondern z. B. auch über das Traversieren geschehen kann. Abhängig von der Art des Suchbaums werden asymptotische mittlere $<$ 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	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$
Rot-Schwarz-Baum	${\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)$
2-3-4-Baum	${\mathcal {O}}(\log n)$		${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
B-Baum	${\mathcal {O}}(\log n)$		${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
Splay-Baum	${\mathcal {O}}(\log n)$ ¹ $\!<\!{\mathcal {O}}(n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$ ¹ $\!<\!{\mathcal {O}}(n)$	${\mathcal {O}}(\log n)$ ¹ $\!<\!{\mathcal {O}}(n)$
binärer Suchbaum	${\mathcal {O}}(\log n)$ ² $\!<\!{\mathcal {O}}(n)$	${\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)$	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$ ² $\!<\!{\mathcal {O}}(n)$
¹ Abhängig vom Zugriffsmuster der Anwendung können bei Splay-Bäumen auch unterlogarihmische mittlere Laufzeiten vorkommen. ² Unter den unbalancierten binären Suchbäumen gibt es Bäume, bei denen ${\mathcal {O}}(\log n)$ nicht garantiert werden kann. Die Angabe ${\mathcal {O}}(\log n)$ gilt jedoch im Mittel über alle möglichen Baumformen hinweg.

Neben den vorgenannten Operationen kommen weitere in Betracht:

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

Laufzeitmessungen einiger Suchalgorithmen anhand realistischer Beispiele sind zu finden bei Ben Pfaff.

Siehe auch

Effizienz (Informatik)

Literatur

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.

Weblinks

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

Einzelnachweise

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

[1] Toal, Ray. "(a,b) Trees"

[2] Der in den Knoten gespeicherte Wert fungiert als Teilstück des Suchschlüssels.

[3] GeeksforGeeks: Ternary Search Tree

[1]

[2]

[3]

Fahrer / Team für die Suche eingeben: