Suchbaum

In der Informatik ist ein Suchbaum eine auf Bäumen basierende abstrakte Datenstruktur, die das Ziel hat, in ihr gespeicherte Objekte und Elemente einer total geordneten Menge effizient suchen zu können.

Operationen

Suchbäume unterstützen die Operationen

• find, zum Auffinden eines Elementes oder eines nächstgelegenen verschiedenen Elementes,
• insert, zum Einfügen eines Elementes und
• delete, zum Entfernen eines Elementes.

Der Aufwand für das Auffinden in O-Notation ist $\mathcal{O}(h)$, wobei h für die Höhe des Suchbaums steht. In höhen-balancierten Suchbäumen entspricht $\mathcal{O}(h) = \mathcal{O}(\log(n))$, wobei n für die Anzahl der Einträge im Suchbaum steht. Das Einfügen und Entfernen kann auch konstanten Aufwand haben.

Spezielle Suchbäume

Es gibt einfache Implementierungen binärer Suchbäume, sie können jedoch im ungünstigen Fall zu linearen Listen entarten, so dass die Grundoperation find nicht mehr effizient ausgeführt wird. Um dieses Problem zu lösen, wurden komplexere Strukturen entwickelt, die durch Selbstmanagement dafür sorgen, dass die Baumstruktur ausbalanciert bleibt.

→ Hauptartikel: Binärer Suchbaum

Nicht mehr binär sind folgende Suchbäume:

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

Der Fibonacci-Heap verwendet eine Baummenge - auch Wald genannt.

Weblinks

• Der Suchbaum zur Errechnung von Fakultäten (Prolog)