Suchbaum
aus Wikipedia, der freien Enzyklopädie
In der Informatik ist ein Suchbaum eine auf Bäumen basierende abstrakte Datenstruktur, die sich dadurch auszeichnet, in ihr gespeicherte Objekte und Elemente einer geordneten Menge effizient suchen zu können.
[Bearbeiten] Operationen
Suchbäume unterstützen die Operationen
- insert, zum Einfügen eines Elementes,
- delete, zum Entfernen eines Elementes und
- find, zum Auffinden eines Elementes.
Der Aufwand dieser drei Operationen in O-Notation ist jeweils O(log(n)), wobei n die Anzahl der Knoten (=Elemente) ist.
[Bearbeiten] Spezielle Suchbäume
Neben dem normalen binären Suchbaum, welcher zwar einfach zu implementieren ist, jedoch nicht garantieren kann, dass die oben genannten Operationen insert, delete und find effizient ausgeführt werden können, gibt es spezielle binäre Suchbäume, welche durch verschiedene Techniken garantieren, dass sie immer balanciert sind, und die Operationen insert, delete und find somit immer effizient (in logarithmischer Zeit) ausgeführt werden können. Einige dieser speziellen Suchbäume sind:
