Benutzer:Randolph33

Ein Rot-Schwarz-Baum, auch RS-Baum oder RB-Baum, (englisch red–black tree oder RB tree) ist eine Datenstruktur vom Typ binärer Suchbaum, die „sehr schnellen“ Zugriff auf die in ihr gespeicherten Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leonidas J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten. Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente (meist Paare vom Typ (Schlüssel,Wert)) werden durch zwei Forderungen erreicht, die die Balance des Baums in einer Weise festlegen, dass die Höhe eines Baums mit ${\displaystyle n}$ Elementen nie größer als ${\displaystyle 2\log _{2}(n\!+\!2)\!-\!2}$ sein kann. Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in ${\displaystyle {\mathcal {O}}(\log n)}$ ausgeführt werden. – Zum Artikel …