AuK/Sortierte Folgen SS12

Wiki-Quelltext dieser Seite.

<language>Java</language>
=Bäume=
==Termminologie==

==Binäre Bäume==


=Binäre Suchbäume=

==Einfügen eines Elementes==

Beim Einfügen eines Elementes macht man sich die Eigenschaft zunutze, dass der Schlüssel des linken Sohns jeweils kleiner oder gleich dem Schlussel ist, den der Knoten selbst enthält. Der rechte Kindknoten dagegen enthält einen echt größeren Schlüssel.
Fügt man also einen Schlüssel in den Baum ein so beginnt man beim Vergleich mit der Wurzel. Ist der Einzufügende Schlüssel größer als der Schlüssel der Wurzel, so setzt man den Vergleich im rechten Teilbaum des aktuellen Knotens fort. Andernfalls also wenn der Schlüssel kleiner 
oder gleich dem Schlüssel der Wurzel ist, setzt man den Vergleich im linken Teilbaum des aktuellen Knotens fort.
Trifft man bei diesem Verfahren auf einen Knoten dessen Wertigkeit null entspricht, so wird an dieser Stelle der neue Schlüssel eingefügt.
Für den Programmablauf lässt sich also folgendes allgemein formulieren:
# Abfrage ob der einzufügende Schlüssel größer oder gleich dem Schlüssel von N ist
# Abfrage ob der sich daraus ergebende Kindknoten dem Wert null entspricht
# wenn ja, dann erzeuge neuen Knoten mit dem einzufügenden Schlüssel
# sonst beginne mit Schritt 1 wobei N nun N.links bzw n.rechts ist

Für die Methode zum Einfügen in einen BST ergibt sich zum einen eine rekursive sowie eine iterative Umsetzungsmöglichkeit, die im folgenden 
durch Pseudocode beschrieben werden.
===Rekursive Umsetzung===
 '''InsertRek( Schlüssel K, Knoten N )'''
 if Schlüssel < N.Schlüssel do
     if N.links is null do
         N.links = neuer Knoten
         N.links.Schlüssel = K
         N.links.Vater = N
     else do 
         InsertRek( K, N.links )
 else
     if N.rechts is null
         N.rechts = neuer Knoten
         N.rechts.Schlüssel = K
         N.rechts.Vater = N
     else do 
         InsertRek( K, N.rechts ) 

===Iterative Umsetzung===
 '''InsertIt( Schlüssel K )'''
 Knoten p = Wurzel
 Knoten o = null
 while p not null
     o = p
     if K < p.schlüssel or K is p.schlüssel
         p = p.links
     else if K > p.schlüssel
         p = p.rechts
     else return
 p = neuer Knoten
 p.Schlüssel = K
 p.Vater = o
 if Wurzel is null
     Wurzel = p
 else if K < o.schlüssel or K is o.schlüssel
     o.links = p
 else o.rechts = p

==Finden eines Elementes==

Beim suchen eines Elementes wird die spezielle Anordnung der Elemente in einem Baum genutzt. Ist der Baum leer, so ist der Schlüssel nicht enthalten. Ist das zu suchende Element größer als der Schlüssel der Wurzel bzw. des Knotens des aktuellen Teilbaumes so vergleicht man dessen rechten Kindknoten, ist er gleich so wurde das gesuchte Element gefunden ansonsten vergleicht man die Wurzel bzw. den linken Kindknoten des aktuellen Knotens. Beinhaltet der binäre Suchbaum ein oder mehrere Duplikate, so wird immer nur der Schlüssel gefunden, der den gerringsten
Weg zu Wurzel des Baumes besitzt, also der Schlüssel mit der geringsten Tiefe. Folgende Schritte sind also beim Einfügen durchzuführen:

* Abfrage ob der Baum leer ist
* Vergleich ob der gesuchte Schlüssel der Schlüssel des Wurzelelementes ist
* Wenn Schlüssel kleiner oder gleich ist, dann suche im linken Teilbaum weiter sonst rechts

===Rekursive Implementierung===
 '''searchRek( Schlüssel k, Knoten n )'''
 if n is null
     return null
 if k is n.schlüssel
     return n 
 if k < n.schlüssel
     return searchRek( k, n.links )
 else return searchRek( k, n.rechts )	

