Rot-schwarzer Baum

In der Informatik ist ein Rot-Schwarz-Baum eine selbstbalancierende binäre Suchbaum- Datenstruktur, die sich durch schnelles Speichern und Abrufen geordneter Informationen auszeichnet. Die Knoten eines Rot-Schwarz-Baums enthalten ein zusätzliches „Farbbit“, das oft als Rot und Schwarz dargestellt wird und dazu beiträgt, dass der Baum stets annähernd ausgeglichen ist. ^{[ 1 ]}

Wird der Entscheidungsbaum modifiziert, wird er neu angeordnet und „neu eingefärbt“, um die Farbgebungseigenschaften wiederherzustellen, die das Ausmaß der Unausgewogenheit im schlimmsten Fall begrenzen. Die Eigenschaften sind so gestaltet, dass diese Neuanordnung und Farbgebung effizient durchgeführt werden kann.

Die (Neu-)Ausbalancierung ist nicht perfekt, garantiert aber eine Suche in Zeit O(n), wobei n die Anzahl der Einträge im Baum ist. Die Einfüge- und Löschoperationen sowie die Baumumordnung und -umfärbung werden ebenfalls in O(n) ausgeführt. ^{[ 2 ] [ 3 ]}${\displaystyle O(\log n)}$${\displaystyle n}$${\displaystyle O(\log n)}$

Die Speicherung der Farbe jedes Knotens benötigt nur ein Bit pro Knoten, da es nur zwei Farben gibt (aufgrund der Speicherausrichtung in manchen Programmiersprachen kann der tatsächliche Speicherverbrauch abweichen). Der Baum enthält keine weiteren Daten, die ihn als Rot-Schwarz-Baum kennzeichnen, daher ist sein Speicherbedarf nahezu identisch mit dem eines klassischen (ungefärbten) binären Suchbaums . In manchen Fällen kann das zusätzliche Bit ohne zusätzlichen Speicherbedarf gespeichert werden.

1972 erfand Rudolf Bayer ^{[ 4 ]} eine Datenstruktur, die einen Spezialfall vierter Ordnung eines B-Baums darstellte . Diese Bäume enthielten alle Pfade von der Wurzel zu den Blättern mit der gleichen Anzahl an Knoten und bildeten somit perfekt balancierte Bäume. Es handelte sich jedoch nicht um binäre Suchbäume. Bayer nannte sie in seiner Arbeit „symmetrische binäre B-Bäume“, und später wurden sie als 2-3-4-Bäume oder auch 2-3-Bäume bekannt . ^{[ 5 ]}

In einer 1978 veröffentlichten Arbeit mit dem Titel „A Dichromatic Framework for Balanced Trees“ ^{[ 6 ]} leiteten Leonidas J. Guibas und Robert Sedgewick den Rot-Schwarz-Baum aus dem symmetrischen binären B-Baum ab. ^{[ 7 ]} Die Farbe „Rot“ wurde gewählt, weil sie die beste Farbe war, die der den Autoren bei ihrer Arbeit im Xerox PARC zur Verfügung stehende Farblaserdrucker erzeugen konnte . ^{[ 8 ]} Guibas gab in einer anderen Antwort an, dass die Wahl auf die ihnen zur Verfügung stehenden roten und schwarzen Stifte zum Zeichnen der Bäume zurückzuführen war. ^{[ 9 ]}

1993 führte Arne Andersson die Idee eines rechtsneigenden Baums ein, um Einfüge- und Löschvorgänge zu vereinfachen. ^{[ 10 ]}

1999 zeigte Chris Okasaki , wie man die Einfügeoperation rein funktional gestalten kann. Ihre Ausgleichsfunktion musste nur vier unausgeglichene Fälle und einen standardmäßigen ausgeglichenen Fall berücksichtigen. ^{[ 11 ]}

Der ursprüngliche Algorithmus verwendete acht unausgewogene Fälle, Cormen et al. (2001) reduzierten diese jedoch auf sechs. ^{[ 1 ]} Sedgewick zeigte, dass die Einfügeoperation in nur 46 Zeilen Java-Code implementiert werden kann . ^{[ 12 ] [ 13 ]} Im Jahr 2008 schlug Sedgewick den linkslastigen Rot-Schwarz-Baum vor , der auf Anderssons Idee zur Vereinfachung der Einfüge- und Löschoperationen basierte. Ursprünglich erlaubte Sedgewick Knoten, deren zwei Kinder rot sind, wodurch seine Bäume eher 2-3-4-Bäumen ähnelten. Später wurde diese Einschränkung jedoch hinzugefügt, sodass die neuen Bäume nun eher 2-3-Bäumen ähneln. Sedgewick implementierte den Einfügealgorithmus in nur 33 Zeilen und verkürzte damit seinen ursprünglichen Code von 46 Zeilen erheblich. ^{[ 14 ] [ 15 ]}

Die Schwarztiefe eines Knotens ist definiert als die Anzahl schwarzer Knoten von der Wurzel bis zu diesem Knoten (d. h. die Anzahl der schwarzen Vorfahren). Die Schwarzhöhe eines Rot-Schwarz-Baums ist die Anzahl schwarzer Knoten auf jedem Pfad von der Wurzel zu den Blättern, die gemäß Anforderung 4 konstant ist (alternativ könnte sie als die Schwarztiefe eines beliebigen Blattknotens definiert werden). ^{[ 16 ] : 154–165} Die Schwarzhöhe eines Knotens ist die Schwarzhöhe des von ihm verwurzelten Teilbaums. In diesem Artikel wird die Schwarzhöhe eines Nullknotens auf 0 gesetzt, da sein Teilbaum, wie in der Beispielabbildung dargestellt, leer ist und seine Baumhöhe ebenfalls 0 beträgt.

Zusätzlich zu den Anforderungen an einen binären Suchbaum müssen an einen Rot-Schwarz-Baum folgende Bedingungen erfüllt sein : ^{[ 17 ]}

1. Jeder Knoten ist entweder rot oder schwarz.
2. Alle Nullknoten werden als schwarz betrachtet.
3. Ein roter Knoten hat kein rotes Kind.
4. Jeder Pfad von einem gegebenen Knoten zu einem seiner Blattknoten (d. h. zu einem beliebigen Nachfolgerknoten vom Typ Null) verläuft über die gleiche Anzahl schwarzer Knoten.
5. (Schlussfolgerung) Hat ein Knoten N genau ein Kind, so muss dieses Kind rot sein. Wäre das Kind schwarz, lägen seine Blätter in einer anderen schwarzen Tiefe als der Nullknoten von N (der gemäß Regel 2 als schwarz gilt), was gegen Anforderung 4 verstößt .

Einige Autoren, z. B. Cormen et al. ^{[ 17 ]} , behaupten, die Wurzel sei schwarz, sei die fünfte Bedingung; Mehlhorn & Sanders ^{[ 16 ]} und Sedgewick & Wayne ^{[ 15 ] hingegen nicht : 432–447} . Da die Wurzel stets von rot nach schwarz geändert werden kann, hat diese Regel kaum Auswirkungen auf die Analyse. Auch in diesem Artikel wird sie weggelassen, da sie die rekursiven Algorithmen und Beweise geringfügig beeinträchtigt.

Beispielsweise ist jeder perfekte Binärbaum , der nur aus schwarzen Knoten besteht, ein Rot-Schwarz-Baum.

Die Leseoperationen, wie Suchen oder Baumtraversieren, beeinträchtigen keine der Anforderungen. Im Gegensatz dazu erfüllen die Änderungsoperationen Einfügen und Löschen die Anforderungen 1 und 2 problemlos, erfordern jedoch hinsichtlich der übrigen Anforderungen zusätzlichen Aufwand, um eine Verletzung der Anforderung 3 zu vermeiden.Verstoß gegen die rote Vorschrift oder gegen Anforderung 4, genannt einschwarze Gewalt .

Die Anforderungen gewährleisten eine entscheidende Eigenschaft von Rot-Schwarz-Bäumen: Der Pfad von der Wurzel zum entferntesten Blatt ist höchstens doppelt so lang wie der Pfad von der Wurzel zum nächstgelegenen Blatt . Dadurch ist der Baum höhenbalanciert . Da Operationen wie Einfügen, Löschen und Suchen von Werten im ungünstigsten Fall eine Laufzeit proportional zur Baumhöhe benötigen , ermöglicht diese obere Schranke für die Höhe, dass Rot-Schwarz-Bäume im ungünstigsten Fall effizient sind, d. h. logarithmisch in der Anzahl der Einträge (eine Eigenschaft, die alle selbstbalancierenden Bäume, z. B. AVL-Bäume oder B-Bäume , gemeinsam haben, nicht aber gewöhnliche binäre Suchbäume ). Einen mathematischen Beweis finden Sie im Abschnitt „ Beweis der Schranken“ . ${\displaystyle h}$${\displaystyle n}$${\displaystyle h\in O(\log n)}$

