Der erste Teil des Algorithmus ist aequivalent zum Einfuegen eines Knoten in einen binaeren Suchbaum.
rbelement current,parent,x;
x=new rbelement();
current=root;
parent=null;
while (current!=NIL) {
if (key==current.searchkey)
return false;
parent=current;
current=(key<current.searchkey)?current.left:current.right;
}
x.parent=parent;
x.left=NIL;
x.right=NIL;
x.color=RED;
x.searchkey=key;
if (parent!=null) {
if (key<parent.searchkey)
parent.left=x;
else
parent.right=x;
} else {
root=x;
}
insertFixup(x);
return true;
} // End of insert
Die Suche terminiert ausserdem, wenn der zu durchsuchende Baum der leere Baum (NIL) ist. Ist dies der Fall, so haben wir die Stelle gefunden, an welcher wir einen neuen Knoten einfuegen koennen. Der leere Baum (NIL) wird dabei durch den einzufuegenden Knoten ersetzt. Der einzufuegende Knoten hat dabei zwei leere Unterbaeume (NIL). Wenn der Vorgaengerknoten nicht existiert, das heisst, den Wert ``null'' hat, so gibt es in dem gesamten Baum noch kein Element und das einzufuegende Element ist die Wurzel des Baumes. Fall das nicht der Fall ist, muss bestimmt werden, ob der einzufuegende Knoten das linke oder das rechte Kind seines Vorgaengerknotens sein soll. Da die binaere Suchbedingung gewahrt werden muss, erfolgt dies durch einen Schluesselvergleich. Ist der Schluessel des einzufuegenden Knotens groesser als der des Vorgaengerknotens, so wird er das rechte, im anderen Fall das linke Kind.
Bis zu diesem Punkt entspricht der Algorithmus dem Algorithmus zum Einfuegen in einen binaeren Suchbaum. Allerdings kann dieses Einfuegen die Bedingungen eines Rot-Schwarz Baumes verletzen.
Erstens steht die Frage, welche Farbe der einzufuegende Knoten bekommen soll. Faerben wir den Knoten schwarz, so ist die Rot-Schwarz Baum Eigenschaft 2 verletzt, da auf einem Pfad ein schwarzer Knoten zuviel ist. Deshalb faerben wir stets jeden eingefuegten Knoten rot.
Dies kann zur Folge haben, dass die Rot-Schwarz Baum Eigenschaft 3 verletzt ist, genau dann, wenn der Vorgaengerknoten von K rot ist.
Sei x ein roter Knoten in einem Rot-Schwarz Suchbaum T und x ist der einzige Knoten, der eine Rot-Schwarz Bedingung verletzt. Abgesehen von x ist T ein Rot-Schwarz Baum.
Fall 1: x ist die Wurzel -> T ist ein Rot-Schwarz Baum
Fall 2: x ist nicht die Wurzel, doch der Elternknoten ist die Wurzel -> Faerben wir die Wurzel schwarz, ist T ein Rot-Schwarz Baum.
Fall 3: x ist nicht die Wurzel, der Elternknoten y von x ist nicht die Wurzel und y ist das linke Kind von seinem Elternknoten z. Sei u das rechte Kind von z.
Fall 3.1: u ist rot. Dann muss u und y schwarz verfaerbt werden, und z rot. Damit kann nur noch z die Rot-Schwarz Baum Bedingungen verletzen und der Algorithmus wird mit x:=z wiederholt. Dieser Fall ist gezeigt im Bild 11.
Fall 3.2: u ist schwarz und x ist das linke Kind von y. In diesem Fall wird y nach rechts rotiert und schwarz verfaerbt. z wird rot gefaerbt. T ist ein Rot-Schwarz Baum. Bild 12 zeigt diesen Fall.
Fall 3.3: u ist schwarz und x ist das rechte Kind von y. In diesem Fall wird
x zuerst nach links rotiert. Damit wurde der Fall 3.3 in den Fall 3.2 umgewandelt,
mit x und y vertauscht. Das heisst: x wird nach rechts rotiert und schwarz verfaerbt.
z wird rot verfaerbt. T ist ein Rot-Schwarz Baum. Bild 13 zeigt diesen Fall.
Fall 4: Der Fall 4 ist symmetrisch zu dem Fall 3. x ist nicht die Wurzel, der Elternknoten y von x ist nicht die Wurzel und y ist das rechte Kind seines Elternknotens z. u sei das linke Kind von z.
Fall 4.1: u ist rot. Dann muss u und y schwarz verfaerbt werden, und z rot. Damit kann nur noch z die Rot-Schwarz Baum Bedingung verletzen, und der Algorithmus wird mit x:=z wiederholt.
Fall 4.2: u ist schwarz und x ist das rechte Kind von y. In diesem Fall wird y nach links rotiert und schwarz verfaerbt. z wird schwarz verfaerbt. T ist ein Rot-Schwarz Baum.
Fall 4.3: u ist schwarz und x ist das linke Kind von y. In diesem Fall wird x zuerst nach recht und anschliessend nach links rotiert. x wird schwarz verfaerbt, z wird rot gefaerbt. T ist ein Rot-Schwarz Baum.
Bild 14 zeigt eine komplexe Einfuegen-Operation in einen Rot-Schwarz Suchbaum (genommen aus [Cormen]).
Der folgende Algorithmus behandelt ausschliesslich die Faelle 3 und 4. Der Fall 1 muss nicht behandelt werden, weil keine Unausgeglichenheit auftritt.
while ((x!=root) && (x.parent.color==RED)) {
if (x.parent==x.parent.parent.left) {
rbelement y=x.parent.parent.right;
if (y.color==RED) {
x.parent.color=BLACK; // Fall 3.1
y.color=BLACK; // Fall 3.1
x.parent.parent.color=RED; // Fall 3.1
x=x.parent.parent; // Fall 3.1
} else {
if (x==x.parent.right) {
x=x.parent; // Fall 3.3
rotateLeft(x); // Fall 3.3
}
x.parent.color=BLACK; // Fall 3.2
x.parent.parent.color=RED; // Fall 3.2
rotateRight(x.parent.parent); // Fall 3.2
}
} else {
rbelement y = x.parent.parent.left;
if (y.color==RED) {
x.parent.color=BLACK; // Fall 4.1
y.color=BLACK; // Fall 4.1
x.parent.parent.color=RED; // Fall 4.1
x=x.parent.parent; // Fall 4.1
} else {
if (x==x.parent.left) {
/* Das hier ist Fall 4.3. Der Fall 4.3 ist dem Fall 4.2 sehr aehnlich,
* und wir koennen ihn einfach umwandeln in einen Fall 4.2 -> siehe
* detaillierte Beschreibung des Projekts. Wir aktualisieren x
* und rotieren x nach rechts.
*/
x=x.parent; // Fall 4.3
rotateRight(x); // Fall 4.3
}
x.parent.color=BLACK; // Fall 4.2
x.parent.parent.color=RED; // Fall 4.2
rotateLeft(x.parent.parent); // Fall 4.2
}
}
}
/* An dieser Stelle nehmen wir eine Vereinfachung vor. Es gibt Faelle, in denen
* die Wurzel einbezogen werden muss. Beispiel:
*
* o Wurzel (Rot)
* / \
* Knoten x (rot) o N il
* / \
* N il N il
*
* Angenommen, der Knoten x wurde angefuegt. Wenn wir in dieser Situtation die
* Schleife durchlaufen lassen, erhalten wir eine NullPointerException, weil dieser Fall
* nicht behandelt wird, insbesondere der Onkel-(oder auch Tanten-)knoten von x
* nicht existiert.
* Die Wurzel eines Rot-Schwarz Baumes kann ohne Beeintraechtigung der
* Invariante schwarz verfaerbt werden, da dies die Anzahl der schwarzen
* Knoten auf JEDEM Pfad um eins erhoeht. Damit entfaellt Fall 2.
*/
root.color=BLACK;
} // End of function insertFixed
Damit haben wir alle moeglichen Faelle behandelt. z muss schwarz sein, da sonst laut Rot-Schwarz Baum Bedingung 3 y schwarz sein muesste, und T damit ein Rot-Schwarz Baum waere. y ist rot. u muss existieren, da wir beim Einfuegen einen schwarzen NIL-Knoten durch den Knoten x ersetzt haben. Laut der zweiten Rot-Schwarz Baum Bedingung muss z also ein weiteres Kind besitzen, dessen Farbe rot oder schwarz sein kann.
Der Algorithmus terminiert in den Faellen 1, 2, 3.2, 3.3, 4.2, 4,3. In den Faellen
3.1 und 4.1 wird die Verletzung der Rot-Schwarz Baum Bedingungen immer um zwei
Knoten nach oben, in Richtung der Wurzel von T verschoben, das Niveau des die
Rot-Schwarz Baum Bedingungen verletzenden Knoten also um 2 verringert. Wieder,
da die Hoehe eine natuerliche Zahl ist, kann sie nicht unendlich oft verringt
werden und der Algorithmus wird terminieren. Weiterhin ist festzustellen, dass
der Algorithmus, falls rotiert wird, terminiert. Die Faelle 3.1 und 4.1 sind
die einzigen Faelle, in denen der Algorithmus nicht terminiert, und in diesen
Faellen finden keine Rotationen statt. Ausserdem finden hoechtens 2 Rotationen
statt. Damit ist die Anzahl der Rotationen 
.
Da zum Auffinden des Punktes, an dem der neue Knoten eingefuegt werden kann,
der gleiche Algorithmus wie beim Finden eines Elementes benutzt wird, kann das
Einfuegen eines Knoten in T in 
Zeit erreicht werden, wenn n
die Anzahl der Knoten in T sei. Die while-Schleife wird nur in den Faellen 3.1
und 4.1 wiederholt, wobei die Verletzung der definierenden Eigenschaften eines
Rot-Schwarz Baumes mit jedem Schleifendurchlauf nach oben in Richtung Wurzel
bewegt wird. Das heisst die Faelle 3.1 und 4.1 laufen in 
Zeit und
damit in Zeit, wenn n die Anzahl von Knoten in dem Baum ist.
Die Operation Einfuegen besitzt demnach ein Laufzeitverhalten von
und damit fuer das Einfuegen eines Elementes in einen Rot-Schwarz
Baum mit n Knoten.