===Iterative Implementierung===
 '''searchIt( Schlüssel k, Knoten n )'''
 Knoten nI = n
 while nI not null and nI.schlüssel not k
     if k < nI.schlüssel
         nI = nI.links
     else nI = nI.rechts
 return nI

==Finden des Minimums==

Um den minimalen Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am linken Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält. Enthält der linke Teilbaum den Wert null, so terminiert der Algorithmus und gibt eine Adresse auf das gesuchte Minimum zurück.

===Iterative Implementierung===
 '''Knoten getMinIt( Knoten wurzel )'''
 if wurzel is null
     return null
 while wurzel.links not null
     wurzel = wurzel.links
 return wurzel

===Rekursive Implementierung===
 '''Knoten getMinRek( Knoten wurzel )'''
 if wurzel is null
     return null
 else if wurzel.links is null 
     return wurzel
 else return getMinRek( wurzel.links )

==Finden des Maximums==

Um den maximalen Schlüssel im Baum zu finden wandert man einfach von der Wurzel beginnend immer am rechten Teilbaum entlang, bis der nächst folgende Knoten den Wert null enthält.

===Iterative Implementierung===
 '''Knoten getMaxIt( Knoten wurzel )'''
 if wurzel is null
     return null
 while wurzel.rechts not null
     wurzel = wurzel.rechts
 return wurzel

===Rekursive Implementierung===
 '''Knoten getMaxRek( Knoten wurzel )'''
 if wurzel is null
     return null
 else if wurzel.rechts is null 
     return wurzel
 else return getMaxRek( wurzel.rechts )

==Finden des Nachfolgers==

Der Nachfolger eines Knotens ist der Knoten, dessen Schlüssel gemäß der Ordnugsrelation größer ist. Existieren Duplikate, so ist der Nachfolger
der Vaterknoten. Das Sohnelement muss in diesem Fall notwendigerweise ein linker Sohn sein. Der Nachfolger eines Knotens ist daher entweder das Minimum des rechten Teilbaumes oder, falls dieser nicht vorhanden, der Vaterknoten.

===Rekursive Implementierung===

===Iterative Implementierung===
 '''NachfolgerIt( Knoten n )'''
     if n is null
         return null
     if n.rechts not null
         return getMin( n.rechts )
     Knoten oben = n.vater
     while oben not null and oben.rechts is n
         n = oben
         oben = n.o
     return oben

==Sortierte Ausgabe des Baumes==

===Rekursive Implementierung===
 '''AusgabeVorwRek( Knoten n )'''
 if n is null do
     return ""
 else return n.toString + lineBreak + AusgabeVorwRek( nachfolger( n ) )
		
===Iterative Implementierung===
 '''AusgabeVorwIt( Knoten n )'''
 String retStr = ""
 while n not null do
     retString + n.toString + lineBreak
     n = nachfolger( n )

==Löschen eines Elementes==

Das löschen eines Knotens in einem BST stellt sich als komplexer heraus. So muss eine grundsätzliche Entscheidung vorgenommen werden, ob der zu löschende Knoten höchstens ein oder zwei Kinder hat.

===Mit einem Sohn===
Wenn der zu löschende Knoten keine Kinder hat kann er bedenkenlos gelöscht werden, hat er allerdings genau ein Kind, so wird der verbleibende
Teilbaum einfach eine Etage nach oben geschoben. Man setzt also den Vorgängerknoten des Kindknotens auf den Entsprechenden linken oder rechten
Kindknoten des Vorgängerknotens des zu löschenden Elementes sowie den entsprechend linken oder rechten Kindknoten dieses Elementes auf das 
Kindelement des zu löschenden Knotens. Ist der zu löschende Knoten die Wurzel, so setzen wir den Wurzelzeiger einfach auf den entsprechend folgenden Knoten.
====Implementierung====

'''deleteNodeWithOneChild( Node n )'''
 // get the child
 Node child;         
 if n.left is null
     child = n.right
 else child = n.left
 
 // handling if the root should be deleted		
 if n is root
     child.parent = null
     root = child
     return
 				
 // handling if the node has a parent node
 if n.parent.left is n
     n.paretn.left = child
 else n.parent.right = child
 
 if child not null
     child.parent = n.parent
 
 n = null

===Mit zwei Söhnen===