Rot-Schwarz-Bäume ermöglichen, wie alle binären Suchbäume , einen effizienten sequenziellen Zugriff auf ihre Elemente (z. B. In-Order-Traversierung , d. h. in der Reihenfolge Links–Wurzel–Rechts). Sie unterstützen aber auch einen asymptotisch optimalen direkten Zugriff durch Traversierung von der Wurzel zu den Blättern, was zu einer Suchzeit von O(n²) führt. ${\displaystyle O(\log n)}$

Rot-Schwarz-Bäume ähneln in ihrer Struktur 2-3-4-Bäumen , die B-Bäume der Ordnung 4 sind. ^{[ 18 ]} In 2-3-4-Bäumen kann jeder Knoten zwischen 1 und 3 Werte enthalten und zwischen 2 und 4 Kinder haben. Diese 2-3-4-Knoten entsprechen den Gruppen aus schwarzem Knoten und rotem Kind in Rot-Schwarz-Bäumen, wie in Abbildung 1 dargestellt. Es handelt sich nicht um eine 1:1-Korrespondenz , da 3-Knoten zwei äquivalente Darstellungen haben: Das rote Kind kann entweder links oder rechts liegen. Die linksgeneigte Variante des Rot-Schwarz-Baums stellt diese Beziehung exakt 1:1 her, indem sie nur die Darstellung des linken Kindes zulässt. Da jedem 2-3-4-Knoten ein schwarzer Knoten zugeordnet ist, besagt Invariante 4 von Rot-Schwarz-Bäumen, dass sich alle Blätter eines 2-3-4-Baums auf derselben Ebene befinden.

Trotz struktureller Ähnlichkeiten sind Operationen auf Rot-Schwarz-Bäumen ökonomischer als auf B-Bäumen. B-Bäume erfordern die Verwaltung von Vektoren variabler Länge, während Rot-Schwarz-Bäume einfach Binärbäume sind. ^{[ 19 ]}

Rot-Schwarz-Bäume bieten Worst-Case-Garantien für Einfüge-, Lösch- und Suchzeiten. Dies macht sie nicht nur in zeitkritischen Anwendungen wie Echtzeitanwendungen wertvoll , sondern auch zu wichtigen Bausteinen anderer Datenstrukturen mit Worst-Case-Garantien. Beispielsweise basieren viele Datenstrukturen der algorithmischen Geometrie auf Rot-Schwarz-Bäumen, und der Completely Fair Scheduler (CFS) sowie der epoll -Systemaufruf des Linux-Kernels verwenden Rot-Schwarz-Bäume. ^{[ 20 ] [ 21 ]} Der AVL-Baum ist eine weitere Struktur, die Suchen, Einfügen und Löschen unterstützt . AVL-Bäume können rot-schwarz gefärbt werden und sind somit eine Teilmenge der Rot-Schwarz-Bäume. Die Worst-Case-Höhe eines AVL-Baums beträgt das 0,720-Fache der Worst-Case-Höhe eines Rot-Schwarz-Baums, wodurch AVL-Bäume eine höhere Balance aufweisen. Leistungsmessungen von Ben Pfaff mit realistischen Testfällen in 79 Durchläufen ergaben AVL/RB-Verhältnisse zwischen 0,677 und 1,077, einen Median von 0,947 und einen geometrischen Mittelwert von 0,910. ^{[ 22 ]} Die Leistungsfähigkeit von WAVL-Bäumen liegt zwischen der von AVL-Bäumen und der von Rot-Schwarz-Bäumen. ${\displaystyle O(\log n)}$

Rot-Schwarz-Bäume sind besonders in der funktionalen Programmierung wertvoll , wo sie zu den gebräuchlichsten persistenten Datenstrukturen zählen. Sie werden verwendet, um assoziative Arrays und Mengen zu konstruieren , die frühere Versionen nach Änderungen beibehalten können. Die persistente Version von Rot-Schwarz-Bäumen benötigt neben Zeit auch Speicherplatz für jede Einfügung oder Löschung. ${\displaystyle O(\log n)}$

Zu jedem 2-3-4-Baum existieren entsprechende Rot-Schwarz-Bäume mit Datenelementen in derselben Reihenfolge. Einfüge- und Löschoperationen in 2-3-4-Bäumen entsprechen Farbumkehr und Rotation in Rot-Schwarz-Bäumen. Daher sind 2-3-4-Bäume ein wichtiges Hilfsmittel zum Verständnis der Logik von Rot-Schwarz-Bäumen. Aus diesem Grund werden 2-3-4-Bäume in vielen einführenden Lehrbüchern zu Algorithmen direkt vor Rot-Schwarz-Bäumen behandelt, obwohl sie in der Praxis selten Anwendung finden.

Im Jahr 2008 führte Sedgewick eine vereinfachte Version des Rot-Schwarz-Baums ein, den sogenannten linksgeneigten Rot-Schwarz-Baum ^{[ 23 ]} , indem er einen zuvor nicht spezifizierten Freiheitsgrad in der Implementierung eliminierte. Der linksgeneigte Rot-Schwarz-Baum (LLRB) hat die zusätzliche Invariante, dass alle roten Kanten nach links geneigt sein müssen, außer bei Einfüge- und Löschvorgängen. Rot-Schwarz-Bäume können für jede Operationsfolge isometrisch zu ^{2-3-Bäumen [} 24] oder 2-3-4-Bäumen [23] gestaltet werden. Die Isometrie des 2-3-4-Baums wurde 1978 von Sedgewick beschrieben [6]. Bei 2-3-4 ^{- Bäumen} wird ^{die Isometrie durch einen „ Farbumschwung} “ erreicht, der einer Aufteilung entspricht. Dabei verlässt die rote Farbe zweier Kindknoten die Kindknoten und wandert zum Elternknoten.

Die ursprüngliche Beschreibung des Tango-Baums , eines für schnelle Suchvorgänge optimierten Baumtyps, verwendet ausdrücklich Rot-Schwarz-Bäume als Teil seiner Datenstruktur. ^{[ 25 ]}

Ab Java 8 wurde die HashMap so modifiziert, dass anstelle einer LinkedList zur Speicherung von Elementen mit kollidierenden Hashcodes ein Rot-Schwarz-Baum verwendet wird. Dies führt zu einer Verbesserung der Zeitkomplexität der Suche nach einem solchen Element von n auf n, wobei n die Anzahl der Elemente mit kollidierenden Hashcodes ist. ^{[ 26 ]}${\displaystyle O(m)}$${\displaystyle O(\log m)}$${\displaystyle m}$

Die Leseoperationen auf einem Rot-Schwarz-Baum, wie Suche oder Baumtraversierung, erfordern keine Modifikationen gegenüber denen für binäre Suchbäume , da jeder Rot-Schwarz-Baum ein Spezialfall eines einfachen binären Suchbaums ist. Das unmittelbare Ergebnis einer Einfügung oder Löschung kann jedoch die Eigenschaften eines Rot-Schwarz-Baums verletzen. Die Wiederherstellung dieser Eigenschaften wird als Rebalancing bezeichnet, sodass Rot-Schwarz-Bäume selbstbalancierend werden. Das Rebalancing (d. h. Farbänderungen) hat eine Worst-Case-Zeitkomplexität von O ⁽ n²) und eine durchschnittliche Komplexität von O (n²) [ ^{27 ] : 310 [ 16 ] : 158,} wobei diese Werte in der Praxis sehr schnell ablaufen. Außerdem benötigt das Rebalancing maximal drei Baumrotationen ^{[ 28 ]} (zwei davon zum Einfügen). ${\displaystyle O(\log n)}$${\displaystyle O(1)}$

Dies ist eine Beispielimplementierung von Einfügen und Entfernen in C. Nachfolgend sind die Datenstrukturen und die rotate_subtreeHilfsfunktion aufgeführt, die in den Beispielen zum Einfügen und Entfernen verwendet werden.

