Rot-Schwarz-Baum
Datenstruktur in der Informatik / aus Wikipedia, der freien encyclopedia
Liebe Wikiwand-AI, fassen wir uns kurz, indem wir einfach diese Schlüsselfragen beantworten:
Können Sie die wichtigsten Fakten und Statistiken dazu auflisten Rot-Schwarz-Baum?
Fass diesen Artikel für einen 10-Jährigen zusammen
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,[1] 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.[2] 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 Elementen nie größer als sein kann.[Anm. 1] Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in (s. Landau-Symbole) ausgeführt werden.
Rot-Schwarz-Baum | ||
---|---|---|
Komplexität bei Elementen | ||
Platz | ||
Operation | im Mittel, amortisiert |
Worst Case |
Suchen | ||
Querschritt | ||
Min, Max | ||
Einfügen | † | |
Löschen | † | |
Platz- und Zeit-Komplexitäten |