Beinhaltet der zu löschende Knoten zwei nichtleere Kindknoten, so wird zunächst der kleinste Knoten des rechten Teilbaums ermittelt. Dieser ist
da er im rechten Teilbaum ist in jedem Falle der Nachfolger von dem zu löschenden Knoten und beinhaltet keinen linken Kindknoten mehr.
Somit wird einfach der Inhalt dieses Knotens in den zu löschenden Knoten kopiert und anschließend das ermittelte minimum gelöscht. Man vereinfacht mit dieser Methode also den Fall, dass zwei Söhne existieren, zu dem Fall, dass nur ein Sohn existiert womit die löschfunktion
für einen Kindknoten angewand werden kann.
Beinhaltet der BST allerdings Duplikate, so würde die oben beschiebene Vorgehensweise zu Komplikationen führen. Würde man also nur das Minimum, welches ein Duplikat im Baum aufweist( dieses Duplikat wäre dann zwangsweise das Elternelement des Minimums ), an den Platz des zu löschenden Knotens kopieren, so würden hierbei Duplikate im rechten Teilbaum des zu gelöschten Elementes übrig bleiben. Diese Fehlplatzierung würde demnach die Invariante binärer Suchbäume verletzen.
Um dieses Problem zu beseitigen wird an die Position des zu löschenden Knotens die Liste aller Duplikate des Minimums aus dem  rechten Teilbaum eingefügt. Somit wird der Elternknoten-Zeiger der Entsprechenden Kindknoten des zu löschenden Elementes auf das Minimum im linken Teilbaum gesetzt und dessen Kindzeiger auf die Kinder des zu löschenden Knotens. Im folgenden wird dann der Kindzeiger des zu löschenden Knotens auf das Kindelement des Duplikates mit der geringsten Tiefe gesetzt und dessen Elternpointer auf das zu löschende Element. Anschließend wird der Inhalt des im rechten Teilbaum übriggebliebenen Duplikates in das zu löschende Element kopiert. Da das im rechten Teilbaum übriggebliebende Element nun im schlimmsten Fall noch einen rechten Sohn beinhaltet, kann dieses Element nun mit der oben beschriebenen Methode zum Löschen eines Elementes entfernt werden.

<language>Java</language>
<language>Java</language>
====Implementierung====

=2-3-4-Bäume=

==Eigenschaften==
# Knoten enthalten bis zu 3 Schlüssel
# 3-Knoten mit 3 ausgehenden Verkettungen sind zugelassen
# 4-Knoten mit 4 ausgehenden Verkettungen sind zugelassen
# Binärbaum Eigenschaften vorhanden (2-Knoten)

==Suchen eines Elements==
Beim Suchen in 2-3-4-Bäumen wird die Top-Down-Methode verwendet. Dabei wird ausgehend von dem kleinsten Element des Wurzelknotens, den entsprechenden Verkettungen bis zum gesuchten Schlüssel gefolgt.
Im ersten Schritt wird dabei der gesuchte Schlüssel mit dem aktiven Element verglichen. Liefert der Vergleich eine wahre Aussage ist schon an dieser Stelle die Suche beendet. Ist dies nicht der Fall wird geprüft, ob der gesuchte Schlüssel kleiner ist als das aktive Element im aktuellen Knoten. Ist dieses Kriterium wahr geht man die Verkettung vor dem aktiven Element weiter entlang und setzt das kleinste Element des Kindknotens als neues aktives Element und beginnt wieder im ersten Schritt. 
Im Fall, dass das Kriterium nicht erfüllt ist wird im Wurzelknoten das nächstgrößere Element aktiviert und beginnt mit diesem wieder bei Schritt eins. Sollte kein nächstes Element im aktuellen Knoten vorhanden sein wird der Verkettung nach dem zuletzt aktiven Elements zum kleinsten Element des Kindknotens gefolgt und der Erste Schritt wieder ausgeführt.

==Einfügen eines Elements==

===Günstiger Fall===

Beim Einfügen wird ein Knoten solange aufgefüllt, bis er 3 Elemente enthält. Soll noch ein viertes Element aufgenommen werden ist dies nur durch ein Spalten des Knotens möglich. Dabei wird der überfüllte Knoten in 3 Teile gesplittet: 
* Knoten mit zwei Elementen
* Knoten mit einem Element
* Mittleres Element
Das mittlere Element rutscht bei der Spaltung in den Elternknoten und stellt somit die Verkettung der zwei neuen Knoten dar.


===Ungünstiger Fall===