typedef enum Color : char {SCHWARZ ,ROT} Farbe ;typedef enum Direction : char {LINKS ,RECHTS} Richtung ;// Rot-Schwarz-Baumknotentypedef struct Node {struct Node * parent ; // null für den WurzelknotenUnion {// Union, damit wir ->left/->right oder ->child[0]/->child[1] verwenden könnenstruct {struct Node * left ;struct Node * right ;};struct Node * child [ 2 ];};Farbe Farbe ;int key ;} Knoten ;typedef struct {struct Node * root ;} Baum ;static Direction direction ( const Node * N ) {return N == N -> parent -> right ? RIGHT : LEFT ;}Node * rotate_subtree ( Tree * tree , Node * sub , Direction dir ) {Node * sub_parent = sub -> parent ;Node * new_root = sub -> child [ 1 - dir ]; // 1 - dir ist die entgegengesetzte RichtungNode * new_child = new_root -> child [ dir ];sub -> child [ 1 - dir ] = new_child ;if ( new_child ) {neues_Kind -> Elternteil = Unterkind ;}new_root -> child [ dir ] = sub ;new_root -> parent = sub_parent ;Unterverzeichnis -> Elternverzeichnis = neues_Wurzelverzeichnis ;if ( sub_parent ) {Unterelternteil -> Kind [ Unterelternteil == Unterelternteil -> rechts ] = neue Wurzel ;} anders {Baum -> Wurzel = neue_Wurzel ;}return new_root ;}

Der Vorschlag unterteilt Einfüge- und Löschvorgänge (von einigen sehr einfachen Fällen abgesehen) in sechs Konstellationen von Knoten, Kanten und Farben, die als Fälle bezeichnet werden. Für Einfüge- und Löschvorgänge enthält der Vorschlag genau einen Fall, der den Baum um eine schwarze Ebene näher an die Wurzel rückt und eine Schleife bildet; die anderen fünf Fälle gleichen den Baum selbstständig aus. Die komplexeren Fälle sind in einem Diagramm dargestellt.

• Ein rotes Symbol steht für einen Knoten, ein schwarzes Symbol für einen Knoten (mit einer Höhe von mindestens 1). Ein schwarzes Symbol steht für die Farbe Rot oder Schwarz eines Knotens, der nicht NULL ist, wobei im gesamten Diagramm dieselbe Farbe verwendet wird. NULL-Knoten werden in den Diagrammen nicht dargestellt.
• Die Variable N bezeichnet den aktuellen Knoten, der in den Diagrammen mit N oder N gekennzeichnet ist.
• Ein Diagramm enthält drei Spalten und zwei bis vier Aktionen. Die linke Spalte zeigt die erste Iteration, die rechte Spalte die höheren Iterationen, die mittlere Spalte zeigt die Segmentierung eines Falls in seine verschiedenen Aktionen. ^{[ 29 ]}

1. Die Aktion „Eintritt“ zeigt die Knotenkonstellation mit ihren Farben, die einen Fall definiert und meist einige der Anforderungen verletzt . Ein blauer Rahmen umgibt den aktuellen Knoten N , und die anderen Knoten sind entsprechend ihrer Beziehung zu N beschriftet .
2. Wenn eine Drehung als sinnvoll erachtet wird, wird dies in der nächsten Aktion dargestellt, die mit „Drehung“ beschriftet ist.
3. Falls eine Umfärbung als nützlich erachtet wird, wird dies im nächsten Schritt dargestellt, der mit „Farbe“ beschriftet ist. ^{[ 30 ]}
4. Falls noch Reparaturen nötig sind, greifen die Fälle auf Code anderer Fälle zurück. Dies geschieht nach einer Neuzuordnung des aktuellen Knotens N , der dann wieder einen blauen Ring trägt und auf den sich gegebenenfalls weitere Knoten beziehen. Diese Aktion wird als „Neuzuordnung“ bezeichnet. Sowohl beim Einfügen als auch beim Löschen gibt es (genau) einen Fall, der eine schwarze Ebene näher an die Wurzel iteriert; die neu zugeordnete Konstellation erfüllt dann die jeweilige Schleifeninvariante.

• Ein möglicherweise nummeriertes Dreieck mit einem schwarzen Kreis darüber repräsentiert einen rot-schwarzen Teilbaum (der gemäß Anforderung 3 mit seinem Elternknoten verbunden ist ), dessen schwarze Höhe der Iterationsebene minus eins entspricht, also in der ersten Iteration null ist. Seine Wurzel kann rot oder schwarz sein. Ein möglicherweise nummeriertes Dreieck repräsentiert einen rot-schwarzen Teilbaum mit einer um eins geringeren schwarzen Höhe, d. h. dessen Elternknoten hat in der zweiten Iteration die schwarze Höhe null.

Bemerkung

Der Beispielcode verwendet der Einfachheit halber die Disjunktion :

U == NULL || U->color == BLACK // considered black

und die Konjunktion :

U != NULL && U->color == RED   // not considered black

Dabei ist zu beachten, dass beide Anweisungen nicht vollständig ausgewertet werden, wenn . Dann bleibt U == NULLin beiden Fällen unberührt (siehe Kurzschlussauswertung ). (Der Kommentar entspricht Anforderung 2. )U->colorconsidered black

Die zugehörigen if-Aussagen müssen weitaus seltener auftreten, wenn der Vorschlag ^{[ 29 ]} umgesetzt wird.

Das Einfügen beginnt damit, dass der neue (nicht-NULL-)Knoten N an der Position eines NULL-Knotens im binären Suchbaum platziert wird. Der Schlüssel des Vorgängerknotens in der In-Order-Reihenfolge ist kleiner als der Schlüssel des neuen Knotens, welcher wiederum kleiner ist als der Schlüssel seines Nachfolgers in der In-Order-Reihenfolge. (Häufig ist diese Positionierung das Ergebnis einer Suche im Baum unmittelbar vor dem Einfügevorgang und besteht aus einem Knoten Pund einer Richtung dirmit P->child[dir] == NULL.) Der neu eingefügte Knoten wird vorübergehend rot gefärbt, sodass alle Pfade dieselbe Anzahl schwarzer Knoten wie zuvor enthalten. Wenn jedoch sein Elternknoten P ebenfalls rot ist, führt diese Aktion zu einer Rotverletzung .

// Elternelement ist optionalvoid insert ( Tree * tree , Node * node , Node * parent , Direction dir ) {Knoten -> Farbe = ROT ;Knoten -> Elternknoten = Elternknoten ;if ( ! parent ) {Baum -> Wurzel = Knoten ;zurückkehren ;}Eltern - Kind-Zustand [ Verzeichnis ] = Knoten ;// Den Baum neu ausbalancierenTun {// Fall Nr. 1if ( parent -> color == BLACK ) {zurückkehren ;}Knoten * Großelternteil = Elternteil -> Elternteil ;if ( ! grandparent ) {// Fall Nr. 4Eltern- > Farbe = SCHWARZ ;zurückkehren ;}dir = Richtung ( Eltern );Node * onkel = Großelternteil -> Kind [ 1 - dir ];if ( ! uncle || uncle -> color == BLACK ) {if ( node == parent -> child [ 1 - dir ]) {// Fall Nr. 5rotate_subtree ( tree , parent , dir );Knoten = Elternknoten ;Elternteil = Großelternteil -> Kind [ Verzeichnis ];}// Fall Nr. 6rotate_subtree ( tree , grandparent , 1 - dir );Eltern- > Farbe = SCHWARZ ;Großelternteil -> Farbe = ROT ;zurückkehren ;}// Fall Nr. 2Eltern- > Farbe = SCHWARZ ;Onkel -> Farbe = SCHWARZ ;Großelternteil -> Farbe = ROT ;Knoten = Großelternteil ;} while (( parent = node -> parent ));// Fall Nr. 3zurückkehren ;}

Die Ausgleichsschleife der Einfügeoperation weist folgende Invarianten auf :

• Node ist der aktuelle Knoten, ursprünglich der Einfügeknoten.
• Der Knoten ist zu Beginn jeder Iteration rot.
• Anforderung 3 ist für alle Paare Knoten←Elternteil erfüllt, mit der möglichen Ausnahme Knoten ← Elternteil , wenn Elternteil ebenfalls rot ist (eine Rotverletzung am Knoten ).
• Alle anderen Eigenschaften (einschließlich Anforderung 4 ) sind im gesamten Baum erfüllt.

vor

Fall

Drehung

Abtretung

nach

nächste

Δ h

P

G

U

X

P

G

U

X

I1

I2

N := G

?

?

2

—

I3

—

I4

ich

I5

P ↶ N

N := P

O

I6

0

O

I6

P ↷ G

Einführen Diese Zusammenfassung zeigt in ihren vorhergehenden Spalten, dass alle möglichen Fälle [ 31 ] von Konstellationen abgedeckt sind.

