Suchbaum-Komplexität

Dieser Artikel wurde aufgrund von inhaltlichen Mängeln auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen und beteilige dich an der Diskussion! (+)

Unter Suchbaum-Komplexität versteht man in der Informatik den asymptotischen Ressourcenverbrauch eines Suchbaums.

Speicherkomplexität

Der Speicherverbrauch eines Suchbaums wächst bei Implementierungen, in denen jedes Blatt mindestens ein Element enthält, linear mit der Anzahl der enthaltenen Elementen. Damit ist die Speicherkomplexität $\mathcal{O}(n)$.

Laufzeitkomplexität

Bei der Laufzeit unterscheidet man Operationen zum Suchen, Einfügen und Löschen. Die Laufzeiten sind abhängig von der Art des Suchbaums sehr unterschiedlich. Darüber hinaus kann man die mittlere oder maximale Laufzeit betrachten.

Beispiele für Laufzeiten

Im folgenden Beispielen sind die mittleren/maximalen Laufzeiten verschiedener Suchbäume aufgeführt.

Suchbaum	Baumhöhe	Suchen	Einfügen	Löschen
Rot-Schwarz-Baum	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \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}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$
2-3-4-Baum	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$	$\mathcal{O}(log_{n}) / \mathcal{O}(log_{n})$
unausgewogener Binärbaum	$\mathcal{O}(log_{n}) / \mathcal{O}(n)$	$\mathcal{O}(log_{n}) / \mathcal{O}(n)$	$\mathcal{O}(log_{n}) / \mathcal{O}(n)$	$\mathcal{O}(log_{n}) / \mathcal{O}(n)$

Neben den vorgenannten Operationen kommen Weitere in Betracht:

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

Siehe auch

• Effizienz