Muss der überfüllte Knoten wie im Günstigen Falle gespalten werden und der Elternknoten ist schon mit 3 Elementen belegt, wird das Spalten in Richtung Wurzel solange nach oben gereicht bis man entweder auf kein 4-Knoten mehr trifft oder auf die Wurzel stößt. Bei der Wurzel wird jedoch nach gleicher Aufteilungsregel eine neue Wurzel erzeugt, wenn diese ebenfalls schon voll besetzt ist.

Laufzeit: $O$(log n)

===Split-Operation===

Eine alternative Möglichkeit um dem ungünstigen Fall sofort vorzubeugen ist die Split-Operation. Dabei wird anders als bei den oben beschriebenen Methoden, während ein Element in den Baum eingefügt wird beim Durchlauf zusätzlich nach 4-Knoten gesucht, die daraufhin ausgepalten werden. Somit wird die Split-Operation im schlimmsten Fall einmal durchgeführt.

==Löschen eines Elements==
Das Löschen eines Elements aus einem Knoten lässt sich immer auf das Löschen eines Elements in einem Blatt zurückführen. Dafür ist es zunächst nötig die Position des zu löschenden Elements zu wissen. Neben dieser Position i wird außerdem das Element benötigt, welches sich an der äußersten rechten Stelle befindet um beide Elemente zu tauschen. Nun kann das Element aus dem Blatt gelöscht werden, wobei drei Fälle zu unterscheiden sind:
* mehr als ein Element im Blatt - einfaches Entfernen
* ein Element im Blatt und Nachbarknoten (gleicher Vorgänger) mindestens zwei Elemente - leihen eines Elements aus dem Nachbarknoten - Schlüssel in Vorgängerknoten verschieben - Vorgängerelement des zu löschenden Elements rückt an dessen Position und ersetz dieses
* nur ein Element im Blatt und Nachbarknoten - Element entfernen - Vorgängerelement mit Nachbarelement zusammengefügt
* vorhergehender Fall und Vorgängerknoten nur ein Element - gleiche Operation auf höherer Ebene

=A-V-L-Bäume=

==Eigenschaften==
# balancierte Knoten
# Höhenunterschied = 1
# Rotation um mittleres Element

==Balancekriterium==
Höhenunterschied = HöheRechts - HöheLinks

==Suchen==

==Einfügen==

==Löschen==

=B-Bäume=

===Eigenschaften===
* alle Höhen von Wurzel zu Blatt immer gleich
* jeder Knoten besteht aus min. k und max. 2k Elemente
* unterschiedliche Anzahl von Elementen in Knoten möglich
* Wurzel besteht aus zwischen 1 und 2k Elementen 
* Knoten mit n Elementen besitzt n+1 Verkettungen
* Blätter haben keine bzw. undefinierte Verkettungen

===Suchen eines Elements===

Der Suchalgorithmus arbeitet nach dem gleichen Schema, wie es bei den 2-3-4-Bäumen der Fall ist.

===Einfügen eines Elements===

Zunächst wird die korrekte Position zum Einfügen des Schlüssels ermittelt. Besitzt der sich an dieser Position befindende Knoten weniger als 2k Elemente erfolgt ein einfaches Einfügen des Schlüssels in den aktuellen Knoten. 
Befinden sich schon 2k Elemente vor dem Einfügen in dem Knoten, ist dieser Überfüllt und es wird auf die Splitting-Methode, wie bei den 2-3-4-Bäumen zurückgegriffen.

===Löschen eines Elements===

==B*-Bäume==

===Vergleich B-Bäume und B*-Bäume===

===Vor- und Nachteile===

==B+-Bäume==

===Eigenschaften===

=Rot-Schwarz-Bäume=
==Komponenten der Knoten==
* Farbe
* Schlüssel
* Adresse des Eleternknotens
* Adresse des linken Kindknotens
* Adresse des rechten Kindknotens

==Eigenschaften==
# Jeder Konten ist entweder rot oder schwarz
# Die Wurzel ist schwarz
# Jedes Blatt( null/ nil ) ist schwarz
# Die Kind-Knoten eines Roten Knotens sind jeweils schwarz
# Alle Pfade die von einem bestimmten Knoten ausgehen und in einem Blatt dieses Teilbaums enden, haben die gleiche Anzahl an schwarzen   Knoten


==Rotationen==