• In den Diagrammen steht P für den Elternteil von N , G für dessen Großelternteil und U für dessen Onkel. In der Tabelle kennzeichnet „—“ die Wurzel.
• Die Diagramme zeigen den Elternknoten P als linkes Kind seines Elternknotens G , obwohl P sich theoretisch auf beiden Seiten befinden könnte. Der Beispielcode deckt beide Möglichkeiten mithilfe der Variable `side` ab dir.
• Die Diagramme zeigen auch die Fälle, in denen P rot ist, die Rotverletzung.
• Die Spalte x gibt die Änderung der Kindrichtung an, d. h. o (für „äußeres“) bedeutet, dass P und N beide linke oder beide rechte Kinder sind, während i (für „inneres“) bedeutet, dass sich die Kindrichtung von P zu N ändert .
• Die vorherige Spaltengruppe definiert den Fall, dessen Name in der Spalte „ Fall“ angegeben ist . Dabei werden mögliche Werte in leeren Zellen ignoriert. Im Fall I2 deckt der Beispielcode also beide Möglichkeiten der Kindrichtungen von N ab , obwohl das zugehörige Diagramm nur eine zeigt.
• Die Zeilen in der Zusammenfassung sind so angeordnet, dass die Abdeckung aller möglichen RB-Fälle leicht verständlich ist.
• Die Spaltenrotation gibt an, ob eine Rotation zur Neuausrichtung beiträgt.
• Die Spaltenzuordnung zeigt eine Zuordnung von N vor dem nächsten Schritt. Dies führt möglicherweise auch zu einer Neuzuordnung der anderen Knoten P , G und U.
• Wenn sich durch den Fall etwas geändert hat, wird dies in der Spaltengruppe danach angezeigt .
• Ein Zeichen in der nächsten Spalte signalisiert, dass die Neuausrichtung mit diesem Schritt abgeschlossen ist. Falls die darauffolgende Spalte genau einen Fall ermittelt, wird dieser als nachfolgender Fall aufgeführt; andernfalls werden Fragezeichen angezeigt.
• Im zweiten Fall besteht das Problem der Neuausrichtung darin, dass der Baum um eine Ebene höher liegt, wobei der Vorgängerknoten G zum neuen aktuellen Knoten N wird . Daher sind maximal h Iterationsschritte erforderlich, um den Baum zu reparieren (wobei h die Höhe des Baums ist). Da die Wahrscheinlichkeit einer Eskalation mit jedem Schritt exponentiell abnimmt, sind die gesamten Neuausrichtungskosten im Durchschnitt konstant, genauer gesagt amortisiert konstant .${\displaystyle \Delta h=2}$${\displaystyle {\tfrac {h}{2}}}$
• In den Fällen I6 und I5 + I6 finden Rotationen außerhalb der Schleife statt. Daher treten insgesamt höchstens zwei Rotationen auf.

Der Elternknoten P des aktuellen Knotens ist schwarz, daher ist Bedingung 3 erfüllt. Bedingung 4 ist gemäß der Schleifeninvariante ebenfalls erfüllt .

erste Iteration

höhere Iteration

Fall 2 einfügen

Sind sowohl der Elternknoten P als auch der Onkelknoten U rot, können beide schwarz eingefärbt werden, und der Großelternknoten G wird rot, um Anforderung 4 zu erfüllen . Da jeder Pfad über den Elternknoten oder Onkelknoten auch über den Großelternknoten führen muss, bleibt die Anzahl der schwarzen Knoten auf diesen Pfaden unverändert. Allerdings kann der Großelternknoten G nun Anforderung 3 verletzen, wenn er einen roten Elternknoten hat. Nach der Umbenennung von G in N ist die Schleifeninvariante erfüllt, sodass die Neuausrichtung auf einer um zwei Baumebenen höheren schwarzen Ebene wiederholt werden kann.

Der Einfügefall 2 wurde n- mal ausgeführt, und die Gesamthöhe des Baums hat sich um 1 erhöht und beträgt nun h . Der aktuelle Knoten N ist die (rote) Wurzel des Baums, und alle RB-Eigenschaften sind erfüllt. ${\displaystyle {\tfrac {h-1}{2}}}$

Der Elternknoten P ist rot und bildet die Wurzel. Da auch N rot ist, ist Bedingung 3 nicht erfüllt. Nach dem Farbwechsel von P hat der Baum jedoch eine RB-Form. Die schwarze Höhe des Baums erhöht sich um 1.

erste Iteration

höhere Iteration

Fall 5 einfügen

Der Elternknoten P ist rot, der Onkelknoten U schwarz. Ziel ist es, den Elternknoten P in die Position des Großelternknotens zu drehen. Dies funktioniert jedoch nicht, wenn N ein „inneres“ Enkelkind von G ist (d. h., wenn N das linke Kind des rechten Kindes von G oder das rechte Kind des linken Kindes von G ist ). Eine dirRotation um P vertauscht die Rollen des aktuellen Knotens N und seines Elternknotens P. Die Rotation fügt Pfade durch N hinzu (diejenigen im Teilbaum mit der Bezeichnung 2 , siehe Diagramm) und entfernt Pfade durch P (diejenigen im Teilbaum mit der Bezeichnung 4 ). Da sowohl P als auch N rot sind, bleibt Bedingung 4 erhalten. Bedingung 3 ist in Fall 6 wiederhergestellt.

erste Iteration

höhere Iteration

Fall 6 einfügen

Der aktuelle Knoten N ist nun mit Sicherheit ein äußerer Enkel von G (links vom linken Kind oder rechts vom rechten Kind). Führe nun (1-dir)eine Rotation um G durch , wobei P an die Stelle von G tritt und P zum Elternknoten von N und G wird . G ist schwarz und sein ehemaliges Kind P ist rot, da Bedingung 3 nicht erfüllt war. Nach dem Vertauschen der Farben von P und G erfüllt der resultierende Baum Bedingung 3. Auch Bedingung 4 bleibt erfüllt, da alle Pfade, die durch das schwarze G verliefen, nun durch das schwarze P verlaufen .

Da der Algorithmus die Eingabe transformiert, ohne eine Hilfsdatenstruktur zu verwenden und nur wenig zusätzlichen Speicherplatz für Hilfsvariablen benötigt, ist er in-place .

• Hat der gelöschte Knoten zwei Kinder (nicht NULL), kann sein Wert mit dem seines Nachfolgers (dem ganz links stehenden Kind des rechten Teilbaums) vertauscht und anschließend der Nachfolger gelöscht werden. Da der Nachfolger ganz links steht, kann er entweder ein rechtes Kind (nicht NULL) oder gar kein Kind haben.
• Wenn der gelöschte Knoten nur ein Kind (nicht NULL) hat, wird er einfach durch sein Kind ersetzt und schwarz eingefärbt.
  • Das einzelne Kind (nicht NULL) muss gemäß Schlussfolgerung 5 rot sein , und der gelöschte Knoten muss gemäß Anforderung 3 schwarz sein .
• Wenn der gelöschte Knoten keine Kinder hat (beide NULL) und die Wurzel ist, wird er durch NULL ersetzt. Der Baum ist leer.
• Wenn der gelöschte Knoten keine Kinder hat (beide NULL) und rot ist , entfernen Sie einfach den Blattknoten.
• Wenn der gelöschte Knoten keine Kinder hat (beide NULL) und schwarz ist , führt das Löschen zu einem Ungleichgewicht und erfordert eine Neuausrichtung, wie im nächsten Abschnitt beschrieben.

Der komplexe Fall tritt auf, wenn N nicht die Wurzel ist, schwarz gefärbt wird und keine echten Kinder hat (⇔ nur NULL-Kinder). In der ersten Iteration wird N durch NULL ersetzt.

