Suchbaum Buchkatalog

Quelle: Wikipedia. Seiten: 34. Kapitel: Rot-Schwarz-Baum, Binärer Suchbaum, AVL-Baum, B-Baum, R-Baum, B+-Baum, Binary Space Partitioning, Splay-Baum, B*-Baum, Octree, Suffixbaum, 2-3-4-Baum, Gewichteter binärer Suchbaum, Balancierter Baum, Treap, K-d-Baum, Bereichsbaum, UB-Baum, Quadtree, Trie, Und-Oder-Baum, Fractional Cascading. Auszug: 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, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leo J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten. Die schnellen Zugriffzeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch fünf Eigenschaften erreicht, die zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit n Werten nie größer wird als . Somit können die wichtigsten Operationen in Suchbäumen - suchen, einfügen und löschen - garantiert in O(log n) ausgeführt werden. Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, in dem jeder Knoten eine Zusatzinformation - seine Farbe - trägt. Neben den Bedingungen, die an binäre Suchbäume gestellt werden, wird an Rot-Schwarz-Bäume jedoch noch die Forderung gestellt, folgende fünf Eigenschaften immer zu erfüllen: Beispiel eines Rot-Schwarz-BaumesDurch diese fünf Bedingungen wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt: Die Anzahl der Knoten auf dem längsten Pfad von der Wurzel zu einem Blatt ist nie mehr als doppelt so hoch wie die Anzahl der Knoten des kürzesten Pfades von der Wurzel zu einem Blatt. Hierdurch ist ein Rot-Schwarz-Baum immer annähernd balanciert, was für die Operationen suchen, einfügen und löschen wichtig ist, da deren Laufzeitkosten proportional zur Höhe des Baumes sind. Da die Höhe eines Rot-Schwarz-Baumes dadurch, dass er annähernd balanciert ist, minimiert wird, wird somit ebenfalls die Laufzeit der oben genannten Operationen minimiert. Somit kann man für Rot-Schwarz-Bäume eine obere Schranke für die Laufzeit der Operationen suchen, einfügen und löschen garantieren. Um zu verstehen, warum diese fünf Eigenschaften eine obere Schranke für die Laufzeit