Suchbaum - LinkFang.de





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. Diese Repräsentation unterstützt ein effizientes Suchen nach Art der Intervallschachtelung, wenn die Elemente in einer Totalordnung angeordnet werden können.

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.

Der maximale Aufwand für das Suchen, d. i. die Maximalzahl der erforderlichen Vergleiche, ist proportional zur Baumhöhe. Bei einem balancierten Baum ist die Höhe logarithmisch in der Anzahl n der Elemente, während sie bei einem zu einer linearen Liste degenerierten Baum proportional zu n ist.

Spezielle Suchbäume

Hauptartikel: Binärer Suchbaum

Insbesondere bei den binären Suchbäumen (engl. BST von binary search tree), bei denen ein Knoten maximal zwei Kindknoten besitzt, sind viele Varianten entwickelt worden, die der Degeneration entgegenwirken sollen.

Nicht binär sind folgende Suchbäume:

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

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 zusätzliche Speicherverbrauch eines Suchbaums – über die Nutzdaten hinaus – ist im Allgemeinen linear in der Anzahl n der Elemente, also [math]\mathcal{O}(n)[/math].

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 mittlere < maximale Laufzeiten gegenübergestellt, wobei die maximale weggelassen ist, wenn sie mit der mittleren zusammenfällt.

Laufzeitkomplexitäten
Suchbaum Suchen
(=Baumhöhe)
Traversieren zum
Nachbarknoten
Einfügen Löschen
AVL-Baum [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math]
Rot-Schwarz-Baum [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(\log n)[/math]
2-3-4-Baum [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math]
B-Baum [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math] [math]\mathcal{O}(\log n)[/math]
Splay-Baum [math]\mathcal{O}(\log n)[/math] 1 [math]\!\lt\! \mathcal{O}(n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(n)[/math] [math]\mathcal{O}(\log n)[/math] 1 [math]\!\lt\! \mathcal{O}(n)[/math] [math]\mathcal{O}(\log n)[/math] 1 [math]\!\lt\! \mathcal{O}(n)[/math]
binärer Suchbaum [math]\mathcal{O}(\log n)[/math] 2 [math]\!\lt\! \mathcal{O}(n)[/math] [math]\mathcal{O}(1)\!\lt\!\mathcal{O}(n)[/math] [math]\mathcal{O}(1)[/math] [math]\mathcal{O}(\log n)[/math] 2 [math]\!\lt\!\mathcal{O}(n)[/math]
1 Abhängig vom Zugriffsmuster der Anwendung können bei Splay-Bäumen auch unterlogarihmische mittlere Laufzeiten vorkommen.

2 Unter den unbalancierten binären Suchbäumen gibt es Bäume, bei denen [math]\mathcal{O}(\log n)[/math] nicht garantiert werden kann. Die Angabe [math]\mathcal{O}(\log n)[/math] 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

Weblinks


Kategorien: Suchbaum | Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Suchbaum (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.