void remove ( Tree * tree , Node * node ) {Knoten * Elternknoten = Knoten -> Elternknoten ;Knoten * Geschwisterknoten ;Node * close_nephew ;Knoten * entfernter_Neffe ;Richtung dir = Richtung ( Knoten );parent -> child [ dir ] = NULL ;gehe zu start_balance ;Tun {dir = Richtung ( Knoten );Startguthaben :Geschwister = Eltern- -> Kind- [ 1 - Verzeichnis ];distant_nephew = sibling -> child [ 1 - dir ];enger_Neffe = Geschwister -> Kind [ Verzeichnis ];if ( sibling -> color == RED ) {// Fall Nr. 3rotate_subtree ( tree , parent , dir );Eltern- > Farbe = ROT ;Geschwister -> Farbe = SCHWARZ ;Geschwister = enger Neffe ;distant_nephew = sibling -> child [ 1 - dir ];if ( distant_nephew && distant_nephew -> color == RED ) {gehe zu Fall_6 ;}enger_Neffe = Geschwister -> Kind [ Verzeichnis ];if ( close_nephew && close_nephew -> color == RED ) {gehe zu Fall_5 ;}// Fall Nr. 4Geschwister -> Farbe = ROT ;Eltern- > Farbe = SCHWARZ ;zurückkehren ;}if ( distant_nephew && distant_nephew -> color == RED ) {gehe zu Fall_6 ;}if ( close_nephew && close_nephew -> color == RED ) {gehe zu Fall_5 ;}if ( parent -> color == RED ) {// Fall Nr. 4Geschwister -> Farbe = ROT ;Eltern- > Farbe = SCHWARZ ;zurückkehren ;}// Fall Nr. 2Geschwister -> Farbe = ROT ;Knoten = Elternknoten ;} while ( parent = node -> parent );// Fall Nr. 1zurückkehren ;Fall_5 :rotate_subtree ( tree , sibling , 1 - dir );Geschwister -> Farbe = ROT ;enger_Neffe -> Farbe = SCHWARZ ;entfernter Neffe = Geschwister ;Geschwister = enger Neffe ;Fall_6 :rotate_subtree ( tree , parent , dir );Geschwister -> Farbe = Eltern -> Farbe ;Eltern- > Farbe = SCHWARZ ;entfernter_Neffe -> Farbe = SCHWARZ ;zurückkehren ;}

Die Ausgleichsschleife der Löschoperation weist folgende Invariante auf :

• Zu Beginn jeder Iteration entspricht die schwarze Höhe von N der Iterationsnummer minus eins, was bedeutet, dass sie in der ersten Iteration null ist und dass N in höheren Iterationen ein echter schwarzer Knoten ist .
• Die Anzahl der schwarzen Knoten auf den Pfaden durch N ist um eins geringer als vor der Löschung, während sie auf allen anderen Pfaden unverändert bleibt, sodass es bei P zu einer Schwarzverletzung kommt , falls andere Pfade existieren.
• Alle anderen Eigenschaften (einschließlich Anforderung 3 ) sind im gesamten Baum erfüllt.

vor

Fall

Drehung

Abtretung

nach

nächste

Δ h

P

C

S

D

P

C

S

D

—

D1

D2

N := P

?

?

1

D3

P ↶ S

N := N

D6

0

D5

0

D4

0

D4

D5

C ↷ S

N := N

D6

0

D6

P ↶ S

Streichung Diese Zusammenfassung zeigt in ihren vorhergehenden Spalten, dass alle möglichen Fälle [ 31 ] von Farbkonstellationen abgedeckt sind.

• In den folgenden Diagrammen steht P für den Elternknoten von N , S für den Geschwisterknoten von N , C (was „naher Neffe“ bedeutet) für das Kind von S in der gleichen Richtung wie N und D (was „ entfernter Neffe“ bedeutet) für das andere Kind von S ( S kann in der ersten Iteration kein NULL-Knoten sein, da er die schwarze Höhe eins haben muss, die die schwarze Höhe von N vor seiner Löschung war, aber C und D können NULL-Knoten sein).
• Die Diagramme zeigen den aktuellen Knoten N als linkes Kind seines Elternknotens P , obwohl N sich auch auf beiden Seiten befinden kann. Die Codebeispiele decken beide Möglichkeiten mithilfe der Seitenvariablen ab dir.
• Zu Beginn (im ersten Iterationsschritt) des Löschvorgangs ist N der NULL-Knoten, der den zu löschenden Knoten ersetzt. Da allein seine Position im übergeordneten Knoten relevant ist, wird er in der linken Spalte der Löschdiagramme symbolisiert (d. h. der aktuelle Knoten N ist ein NULL-Knoten und linkes Kind). Im weiteren Verlauf des Vorgangs können auch reguläre Knoten (mit einer schwarzen Höhe ≥ 1) aktuell werden (siehe z. B. Fall 2 ).
• Durch Zählen der schwarzen Punkte ( und ) in einem Löschdiagramm lässt sich feststellen, dass die Pfade durch N einen Punkt weniger aufweisen als die anderen Pfade. Dies bedeutet eine Verletzung der Schwarzregel bei P – sofern diese existiert.
• Die Farbkonstellation in der vorherigen Spaltengruppe definiert den Fall, dessen Name in der Spalte „ Fall“ angegeben ist . Dabei werden mögliche Werte in leeren Zellen ignoriert.
• Die Zeilen in der Zusammenfassung sind so angeordnet, dass die Abdeckung aller möglichen RB-Fälle leicht verständlich ist.
• Die Spaltenrotation gibt an, ob eine Rotation zur Neuausrichtung beiträgt.
• Die Spaltenzuordnung zeigt eine Zuordnung von N vor dem nächsten Iterationsschritt. Dies führt möglicherweise auch zu einer Neuzuordnung der anderen Knoten P , C , S , D.
• Wenn sich durch den Fall etwas geändert hat, wird dies in der Spaltengruppe danach angezeigt .
• Ein Zeichen in der nächsten Spalte signalisiert, dass die Neuausrichtung mit diesem Schritt abgeschlossen ist. Falls die darauffolgende Spalte genau einen Fall ermittelt, wird dieser als nachfolgender Fall aufgeführt; andernfalls werden Fragezeichen angezeigt.
• In der Schleife wird das Problem der Neuausrichtung auf eine höhere Ebene im Baum eskaliert, indem der Elternknoten P zum neuen aktuellen Knoten N wird . Daher sind maximal h Iterationen erforderlich, um den Baum zu reparieren (wobei h die Höhe des Baums ist). Da die Wahrscheinlichkeit der Eskalation mit jeder Iteration exponentiell abnimmt, sind die gesamten Neuausrichtungskosten im Durchschnitt konstant, genauer gesagt amortisiert konstant . (Nebenbei bemerkt: Mehlhorn & Sanders weisen darauf hin: „AVL-Bäume unterstützen keine konstanten amortisierten Aktualisierungskosten.“ ^{[ 16 ] : 165, 158} Dies trifft auf die Neuausrichtung nach einer Löschung zu, nicht jedoch auf AVL-Einfügungen. ^{[ 32 ]} )${\displaystyle \Delta h=1}$
• Aus dem Schleifenkörper zweigen Ausgänge zu den Fällen 3 , 6 , 5 , 4 und 1 ab ; der Abschnitt „Fall 3 löschen“ hat seinerseits drei verschiedene Ausgänge zu den Fällen 6 , 5 und 4 .
• Rotationen finden in den Fällen 6 , 5 + 6 und 3 + 5 + 6 statt – alle außerhalb der Schleife. Daher finden insgesamt höchstens drei Rotationen statt.

Der aktuelle Knoten N ist die neue Wurzel. Aus jedem Pfad wurde ein schwarzer Knoten entfernt, sodass die RB-Eigenschaften erhalten bleiben. Die Höhe des Baums im schwarzen Bereich verringert sich um 1.

→ Erklärung der Symbole

erste Iteration

höhere Iteration

Fall D2 löschen

P , S und die Kinder von S sind schwarz. Nachdem S rot eingefärbt wurde, haben alle Pfade, die durch S verlaufen (also genau diejenigen, die nicht durch N verlaufen ) , einen schwarzen Knoten weniger. Nun haben alle Pfade im Teilbaum mit Wurzel P die gleiche Anzahl schwarzer Knoten, aber einen weniger als die Pfade, die nicht durch P verlaufen. Daher ist Bedingung 4 möglicherweise noch nicht erfüllt. Nach der Umbenennung von P in N ist die Schleifeninvariante erfüllt, sodass die Neuausrichtung auf einer um eine Ebene höheren schwarzen Knoten (entspricht einer Baumebene) wiederholt werden kann.

erste Iteration

höhere Iteration

Fall D3 löschen

Da das Geschwisterkind S rot ist, müssen P und die Neffen C und D schwarz sein. Eine dirDrehung um P macht S zum Großelternteil von N. Nach dem Vertauschen der Farben von P und S fehlt dem Pfad durch N immer noch ein schwarzer Knoten. Da N nun aber ein rotes Elternkind P und nach der Neuzuordnung ein schwarzes Geschwisterkind S hat , können die Transformationen in den Fällen 4, 5 oder 6 die RB-Form wiederherstellen.

erste Iteration

höhere Iteration

Fall D4 löschen

Die Geschwisterknoten S und S ' sind schwarz, P hingegen ist rot. Ein Farbtausch zwischen S und P ändert nichts an der Anzahl schwarzer Knoten auf Pfaden durch S , erhöht aber die Anzahl schwarzer Knoten auf Pfaden durch N um eins und kompensiert so den fehlenden schwarzen Knoten auf diesen Pfaden.

erste Iteration

höhere Iteration

Fall D5 löschen

Das Geschwisterkind S ist schwarz, S ’ nahes Kind C ist rot und S ’ entferntes Kind D ist schwarz. Nach einer (1-dir)Rotation um S wird der Neffe C zu S ’ Elternteil und zu N ’s neuem Geschwisterkind. Die Farben von S und C werden vertauscht. Alle Pfade haben weiterhin die gleiche Anzahl schwarzer Knoten, aber N hat nun ein schwarzes Geschwisterkind, dessen entferntes Kind rot ist, sodass die Konstellation für Fall D6 geeignet ist. Weder N noch sein Elternteil P sind von dieser Transformation betroffen, und P kann rot oder schwarz sein ( im Diagramm).

erste Iteration

höhere Iteration

Fall D6 löschen

Der Geschwisterknoten S ist schwarz, sein entferntes Kind D ist rot. Nach einer dirRotation um P wird der Geschwisterknoten S zum Elternteil von P und seinem entfernten Kind D. Die Farben von P und S werden vertauscht, und D wird schwarz. Der gesamte Teilbaum behält an seiner Wurzel S die gleiche Farbe , nämlich entweder Rot oder Schwarz ( im Diagramm), was bedeutet, dass die Farbe vor und nach der Transformation gleich bleibt. Dadurch wird Bedingung 3 erfüllt. Die Pfade im Teilbaum, die nicht durch N verlaufen (d. h. durch D und Knoten 3 im Diagramm), durchlaufen dieselbe Anzahl schwarzer Knoten wie zuvor, aber N hat nun einen zusätzlichen schwarzen Vorfahren: Entweder ist P schwarz geworden, oder es war schwarz und S wurde als schwarzer Großelternteil hinzugefügt. Somit durchlaufen die Pfade, die durch N verlaufen, einen zusätzlichen schwarzen Knoten, sodass Bedingung 4 wiederhergestellt ist und der Gesamtbaum die Form eines runden Kreises (RB) annimmt.

Da der Algorithmus die Eingabe transformiert, ohne eine Hilfsdatenstruktur zu verwenden und nur wenig zusätzlichen Speicherplatz für Hilfsvariablen benötigt, ist er in-place .

Denn da ist ein rot-schwarzer Baum von Höhe mit ${\displaystyle h\in \mathbb {N} }$${\displaystyle h}$

${\displaystyle m_{h}}$	${\displaystyle =2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2}$
	${\displaystyle ={\Biggl \{}}$	${\displaystyle 2\cdot 2^{\tfrac {h}{2}}-2=2^{{\tfrac {h}{2}}+1}-2}$		selbst wenn${\displaystyle h}$
	${\displaystyle 3\cdot 2^{\tfrac {h-1}{2}}-2}$		wenn ungerade ${\displaystyle h}$

Knoten ( ist die Abrundungsfunktion ) und es gibt keinen Rot-Schwarz-Baum dieser Baumhöhe mit weniger Knoten – daher ist er minimal . Seine schwarze Höhe ist (mit schwarzer Wurzel) oder für ungerade (dann mit roter Wurzel) ebenfalls ${\displaystyle \lfloor \,\rfloor }$${\displaystyle \lceil h/2\rceil }$${\displaystyle h}$${\displaystyle (h-1)/2~.}$

Nachweisen

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe eine minimale Anzahl an Knoten aufweist, muss er genau einen längsten Pfad mit maximaler Anzahl roter Knoten besitzen, um eine maximale Baumhöhe bei minimaler Höhe der schwarzen Knoten zu erreichen. Abgesehen von diesem Pfad müssen alle anderen Knoten schwarz sein. ^{[ 15 ] : 444 Beweisskizze:} Wird ein Knoten aus diesem Baum entfernt, verliert er entweder an Höhe oder an einer Rot-Schwarz-Eigenschaft.

Die Höhe des RB-Baums mit roter Wurzel ist minimal. Dies stimmt mit Folgendem überein: ${\displaystyle h=1}$

${\displaystyle m_{1}=2^{\lfloor (1+1)/2\rfloor }\!+\!2^{\lfloor 1/2\rfloor }\!\!-\!\!2=2^{1}\!+\!2^{0}\!\!-\!\!2=1~.}$

Ein minimaler RB-Baum (RB_{_h} in Abbildung 2) der Höhe H besitzt eine Wurzel, deren zwei Kind-Teilbäume unterschiedliche Höhen aufweisen. Der höhere Kind-Teilbaum ist ebenfalls ein minimaler RB-Baum, RB_{_{h -1}} , der einen längsten Pfad enthält, der seine Höhe H definiert ; er hat H Knoten und die Höhe H₀. Der andere Teilbaum ist ein perfekter Binärbaum der Höhe H₀ mit schwarzen Knoten – und keinem roten Knoten. Die Anzahl der Knoten lässt sich dann per Induktion bestimmen.${\displaystyle h>1}$${\displaystyle h\!\!-\!\!1}$${\displaystyle m_{h-1}}$${\displaystyle \lfloor (h\!\!-\!\!1)/2\rfloor =:s.}$${\displaystyle s}$${\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}$

	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (m_{h-1})}$	${\displaystyle +}$	${\displaystyle (1)}$	${\displaystyle +}$	${\displaystyle (2^{\lfloor (h-1)/2\rfloor }-1)}$
			(höherer Teilbaum)		(Wurzel)		(zweiter Teilbaum)
ergebend
	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)}$	${\displaystyle +}$	${\displaystyle 2^{\lfloor (h-1)/2\rfloor }}$
		${\displaystyle =}$	${\displaystyle 2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2}$  ■

Der Graph der Funktion ist konvex und stückweise linear mit Knickpunkten bei . Die Funktion wurde als A027383( h –1) für (Folge A027383 in der OEIS ) tabelliert.${\displaystyle m_{h}}$${\displaystyle (h=2k\;|\;m_{2k}=2\cdot 2^{k}\!-\!2)}$${\displaystyle k\in \mathbb {N} .}$${\displaystyle m_{h}=}$${\displaystyle h\geq 1}$

Die Funktion auflösen nach${\displaystyle h}$

Die Ungleichung führt zu , was für ungerade Werte zu führt ${\displaystyle 9>8=2^{3}}$${\displaystyle 3>2^{3/2}}$${\displaystyle h}$

${\displaystyle m_{h}=3\cdot 2^{(h-1)/2}-2={\bigl (}3\cdot 2^{-3/2}{\bigr )}\cdot 2^{(h+2)/2}-2>2\cdot 2^{h/2}-2}$Die

Sowohl im geraden als auch im ungeraden Fall liegt die Zahl also im Intervall ${\displaystyle h}$

	${\displaystyle \log _{2}(n+1)}$	${\displaystyle \leq h\leq }$	${\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)}$	${\displaystyle {\bigl [}<2\log _{2}(n+1)\;{\bigr ]}}$
	(perfekter Binärbaum)		(minimaler rot-schwarzer Baum)