Durch die Einfüge- und Löschoperationen kann es dazu kommen, das eine oder mehrere Eigenschaften des Rot-Schwarzbaumes verletzt werden.
Um die Zeigerstruktur des Baumes zu "reparieren" bedient man sich der Rotation.

===Linksrotation===
===Rechtsrotation===

==Einfügen==

===Fall 1===
Der erste Fall beschreibt den Sachverhalt, dass der neu eingefügte Knoten die Wurzel des Baumes darstellt. Dies würde berreits die Eigenschaft, dass die Wurzel des Baumes schwarz sein muss verletzen. Aus diesem Grund wird die noch rote Wurzel schwarz gefärbt wodurch das Gleichgewicht wieder hergestellt ist.

 '''insertCase1( Knoten n )'''
     if n.parent is null
         n.color = BLACK
     else insertCase2( n )

===Fall 2===
Ist der Vater des neuen Knotens schwarz, so tritt der zweite Fall ein. In diesem Fall könnte der Gedanke aufkommen, dass die fünfte Eigenschaft, also dass der Baum auf allen Pfaden von der wurzel zu den Blättern die gleiche Schwaarztiefe besitzt. Da allerdings ein schwazknoten( Nil ) beim einfügen gelöscht wird bleibt die Schwarztiefe im Baum erhalten und es ist nichts weiter zu tun.
 
 '''insertCase2( Knoten n )'''
 if n.parent.color is BLACK
     return
 else insertCase3( n )

===Fall 3===
Ab dem Fall drei beginnent, kann davon ausgegangen werden, dass der einzufügende Knoten einen Großvater besitzt, da der Vater rot sein muss ( sonst wäre bereits Fall eins oder Fall zwei eingetreten ) und damit nicht die Wurzel sein kann. Somit beschreibt der dritte Fall die Situation, dass sowohl der Onkel als auch der Vater rot sind. Da durch das Anhängen eines weiteren roten Knotens nun die Eigenschaft verletzt wird, dass ein roter Knoten immer zwei schwarze Kindknoten haben muss, werden der Onkel sowie der Vaterknoten schwarz und der Großvater rot gefärbt. Mit diesem Verfahren sowie der Hilfe der Verfahren von Fall eins und Fall zwei verschiebt man das Problem also soweit nach oben bis es sich auflöst, andernfalls betrachtet man einen neuen Fall.

 '''insertCase3( Knoten n )'''
 if uncle( n ) not null and uncle( n ).color is RED
     n.parent = BLACK
     uncle( n ).color = BLACK
     grandparent( n ).color = RED
     insertCase1( n )
 else insertCase4( n )

===Fall 4===
Der nächste Fall betrachtet die Situation, dass der Onkel des neuen Knotens schwarz ist( kann also auch Nil sein ) und der neue Knoten das 
rechte Kind seines roten Vaters ist, welcher jedoch links an seinem Größvater sitzt. Analog dazu kann der neu einzufügende Knoten auch das linke Kind seines roten Vaters sein, welcher rechts an seinem Großvater angebracht ist. Im ersten der beiden Fälle wird eine Linksrotation
und im zweiten eine Rechtsrotation um den Vater durchgeführt. Anschließend wird in jedem Falle der fünfte und damit letzte Fall überprüft.

 '''insertCase4( Knoten n )'''
 if n is n.parent.right and n.parent is gradnparent( n ).left
     rotateLeft( n.parent )
     n = n.left
 else 
     if n is n.parent.left and n.parent is gradnparent( n ).right
         rotateRight( n.parent )
         n = n.right
 insertCase5( n )

===Fall 5===
Der letzte Fall beinhaltet die Situationen, dass der neue Knoten einen schwarzen Onkel hat( auch Nil ist schwarz ) und der linke Knoten seines Vaters ist, der sich ebenfalls links am Großvater befindet bzw. dass der neue Knoten rechts an seinem Vater hängt, der sich ebenfalls am Großvater befindet. Da in diesem Fall die Eigenschaft verletzt ist, dass der Vater des neuen knoten keine zwei schwarzen Kinder aufweisen kann, bedient man sich einer Rechtsrotation, sofern der neue Knoten links an seinem Vater ist und sich dieser links am Großvater befindet. Im entgegengesetztem Fall bedient man sich der Linksrotation um den Großvater. Anschließend wird der ehemalige Vater schwarz und der ehemalige Großvater rot gefärbt.

 '''insertCase5( Knoten n )'''
 n.parent.color = BLACK
 grandparent( n ).color = RED
 if n is n.parent.left and n.patent is grandparent( n ).left
     rotateRight( grandparent( n ) )
 else rotateLeft( grandparent ( n ) )

