Suchbaum

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:

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

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Suchbaum — Such|baum, der (EDV): ↑ Baum (3) mit einer hierarchischen Struktur, in den Daten leicht u. schnell eingeordnet u. in dem sie leicht u. schnell wieder gefunden werden können. * * * Suchbaum,   ein Baum, der das leichte und schnelle Einsortieren… …   Universal-Lexikon

  • 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… …   Deutsch Wikipedia

  • Binärer Suchbaum — der Höhe 5 mit 13 Knoten: Wurzel J und Blättern C, G, N, Q, U und X In der Informatik ist ein binärer Suchbaum eine spezielle Implementierung der abstrakten Datenstruktur Suchbaum. Ein binärer Suchbaum, häufig abgekürzt als BST (von englisch …   Deutsch Wikipedia

  • Balancierter Suchbaum — Ein Balancierter Baum ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist. Inhaltsverzeichnis 1 Problem:… …   Deutsch Wikipedia

  • Gewichteter binärer Suchbaum — Ein binärer Suchbaum mit 2 Knoten und Gewichts Angaben (rot) In der Informatik ist ein gewichteter binärer Suchbaum eine Ausprägung der abstrakten Datenstruktur binärer Suchbaum, bei der jedem Knoten neben Schlüssel und anderen Daten ein Gewicht… …   Deutsch Wikipedia

  • Red-black-tree — Ein Rot Schwarz Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, die sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot Schwarz Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben[1],… …   Deutsch Wikipedia

  • Schwarz-Rot-Baum — Ein Rot Schwarz Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, die sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot Schwarz Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben[1],… …   Deutsch Wikipedia

  • AVL-Baum — Abbildung 1: AVL Baum mit Balance Werten (grün) AVL Baum Komplexität Platz O(n) …   Deutsch Wikipedia

  • Bellman-Algorithmus — Der Algorithmus von Bellman konstruiert aus einer gegebenen Schlüsselliste und einer korrespondierenden Suchwahrscheinlichkeit einen optimalen binären Suchbaum. Der Algorithmus basiert auf dem von Richard Bellman 1957 gefundenen Satz über… …   Deutsch Wikipedia

  • Balancierter Baum — Ein Balancierter Baum ist in der Informatik ein Spezialfall der Datenstruktur Baum, der eine maximale Höhe von garantiert, wobei n die Anzahl der Elemente im Baum angibt und c eine von n unabhängige Konstante ist. Manche Autoren rechnen auch… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”