wobei die Anzahl der Knoten ist. ^{[ 33 ]}${\displaystyle n}$

Abschluss

Ein Rot-Schwarz-Baum mit Knoten (Schlüsseln) hat die Baumhöhe${\displaystyle n}$${\displaystyle h\in O(\log n).}$

Zusätzlich zu den Operationen zum Einfügen, Löschen und Suchen einzelner Elemente wurden für Rot-Schwarz-Bäume verschiedene Mengenoperationen definiert : Vereinigung , Schnittmenge und Mengendifferenz . Auf Basis dieser Mengenfunktionen lassen sich schnelle Massenoperationen für Einfügungen oder Löschungen implementieren. Diese Mengenoperationen benötigen die Hilfsoperationen Split und Join . Mit den neuen Operationen kann die Implementierung von Rot-Schwarz-Bäumen effizienter und hochgradig parallelisierbar gestaltet werden. ^{[ 34 ]} Um die angestrebte Zeitkomplexität zu erreichen, setzt diese Implementierung voraus, dass die Wurzel entweder rot oder schwarz sein kann und dass jeder Knoten seine eigene schwarze Höhe speichert .

• Join : Die Funktion Join vergleicht zwei Rot-Schwarz-Bäume t₁ und t₂ sowie einen Schlüssel k , wobei t₁ < k < t₂ _gilt , d _{. h .} alle Schlüssel in t₁ sind kleiner als k und alle Schlüssel in t₂ sind größer als k . Sie gibt einen Baum zurück, der alle _{Elemente von} t₁ und _t₂ sowie k _enthält .

Haben die beiden Bäume die gleiche schwarze Höhe, erzeugt Join einfach einen neuen Knoten mit linkem Teilbaum t₁ , Wurzel k und rechtem Teilbaum _t₂ . Haben sowohl t₁ _{als auch} t₂ _eine schwarze Wurzel, wird k rot gesetzt. Andernfalls wird k schwarz gesetzt.

_{Sind die Höhen der schwarzen} Elemente ungleich, wird angenommen, dass _t₁ eine größere Höhe als t₂ hat (anderer Fall ist symmetrisch). Der Join-Befehl folgt der rechten Wirbelsäule von _t₁ bis zu einem schwarzen Knoten c , der mit t₂ ausgeglichen ist . An diesem Punkt wird ein neuer Knoten mit dem linken Kind c , der Wurzel k (rot) und dem rechten Kind t₂ erstellt _{, um c zu ersetzen. Der neue Knoten kann die Rot-Schwarz-Invariante verletzen ,} da maximal drei rote Knoten in Folge vorkommen dürfen. Dies lässt sich durch eine doppelte Rotation beheben. Falls das Problem mit den doppelten roten Elementen bis zur Wurzel fortpflanzt, wird die Wurzel schwarz gesetzt, wodurch die Eigenschaften wiederhergestellt werden. Die Kosten dieser Funktion entsprechen der Differenz der Höhen der schwarzen Elemente zwischen den beiden Eingabebäumen.