==Löschen==
===Fall 1===
Der erste Fall beschreibt die Situation, dass der Konfliktknoten( n ) die Wurzel des Baumes darstellt. Da die Wurzel immer schwarz sein muss ist an dieser Stelle nichts weiter zu tun, da der schwarze Knoten( also die Wurzel ) von jedem Pfad entfernt wurde. Da die neue Wurzel ebenfalls schwarz ist bleiben alle Eigenschaften des Rot-Schwarz-Baumes erhalten.

 '''deleteCase1( Node n )'''
 if n.parent is null
     return
 else deleteCase2( n )

===Fall 2===
Im zweiten Fall wird auf die Situation eingegangen, dass der Bruder des Konfliktknotens rot ist. Tritt dieser Fall ein, so wird die Farbe vom Vater sowie vom Bruder des Konfliktknotens invertiert. Im Anschluss daran wird eine Rotation um den Vater durchgeführt, wodurch der Bruder zum Großvater des Konfliktknotens wird.

 '''deleteCase2( Node n )'''
 if sibling( n ).color is RED
     n.parent.color = RED
     sibling( n).color = BLACK
     if n is n.parent.left
         rotateLeft( n.parent )
     else rotateRight( n.parent )
 deleteCase3( n )

===Fall 3===
Sind der Vater, der Bruder und die Kinder des Konfliktknotens schwarz, so tritt der dritte Fall ein. In diesem Fall wird der Bruder rot gefärbt. Im weiteren haben jedoch noch immer alle Pfade, die durch den Vater laufen einen schwarzen Knoten weniger, woduch die Eigenschaft der gleichmäßigen Schwarztiefe verletzt wird. Um dies zu "reparieren" und die Ordnung wieder herzustellen versucht man einen der sechs Fälle anzuwenden.
 
 '''deleteCase3( Node n )'''
 if n.parent.color is BLACK and
    sibling( n ).color is BLACK and
    sibling( n ).left.color is BLACK and
    sibling( n ).right.color is BLACK 
    do
        sibling( n ).color = RED
        deleteCase1( n.parent )
 else do
     delelteCase4( n )
===Fall 4===
Der vierte Fall beinhaltet den Sachverhalt, dass der Bruder sowie die Kinder schwarz sind, der Vater jedoch eine rote Farbe beinhaltet. Um in diesem Fall die Ordnung wieder herzustellen ist es ausreichend dem Vater die Farbe des Bruders( schwarz ) und dem Bruder die Farbe des Vaters( rot ) zuzuweisen. Durch dieses Verfahren bleibt die Anzahl der schwarzen Knoten die nicht durch den Konfliktknoten führen gleich. Da aber auf allden Pfaden, die duch den Konfliktknoten führen ein schwarzer Knoten eingefügt wird wird das Gleichgewicht wieder hergestellt.

 '''deleteCase4( Node n )'''
 if n.parent.color is RED and
    sibling( n ).color is BLACK and
    sibling( n ).left.color is BLACK and
    sibling( n ).right.color is BLACK
    do
        sibling( n ).color = RED
        n.color = BLACK
 else deleteCase5( n )

===Fall 5===
Der fünfte Fall trifft auf zwei Sachverhalte zu, die sich lediglich durch ihre Ausrichtung unterscheiden. Zum einen ist dies, dass das linke Kind des Bruders rot und das rechte Kind sowie der Bruder des Konfliktknotens schwarz sind. Der Konfliktknoten ist hierbei das linke Kind seines Vaters. Der zweite Fall stellt also somit die Situation dar, dass das rechte Kind des Bruders rot und das linke Kind sowie der Bruder schwarz sind. In diesem Fall ist der Konfliktknoten das rechte Kind seines Vaters.
Um in diesem Fall die Ordnung zu wahren wird bei der ersten Möglichkeit des fünften Falles eine Rechts- und bei der zweiten dem entsprechend eine Linksrotation um den Bruder durchgeführt. Das linke bzw. das rechte Kind des Bruders wird dabei dessen neuer Vater und dieser wird Bruder des Konfliktknotens. Zudem werden die Farben des Bruders und des neuen Vaters getauscht. Zwar haben alle Pfade noch die gleiche Anzahl an schwarzen Knoten wie vorher jedoch hat der Konfliktknoten nun einen schwarzen Bruder der rechts bzw. links ein rotes Kind hat. Damit ist die Voraussetzung für den sechsten Fall gegeben ohne dass der Konfliktknoten noch der Vater beeinflusst wurden.

 '''deleteCase6( Node n )'''
 if n is n.parent.left and
    sibling( n ).color is BLACK and 
    sibling( n ).left.color is RED and
    sibling( n ).right.color is BLACK
    do 
        sibling( n ).color = RED
        sibling( n ).left.color = BLACK
        rotateRight( sibling( n ) )
    else
        if n is parent.right and
           sibling( n ).color is BLACK and
           sibling( n ).left.color is BLACK and
           sibling( n ).right.color is RED
           do
               sibling( n ).color = RED
               rotateLeft( sibling( n ) )
 deleteCase6( n )

===Fall 6===
Der letzte Fall fordert, dass der Bruder des Konfliktknotens schwarz, das Rechte Kind des Bruders rot ist. Zudem soll der Konfliktknoten das linke Kind seines Vaters sein. Aquivalent dazu ist auch die Möglichkeit, dass das linke Kind des Bruders rot ist und der Konfliktknoten das rechte Kind seines Vaters ist. Hierbei würden dann jeweils eine Links- bzw. eine Rechtsrotation um den Vater des Konfliktknotens stattfinden, wodurch der Bruder zum Großvater des Konfliktknotens wird und der Bruder wird Vater des ehemaligen rechten bzw. linken Kindes des Konfliktknotens. Im weiteren wird die Farbe des Bruders mit der Farbe des Vaters( jeweils vom Konfliktknoten ) getauscht. Das rechte bzw. das linke Kind wird schwarzgefärbt. Zu beachten ist, dass der noch immer die selbe Farbe in der Wurzel hat, wodurch die vierte Eigenschaft, dass wenn ein Knoten rot ist beide Kinder schwarz sein müssen, erhalten bleibt. Allerdings hat der Konfliktknoten einen weiteren schwarzen Vorfahren. Um diesen Sachverhalt näher zu analysieren verdeutlichen wir, dass der Vater falls er vor der Transformation  nicht schwarz war er es anschließend ist. War der Vater vor der Transformation bereits schwarz, so ist er es anschließend immernoch und er hat seinen ehemaligen Bruder nun als schwarzen Großvater. Somit beinhalten die Pfade, die duch den Konfliktknoten verlaufen einen zusätzlichen Schwarzen Knoten. Für die Pfade, die den Konfliktknoen nicht enthalten ergeben sich nun zwei möglichkeiten. Zum einen kann dieser Pfad duch den Bruder des Konfliktknotens verlaufen, in diesem Fall verliefe der Pfad vor und nach der Transformatation durch den alten Bruder sowie den neuen Vater des Konfliktknotens. In diesem Falle hätten die beiden Knoten lediglich ihre Farbe vertauscht, was zur Folge hätte, dass sich an der Schwarztiefe dieses Pfades nichts ändert. Zum anderen kann es allerdings auch sein, dass der Pfad duch den neuen Onkel, welcher das rechte bzw. das linke Kind des Bruders ist, des Konfliktknotens verläuft. Das bedeutet, dass der Pfad nach der Transformation nicht mehr duch den Bruder, dessen Vater sowie dem rechten bzw. dem linken Kind des Bruders verläuft, sondern stattdessen nur noch durch den Bruder, der nun die Farbe seines alten Vaters besitzt, sowie durch das rechte bzw. linke Kind des Bruders, dessen Farbe duch die Transformation von rot auf schwarz gewechselt hat. Beide Fälle verändern somit nichts an der Anzahl der schwarzen Knoten auf den Pfaden wodurch das Gleichgewicht wieder hergestellt ist.

 '''deleteCase6( Node n )'''
 sibling( n ).color = n.parent.color
 n.parent.color = BLACK
 if n is n.parent.left do
     sibling( n ).right.color = BLACK
     rotateLeft( n.parent )
 else do
     sibling( n ).left.color = BLACK
     rotateRight( n.parent )