• Aufteilen : Um einen Rot-Schwarz-Baum in zwei kleinere Bäume zu teilen – einen mit Werten kleiner als x und einen mit Werten größer als x – , wird zunächst ein Pfad von der Wurzel aus gezeichnet, indem x in den Rot-Schwarz-Baum eingefügt wird. Nach diesem Einfügen befinden sich alle Werte kleiner als x links vom Pfad und alle Werte größer als x rechts davon. Durch Anwenden der Funktion „Verbinden“ werden alle Teilbäume auf der linken Seite von unten nach oben zusammengeführt, wobei die Schlüssel des Pfades als Zwischenknoten dienen. Der rechte Teilbaum ist symmetrisch.

Für manche Anwendungen gibt Split auch einen booleschen Wert zurück, der angibt, ob x im Baum vorkommt. Die Kosten von Split entsprechen der Ordnung der Baumhöhe. Dieser Algorithmus hat nichts mit speziellen Eigenschaften eines Rot-Schwarz-Baums zu tun und kann auf jeden Baum mit einer Join -Operation angewendet werden, beispielsweise auf einen AVL-Baum .${\displaystyle O(\log n),}$

Der Join-Algorithmus ist wie folgt:

function joinRightRB(T L , k, T R ): if (T L .color=black) and (T L .blackHeight=T R .blackHeight): return Node(T L ,⟨k,red⟩,T R ) T'=Node(T L .left,⟨T L .key,T L .color⟩,joinRightRB(T L .right,k,T R )) if (T L .color=black) and (T'.right.color=T'.right.right.color=red): T'.right.right.color=black; return rotateLeft(T') return T' /* T ' '[recte T'] */ function joinLeftRB(T L , k, T R ): /* symmetrisch zu joinRightRB */ function join(T L , k, T R ): if T L .blackHeight>T R .blackHeight: T'=joinRightRB(T L ,k,T R ) if (T'.color=red) and (T'.right.color=red): T'.color=black return T' if T R .blackHeight>T L .blackHeight: /* symmetrisch */ Falls ( TL.color =black) und ( TR.color =black): return Node(TL , ⟨k,red⟩, TR ) return Node(TL , ⟨k,black⟩, TR ) 

Der Aufteilungsalgorithmus ist wie folgt:

function split(T, k): if (T = NULL) return (NULL, false, NULL) if (k = T.key) return (T.left, true, T.right) if (k < T.key): (L',b,R') = split(T.left, k) return (L',b,join(R',T.key,T.right)) (L',b,R') = split(T.right, k) return (join(T.left,T.key,L'),b,R') 

Die Vereinigung zweier Rot-Schwarz-Bäume t₁ und t₂ _, die Mengen A und B repräsentieren , ist ein Rot-Schwarz-Baum t _{, der} A ∪ B repräsentiert . Die folgende rekursive Funktion berechnet diese Vereinigung:

function union(t 1 , t 2 ): if t 1 = NULL return t 2 if t 2 = NULL return t 1 (L 1 ,b,R 1 )=split(t 1 ,t 2 .key) proc1= start : T L =union(L 1 ,t 2 .left) proc2= start : T R =union(R 1 ,t 2 .right) wait all proc1,proc2 return join(T L , t 2 .key, T R ) 

Hierbei wird angenommen, dass split zwei Bäume zurückgibt: einen mit den Schlüsseln kleiner als der Eingabeschlüssel und einen mit den Schlüsseln größer als der Eingabeschlüssel. (Der Algorithmus ist nicht-destruktiv , es existiert aber auch eine destruktive Version, die die Änderungen direkt im Baum vornimmt.)

Der Algorithmus für Schnittmenge oder Differenz ist ähnlich, benötigt aber die Hilfsroutine Join2 , die Join entspricht , jedoch ohne den mittleren Schlüssel. Basierend auf den neuen Funktionen für Vereinigung, Schnittmenge oder Differenz können entweder ein oder mehrere Schlüssel in den Rot-Schwarz-Baum eingefügt oder daraus entfernt werden. Da Split Join aufruft , aber die Ausgleichskriterien von Rot-Schwarz-Bäumen nicht direkt berücksichtigt, wird eine solche Implementierung üblicherweise als „join-basierte“ Implementierung bezeichnet .

Die Komplexität von Vereinigung, Schnittmenge und Differenz beträgt für zwei Rot-Schwarz-Bäume der Größen und . Diese Komplexität ist hinsichtlich der Anzahl der Vergleiche optimal. Wichtiger noch: Da die rekursiven Aufrufe von Vereinigung, Schnittmenge und Differenz voneinander unabhängig sind, können sie parallel mit einer Paralleltiefe von ausgeführt werden . ^{[ 34 ]} Für hat die Join-basierte Implementierung denselben gerichteten azyklischen Graphen (DAG) wie das Einfügen und Löschen einzelner Elemente, wenn die Wurzel des größeren Baums zum Aufteilen des kleineren Baums verwendet wird. ${\displaystyle O\left(m\log \left({n \over m}+1\right)\right)}$${\displaystyle m}$${\displaystyle n(\geq m)}$${\displaystyle O(\log m\log n)}$${\displaystyle m=1}$

Parallele Algorithmen zur Konstruktion von Rot-Schwarz-Bäumen aus sortierten Listen von Elementen können je nach Computermodell in konstanter Zeit oder in O(n²) ausgeführt werden, wenn die Anzahl der verfügbaren Prozessoren asymptotisch proportional zur Anzahl der Elemente ist . Schnelle parallele Such-, Einfüge- und Löschalgorithmen sind ebenfalls bekannt. ^{[ 35 ]}${\displaystyle O(\log \log n)}$${\displaystyle n}$${\displaystyle n\to \infty }$

Die Join-basierten Algorithmen für Rot-Schwarz-Bäume sind für Massenoperationen parallelisierbar, einschließlich Vereinigung, Schnittmenge, Konstruktion, Filterung, MapReduce usw.

Grundlegende Operationen wie Einfügen, Entfernen oder Aktualisieren lassen sich parallelisieren, indem Operationen definiert werden, die mehrere Elemente in Gruppen verarbeiten. Es ist auch möglich, Gruppen mit mehreren grundlegenden Operationen zu verarbeiten; beispielsweise können Gruppen Elemente zum Einfügen und Elemente zum Entfernen aus dem Baum enthalten.

Die Algorithmen für Massenoperationen sind nicht nur auf den Rot-Schwarz-Baum anwendbar, sondern lassen sich auch auf andere sortierte Sequenzdatenstrukturen wie den 2-3-Baum , den 2-3-4-Baum und den (a,b)-Baum übertragen . Im Folgenden werden verschiedene Algorithmen für das Einfügen von Massenelementen erläutert; dieselben Algorithmen können jedoch auch zum Entfernen und Aktualisieren von Elementen verwendet werden. Das Einfügen von Massenelementen ist eine Operation, die jedes Element einer Sequenz in einen Baum einfügt . ${\displaystyle I}$${\displaystyle T}$

Dieser Ansatz lässt sich auf jede sortierte Sequenzdatenstruktur anwenden, die effiziente Join- und Split-Operationen unterstützt. ^{[ 36 ]} Die Grundidee besteht darin, I und T in mehrere Teile zu zerlegen und die Einfügungen in diesen Teilen parallel durchzuführen.

1. Zuerst muss der Hauptteil I der einzufügenden Elemente sortiert werden.
2. Anschließend teilt der Algorithmus I in Teile von etwa gleicher Größe auf.${\displaystyle k\in \mathbb {N} ^{+}}$${\displaystyle \langle I_{1},\cdots ,I_{k}\rangle }$
3. Als Nächstes muss der Baum T in k Teile zerlegt werden , sodass sich die Wertebereiche von und nur für entsprechende Teile überschneiden ( ); mit anderen Worten, dank der Ordnung gelten für jedes die folgenden Bedingungen: ${\displaystyle \langle T_{1},\cdots ,T_{k}\rangle }$${\displaystyle I_{m}}$${\displaystyle T_{n}}$${\displaystyle m=n}$${\displaystyle j\in \mathbb {N} ^{+}|\,1\leq j<k}$
   1. ${\displaystyle {\text{letzter}}(I_{j})<{\text{erster}}(T_{j+1})}$
   2. ${\displaystyle {\text{letzter}}(T_{j})<{\text{erster}}(I_{j+1})}$
4. Der Algorithmus fügt nun jedes Element nacheinander in die Tabelle ein . Dieser Schritt muss für jedes j durchgeführt werden , was von bis zu k Prozessoren parallel erledigt werden kann.${\displaystyle I_{j}}$${\displaystyle T_{j}}$
5. Schließlich werden die entstandenen Bäume zusammengefügt, um das Endergebnis der gesamten Operation zu erhalten.

Beachten Sie, dass in Schritt 3 die Einschränkungen für die Aufteilung sichergestellt werden, dass in Schritt 5 die Bäume wieder zusammengefügt werden können und die resultierende Sequenz sortiert ist.

• 
  Anfangsbaum
• 
  I und T teilen
• 
  in das geteilte T-Stück einsetzen
• 
  gemeinsam

Der Pseudocode zeigt eine einfache Divide-and-Conquer-Implementierung des Join-basierten Algorithmus für das Masseneinfügen. Beide rekursiven Aufrufe können parallel ausgeführt werden. Die hier verwendete Join-Operation unterscheidet sich von der in diesem Artikel beschriebenen Version; stattdessen wird `join2` verwendet, das den zweiten Parameter `k` nicht berücksichtigt.

bulkInsert (T, I, k): I.sort() bulklInsertRec(T, I, k) bulkInsertRec (T, I, k): if k = 1: forall e in I: T.insert(e) else m := ⌊size(I) / 2⌋ (T 1 , _, T 2 ) := split(T, I[m]) bulkInsertRec(T 1 , I[0 .. m], ⌈k / 2⌉) || bulkInsertRec(T 2 , I[m + 1 .. size(I) - 1], ⌊k / 2⌋) T ← join2(T 1 , T 2 ) 

Die Sortierung I wird in dieser Analyse nicht berücksichtigt.

#Rekursionsebenen	${\displaystyle \in O(\log k)}$
T(split) + T(join)	${\displaystyle \in O(\log |T|)}$
Einfügungen pro Faden	${\displaystyle \in O\left({\frac {|I|}{k}}\right)}$
T(einfügen)	${\displaystyle \in O(\log |T|)}$
T(bulkInsert) mit k = #Prozessoren	${\displaystyle \in O\left(\log k\log |T|+{\frac {|I|}{k}}\log |T|\right)}$

Dies lässt sich durch die Verwendung paralleler Algorithmen für das Aufteilen und Zusammenfügen verbessern. In diesem Fall beträgt die Ausführungszeit . ^{[ 37 ]}${\displaystyle \in O\left(\log |T|+{\frac {|I|}{k}}\log |T|\right)}$

#Splits, #Joins	${\displaystyle \in O(k)}$
W(split) + W(join)	${\displaystyle \in O(\log |T|)}$
#Einfügungen	${\displaystyle \in O(|I|)}$
W(einfügen)	${\displaystyle \in O(\log |T|)}$
W(bulkInsert)	${\displaystyle \in O(k\log |T|+|I|\log |T|)}$

Eine weitere Methode zur Parallelisierung von Massenoperationen ist die Verwendung von Pipelining . ^{[ 38 ]} Dies kann erreicht werden, indem die Verarbeitung einer Basisoperation in eine Folge von Teilaufgaben zerlegt wird. Bei mehreren Basisoperationen können die Teilaufgaben parallel verarbeitet werden, indem jede Teilaufgabe einem separaten Prozessor zugewiesen wird.

1. Zuerst muss der Hauptteil I der einzufügenden Elemente sortiert werden.
2. Für jedes Element in I ermittelt der Algorithmus die entsprechende Einfügeposition in T. Dies kann für jedes Element parallel erfolgen, da T in diesem Prozess nicht verändert wird. Nun muss I anhand der Einfügeposition jedes Elements in Teilsequenzen S unterteilt werden . Beispielsweise ist die Teilsequenz von I , die die Elemente enthält, deren Einfügeposition links vom Knoten n liegt .${\displaystyle \in I}$${\displaystyle s_{n,{\mathit {left}}}}$
3. Das mittlere Element jeder Teilfolge wird als neuer Knoten in T eingefügt . Dies kann für jedes Element parallel erfolgen, da die Einfügeposition per Definition eindeutig ist. Enthält die Folge Elemente links oder rechts von , werden diese in einer neuen Menge von Teilfolgen S als oder zusammengefasst .${\displaystyle m_{n,{\mathit {dir}}}}$${\displaystyle s_{n,{\mathit {dir}}}}$${\displaystyle n'}$${\displaystyle m_{n,{\mathit {dir}}}}$${\displaystyle m_{n,{\mathit {dir}}}}$${\displaystyle s_{n,{\mathit {dir}}}}$${\displaystyle m_{n,{\mathit {dir}}}}$${\displaystyle s_{n',{\mathit {left}}}}$${\displaystyle s_{n',{\mathit {right}}}}$
4. Nun enthält T möglicherweise bis zu zwei aufeinanderfolgende rote Knoten am Ende der Pfade von der Wurzel zu den Blättern, die repariert werden müssen. Beachten Sie, dass während der Reparatur die Einfügeposition von Elementen aktualisiert werden muss, falls die entsprechenden Knoten von Rotationen betroffen sind. ${\displaystyle \in S}$
   • Haben zwei Knoten unterschiedliche nächste schwarze Vorfahren, können sie parallel repariert werden. Da höchstens vier Knoten denselben nächsten schwarzen Vorfahren haben können, lassen sich die Knoten der untersten Ebene in einer konstanten Anzahl paralleler Schritte reparieren.
   • Dieser Schritt wird nacheinander auf die darüber liegenden Schwarzwerte angewendet, bis T vollständig repariert ist.
5. Die Schritte 3 bis 5 werden mit den neuen Teilfolgen wiederholt, bis S leer ist. Dann ist jedes Element eingefügt. Jede Anwendung dieser Schritte wird als Stufe bezeichnet . Da die Länge der Teilfolgen in S gleich ist und die Teilfolgen in jeder Stufe halbiert werden, beträgt die Anzahl der Stufen . ${\displaystyle \in I}$${\displaystyle \in O(|I|)}$${\displaystyle \in O(\log |I|)}$
   • Da sich alle Stufen innerhalb der schwarzen Ebenen des Baums nach oben bewegen, können sie in einer Pipeline parallelisiert werden. Sobald eine Stufe die Verarbeitung einer schwarzen Ebene abgeschlossen hat, kann die nächste Stufe auf diese Ebene wechseln und dort fortfahren.

• 
  Anfangsbaum
• 
  Einfügepositionen finden
• 
  Phase 1 fügt Elemente ein
• 
  Phase 1 beginnt mit der Reparatur der Knoten.
• 
  Phase 2 fügt Elemente ein
• 
  Phase 2 beginnt mit der Reparatur der Knoten.
• 
  Phase 3 fügt Elemente ein
• 
  Phase 3 beginnt mit der Reparatur der Knoten.
• 
  Phase 3 setzt die Reparatur der Knotenpunkte fort.

Sortierung I wird in dieser Analyse nicht berücksichtigt. Außerdem wird angenommen, dass kleiner als ist , da es sonst effizienter wäre, den resultierenden Baum von Grund auf neu zu erstellen. ${\displaystyle |I|}$${\displaystyle |T|}$

T (Einfügeposition finden)	${\displaystyle \in O(\log |T|)}$
#Phasen	${\displaystyle \in O(\log |I|)}$
T(Einfügen) + T(Reparieren)	${\displaystyle \in O(\log |T|)}$
T(bulkInsert) mit ~ #Prozessoren${\displaystyle |I|}$	${\displaystyle \in O(\log |I|+2\cdot \log |T|)}$${\displaystyle =O(\log |T|)}$

W (Einfügepositionen finden)	${\displaystyle \in O(|I|\log |T|)}$
#Einsätze, #Reparaturen	${\displaystyle \in O(|I|)}$
W(Einfügen) + W(Reparieren)	${\displaystyle \in O(\log |T|)}$
W(bulkInsert)	${\displaystyle \in O(2\cdot |I|\log |T|)}$${\displaystyle =O(|I|\log |T|)}$

• Liste der Datenstrukturen
• Baumdatenstruktur
• Baumrotation
• Ordnungsstatistikbaum
• AA-Baum , eine Variante des Rot-Schwarz-Baums
• Linksgerichteter rot-schwarzer Baum
• AVL-Baum
• B-Baum ( 2–3-Baum , 2–3–4-Baum , B+-Baum , B*-Baum , UB-Baum )
• Sündenbockbaum
• Spreizbaum
• T-Baum
• WAVL-Baum
• GNU libavl