{"id":22336,"date":"2021-09-29T12:30:41","date_gmt":"2021-09-29T10:30:41","guid":{"rendered":"https:\/\/www.happycoders.eu\/?p=22336"},"modified":"2025-06-12T09:12:35","modified_gmt":"2025-06-12T07:12:35","slug":"rot-schwarz-baum-java","status":"publish","type":"post","link":"https:\/\/www.happycoders.eu\/de\/algorithmen\/rot-schwarz-baum-java\/","title":{"rendered":"Rot-Schwarz-Baum (vollst\u00e4ndig erkl\u00e4rt, mit Java-Code)"},"content":{"rendered":"\n<p>Der Rot-Schwarz-Baum ist eine weit verbreitete konkrete Implementierung eines&nbsp;<a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Selbstbalancierender_binarer_Suchbaum\">selbstbalancierenden bin\u00e4ren Suchbaums<\/a>.&nbsp;Im JDK wird er in der <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/17\/docs\/api\/java.base\/java\/util\/TreeMap.html\" target=\"_blank\">TreeMap<\/a> und seit Java 8 auch bei Bucket-Kollisionen in der <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/17\/docs\/api\/java.base\/java\/util\/HashMap.html\" target=\"_blank\">HashMap<\/a> verwendet. Wie funktioniert er?<\/p>\n\n\n\n<p>In diesem Artikel erf\u00e4hrst du:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Was ist ein Rot-Schwarz-Baum?<\/li>\n\n\n\n<li><span style=\"color: initial;\">Wie f\u00fcgt man Elemente in einen Rot-Schwarz-Baum ein? Wie entfernt man sie?<\/span><\/li>\n\n\n\n<li>Nach welchen Regeln wird ein Rot-Schwarz-Baum balanciert?<\/li>\n\n\n\n<li><span style=\"color: initial;\">Wie implementiert man einen Rot-Schwarz-Baum in Java?<\/span><\/li>\n\n\n\n<li>Wie bestimmt man die Zeitkomplexit\u00e4t?<\/li>\n\n\n\n<li>Was unterscheidet einen Rot-Schwarz-Baum von anderen Datenstrukturen?<\/li>\n<\/ul>\n\n\n\n<p>Den Quellcode zum Artikel findest du in diesem&nbsp;<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\" target=\"_blank\">GitHub-Repository<\/a>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"was-ist-ein-rot-schwarz-baum\">Was ist ein Rot-Schwarz-Baum?<\/h2>\n\n\n\n<p>Ein Rot-Schwarz-Baum ist ein selbstbalancierender bin\u00e4rer Suchbaum, d. h. ein bin\u00e4rer Suchbaum, der automatisch eine gewisse Balance aufrechterh\u00e4lt.<\/p>\n\n\n\n<p>Jedem Knoten ist eine Farbe (rot oder schwarz) zugewiesen. Ein Satz von Regeln legt fest, wie diese Farben angeordnet sein m\u00fcssen (z. B. darf ein roter Knoten keine roten Kinder haben). Durch diese Anordnung wird sichergestellt, dass der Baum eine gewisse Balance erh\u00e4lt.<\/p>\n\n\n\n<p>Nach dem Einf\u00fcgen und L\u00f6schen von Knoten werden recht komplexe Algorithmen angewendet, um die Einhaltung der Regeln zu \u00fcberpr\u00fcfen \u2013 und bei Abweichungen die vorgeschriebenen Eigenschaften durch Umf\u00e4rben von Knoten und Rotationen wiederherzustellen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"nil-knoten-im-rot-schwarz-baum\">NIL-Knoten im Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Rot-Schwarz-B\u00e4ume werden in der Literatur mit und ohne sogenannte NIL-Knoten dargestellt. Ein NIL-Knoten ist ein Blatt, das keinen Wert enth\u00e4lt. NIL-Knoten werden im sp\u00e4teren Verlauf f\u00fcr die Algorithmen relevant, um z. B. Farben von Onkel- oder Geschwister-Knoten zu bestimmen.<\/p>\n\n\n\n<p>In Java k\u00f6nnen NIL-Knoten einfach durch <code>null<\/code>-Referenzen dargestellt werden; dazu sp\u00e4ter mehr.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"beispiel-fuer-einen-rot-schwarz-baum\">Beispiel f\u00fcr einen Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Im folgenden Beispiel siehst du zwei m\u00f6gliche Darstellungen eines Rot-Schwarz-Baums. Die erste Grafik zeigt den Baum ohne (d. h. mit impliziten) NIL- Bl\u00e4ttern; die zweite Grafik zeigt den Baum mit expliziten NIL-Bl\u00e4ttern.<\/p>\n\n\n\n<div class=\"wp-block-columns hc-no-margin-columns is-layout-flex wp-container-core-columns-is-layout-28f84493 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-400x229.png\" alt=\"Rot-Schwarz-Baum Beispiel mit impliziten NIL-Bl\u00e4ttern\" class=\"wp-image-22370\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-400x229.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-224x128.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-336x192.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-504x289.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-672x385.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-600x344.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Rot-Schwarz-Baum mit impliziten NIL-Bl\u00e4ttern<\/figcaption><\/figure>\n<\/div><\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\"><div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_400\"><img decoding=\"async\" width=\"400\" height=\"274\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-400x274.png\" alt=\"Rot-Schwarz-Baum Beispiel mit expliziten NIL-Bl\u00e4ttern\" class=\"wp-image-22371\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-400x274.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-224x153.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-336x230.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-504x345.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-672x460.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil-600x411.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-example-with-nil.png 800w\" sizes=\"(max-width: 400px) 100vw, 400px\" \/><figcaption class=\"wp-element-caption\">Rot-Schwarz-Baum mit expliziten NIL-Bl\u00e4ttern<\/figcaption><\/figure>\n<\/div><\/div>\n<\/div>\n\n\n\n<p>Im Verlauf dieses Artikels werde ich auf die Darstellung der NIL-Bl\u00e4tter in der Regel verzichten. Bei der Erkl\u00e4rung der Einf\u00fcge- und L\u00f6schoperationen werde ich sie vereinzelt anzeigen, wenn es das Verst\u00e4ndnis des jeweiligen Algorithmus erleichert.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"eigenschaften-eines-rot-schwarz-baums\">Eigenschaften eines Rot-Schwarz-Baums<\/h3>\n\n\n\n<p>Die Balance des Rot-Schwarz-Baums wird durch folgende Regeln sichergestellt:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Jeder Knoten ist entweder rot oder schwarz.<\/li>\n\n\n\n<li>(Die Wurzel ist schwarz.)<\/li>\n\n\n\n<li>Alle NIL-Bl\u00e4tter sind schwarz.<\/li>\n\n\n\n<li>Ein roter Knoten darf keine roten Kinder haben.<\/li>\n\n\n\n<li>Alle Pfade von einem Knoten zu den darunterliegenden Bl\u00e4ttern enthalten die gleiche Anzahl schwarzer Knoten.<\/li>\n<\/ol>\n\n\n\n<p>Regel 2 steht in Klammern, da sie auf die Balance des Baumes keinerlei Auswirkung hat. Wenn ein Kind einer roten Wurzel ebenfalls rot ist, muss die Wurzel laut Regel 4 schwarz gef\u00e4rbt werden. Wenn eine rote Wurzel allerdings nur schwarze Kinder hat, bringt es keinen Vorteil die Wurzel schwarz zu f\u00e4rben.<\/p>\n\n\n\n<p>Von daher wird Regel 2 in der Literatur oft weggelassen.<\/p>\n\n\n\n<p>Ich werde in der Erkl\u00e4rung der Einf\u00fcge- und L\u00f6schoperationen und im Java-Code darauf hinweisen, wo es Unterschiede g\u00e4be, wenn auch Regel 2 umgesetzt w\u00fcrde. Soviel im Voraus: Der Unterschied ist pro Operation nur eine Zeile Code :)<\/p>\n\n\n\n<p>Aus Regeln 4 und 5 folgt \u00fcbrigens, dass ein roter Knoten immer entweder zwei NIL-Bl\u00e4tter hat oder zwei schwarze Kind-Knoten mit Werten. H\u00e4tte er <em>ein<\/em> NIL-Blatt und <em>ein<\/em> schwarzes Kind mit Wert, dann w\u00fcrden die Pfade durch dieses Kind mindestens einen schwarzen Knoten mehr haben als der Pfad zum NIL-Blatt, und das w\u00fcrde Regel 5 verletzen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"hoehe-des-rot-schwarz-baums\">H\u00f6he des Rot-Schwarz-Baums<\/h3>\n\n\n\n<p>Als H\u00f6he des Rot-Schwarz-Baums bezeichnen wir die maximale Anzahl an Knoten von der Wurzel bis zu einem NIL-Blatt, die Wurzel nicht eingerechnet. Die H\u00f6he des Rot-Schwarz-Baums im Beispiel oben betr\u00e4gt 4:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"274\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-600x274.png\" alt=\"H\u00f6he eines Rot-Schwarz-Baums\" class=\"wp-image-22379\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-600x274.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-224x102.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-336x153.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-504x230.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-672x307.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-800x365.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height-944x431.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-height.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">H\u00f6he eines Rot-Schwarz-Baums<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Aus Regeln 3 und 4 folgt:<\/p>\n\n\n\n<p>Der <em>l\u00e4ngste<\/em> Pfad von der Wurzel zu einem Blatt (die Wurzel nicht eingerechnet) ist maximal doppelt so lang wie der <em>k\u00fcrzeste<\/em> Pfad von der Wurzel zu einem Blatt.<\/p>\n\n\n\n<p>Dies ist einfach erkl\u00e4rt:<\/p>\n\n\n\n<p>Nehmen wir an, der k\u00fcrzeste Pfad hat (zus\u00e4tzlich zur Wurzel) <em>n<\/em> schwarze und keine roten Knoten. Dann k\u00f6nnten wir noch einmal <em>n<\/em> rote Knoten vor jedem schwarzen Knoten einf\u00fcgen, ohne Regel 3 zu brechen (die man auch umformulieren k\u00f6nnte in: es d\u00fcrfen keine zwei rote Knoten aufeinander folgen).<\/p>\n\n\n\n<p>Das folgende Beispiel zeigt links den k\u00fcrzestestm\u00f6glichen Pfad und rechts den l\u00e4ngstm\u00f6glichen Pfad durch einen Rot-Schwarz-Baum der H\u00f6he 4:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"274\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-600x274.png\" alt=\"K\u00fcrzester und l\u00e4ngster Pfad in einem Rot-Schwarz-Baum\" class=\"wp-image-22392\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-600x274.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-224x102.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-336x153.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-504x230.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-672x307.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-400x183.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-800x365.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths-944x431.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-shortest-longest-paths.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">K\u00fcrzester und l\u00e4ngster Pfad in einem Rot-Schwarz-Baum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Pfade zu den NIL-Bl\u00e4ttern links haben eine L\u00e4nge (exklusive Wurzel) von 2; die Pfade zu den NIL-Bl\u00e4ttern rechts unten haben eine L\u00e4nge von 4.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"schwarz-hoehe-des-rot-schwarz-baums\">Schwarz-H\u00f6he des Rot-Schwarz-Baums<\/h3>\n\n\n\n<p>Als Schwarz-H\u00f6he bezeichnet man die Anzahl schwarzer Knoten von einem bestimmten Knoten bis zu seinen Bl\u00e4ttern. Die schwarzen NIL-Bl\u00e4tter werden dabei mitgez\u00e4hlt, der Startknoten nicht.<\/p>\n\n\n\n<p>Die Schwarz-H\u00f6he des gesamten Baumes ist die Anzahl der schwarzen Knoten von der Wurzel (diese wird nicht mitgez\u00e4hlt) bis zu den NIL-Bl\u00e4ttern.<\/p>\n\n\n\n<p>Die Schwarz-H\u00f6he aller bisher gezeigten Rot-Schwarz-B\u00e4ume ist 2.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"implementierung-eines-rot-schwarz-baums-in-java\">Implementierung eines Rot-Schwarz-Baums in Java<\/h2>\n\n\n\n<p>Als Ausgangspunkt f\u00fcr f\u00fcr die Implementierung des Rot-Schwarz-Baums in Java verwende ich den <a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Binarer_Suchbaum_in_Java\">Java-Quellcode f\u00fcr den bin\u00e4ren Suchbaum<\/a>&nbsp;aus dem zweiten Teil der Bin\u00e4rbaum-Serie.<\/p>\n\n\n\n<p>Knoten werden durch die Klasse&nbsp;<code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/Node.java\" target=\"_blank\">Node<\/a><\/code>&nbsp;dargestellt. Als Knotenwert verwenden wir der Einfachheit halber&nbsp;<code>int<\/code>-Primitive.<\/p>\n\n\n\n<p>Neben den Kind-Knoten <code>left<\/code> und <code>right<\/code> ben\u00f6tigen wir f\u00fcr die Implementierung des Rot-Schwarz-Baums eine Referenz auf den Elternknoten <code>parent<\/code> sowie die Farbe des Knotens, <code>color<\/code>. Diese speichern wir in einem <code>boolean<\/code>, wobei wir rot als <code>false<\/code> festlegen und schwarz als <code>true<\/code>.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Node<\/span> <\/span>{\n  <span class=\"hljs-keyword\">int<\/span> data;\n\n  Node left;\n  Node right;\n  Node parent;\n\n  <span class=\"hljs-keyword\">boolean<\/span> color;\n\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-title\">Node<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> data)<\/span> <\/span>{\n    <span class=\"hljs-keyword\">this<\/span>.data = data;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Den Rot-Schwarz-Baum implementieren wir in der Klasse <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java\" target=\"_blank\">RedBlackTree<\/a><\/code>. Diese erweitert die im zweiten Teil der Serie vorgestellte Klasse&nbsp;<code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BaseBinaryTree.java\" target=\"_blank\">BaseBinaryTree<\/a><\/code> (die im Wesentlichen eine <code>getRoot()<\/code>-Funktion zur Verf\u00fcgung stellt).<\/p>\n\n\n\n<p>Die Operationen (Einf\u00fcgen, Suche, L\u00f6schen) werden in den folgenden Abschnitten nach und nach hinzugef\u00fcgt.<\/p>\n\n\n\n<p>Doch zun\u00e4chst m\u00fcssen wir einige Hilfsfunktionen definieren.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rot-schwarz-baum-rotation\">Rot-Schwarz-Baum Rotation<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Einfugen_im_binaren_Suchbaum\">Einf\u00fcgen<\/a>&nbsp;und&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerer-suchbaum-java\/#Loschen_im_binaren_Suchbaum\">L\u00f6schen<\/a>&nbsp;funktioniert grunds\u00e4tzlich so wie im Artikel \u00fcber bin\u00e4re Suchb\u00e4ume beschrieben.<\/p>\n\n\n\n<p>Nach dem Einf\u00fcgen und L\u00f6schen werden die Rot-Schwarz-Regeln (<a href=\"#Eigenschaften_eines_Rot-Schwarz-Baums\">s. o.<\/a>) \u00fcberpr\u00fcft. Wenn diese verletzt wurden, m\u00fcssen sie wiederhergestellt werden. Dies geschieht durch Umf\u00e4rben von Knoten und durch Rotationen.<\/p>\n\n\n\n<p>Die Rotation funktioniert exakt wie bei den <a href=\"\/de\/algorithmen\/avl-baum-java\/\">AVL-B\u00e4umen<\/a>, die ich im vorangegangenen Tutorial beschrieben habe. Ich zeige dir hier noch einmal die entsprechenden Diagramme. Ausf\u00fchrliche Erkl\u00e4rungen findest du im Abschnitt <a href=\"\/de\/algorithmen\/avl-baum-java\/#AVL-Baum_Rotation\">\"AVL-Baum-Rotationen\"<\/a> des eben genannten Artikels.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rechts-rotation\">Rechts-Rotation<\/h3>\n\n\n\n<p>Die folgende Grafik zeigt eine Rechts-Rotation. Die Farben haben keinen Bezug zu denen des Rot-Schwarz-Baumes. Sie dienen lediglich der besseren Nachverfolgung der Knotenbewegungen.<\/p>\n\n\n\n<p>Der linke Knoten <em>L<\/em> wird zur neuen Wurzel, die Wurzel <em>N<\/em> zu dessen rechtem Kind. Das rechte Kind <em>LR<\/em> des vor der Rotation linken Knotens <em>L<\/em> wird zum linken Kind des nach der Rotation rechten Knotens <em>N<\/em>. Die zwei wei\u00dfen Knoten <em>LL<\/em> und <em>R<\/em> \u00e4ndern ihre relative Position nicht.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-800x228.png\" alt=\"Rechts-Rotation im Rot-Schwarz-Baum\" class=\"wp-image-22416\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-right-rotation.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Rechts-Rotation im Rot-Schwarz-Baum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Der Java-Code ist etwas l\u00e4nger als beim AVL-Baum \u2013 aus folgenden zwei Gr\u00fcnden:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Wir m\u00fcssen auch die <code>parent<\/code>-Referenzen der Knoten aktualisieren (im AVL-Baum haben wir ohne <code>parent<\/code>-Referenzen gearbeitet).<\/li>\n\n\n\n<li>Wir m\u00fcssen die Referenzen von und zum Eltern-Knoten desjenigen Knotens, der zu Beginn der Rotation oben liegt (in der Grafik <em>N<\/em>), aktualisieren. Dies geschah beim AVL-Baum indirekt durch das Zur\u00fcckgeben der neuen Wurzel des rotierten Teilbaums und das \"Einh\u00e4ngen\" der Rotation in den rekursiven Aufruf der Einf\u00fcge- und L\u00f6sch-Operationen.<\/li>\n<\/ol>\n\n\n\n<p>Die Implementierung der Rechts-Rotation findest du im <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L358\" target=\"_blank\">Quellcode ab Zeile 358<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">rotateRight<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node parent = node.parent;\n  Node leftChild = node.left;\n\n  node.left = leftChild.right;\n  <span class=\"hljs-keyword\">if<\/span> (leftChild.right != <span class=\"hljs-keyword\">null<\/span>) {\n    leftChild.right.parent = node;\n  }\n\n  leftChild.right = node;\n  node.parent = leftChild;\n\n  replaceParentsChild(parent, node, leftChild);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die am Ende aufgerufene Methode <code>replaceParentsChild()<\/code> setzt die Eltern-Kind-Beziehung zwischen dem Eltern-Knoten des ehemaligen Wurzelknotens <em>N<\/em> des rotierten Teilbaums und dessen neuen Wurzelknoten <em>L<\/em>. Du findest sie <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L388\" target=\"_blank\">im Code ab Zeile 388<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">replaceParentsChild<\/span><span class=\"hljs-params\">(Node parent, Node oldChild, Node newChild)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">if<\/span> (parent == <span class=\"hljs-keyword\">null<\/span>) {\n    root = newChild;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (parent.left == oldChild) {\n    parent.left = newChild;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (parent.right == oldChild) {\n    parent.right = newChild;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(<span class=\"hljs-string\">\"Node is not a child of its parent\"<\/span>);\n  }\n\n  <span class=\"hljs-keyword\">if<\/span> (newChild != <span class=\"hljs-keyword\">null<\/span>) {\n    newChild.parent = parent;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"links-rotation\">Links-Rotation<\/h3>\n\n\n\n<p>Die Links-Rotation funktioniert analog: Der rechte Knoten <em>R<\/em> wandert hoch an die Spitze. Die Wurzel <em>N<\/em> wird zum linken Kind von <em>R<\/em>. Das linke Kind <em>RL<\/em> des ehemals rechten Knotens <em>R<\/em> wird zum rechten Kind des nach der Rotation linken Knotens <em>N<\/em>. <em>L<\/em> und <em>RR<\/em> \u00e4ndern ihre relative Position nicht.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-800x228.png\" alt=\"Links-Rotation im Rot-Schwarz-Baum\" class=\"wp-image-22415\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-left-rotation-v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Links-Rotation im Rot-Schwarz-Baum<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Hier ist der Java-Code f\u00fcr die Links-Rotation (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L373\" target=\"_blank\">Quellcode ab Zeile 373<\/a>):<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">rotateLeft<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node parent = node.parent;\n  Node rightChild = node.right;\n\n  node.right = rightChild.left;\n  <span class=\"hljs-keyword\">if<\/span> (rightChild.left != <span class=\"hljs-keyword\">null<\/span>) {\n    rightChild.left.parent = node;\n  }\n\n  rightChild.left = node;\n  node.parent = rightChild;\n\n  replaceParentsChild(parent, node, rightChild);\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"operationen-im-rot-schwarz-baum\">Operationen im Rot-Schwarz-Baum<\/h2>\n\n\n\n<p>Wie jeder Bin\u00e4rbaum bietet auch der Rot-Schwarz-Baum Operationen zum Suchen, Einf\u00fcgen und L\u00f6schen von Knoten. Diese gehen wir in den folgenden Abschnitten Schritt f\u00fcr Schritt durch.<\/p>\n\n\n\n<p>An dieser Stelle m\u00f6chte ich dir den <a rel=\"noopener\" href=\"https:\/\/www.cs.usfca.edu\/~galles\/visualization\/RedBlack.html\" target=\"_blank\">Rot-Schwarz-Baum-Simulator von David Galles<\/a> empfehlen. Mit diesem kannst du beliebige Einf\u00fcge-, L\u00f6sch- und Suchoperationen grafisch animiert darstellen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"suche-im-rot-schwarz-baum\">Suche im Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Die Suche funktioniert wie in jedem bin\u00e4ren Suchbaum: Wir vergleichen den Suchschl\u00fcssel zun\u00e4chst mit der Wurzel. Ist der Suchschl\u00fcssel kleiner, setzen wir die Suche im linken Teilbaum fort; ist der Suchschl\u00fcssel gr\u00f6\u00dfer, setzen wir die Suche im rechten Teilbaum fort.<\/p>\n\n\n\n<p>Dies wiederholen wir solange, bis wir entweder den gesuchten Knoten gefunden haben \u2013 oder bis wir ein NIL-Blatt (im Java-Code: eine <code>null<\/code>-Referenz) erreicht haben. Das bedeutet dann, dass der gesuchte Schl\u00fcssel im Baum nicht existiert.<\/p>\n\n\n\n<p>Eine grafische Darstellung der Suche findest du <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Binarer_Suchbaum_Beispiel\">im Beispiel des Artikels \u00fcber bin\u00e4re Suchb\u00e4ume<\/a>. <\/p>\n\n\n\n<p>F\u00fcr den Rot-Schwarz-Baum implementieren wir eine iterative Variante der Suche. Du findest sie im <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L14\" target=\"_blank\">Quellcode ab Zeile 14<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> Node <span class=\"hljs-title\">searchNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node node = root;\n  <span class=\"hljs-keyword\">while<\/span> (node != <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">if<\/span> (key == node.data) {\n      <span class=\"hljs-keyword\">return<\/span> node;\n    } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      node = node.left;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      node = node.right;\n    }\n  }\n\n  <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-keyword\">null<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Der Code sollte selbsterkl\u00e4rend sein.<\/p>\n\n\n\n<p>Im Abschnitt <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Suche_im_binaren_Suchbaum\">\"Suche im bin\u00e4ren Suchbaum\"<\/a> des o. g. Artikels findest du auch eine rekursive Version der Suche.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"einfuegen-in-einen-rot-schwarz-baum\">Einf\u00fcgen in einen Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Um einen neuen Knoten einzuf\u00fcgen, gehen wir zun\u00e4chst so vor wie im Abschnitt <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Einfugen_im_binaren_Suchbaum\">\"Einf\u00fcgen im bin\u00e4ren Suchbaum\"<\/a> des entsprechenden Artikels beschrieben. D. h. wir suchen von der Wurzel abw\u00e4rts die Einf\u00fcgeposition und h\u00e4ngen den neuen Knoten an ein Blatt oder Halbblatt an.<\/p>\n\n\n\n<p>Den Code findest du in der <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L29\" target=\"_blank\" rel=\"noopener\">Klasse <code>RedBlackTree<\/code> ab Zeile 29<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-7\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">insertNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node node = root;\n  Node parent = <span class=\"hljs-keyword\">null<\/span>;\n\n  <span class=\"hljs-comment\">\/\/ Traverse the tree to the left or right depending on the key<\/span>\n  <span class=\"hljs-keyword\">while<\/span> (node != <span class=\"hljs-keyword\">null<\/span>) {\n    parent = node;\n    <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      node = node.left;\n    } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &gt; node.data) {\n      node = node.right;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalArgumentException(<span class=\"hljs-string\">\"BST already contains a node with key \"<\/span> + key);\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Insert new node<\/span>\n  Node newNode = <span class=\"hljs-keyword\">new<\/span> Node(key);\n  newNode.color = RED;\n  <span class=\"hljs-keyword\">if<\/span> (parent == <span class=\"hljs-keyword\">null<\/span>) {\n    root = newNode;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (key &lt; parent.data) {\n    parent.left = newNode;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    parent.right = newNode;\n  }\n  newNode.parent = parent;\n\n  fixRedBlackPropertiesAfterInsert(newNode);\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-7\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Den neuen Knoten f\u00e4rben wir initial rot, so dass Regel 5 erf\u00fcllt ist, d. h. dass alle Pfade auch nach dem Einf\u00fcgen die gleiche Anzahl schwarzer Knoten aufweisen.<\/p>\n\n\n\n<p>Wenn der Elternknoten des eingef\u00fcgten Knotens allerdings ebenfalls rot ist, haben wir Regel 4 verletzt. Wir m\u00fcssen dann durch Umf\u00e4rben und\/oder Rotationen den Baum so reparieren, dass alle Regeln wieder erf\u00fcllt sind. Dies geschieht in der Methode <code>fixRedBlackPropertiesAfterInsert()<\/code>, die in der letzten Zeile der <code>insertNode()<\/code>-Methode aufgerufen wird.<\/p>\n\n\n\n<p>Bei der Reparatur m\u00fcssen wir f\u00fcnf unterschiedliche F\u00e4lle behandeln:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Fall 1: Neuer Knoten ist die Wurzel<\/li>\n\n\n\n<li>Fall 2: Elternknoten ist rot und die Wurzel<\/li>\n\n\n\n<li>Fall 3: Elternknoten und Onkelknoten sind rot<\/li>\n\n\n\n<li>Fall 4: Elternknoten ist rot, Onkelknoten ist schwarz, eingef\u00fcgter Knoten ist \"innerer Enkel\"<\/li>\n\n\n\n<li>Fall 5: Elternknoten ist rot, Onkelknoten ist schwarz, eingef\u00fcgter Knoten ist \"\u00e4u\u00dferer Enkel\"<\/li>\n<\/ul>\n\n\n\n<p>Die f\u00fcnf F\u00e4lle werden im folgenden beschrieben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 1: Neuer Knoten ist die Wurzel<\/h4>\n\n\n\n<p>Sollte der neue Knoten die Wurzel sein, m\u00fcssen wir nichts weiter tun. Es sein denn, wir arbeiten mit Regel 2 (\"die Wurzel ist immer schwarz\"). Dann m\u00fcssten wir die Wurzel schwarz f\u00e4rben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 2: Elternknoten ist rot und die Wurzel<\/h4>\n\n\n\n<p>In diesem Fall ist Regel 4 verletzt (\"kein rot-rot!\"). Wir m\u00fcssen nun lediglich die Wurzel schwarz f\u00e4rben. Dies f\u00fchrt dazu, dass Regel 4 wieder eingehalten wird.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"130\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-600x130.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Umf\u00e4rben einer roten Wurzel \" class=\"wp-image-22488\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-600x130.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-224x49.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-336x73.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-504x109.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-672x146.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-400x87.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-800x173.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root-944x205.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-recolor-red-root.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Umf\u00e4rben einer roten Wurzel<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Und Regel 5? Da die Wurzel bei dieser Regel nicht mitgez\u00e4hlt wird, haben alle Pfade nach wie vor <em>einen<\/em> schwarzen Knoten (die in der Grafik nicht eingezeichneten NIL-Bl\u00e4tter). Und w\u00fcrden wir die Wurzel mitz\u00e4hlen, dann h\u00e4tten <em>alle<\/em> Pfade jetzt zwei statt einen schwarze Knoten \u2013 auch das w\u00e4re erlaubt.<\/p>\n\n\n\n<p>Wenn wir mit Regel 2 arbeiten (\"die Wurzel ist immer schwarz\"), dann haben wir die Wurzel bereits in Fall 1 schwarz gef\u00e4rbt, und Fall 2 kann nicht mehr eintreten.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 3:  Elternknoten und Onkelknoten sind rot<\/h4>\n\n\n\n<p>Als Onkelknoten bezeichnen wir den Geschwisterknoten des Elternknotens, also das zweite Kind des Gro\u00dfelternknotens neben dem Elternknoten. Die folgende Grafik sollte das verst\u00e4ndlich machen: Eingef\u00fcgt wurde die 81; deren Elternknoten ist die 75, der Gro\u00dfelternknoten die 19 und der Onkel die 18.<\/p>\n\n\n\n<p>Sowohl der Elternknoten als auch der Onkelknoten sind rot. In diesem Fall machen wir folgendes:<\/p>\n\n\n\n<p>Wir f\u00e4rben Eltern- und Onkelknoten (im Beispiel 18 und 75) schwarz und den Gro\u00dfelternknoten (im Beispiel 19) rot. Damit ist Regel 4 (\"kein rot-rot!\") am eingef\u00fcgten Knoten wieder erf\u00fcllt. Die Anzahl schwarzer Knoten pro Pfad \u00e4ndert sich nicht (im Beispiel bleibt sie bei 2).<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"259\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-800x259.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Umf\u00e4rben von Eltern-, Gro\u00dfeltern- und Onkelknoten\" class=\"wp-image-22490\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-800x259.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-224x73.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-336x109.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-504x163.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-672x218.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-400x130.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-600x194.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-944x306.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor-1200x389.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-insert-red-uncle-recolor.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Umf\u00e4rben von Eltern-, Gro\u00dfeltern- und Onkelknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Allerdings k\u00f6nnte es nun am Gro\u00dfelternknoten zu zwei roten Knoten in Folge kommen \u2013 n\u00e4mlich dann, wenn auch der Urgro\u00dfelternknoten (im Beispiel die 17) rot w\u00e4re. In diesem Fall m\u00fcssten wir weitere Reparaturen vornehmen. Dies w\u00fcrden wir machen, indem wir die Reparaturfunktion rekursiv auf dem Gro\u00dfelternknoten aufrufen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 4: Elternknoten ist rot, Onkelknoten ist schwarz, eingef\u00fcgter Knoten ist \"innerer Enkel\"<\/h4>\n\n\n\n<p>Diesen Fall muss ich zun\u00e4chst erkl\u00e4ren: \"innerer Enkel\" bedeutet, dass der Weg vom Gro\u00dfeltern-Knoten zum eingef\u00fcgten Knoten ein Dreieck bildet, wie in folgender Grafik anhand der 19, 75 und 24 gezeigt. In diesem Beispiel sieht man au\u00dferdem, dass auch ein NIL-Blatt als schwarzer Onkelknoten angesehen wird (entsprechend Regel 3).<\/p>\n\n\n\n<p>(Die jeweils zwei NIL-Bl\u00e4tter der 9 und der 24, sowie das rechte NIL-Blatt der 75 habe ich der \u00dcbersicht halber nicht mit eingezeichnet.)<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"261\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-600x261.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Schwarzer Onkelknoten, eingef\u00fcgter Knoten ist &quot;innerer&quot; Enkel\" class=\"wp-image-22468\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-600x261.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-224x97.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-336x146.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-504x219.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-672x292.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-400x174.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-800x348.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-944x411.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Fall 4: Schwarzer Onkelknoten, eingef\u00fcgter Knoten ist \"innerer\" Enkel<\/figcaption><\/figure>\n<\/div>\n\n\n<p>In diesem Fall rotieren wir zun\u00e4chst am Elternknoten in <em>entgegengesetzter Richtung des eingef\u00fcgten Knotens<\/em>.<\/p>\n\n\n\n<p>Was bedeutet das?<\/p>\n\n\n\n<p>Wenn der eingef\u00fcgte Knoten <em>linkes<\/em> Kind seines Elternknotens ist, rotieren wir am Elternknoten nach <em>rechts<\/em>. Wenn der eingef\u00fcgte Knoten <em>rechtes<\/em> Kind ist, dann rotieren wir nach <em>links<\/em>.<\/p>\n\n\n\n<p>Im Beispiel ist der eingef\u00fcgte Knoten (die 24) linkes Kind, also rotieren wir am Elternknoten (im Beispiel 75) nach rechts:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"261\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-800x261.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Rechtsrotation um Elternknoten\" class=\"wp-image-22469\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-800x261.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-224x73.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-336x110.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-504x164.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-672x219.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-400x131.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-600x196.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-944x308.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1-1200x392.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 1: Rechts-Rotation um Elternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Als zweites rotieren wir am Gro\u00dfelternknoten in <em>entgegengesetzter<\/em> Richtung zur vorherigen Rotation (im Beispiel an der 19 linksherum):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img decoding=\"async\" width=\"1600\" height=\"458\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Linksrotation um Gro\u00dfelternknoten\" class=\"wp-image-22470\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2.png 1600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-600x172.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-800x229.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-944x270.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-rotate2-1200x344.png 1200w\" sizes=\"(max-width: 1600px) 100vw, 1600px\" \/><figcaption class=\"wp-element-caption\">Schritt 2: Links-Rotation um Gro\u00dfelternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Zuletzt f\u00e4rben wir den gerade eingef\u00fcgten Knoten (im Beispiel die 24) schwarz und den urspr\u00fcnglichen Gro\u00dfelternknoten (im Beispiel die 19) rot:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"160\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-800x160.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Umf\u00e4rben des eingef\u00fcgten und des urspr\u00fcnglichen Gro\u00dfelternknotens\" class=\"wp-image-22471\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-800x160.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-224x45.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-336x67.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-504x101.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-672x134.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-400x80.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-600x120.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-944x189.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor-1200x240.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-inner-grandchild-recolor.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 3: Umf\u00e4rben des eingef\u00fcgten und des urspr\u00fcnglichen Gro\u00dfelternknotens<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Da an der Spitze des zuletzt rotierten Teilbaumes jetzt ein schwarzer Knoten steht, kann es dort nicht zu einer Verletzung von Regel 4 (\"kein rot-rot!\") kommen.<\/p>\n\n\n\n<p>Auch das Rotf\u00e4rben des urspr\u00fcnglichen Gro\u00dfelternknotens (19) kann nicht zu einer Verletzung von Regel 4 f\u00fchren. Denn dessen linkes Kind ist der Onkelknoten, der per Definition dieses Falles schwarz ist. Und das rechte Kind ist als Folge der zweiten Rotation das linke Kind des eingef\u00fcgten Knotens, also ein schwarzes NIL-Blatt.<\/p>\n\n\n\n<p>Die eingef\u00fcgte rote 75 hat als Kinder zwei NIL-Bl\u00e4tter, somit gibt es auch hier keinen Versto\u00df gegen Regel 4.<\/p>\n\n\n\n<p>Die Reparatur ist damit abgeschlossen, ein rekursiver Aufruf der Reparaturfunktion ist nicht erforderlich.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 5: Elternknoten ist rot, Onkelknoten ist schwarz, eingef\u00fcgter Knoten ist \"\u00e4u\u00dferer Enkel\" <\/h4>\n\n\n\n<p>\"\u00c4u\u00dferer Enkel\" bedeutet, dass der Weg vom Gro\u00dfelternknoten zum eingef\u00fcgten Knoten eine Linie bildet, wie in folgendem Beispiel die 19, die 75 und die gerade eingef\u00fcgte 81:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"262\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-600x262.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Schwarzer Onkelknoten, eingef\u00fcgter Knoten ist &quot;\u00e4u\u00dferer&quot; Enkel\" class=\"wp-image-22459\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-600x262.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-224x98.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-336x147.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-504x220.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-672x293.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-400x175.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-800x349.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-944x412.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Fall 5: Schwarzer Onkelknoten, eingef\u00fcgter Knoten ist \"\u00e4u\u00dferer\" Enkel<\/figcaption><\/figure>\n<\/div>\n\n\n<p>In diesem Fall rotieren wir am Gro\u00dfelternknoten (im Beispiel 19) in <em>entgegengesetzter Richtung des Eltern- und eingef\u00fcgten Knotens<\/em> (beide gehen in diesem Fall ja in die gleiche Richtung). Im Beispiel sind Eltern- und eingef\u00fcgter Knoten jeweils <em>rechtes<\/em> Kind, also rotieren wir am Gro\u00dfelternknoten nach <em>links<\/em>:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"260\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-800x260.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Linksrotation um Gro\u00dfelternknoten\" class=\"wp-image-22461\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-800x260.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-224x73.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-336x109.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-504x164.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-672x218.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-400x130.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-600x195.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-944x307.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate-1200x390.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-rotate.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 1: Links-Rotation um Gro\u00dfelternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Danach f\u00e4rben wir den ehemaligen Elternknoten (im Beispiel die 75) schwarz und den ehemaligen Gro\u00dfelternknoten (die 19) rot:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"160\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-800x160.png\" alt=\"Einf\u00fcgen im Rot-Schwarz-Baum: Umf\u00e4rben von ehemaligem Eltern- und Gro\u00dfelternknoten\" class=\"wp-image-22464\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-800x160.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-224x45.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-336x67.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-504x101.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-672x134.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-400x80.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-600x120.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-944x189.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor-1200x240.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-black-uncle-outer-grandchild-recolor.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 2: Umf\u00e4rben von ehemaligem Eltern- und Gro\u00dfelternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wie am Ende von Fall 4 haben wir an der Spitze der Rotation einen schwarzen Knoten, so dass es dort zu keiner Verletzung von Regel 4 (\"kein rot-rot!\") kommen kann. <\/p>\n\n\n\n<p>Das linke Kind der 19 ist nach der Rotation der urspr\u00fcngliche Onkelknoten, also per Fall-Definition schwarz; das rechte Kind der 19 ist das urspr\u00fcnglich linke Kind des Elternknotens (75), welches ebenfalls ein schwarzes NIL-Blatt sein muss, da sonst der rechte Platz, an dem wir die 81 eingef\u00fcgt haben, nicht frei gewesen w\u00e4re (denn ein roter Knoten hat immer entweder zwei schwarze Kinder mit Wert oder zwei schwarze NIL-Kinder).<\/p>\n\n\n\n<p>Die rote 81 ist der eingef\u00fcgte Knoten und hat daher ebenfalls zwei schwarze NIL-Bl\u00e4tter.<\/p>\n\n\n\n<p>Die Reparatur des Rot-Schwarz-Baumes ist an dieser Stelle abgeschlossen.<\/p>\n\n\n\n<p>Wer genau aufgepasst hat, stellt fest: Fall 5 entspricht exakt der zweiten Rotation aus Fall 4. Im Code wird sich das dadurch zeigen, dass f\u00fcr Fall 4 nur die erste Rotation implementiert ist und danach zum Code von Fall 5 gesprungen wird.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Implementierung der Reparaturfunktion nach dem Einf\u00fcgen<\/h4>\n\n\n\n<p>Die vollst\u00e4ndige Reparaturfunktion findest du in <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L64\" target=\"_blank\" rel=\"noopener\"><code>RedBlackTree<\/code> ab Zeile 64<\/a>. Die F\u00e4lle 1 bis 5 sind durch Kommentare markiert. Die F\u00e4lle 4 und 5 sind in 4a\/4b und 5a\/5b aufgeteilt, je nachdem, ob der Elternknoten linkes (4a\/5a) oder rechtes Kind (4b\/5b) des Gro\u00dfelternknotens ist.  <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-8\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">fixRedBlackPropertiesAfterInsert<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node parent = node.parent;\n\n  <span class=\"hljs-comment\">\/\/ Case 1: Parent is null, we've reached the root, the end of the recursion<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (parent == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-comment\">\/\/ Uncomment the following line if you want to enforce black roots (rule 2):<\/span>\n    <span class=\"hljs-comment\">\/\/ node.color = BLACK;<\/span>\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Parent is black --&gt; nothing to do<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (parent.color == BLACK) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ From here on, parent is red<\/span>\n  Node grandparent = parent.parent;\n\n  <span class=\"hljs-comment\">\/\/ Case 2:<\/span>\n  <span class=\"hljs-comment\">\/\/ Not having a grandparent means that parent is the root. If we enforce black roots<\/span>\n  <span class=\"hljs-comment\">\/\/ (rule 2), grandparent will never be null, and the following if-then block can be<\/span>\n  <span class=\"hljs-comment\">\/\/ removed.<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (grandparent == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-comment\">\/\/ As this method is only called on red nodes (either on newly inserted ones - or -<\/span>\n    <span class=\"hljs-comment\">\/\/ recursively on red grandparents), all we have to do is to recolor the root black.<\/span>\n    parent.color = BLACK;\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Get the uncle (may be null\/nil, in which case its color is BLACK)<\/span>\n  Node uncle = getUncle(parent);\n\n  <span class=\"hljs-comment\">\/\/ Case 3: Uncle is red -&gt; recolor parent, grandparent and uncle<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (uncle != <span class=\"hljs-keyword\">null<\/span> &amp;&amp; uncle.color == RED) {\n    parent.color = BLACK;\n    grandparent.color = RED;\n    uncle.color = BLACK;\n\n    <span class=\"hljs-comment\">\/\/ Call recursively for grandparent, which is now red.<\/span>\n    <span class=\"hljs-comment\">\/\/ It might be root or have a red parent, in which case we need to fix more...<\/span>\n    fixRedBlackPropertiesAfterInsert(grandparent);\n  }\n\n  <span class=\"hljs-comment\">\/\/ Parent is left child of grandparent<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (parent == grandparent.left) {\n    <span class=\"hljs-comment\">\/\/ Case 4a: Uncle is black and node is left-&gt;right \"inner child\" of its grandparent<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (node == parent.right) {\n      rotateLeft(parent);\n\n      <span class=\"hljs-comment\">\/\/ Let \"parent\" point to the new root node of the rotated sub-tree.<\/span>\n      <span class=\"hljs-comment\">\/\/ It will be recolored in the next step, which we're going to fall-through to.<\/span>\n      parent = node;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Case 5a: Uncle is black and node is left-&gt;left \"outer child\" of its grandparent<\/span>\n    rotateRight(grandparent);\n\n    <span class=\"hljs-comment\">\/\/ Recolor original parent and grandparent<\/span>\n    parent.color = BLACK;\n    grandparent.color = RED;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Parent is right child of grandparent<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-comment\">\/\/ Case 4b: Uncle is black and node is right-&gt;left \"inner child\" of its grandparent<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (node == parent.left) {\n      rotateRight(parent);\n\n      <span class=\"hljs-comment\">\/\/ Let \"parent\" point to the new root node of the rotated sub-tree.<\/span>\n      <span class=\"hljs-comment\">\/\/ It will be recolored in the next step, which we're going to fall-through to.<\/span>\n      parent = node;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Case 5b: Uncle is black and node is right-&gt;right \"outer child\" of its grandparent<\/span>\n    rotateLeft(grandparent);\n\n    <span class=\"hljs-comment\">\/\/ Recolor original parent and grandparent<\/span>\n    parent.color = BLACK;\n    grandparent.color = RED;\n  }\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-8\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Hilfsfunktion <code>getUncle()<\/code> findest du <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L152\" target=\"_blank\">ab Zeile 152<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-9\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">getUncle<\/span><span class=\"hljs-params\">(Node parent)<\/span> <\/span>{\n  Node grandparent = parent.parent;\n  <span class=\"hljs-keyword\">if<\/span> (grandparent.left == parent) {\n    <span class=\"hljs-keyword\">return<\/span> grandparent.right;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (grandparent.right == parent) {\n    <span class=\"hljs-keyword\">return<\/span> grandparent.left;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(<span class=\"hljs-string\">\"Parent is not a child of its grandparent\"<\/span>);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-9\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h4 class=\"wp-block-heading\">Anmerkungen zur Implementierung<\/h4>\n\n\n\n<p>Im Gegensatz zum AVL-Baum k\u00f6nnen wir die Reparatur-Funktion des Rot-Schwarz-Baumes nicht ohne weiteres in die bestehende Rekursion aus <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeRecursive.java#L34\"><code>BinarySearchTreeRecursive<\/code><\/a> einh\u00e4ngen. Der Grund daf\u00fcr ist, dass wir nicht nur an demjenigen Knoten rotieren m\u00fcssen, unter dem wir den neuen Knoten eingef\u00fcgt haben, sondern ggf. auch am Gro\u00dfelternknoten (F\u00e4lle 3 und 4).<\/p>\n\n\n\n<p>Du wirst in der Literatur zahlreiche alternative Implementierungen finden. Diese sind teilweise minimal performanter als der hier vorgestellte Weg, da mehrere Schritte kombiniert werden. Das \u00e4ndert nichts an der Gr\u00f6\u00dfenordnung der Performance, kann aber ein paar Prozente herausholen. Mir war es in erster Linie wichtig den Algorithmus verst\u00e4ndlich zu implementieren. Die performanteren Algorithmen sind immer auch komplexer.<\/p>\n\n\n\n<p>Ich habe das iterative Einf\u00fcgen hier in zwei Schritten implementiert \u2013 erst Suche, dann Einf\u00fcgen \u2013 im Gegensatz zu <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinarySearchTreeIterative.java#L26\" target=\"_blank\"><code>BinarySearchTreeIterative<\/code><\/a>, wo beides kombiniert war. Das macht das Lesen etwas einfacher, ben\u00f6tigt allerdings auch einen zus\u00e4tzlichen \"<code>if (key &lt; parent.data)<\/code>\"-Check, um zu bestimmen, ob der neue Knoten als linkes oder rechtes Kind unter seinen Elternknoten eingef\u00fcgt werden muss.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"loeschen-aus-einem-rot-schwarz-baum\">L\u00f6schen aus einem Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Wenn du das Kapitel \u00fcber das Einf\u00fcgen gerade fertiggelesen hast, solltest du vielleicht eine kurze Pause machen. Denn das L\u00f6schen ist noch komplexer.<\/p>\n\n\n\n<p>Zun\u00e4chst gehen wir so vor, wie im Abschnitt <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/#Loschen_im_binaren_Suchbaum\">\"L\u00f6schen im bin\u00e4ren Suchbaum\"<\/a> des Artikels \u00fcber bin\u00e4re Suchb\u00e4ume im Allgemeinen beschrieben.<\/p>\n\n\n\n<p>Hier noch einmal eine kurze Zusammenfassung:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Hat der zu l\u00f6schende Knoten <em>keine<\/em> Kinder, entfernen wir ihn einfach.<\/li>\n\n\n\n<li>Hat der zu l\u00f6schende Knoten <em>ein<\/em> Kind, dann entfernen wir den Knoten und lassen sein einziges Kind an dessen Position aufr\u00fccken.<\/li>\n\n\n\n<li>Hat der zu l\u00f6schende Knoten <em>zwei<\/em> Kinder, dann kopieren wir den Inhalt (nicht die Farbe!) des In-Order-Nachfolgers des rechten Kindes in den zu l\u00f6schenden Knoten und l\u00f6schen danach den In-Order-Nachfolger nach Vorschrift 1 oder 2 (der In-Order-Nachfolger hat per Definiton maximal ein Kind).<\/li>\n<\/ol>\n\n\n\n<p>Danach m\u00fcssen wir die Regeln des Baumes \u00fcberpr\u00fcfen und ggf. den Baum reparieren. Dazu m\u00fcssen wir uns merken, welche Farbe der gel\u00f6schte Knoten hat und welchen Knoten wir haben aufr\u00fccken lassen.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Ist der gel\u00f6schte Knoten rot, dann k\u00f6nnen wir keine Regel verletzt haben: Weder kann es dadurch zu zwei aufeinanderfolgenden roten Knoten kommen (Regel 4), noch \u00e4ndert sich die Anzahl schwarzer Knoten auf irgendeinem Pfad (Regel 5).<\/li>\n\n\n\n<li>Ist der gel\u00f6schte Knoten allerdings schwarz, haben wir Regel 5 garantiert verletzt (au\u00dfer der Baum enthielt nichts als eine schwarze Wurzel) und Regel 4 m\u00f6glicherweise auch \u2013 n\u00e4mlich dann, wenn sowohl Elternknoten als auch das aufger\u00fcckte Kind des gel\u00f6schten Knotens rot waren.<\/li>\n<\/ul>\n\n\n\n<p>Hier zun\u00e4chst der Code f\u00fcr das eigentliche L\u00f6schen eines Knotens (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L163\" target=\"_blank\">Klasse <code>RedBlackTree<\/code>, Zeile 163<\/a>). Unter dem Code erkl\u00e4re ich dir dessen Teile:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-10\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">public<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">deleteNode<\/span><span class=\"hljs-params\">(<span class=\"hljs-keyword\">int<\/span> key)<\/span> <\/span>{\n  Node node = root;\n\n  <span class=\"hljs-comment\">\/\/ Find the node to be deleted<\/span>\n  <span class=\"hljs-keyword\">while<\/span> (node != <span class=\"hljs-keyword\">null<\/span> &amp;&amp; node.data != key) {\n    <span class=\"hljs-comment\">\/\/ Traverse the tree to the left or right depending on the key<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (key &lt; node.data) {\n      node = node.left;\n    } <span class=\"hljs-keyword\">else<\/span> {\n      node = node.right;\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node not found?<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == <span class=\"hljs-keyword\">null<\/span>) {\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  <span class=\"hljs-comment\">\/\/ At this point, \"node\" is the node to be deleted<\/span>\n\n  <span class=\"hljs-comment\">\/\/ In this variable, we'll store the node at which we're going to start to fix the R-B<\/span>\n  <span class=\"hljs-comment\">\/\/ properties after deleting a node.<\/span>\n  Node movedUpNode;\n  <span class=\"hljs-keyword\">boolean<\/span> deletedNodeColor;\n\n  <span class=\"hljs-comment\">\/\/ Node has zero or one child<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.left == <span class=\"hljs-keyword\">null<\/span> || node.right == <span class=\"hljs-keyword\">null<\/span>) {\n    movedUpNode = deleteNodeWithZeroOrOneChild(node);\n    deletedNodeColor = node.color;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has two children<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-comment\">\/\/ Find minimum node of right subtree (\"inorder successor\" of current node)<\/span>\n    Node inOrderSuccessor = findMinimum(node.right);\n\n    <span class=\"hljs-comment\">\/\/ Copy inorder successor's data to current node (keep its color!)<\/span>\n    node.data = inOrderSuccessor.data;\n\n    <span class=\"hljs-comment\">\/\/ Delete inorder successor just as we would delete a node with 0 or 1 child<\/span>\n    movedUpNode = deleteNodeWithZeroOrOneChild(inOrderSuccessor);\n    deletedNodeColor = inOrderSuccessor.color;\n  }\n\n  <span class=\"hljs-keyword\">if<\/span> (deletedNodeColor == BLACK) {\n    fixRedBlackPropertiesAfterDelete(movedUpNode);\n\n    <span class=\"hljs-comment\">\/\/ Remove the temporary NIL node<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (movedUpNode.getClass() == NilNode<span class=\"hljs-class\">.<span class=\"hljs-keyword\">class<\/span>) <\/span>{\n      replaceParentsChild(movedUpNode.parent, movedUpNode, <span class=\"hljs-keyword\">null<\/span>);\n    }\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-10\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die ersten Zeilen des Codes suchen den zu l\u00f6schenden Knoten; wird dieser nicht gefunden, wird die Methode beendet.<\/p>\n\n\n\n<p>Wie es weiter geht, h\u00e4ngt von der Anzahl der Kinder zu l\u00f6schenden Knotens ab.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">L\u00f6schen eines Knotens mit keinem oder einem Kind<\/h4>\n\n\n\n<p>Hat der gel\u00f6schte Knoten maximal ein Kind, wird die Methode <code>deleteNodeWithZeroOrOneChild()<\/code> aufgerufen. Diese findest du im <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L221\" target=\"_blank\">Quellcode ab Zeile 221<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-11\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">deleteNodeWithZeroOrOneChild<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ Node has ONLY a left child --&gt; replace by its left child<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node.left != <span class=\"hljs-keyword\">null<\/span>) {\n    replaceParentsChild(node.parent, node, node.left);\n    <span class=\"hljs-keyword\">return<\/span> node.left; <span class=\"hljs-comment\">\/\/ moved-up node<\/span>\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has ONLY a right child --&gt; replace by its right child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node.right != <span class=\"hljs-keyword\">null<\/span>) {\n    replaceParentsChild(node.parent, node, node.right);\n    <span class=\"hljs-keyword\">return<\/span> node.right; <span class=\"hljs-comment\">\/\/ moved-up node<\/span>\n  }\n\n  <span class=\"hljs-comment\">\/\/ Node has no children --&gt;<\/span>\n  <span class=\"hljs-comment\">\/\/ * node is red --&gt; just remove it<\/span>\n  <span class=\"hljs-comment\">\/\/ * node is black --&gt; replace it by a temporary NIL node (needed to fix the R-B rules)<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    Node newChild = node.color == BLACK ? <span class=\"hljs-keyword\">new<\/span> NilNode() : <span class=\"hljs-keyword\">null<\/span>;\n    replaceParentsChild(node.parent, node, newChild);\n    <span class=\"hljs-keyword\">return<\/span> newChild;\n  }\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-11\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die hier mehrfach aufgerufene Methode <code>replaceParentsChild()<\/code> habe ich dir bereits bei der Rotation vorgestellt.<\/p>\n\n\n\n<p>Der Fall, dass der gel\u00f6schte Knoten schwarz ist und keine Kinder hat, stellt eine Besonderheit dar. Dieser wird im letzten <code>else<\/code>-Block behandelt:<\/p>\n\n\n\n<p>Wir haben oben festgestellt, dass das L\u00f6schen eines schwarzen Knotens dazu f\u00fchrt, dass die Anzahl schwarzer Knoten nicht mehr auf allen Pfaden gleich ist. D. h., wir werden den Baum reparieren m\u00fcssen. Die Baumreparatur beginnt (wie du in K\u00fcrze sehen wirst) immer beim aufger\u00fcckten Knoten.<\/p>\n\n\n\n<p>Wenn der gel\u00f6schte Knoten keine Kinder hat, r\u00fcckt quasi eines seiner NIL-Bl\u00e4tter an seine Position auf. Um sp\u00e4ter von diesem NIL-Blatt zu seinem Elternknoten navigieren zu k\u00f6nnen, brauchen wir einen speziellen Platzhalter. Dieser ist in der Klasse <code>NilNode<\/code> implementiert, die du im <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L349\" target=\"_blank\">Quellcode ab Zeile 349<\/a> findest:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-12\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">NilNode<\/span> <span class=\"hljs-keyword\">extends<\/span> <span class=\"hljs-title\">Node<\/span> <\/span>{\n  <span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-title\">NilNode<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">super<\/span>(<span class=\"hljs-number\">0<\/span>);\n    <span class=\"hljs-keyword\">this<\/span>.color = BLACK;\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-12\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Methode <code>deleteNodeWithZeroOrOneChild()<\/code> gibt schlie\u00dflich den aufger\u00fcckten Knoten zur\u00fcck, den sich die aufrufende Methode <code>deleteNode()<\/code> in der Variablen <code>movedUpNode<\/code> merkt.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">L\u00f6schen eines Knotens mit zwei Kindern<\/h4>\n\n\n\n<p>Hat der zu l\u00f6schende Knoten zwei Kinder, suchen wir zun\u00e4chst mit der Methode <code>findMinimum()<\/code> (<a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L244\" target=\"_blank\">Zeile 244<\/a>) den In-Order-Nachfolger des Teilbaumes, der am rechten Kind beginnt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-13\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">findMinimum<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">while<\/span> (node.left != <span class=\"hljs-keyword\">null<\/span>) {\n    node = node.left;\n  }\n  <span class=\"hljs-keyword\">return<\/span> node;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-13\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Daraufhin kopieren wir die Daten des In-Order-Nachfolgers in den zu l\u00f6schenden Knoten und rufen die oben vorgestellte Methode <code>deleteNodeWithZeroOrOneChild()<\/code> auf, um den In-Order-Nachfolger aus dem Baum zu entfernen. Wiederum merken wir uns den aufger\u00fcckten Knoten in <code>movedUpNode<\/code>.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Reparatur des Baumes<\/h4>\n\n\n\n<p>Hier noch einmal der letzte <code>if<\/code>-Block der <code>deleteNode()<\/code>-Methode:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-14\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-keyword\">if<\/span> (deletedNodeColor == BLACK) {\n  fixRedBlackPropertiesAfterDelete(movedUpNode);\n\n  <span class=\"hljs-comment\">\/\/ Remove the temporary NIL node<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (movedUpNode.getClass() == NilNode<span class=\"hljs-class\">.<span class=\"hljs-keyword\">class<\/span>) <\/span>{\n    replaceParentsChild(movedUpNode.parent, movedUpNode, <span class=\"hljs-keyword\">null<\/span>);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-14\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Wie oben bereits festgestellt, werden durch das L\u00f6schen eines roten Knotens keine Regeln verletzt. Wenn der gel\u00f6schte Knoten hingegen schwarz ist, rufen wir die Reparaturmethode <code>fixRedBlackPropertiesAfterDelete()<\/code> auf.<\/p>\n\n\n\n<p>Der ggf. in <code>deleteNodeWithZeroOrOneChild()<\/code> angelegte tempor\u00e4re <code>NilNode<\/code>-Platzhalter wurde nur f\u00fcr den Aufruf der Reparaturfunktion ben\u00f6tigt und kann daher im Anschluss entfernt werden.<\/p>\n\n\n\n<p>Beim L\u00f6schen m\u00fcssen wir noch einen Fall mehr beachten als beim Einf\u00fcgen: n\u00e4mlich sechs. Im Gegensatz zum Einf\u00fcgen ist dabei nicht die Farbe des Onkelknotens relevant, sondern die des Geschwisterknotens des aufger\u00fcckten Knotens.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Fall 1: Aufger\u00fcckter Knoten ist die Wurzel<\/li>\n\n\n\n<li>Fall 2: Geschwisterknoten ist rot<\/li>\n\n\n\n<li>Fall 3: Geschwisterknoten ist schwarz und hat zwei schwarze Kinder, Elternknoten ist rot<\/li>\n\n\n\n<li>Fall 4: Geschwisterknoten ist schwarz und hat zwei schwarze Kinder, Elternknoten ist schwarz<\/li>\n\n\n\n<li>Fall 5: Geschwisterknoten ist schwarz und hat mind. ein rotes Kind, \"\u00e4u\u00dferer Neffe\" ist schwarz<\/li>\n\n\n\n<li>Fall 6: Geschwisterknoten ist schwarz und hat mind. ein rotes Kind, \"\u00e4u\u00dferer Neffe\" ist rot<\/li>\n<\/ul>\n\n\n\n<p>Die folgenden Abschnitte beschreiben die sechs F\u00e4lle im Detail:<\/p>\n\n\n\n<h4 class=\"wp-block-heading\"><span style=\"font-size: revert; color: initial;\">Fall 1: Aufger\u00fcckter Knoten ist die Wurzel<\/span><\/h4>\n\n\n\n<p>Wurde die Wurzel entfernt, r\u00fcckt ein anderer Knoten an deren Position auf. Das kann nur dann passieren, wenn die Wurzel kein oder nur ein Kind hatte. Denn h\u00e4tte die Wurzel zwei Kinder gehabt, w\u00e4re letztendlich der In-Order-Nachfolger entfernt worden und nicht der Wurzelknoten.<\/p>\n\n\n\n<p>Wenn die Wurzel <em>kein<\/em> Kind hatte, ist die neue Wurzel ein schwarzer NIL-Knoten. Somit ist der Baum leer und g\u00fcltig:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"72\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-600x72.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Entfernen einer Wurzel ohne Kind\" class=\"wp-image-22541\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-600x72.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-224x27.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-336x40.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-504x60.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-672x81.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-400x48.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-800x96.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a-944x113.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1a.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\">Fall 1a: Entfernen einer Wurzel ohne Kind<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wenn die Wurzel <em>ein<\/em> Kind hatte, dann musste dies rot sein und keine weiteren Kinder haben.<\/p>\n\n\n\n<p>Denn: H\u00e4tte das rote Kind ein weiteres rotes Kind, w\u00e4re Regel 4 (\"kein rot-rot!\") verletzt gewesen. H\u00e4tte das rote Kind ein schwarzes Kind, dann h\u00e4tten die Pfade durch den roten Knoten wenigstens einen schwarzen Knoten mehr als der NIL-Teilbaum der Wurzel, und damit w\u00e4re Regel 5 verletzt gewesen.<\/p>\n\n\n\n<p>Somit besteht der Baum nur noch aus einer roten Wurzel und ist damit ebenfalls g\u00fcltig.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-half_600\"><img decoding=\"async\" width=\"600\" height=\"114\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-600x114.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Entfernen einer Wurzel mit einem Kind\" class=\"wp-image-22542\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-600x114.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-224x43.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-336x64.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-504x96.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-672x128.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-400x76.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-800x152.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b-944x179.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-1b.png 1200w\" sizes=\"(max-width: 600px) 100vw, 600px\" \/><figcaption class=\"wp-element-caption\"> Fall 1b: Entfernen einer Wurzel mit einem Kind<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Sollten wir mit Regel 2 arbeiten (\"die Wurzel ist immer schwarz\"), dann w\u00fcrden wir an dieser Stelle die Wurzel schwarz f\u00e4rben.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 2: Geschwisterknoten ist rot<\/h4>\n\n\n\n<p>F\u00fcr alle anderen F\u00e4lle pr\u00fcfen wir zun\u00e4chst die Farbe des Geschwisterknotens. Dies ist das zweite Kind des Elternknotens des gel\u00f6schten Knotens. In folgendem Beispiel l\u00f6schen wir die 9; deren Geschwisterknoten ist die rote 19:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"161\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-800x161.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Roter Geschwisterknoten\" class=\"wp-image-22553\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-800x161.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-224x45.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-336x68.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-504x101.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-672x135.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-400x81.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-600x121.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-944x190.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1-1200x242.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Fall 2: Roter Geschwisterknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>In diesem Fall f\u00e4rben wir zun\u00e4chst den Geschwisterknoten schwarz und den Elternknoten rot:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"175\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-800x175.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Roter Geschwisterknoten, Schritt 1: Umf\u00e4rben von Geschwister- und Elternknoten\" class=\"wp-image-22554\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-800x175.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-224x49.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-336x74.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-504x110.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-672x147.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-400x88.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-600x131.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-944x207.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2-1200x263.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 1: Umf\u00e4rben von Geschwister- und Elternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Dadurch wurde offensichtlich Regel 5 verletzt: Die Pfade im rechten Teilbaum des Elternknotens haben jeweils zwei schwarze Knoten mehr als die des linken Teilbaum. Dies beheben wir durch eine Rotation um den Elternknoten in Richtung des gel\u00f6schten Knotens.<\/p>\n\n\n\n<p>Im Beispiel haben wir den <em>linken<\/em> Knoten des Elternknotens gel\u00f6scht \u2013 wir f\u00fchren daher eine <em>Links<\/em>-Rotation durch:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"174\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-800x174.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Roter Geschwisterknoten, Schritt 2: Rotation um Elternknoten\" class=\"wp-image-22555\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-800x174.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-224x49.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-336x73.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-504x110.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-672x146.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-400x87.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-600x131.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-944x205.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3-1200x261.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 2: Rotation um Elternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Jetzt haben wir auf dem rechten Pfad zwei schwarze Knoten, auf dem zur 18 ebenfalls zwei. Allerdings haben wir <em>nur einen<\/em> schwarzen Knoten auf dem Pfad zum linken NIL-Blatt der 17 (zur Erinnerung: die Wurzel z\u00e4hlt nicht mit, die NIL-Knoten z\u00e4hlen mit \u2013 auch die in der Grafik nicht eingezeichneten).<\/p>\n\n\n\n<p>Wir schauen auf den neuen Geschwisterknoten des gel\u00f6schten Knotens (im Beispiel die 18). Dieser ist jetzt in jedem Fall schwarz, denn es handelt sich um ein urspr\u00fcngliches Kind des roten Geschwisterknotens vom Anfang des Falls.<\/p>\n\n\n\n<p>Au\u00dferdem hat der neue Geschwisterknoten schwarze Kinder. Deshalb f\u00e4rben wir den Geschwisterknoten (die 18) rot und den Elternknoten (die 17) schwarz:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"194\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-800x194.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Roter Geschwisterknoten, Schritt 3: Umf\u00e4rben von Eltern- und neuem Geschwisterknoten\" class=\"wp-image-22556\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-800x194.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-224x54.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-336x81.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-504x122.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-672x163.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-400x97.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-600x146.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-944x229.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4-1200x291.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-2-step4.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">(Schritt 3: Umf\u00e4rben von Eltern- und neuem Geschwisterknoten)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Jetzt haben alle Pfade zwei schwarze Knoten; wir haben also wieder einen g\u00fcltigen Rot-Schwarz-Baum.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 2 \u2012 Fall-Through<\/h4>\n\n\n\n<p>Tats\u00e4chlich habe ich in diesem letzten Schritt etwas vorweggenommen. Wir haben n\u00e4mlich die Regeln von Fall 3 ausgef\u00fchrt (deswegen ist der Bilduntertitel auch in Klammern).<\/p>\n\n\n\n<p>In diesem letzten Schritt von Fall 2 haben wir immer einen schwarzen Geschwisterknoten. Dass dieser zwei schwarze Kinder hatte, wie f\u00fcr Fall 3 gefordert, war Zufall. Tats\u00e4chlich kann am Ende von Fall 2 jeder der F\u00e4lle 3 bis 6 eintreten und muss entsprechend der folgenden Abschnitte behandelt werden.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 3: Geschwisterknoten ist schwarz und hat zwei schwarze Kinder, Elternknoten ist rot<\/h4>\n\n\n\n<p>In folgendem Beispiel l\u00f6schen wir die 75 und lassen eines seiner schwarzen NIL-Bl\u00e4tter aufr\u00fccken.<\/p>\n\n\n\n<p>(Nochmal zur Erinnerung: Ich zeige in den Grafiken nur dann NIL-Bl\u00e4tter an, wenn diese f\u00fcr das Verst\u00e4ndnis relevant sind.)<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"161\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-800x161.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit schwarzen Kindern und rotem Elternknoten\" class=\"wp-image-22545\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-800x161.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-224x45.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-336x68.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-504x101.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-672x135.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-400x81.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-600x121.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-944x190.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2-1200x242.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step1-v2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Fall 3: Schwarzer Geschwisterknoten mit schwarzen Kindern und rotem Elternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Das f\u00fchrt zu einem Versto\u00df von Regel 5: Im ganz rechten Pfad haben wir jetzt einen schwarzen Knoten weniger als in allen anderen.<\/p>\n\n\n\n<p>Der Geschwisterknoten (im Beispiel die 18) ist schwarz und hat zwei schwarze Kinder (die nicht dargestellten NIL-Bl\u00e4tter). Der Elternknoten (die 19) ist rot. In diesem Fall reparieren wir den Baum wie folgt:<\/p>\n\n\n\n<p>Wir f\u00e4rben den Geschwisterknoten (die 18) rot und den Elternknoten (die 19) schwarz:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img decoding=\"async\" width=\"1600\" height=\"358\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit schwarzen Kindern und rotem Elternknoten: Eltern- und Geschwisterknoten\" class=\"wp-image-22544\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2.png 1600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-224x50.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-336x75.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-504x113.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-672x150.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-400x90.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-600x134.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-800x179.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-944x211.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-3-step2-1200x269.png 1200w\" sizes=\"(max-width: 1600px) 100vw, 1600px\" \/><figcaption class=\"wp-element-caption\">Umf\u00e4rben von Eltern- und Geschwisterknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Somit haben wir wieder einen g\u00fcltigen Rot-Schwarz-Baum. Die Anzahl der schwarzen Knoten ist auf allen Pfaden gleich (wie von Regel 5 gefordert). Und da der Geschwisterknoten nur schwarze Kinder hat, kann es durch das Rotf\u00e4rben desselben nicht zu einer Verletzung von Regel 4 (\"kein rot-rot!\") kommen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 4: Geschwisterknoten ist schwarz und hat zwei schwarze Kinder, Elternknoten ist schwarz<\/h4>\n\n\n\n<p>Im n\u00e4chsten Beispiel l\u00f6schen wir die 18:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"169\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-800x169.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit schwarzen Kindern und schwarzem Elternknoten\" class=\"wp-image-22559\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-800x169.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-224x47.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-336x71.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-504x106.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-672x142.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-400x85.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-600x127.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-944x199.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1-1200x254.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-4-step1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Fall 4:  Schwarzer Geschwisterknoten mit schwarzen Kindern und schwarzem Elternknoten <\/figcaption><\/figure>\n<\/div>\n\n\n<p>Dies f\u00fchrt (genau wie bei Fall 3) zu einem Versto\u00df gegen Regel 5: Auf dem Pfad zum gel\u00f6schten Knoten haben wir jetzt einen schwarzen Knoten weniger als auf allen anderen Pfaden.<\/p>\n\n\n\n<p>Im Gegensatz zu Fall 3 ist bei Fall 4 der Elternknoten des gel\u00f6schten Knotens schwarz. Wir f\u00e4rben zun\u00e4chst den Geschwisterknoten rot:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"179\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-800x179.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit schwarzen Kindern und schwarzem Elternknoten: Umf\u00e4rben des Geschwisterknotens\" class=\"wp-image-32957\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-800x179.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-224x50.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-336x75.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-504x113.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-672x150.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-400x90.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-600x134.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-944x211.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3-1200x269.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step2.v3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\"> Schritt 1: Umf\u00e4rben des Geschwisterknotens<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Damit ist die Schwarzh\u00f6he in demjenigen Teilbaum, der am Elternknoten beginnt, wieder einheitlich (n\u00e4mlich 2). Im linken Teilbaum ist sie allerdings eins h\u00f6her (3). Gegen Regel 5 wird also noch immer versto\u00dfen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 4 \u2012 Rekursion<\/h4>\n\n\n\n<p>Dieses Problem l\u00f6sen wir, indem wir so tun, als h\u00e4tten wir zwischen der 17 und der 19 einen schwarzen Knoten gel\u00f6scht (was den gleichen Effekt gehabt h\u00e4tte). Dementsprechend rufen wir die Reparaturfunktion rekursiv auf dem Elternknoten, also der 19 auf (was in diesem Fall der aufger\u00fcckte Knoten gewesen w\u00e4re).<\/p>\n\n\n\n<p>Die 19 hat einen schwarzen Geschwisterknoten (die 9) mit zwei schwarzen Kindern (3 und 12) und einem roten Elternteil (17). Dementsprechend sind wir jetzt wieder bei Fall 3.<\/p>\n\n\n\n<p>Fall 3 l\u00f6sen wir, in dem wir den Geschwisterknoten rot und den Elternknoten schwarz f\u00e4rben:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"174\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-800x174.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit schwarzen Kindern und schwarzem Elternknoten: Umf\u00e4rben von Eltern- und Geschwisterknoten\" class=\"wp-image-32955\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-800x174.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-224x49.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-336x73.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-504x110.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-672x146.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-400x87.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-600x131.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-944x205.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1-1200x261.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2022\/07\/red-black-tree-delete-node-case-4-step3.v3-1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">(Schritt 2: Umf\u00e4rben von Eltern- und Geschwisterknoten)<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Die Schwarzh\u00f6he betr\u00e4gt nun auf allen Pfaden 2. Unser Rot-Schwarz-Baum ist damit wieder valide.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 5: Geschwisterknoten ist schwarz und hat mindestens ein rotes Kind, \"\u00e4u\u00dferer Neffe\" ist schwarz<\/h4>\n\n\n\n<p>In diesem Beispiel l\u00f6schen wir die 18:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-800x228.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem &quot;\u00e4u\u00dferen Neffen&quot;\" class=\"wp-image-22580\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Fall 5: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem \"\u00e4u\u00dferen Neffen\"<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Als Folge haben wir wieder einen Versto\u00df gegen Regel 5, da der Teilbaum, der am Geschwisterknoten beginnt, jetzt eine um eins gr\u00f6\u00dfere Schwarzh\u00f6he hat. <\/p>\n\n\n\n<p>Wir betrachten den \"\u00e4u\u00dferen Neffen\" des gel\u00f6schten Knotens. \"\u00c4u\u00dferer Neffe\" bezeichnet dasjenige Kind des Geschwisterknotens, das gegen\u00fcber dem gel\u00f6schten Knoten liegt. Im Beispiel ist das das rechte, per Definition schwarze, NIL-Blatt unter der 75.<\/p>\n\n\n\n<p>In folgender Grafik siehst du, dass Elternknoten, Geschwisterknoten und Neffe gemeinsam eine Linie bilden (im Beispiel die 19, die 75 und dessen rechtes NIL-Kind).<\/p>\n\n\n\n<p>Wir beginnen mit der Reparatur, indem wir den <em>inneren<\/em> Neffen (im Beispiel die 24) schwarz f\u00e4rben und den Geschwisterknoten (die 75) rot:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-800x229.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem &quot;\u00e4u\u00dferen Neffen&quot;: Umf\u00e4rben von Geschwisterknoten und innerem Neffen\" class=\"wp-image-22581\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-800x229.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-600x172.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-944x270.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2-1200x344.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 1: Umf\u00e4rben von Geschwisterknoten und innerem Neffen<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Danach f\u00fchren wir eine Rotation am Geschwisterknoten <em>in entgegengesetzter Richtung des gel\u00f6schten Knotens<\/em> durch. Im Beispiel wurde das <em>linke<\/em> Kind des Elternknotens gel\u00f6scht, also erfolgt am Geschwisterknoten (der 75) eine Rotation nach <em>rechts<\/em>:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-800x229.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem &quot;\u00e4u\u00dferen Neffen&quot;: Rotation um Geschwisterknoten\" class=\"wp-image-22582\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-800x229.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-600x172.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-944x270.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3-1200x344.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step3.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 2: Rotation um Geschwisterknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Wir f\u00fchren erneut ein paar Umf\u00e4rbungen durch:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Wir f\u00e4rben den Geschwisterknoten in der Farbe des Elternknotens (im Beispiel die 24 rot). <\/li>\n\n\n\n<li>Dann f\u00e4rben wir den Elternknoten (die 19) sowie den \u00e4u\u00dferen Neffen des gel\u00f6schten Knotens, also das rechte Kind des neuen Geschwisterknotens (im Beispiel die 75) schwarz:<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-800x229.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem &quot;\u00e4u\u00dferen Neffen&quot;: Umf\u00e4rben von Eltern- Geschwister- und Neffenknoten\" class=\"wp-image-22583\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-800x229.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-600x172.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-944x270.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4-1200x344.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step4.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 3:  Umf\u00e4rben von Eltern- Geschwister- und Neffenknoten  <\/figcaption><\/figure>\n<\/div>\n\n\n<p>Als letztes f\u00fchren wir eine Rotation am Elternknoten <em>in Richtung des gel\u00f6schten Knotens<\/em> durch. Im Beispiel war der gel\u00f6schte Knoten das <em>linke<\/em> Kind, dementsprechend f\u00fchren wir eine <em>Links<\/em>-Rotation aus (im Beispiel an der 19):<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-800x228.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und schwarzem &quot;\u00e4u\u00dferen Neffen&quot;: \" class=\"wp-image-22584\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-5-step5.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\"> Schritt 4: Rotation um Elternknoten <\/figcaption><\/figure>\n<\/div>\n\n\n<p>Damit werden alle Rot-Schwarz-Regeln wieder eingehalten. Es gibt keine zwei aufeinanderfolgenden roten Knoten, und die Anzahl schwarzer Knoten betr\u00e4gt auf allen Pfaden einheitlich zwei. Die Reparatur des Baumes ist damit abgeschlossen.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Fall 6: Geschwisterknoten ist schwarz und hat mindestens ein rotes Kind, \"\u00e4u\u00dferer Neffe\" ist rot<\/h4>\n\n\n\n<p>Im letzten Beispiel, welches Fall 5 stark \u00e4hnelt, l\u00f6schen wir ebenfalls die 18:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"229\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-800x229.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und rotem &quot;\u00e4u\u00dferen Neffen&quot;\" class=\"wp-image-22569\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-800x229.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-400x115.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-600x172.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-944x270.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1-1200x344.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step1.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Fall 6: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und rotem \"\u00e4u\u00dferen Neffen\"<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Als Folge haben wir, wie in Fall 5, einen Versto\u00df gegen Regel 5, da der Pfad zum gel\u00f6schten Knoten nun einen schwarzen Knoten weniger enth\u00e4lt.<\/p>\n\n\n\n<p>Bei Fall 6 ist, im Gegensatz zu Fall 5, der \u00e4u\u00dfere Neffe (im Beispiel die 81) rot und nicht schwarz.<\/p>\n\n\n\n<p>Wir f\u00e4rben zun\u00e4chst den Geschwisterknoten in der Farbe des Elternknotens (im Beispiel die 75 rot). Danach f\u00e4rben wir den Elternknoten (im Beispiel die 19) und den \u00e4u\u00dferen Neffen (die 81) schwarz:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"228\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-800x228.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und rotem &quot;\u00e4u\u00dferen Neffen&quot;: Umf\u00e4rben von Eltern- Geschwister- und Neffenknoten\" class=\"wp-image-22570\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-800x228.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-224x64.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-336x96.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-504x144.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-672x192.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-400x114.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-600x171.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-944x269.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2-1200x342.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step2.png 1600w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 1: Umf\u00e4rben von Eltern- Geschwister- und Neffenknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Als zweites f\u00fchren wir am Elternknoten eine Rotation <em>in Richtung des gel\u00f6schten Knotens<\/em> durch. Im Beispiel wurde das <em>linke<\/em> Kind seines Elternknotens gel\u00f6scht; entsprechend vollziehen wir eine <em>Links<\/em>-Rotation um die 19:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full_800\"><img decoding=\"async\" width=\"800\" height=\"239\" src=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-800x239.png\" alt=\"L\u00f6schen aus dem Rot-Schwarz-Baum: Schwarzer Geschwisterknoten mit mindestens einem roten Kind und rotem &quot;\u00e4u\u00dferen Neffen&quot;: Rotation um Elternknoten\" class=\"wp-image-22571\" srcset=\"https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-800x239.png 800w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-224x67.png 224w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-336x100.png 336w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-504x151.png 504w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-672x201.png 672w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-400x120.png 400w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-600x179.png 600w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-944x282.png 944w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3-1200x359.png 1200w, https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-delete-node-case-6-step3.png 1526w\" sizes=\"(max-width: 800px) 100vw, 800px\" \/><figcaption class=\"wp-element-caption\">Schritt 2: Rotation um Elternknoten<\/figcaption><\/figure>\n<\/div>\n\n\n<p>Damit sind die Rot-Schwarz-Regeln wiederhergestellt. Es folgen keine zwei roten Knoten aufeinander, und die Anzahl der schwarzen Knoten ist auf allen Pfaden gleich (n\u00e4mlich 2).<\/p>\n\n\n\n<p>Die Vorschriften in diesem letzten Fall gleichen den letzten zwei Schritten aus Fall 5. Im Quellcode wirst du sehen, dass f\u00fcr Fall 5 nur dessen ersten zwei Schritte implementiert sind und die Ausf\u00fchrung dann zu Fall 6 springt, um die letzten zwei Schritte auszuf\u00fchren.<\/p>\n\n\n\n<p>Damit haben wir alle sechs F\u00e4lle betrachtet. Kommen wir zur Implementierung der Reparaturfunktion in Java.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Implementierung der Reparaturfunktion nach dem L\u00f6schen<\/h4>\n\n\n\n<p>Du findest die Reparaturmethode <code>fixRedBlackPropertiesAfterDelete()<\/code> <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L252\" target=\"_blank\">im Quellcode ab Zeile 252<\/a>. Die F\u00e4lle 1 bis 6 sind durch Kommentare markiert. <\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-15\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">fixRedBlackPropertiesAfterDelete<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ Case 1: Examined node is root, end of recursion<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == root) {\n    <span class=\"hljs-comment\">\/\/ Uncomment the following line if you want to enforce black roots (rule 2):<\/span>\n    <span class=\"hljs-comment\">\/\/ node.color = BLACK;<\/span>\n    <span class=\"hljs-keyword\">return<\/span>;\n  }\n\n  Node sibling = getSibling(node);\n\n  <span class=\"hljs-comment\">\/\/ Case 2: Red sibling<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (sibling.color == RED) {\n    handleRedSibling(node, sibling);\n    sibling = getSibling(node); <span class=\"hljs-comment\">\/\/ Get new sibling for fall-through to cases 3-6<\/span>\n  }\n\n  <span class=\"hljs-comment\">\/\/ Cases 3+4: Black sibling with two black children<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (isBlack(sibling.left) &amp;&amp; isBlack(sibling.right)) {\n    sibling.color = RED;\n\n    <span class=\"hljs-comment\">\/\/ Case 3: Black sibling with two black children + red parent<\/span>\n    <span class=\"hljs-keyword\">if<\/span> (node.parent.color == RED) {\n      node.parent.color = BLACK;\n    }\n\n    <span class=\"hljs-comment\">\/\/ Case 4: Black sibling with two black children + black parent<\/span>\n    <span class=\"hljs-keyword\">else<\/span> {\n      fixRedBlackPropertiesAfterDelete(node.parent);\n    }\n  }\n\n  <span class=\"hljs-comment\">\/\/ Case 5+6: Black sibling with at least one red child<\/span>\n  <span class=\"hljs-keyword\">else<\/span> {\n    handleBlackSiblingWithAtLeastOneRedChild(node, sibling);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-15\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Hilfsmethoden <code>getSibling()<\/code> und <code>isBlack()<\/code> findest du <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L334\" target=\"_blank\" rel=\"noopener\">ab Zeile 334<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-16\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> Node <span class=\"hljs-title\">getSibling<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  Node parent = node.parent;\n  <span class=\"hljs-keyword\">if<\/span> (node == parent.left) {\n    <span class=\"hljs-keyword\">return<\/span> parent.right;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (node == parent.right) {\n    <span class=\"hljs-keyword\">return<\/span> parent.left;\n  } <span class=\"hljs-keyword\">else<\/span> {\n    <span class=\"hljs-keyword\">throw<\/span> <span class=\"hljs-keyword\">new<\/span> IllegalStateException(<span class=\"hljs-string\">\"Parent is not a child of its grandparent\"<\/span>);\n  }\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">boolean<\/span> <span class=\"hljs-title\">isBlack<\/span><span class=\"hljs-params\">(Node node)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">return<\/span> node == <span class=\"hljs-keyword\">null<\/span> || node.color == BLACK;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-16\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Ein roter Geschwisterknoten (Fall 2) wird <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L289\" target=\"_blank\" rel=\"noopener\">ab Zeile 289<\/a> behandelt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-17\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">handleRedSibling<\/span><span class=\"hljs-params\">(Node node, Node sibling)<\/span> <\/span>{\n  <span class=\"hljs-comment\">\/\/ Recolor...<\/span>\n  sibling.color = BLACK;\n  node.parent.color = RED;\n\n  <span class=\"hljs-comment\">\/\/ ... and rotate<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (node == node.parent.left) {\n    rotateLeft(node.parent);\n  } <span class=\"hljs-keyword\">else<\/span> {\n    rotateRight(node.parent);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-17\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Die Implementierung f\u00fcr einen schwarzen Geschwisterknoten mit wenigstens einem roten Kind (F\u00e4lle 5 und 6) findest du <a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java#L302\" target=\"_blank\" rel=\"noopener\">ab Zeile 302<\/a>:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-18\" data-shcb-language-name=\"Java\" data-shcb-language-slug=\"java\"><span><code class=\"hljs language-java\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">private<\/span> <span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">handleBlackSiblingWithAtLeastOneRedChild<\/span><span class=\"hljs-params\">(Node node, Node sibling)<\/span> <\/span>{\n  <span class=\"hljs-keyword\">boolean<\/span> nodeIsLeftChild = node == node.parent.left;\n\n  <span class=\"hljs-comment\">\/\/ Case 5: Black sibling with at least one red child + \"outer nephew\" is black<\/span>\n  <span class=\"hljs-comment\">\/\/ --&gt; Recolor sibling and its child, and rotate around sibling<\/span>\n  <span class=\"hljs-keyword\">if<\/span> (nodeIsLeftChild &amp;&amp; isBlack(sibling.right)) {\n    sibling.left.color = BLACK;\n    sibling.color = RED;\n    rotateRight(sibling);\n    sibling = node.parent.right;\n  } <span class=\"hljs-keyword\">else<\/span> <span class=\"hljs-keyword\">if<\/span> (!nodeIsLeftChild &amp;&amp; isBlack(sibling.left)) {\n    sibling.right.color = BLACK;\n    sibling.color = RED;\n    rotateLeft(sibling);\n    sibling = node.parent.left;\n  }\n\n  <span class=\"hljs-comment\">\/\/ Fall-through to case 6...<\/span>\n\n  <span class=\"hljs-comment\">\/\/ Case 6: Black sibling with at least one red child + \"outer nephew\" is red<\/span>\n  <span class=\"hljs-comment\">\/\/ --&gt; Recolor sibling + parent + sibling's child, and rotate around parent<\/span>\n  sibling.color = node.parent.color;\n  node.parent.color = BLACK;\n  <span class=\"hljs-keyword\">if<\/span> (nodeIsLeftChild) {\n    sibling.right.color = BLACK;\n    rotateLeft(node.parent);\n  } <span class=\"hljs-keyword\">else<\/span> {\n    sibling.left.color = BLACK;\n    rotateRight(node.parent);\n  }\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-18\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">Java<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">java<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<p>Genau wie f\u00fcr das Einf\u00fcgen, wirst du auch f\u00fcr das L\u00f6schen in der Literatur zahlreiche alternative Vorgehensweisen finden. Ich habe mich bem\u00fcht den Code so zu strukturieren, dass du den Codefluss so gut wie m\u00f6glich nachvollziehen kannst.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"traversierung-durch-den-rot-schwarz-baum\">Traversierung durch den Rot-Schwarz-Baum<\/h3>\n\n\n\n<p>Wie jeden Bin\u00e4rbaum k\u00f6nnen wir auch den Rot-Schwarz-Baum in Pre-order-, Post-order-, In-order-, Reverse-in-order- und Level-order-Reihenfolge traversieren. Die Traversierung wird im&nbsp;<a href=\"https:\/\/www.happycoders.eu\/de\/algorithmen\/binaerbaum-java\/#Binarbaum-Traversierung\">Abschnitt \"Bin\u00e4rbaum-Traversierung\"<\/a> des Einf\u00fchrungsartikels \u00fcber Bin\u00e4rb\u00e4ume beschrieben. <\/p>\n\n\n\n<p>Dort findest du auch den entsprechenden Java-Quellcode, implementiert in den Klassen <code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversal.java\" target=\"_blank\">DepthFirstTraversal<\/a><\/code>,&nbsp;<code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalIterative.java\" target=\"_blank\">DepthFirstTraversalIterative<\/a><\/code>&nbsp;und&nbsp;<code><a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/DepthFirstTraversalRecursive.java\" target=\"_blank\">DepthFirstTraversalRecursive<\/a><\/code>.<\/p>\n\n\n\n<p>Die Traversal-Methoden arbeiten auf dem <a rel=\"noopener\" href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/BinaryTree.java\" target=\"_blank\"><code>BinaryTree<\/code><\/a>-Interface. Da auch der <code><a href=\"https:\/\/github.com\/SvenWoltmann\/binary-tree\/blob\/main\/src\/main\/java\/eu\/happycoders\/binarytree\/RedBlackTree.java\" target=\"_blank\" rel=\"noopener\">RedBlackTree<\/a><\/code> dieses Interface implementiert, k\u00f6nnen die Traversierungsmethoden ohne weiteres auch auf diesen angewendet werden.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"zeitkomplexitaet-des-rot-schwarz-baums\">Zeitkomplexit\u00e4t des Rot-Schwarz-Baums<\/h2>\n\n\n\n<p>Eine Einf\u00fchrung in das Thema der Zeitkomplexit\u00e4t und der O-Notation findest du in diesem <a href=\"\/de\/algorithmen\/o-notation-zeitkomplexitaet\/\">Grundlagenartikel<\/a>.<\/p>\n\n\n<div class=\"convertkit-form wp-block-convertkit-form\" style=\"\"><script async data-uid=\"5c918c0177\" src=\"https:\/\/happycoders.kit.com\/5c918c0177\/index.js\" data-jetpack-boost=\"ignore\" data-no-defer=\"1\" data-no-optimize=\"1\" nowprocket><\/script><\/div>\n\n\n\n<p>Den Aufwand f\u00fcr die Suche, das Einf\u00fcgen und L\u00f6schen eines Knotens im Bin\u00e4rbaum k\u00f6nnen wir wie folgt bestimmen:<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"aufwand-fuer-die-suche\">Aufwand f\u00fcr die Suche<\/h3>\n\n\n\n<p>Bei der Suche folgen wir einem Pfad von der Wurzel bis zum gesuchten Knoten (oder zu einem NIL-Blatt). Auf jeder Ebene f\u00fchren wir einen Vergleich durch. Der Aufwand f\u00fcr den Vergleich ist konstant.<\/p>\n\n\n\n<p>Der Aufwand f\u00fcr die Suche ist damit propertional zur Baumh\u00f6he.<\/p>\n\n\n\n<p>Wir bezeichnen mit <em>n<\/em> die Anzahl der Knoten des Baums. Wir haben im Abschnitt <a href=\"#Hohe_des_Rot-Schwarz-Baums\">\"H\u00f6he des Rot-Schwarz-Baumes\"<\/a> erkannt, dass der l\u00e4ngste Pfad maximal doppelt so lang ist wie der k\u00fcrzeste Pfad. Hieraus folgt, dass die H\u00f6he des Baumes durch <em>O(log n)<\/em> begrenzt ist.<\/p>\n\n\n\n<p>Der formale Beweis daf\u00fcr w\u00fcrde den Rahmen dieses Artikels sprengen. Du kannst den Beweis auf <a rel=\"noopener\" href=\"https:\/\/de.wikipedia.org\/wiki\/Rot-Schwarz-Baum#H%C3%B6henbeweis\" target=\"_blank\">Wikipedia<\/a> nachlesen.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t f\u00fcr die Suche im Rot-Schwarz-Baum betr\u00e4gt somit: <em>O(log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"aufwand-fuer-das-einfuegen\">Aufwand f\u00fcr das Einf\u00fcgen<\/h3>\n\n\n\n<p>Beim Einf\u00fcgen f\u00fchren wir zun\u00e4chst eine Suche durch. Derem Aufwand haben wir soeben als <em>O(log n)<\/em> bestimmt.<\/p>\n\n\n\n<p>Als n\u00e4chstes f\u00fcgen wir einen Knoten ein. Der Aufwand hierf\u00fcr ist unabh\u00e4ngig von der Baumgr\u00f6\u00dfe konstant, also <em>O(1)<\/em>.<\/p>\n\n\n\n<p>Danach \u00fcberpr\u00fcfen wir die Rot-Schwarz-Regeln und stellen diese ggf. wieder her. Dies tun wir beginnend beim eingef\u00fcgten Knoten aufsteigend bis zur Wurzel. Auf jeder Ebene f\u00fchren wir eine oder mehrere der folgenden Operationen durch:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Pr\u00fcfung der Farbe des Elternknotens<\/li>\n\n\n\n<li>Bestimmung des Onkelknotens und Pr\u00fcfung dessen Farbe<\/li>\n\n\n\n<li>Umf\u00e4rbung von ein bis maximal drei Knoten<\/li>\n\n\n\n<li>Durchf\u00fchrung von ein oder zwei Rotationen<\/li>\n<\/ul>\n\n\n\n<p>Jede dieser Operationen hat in sich einen konstanten Aufwand <em>O(1)<\/em>. Der Gesamtaufwand f\u00fcr das \u00dcberpr\u00fcfen und die Reparatur des Baumes ist in Summe also ebenfalls proportional zu dessen H\u00f6he.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t f\u00fcr das Einf\u00fcgen in den Rot-Schwarz-Baum betr\u00e4gt also ebenfalls: <em>O(log n)<\/em><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"aufwand-fuer-das-loeschen\">Aufwand f\u00fcr das L\u00f6schen<\/h3>\n\n\n\n<p>Genau wie beim Einf\u00fcgen suchen wir zun\u00e4chst den zu l\u00f6schenden Knoten mit Aufwand <em>O(log n)<\/em>.<\/p>\n\n\n\n<p>Auch der Aufwand f\u00fcr das L\u00f6schen an sich ist unabh\u00e4ngig von der Baumgr\u00f6\u00dfe, also konstant <em>O(1)<\/em>.<\/p>\n\n\n\n<p>F\u00fcr das Pr\u00fcfen der Regeln und die Reparatur des Baumes fallen \u2013 maximal einmal pro Ebene \u2013 eine oder mehrere der folgenden Operationen an:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Pr\u00fcfung der Farbe des gel\u00f6schten Knotens<\/li>\n\n\n\n<li>Bestimmung des Geschwisterknotens und Pr\u00fcfung dessen Farbe<\/li>\n\n\n\n<li>Pr\u00fcfung der Farben der Kinder des Geschwisterknotens <\/li>\n\n\n\n<li>Umf\u00e4rben des Elternknoten<\/li>\n\n\n\n<li>Umf\u00e4rben von Geschwisterknoten und ggf. einem seiner Kinder<\/li>\n\n\n\n<li>Durchf\u00fchrung von ein oder zwei Rotationen<\/li>\n<\/ul>\n\n\n\n<p>Auch diese Operationen haben in sich alle einen konstanten Aufwand. Somit ist also auch der Gesamtaufwand f\u00fcr das Pr\u00fcfen und Wiederherstellen der Regeln nach dem L\u00f6schen eines Knotens proportional zur Baumh\u00f6he.<\/p>\n\n\n\n<p>Die Zeitkomplexit\u00e4t f\u00fcr das L\u00f6schen aus dem Rot-Schwarz-Baum betr\u00e4gt also ebenfalls: <em>O(log n)<\/em><\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rot-schwarz-baum-im-vergleich-mit-anderen-datenstrukturen\">Rot-Schwarz-Baum im Vergleich mit anderen Datenstrukturen<\/h2>\n\n\n\n<p>Die folgenden Abschnitte beschreiben die Unterschiede, sowie die Vor- und Nachteile des Rot-Schwarz-Baumes gegen\u00fcber alternativen Datenstrukturen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rot-schwarz-baum-vs-avl-baum\">Rot-Schwarz-Baum vs. AVL-Baum<\/h3>\n\n\n\n<p>Der Rot-Schwarz-Baum sowie der <a href=\"\/de\/algorithmen\/avl-baum-java\/\">AVL-Baum<\/a> sind selbstbalancierende bin\u00e4re Suchb\u00e4ume.<\/p>\n\n\n\n<p>Beim Rot-Schwarz-Baum ist der l\u00e4ngste Pfad zur Wurzel maximal doppelt so lang wie der k\u00fcrzeste Pfad zur Wurzel. Beim AVL-Baum hingegen unterscheidet sich die Tiefe keiner zwei Teilb\u00e4ume um mehr als 1.<\/p>\n\n\n\n<p>Im Rot-Schwarz-Baum wird die Balance durch die Farben der Knoten, ein Set von Regeln, und durch Rotationen und Umf\u00e4rben der Knoten sichergestellt. Im AVL-Baum hingegen werden die H\u00f6hen der Teilb\u00e4ume verglichen und bei Bedarf Rotationen durchgef\u00fchrt.<\/p>\n\n\n\n<p>Diese Unterschiede in den Eigenschaften der zwei Baumarten f\u00fcnren zu folgenden Unterschieden bzgl. Performance und Speicherbedarf: <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Aufgrund der gleichm\u00e4\u00dfigeren Balancierung des AVL-Baums erfolgt die Suche in diesem in der Regel schneller als im Rot-Schwarz-Baum. Von der Gr\u00f6\u00dfenordnung her liegen aber beide im Bereich <em>O(log n)<\/em>.<\/li>\n\n\n\n<li>Auch f\u00fcr das Einf\u00fcgen und L\u00f6schen betr\u00e4gt die Zeitkomplexit\u00e4t in beiden B\u00e4umen <em>O(log n)<\/em>. Im direkten Vergleich ist allerdings der Rot-Schwarz-Baum schneller, da dieser seltener rebalanciert wird.<\/li>\n\n\n\n<li>Beide B\u00e4ume ben\u00f6tigen zus\u00e4tzlichen Speicher: der AVL-Baum ein Byte pro Knoten f\u00fcr die H\u00f6he des an einem Knoten beginnenden Teilbaums; der Rot-Schwarz-Baum ein Bit pro Knoten f\u00fcr die Farbinformation. In der Praxis macht dies selten einen Unterschied, da ein einzelnes Bit in der Regel mindestens ein Byte belegt.<\/li>\n<\/ul>\n\n\n\n<p>Erwartet man viele Einf\u00fcge-\/L\u00f6schoperationen, dann sollte man also eher einen Rot-Schwarz-Baum einsetzen. Geht man dagegen von mehr Suchoperationen aus, dann sollte die Wahl auf den AVL-Baum fallen.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"rot-schwarz-baum-vs-binaerer-suchbaum\">Rot-Schwarz-Baum vs. Bin\u00e4rer Suchbaum<\/h3>\n\n\n\n<p>Der Rot-Schwarz-Baum ist eine konkrete Implementierung eines selbstbalancierenden bin\u00e4ren Suchbaums. Jeder Rot-Schwarz-Baum ist also auch ein bin\u00e4rer Suchbaum.<\/p>\n\n\n\n<p>Es gibt auch andere Arten von bin\u00e4ren Suchb\u00e4umen, wie z. B. den oben genannten AVL-Baum \u2013 oder triviale nicht-balancierte Implementierungen. Somit ist also nicht jeder bin\u00e4re Suchbaum auch ein Rot-Schwarz-Baum.  <\/p>\n\n\n\n<h2 class=\"wp-block-heading\" class=\"wp-block-heading\" id=\"fazit\">Fazit<\/h2>\n\n\n\n<p>In diesem Tutorial hast du gelernt, was ein Rot-Schwarz-Baum ist, welche Regeln in ihm gelten und wie diese Regeln nach dem Einf\u00fcgen und L\u00f6schen von Knoten \u00fcberpr\u00fcft und ggf. wiederhergestellt werden. Au\u00dferdem habe ich dir eine m\u00f6glichst einfach zu verstehende Java-Implementierung vorgestellt.<\/p>\n\n\n\n<p>Im JDK werden Rot-Schwarz-B\u00e4ume in der <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/17\/docs\/api\/java.base\/java\/util\/TreeMap.html\" target=\"_blank\">TreeMap<\/a> (hier der <a rel=\"noopener\" href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/TreeMap.java\" target=\"_blank\">Quellcode<\/a> auf GitHub) und bei Bucket Collisions in der <a rel=\"noopener\" href=\"https:\/\/docs.oracle.com\/en\/java\/javase\/17\/docs\/api\/java.base\/java\/util\/HashMap.html\" target=\"_blank\">HashMap<\/a> (hier der <a rel=\"noopener\" href=\"https:\/\/github.com\/openjdk\/jdk\/blob\/master\/src\/java.base\/share\/classes\/java\/util\/HashMap.java#L1932\" target=\"_blank\">Quellcode<\/a>) eingesetzt.<\/p>\n\n\n\n<p>Damit endet die Tutorial-Serie \u00fcber Bin\u00e4rb\u00e4ume.<\/p>\n\n\n\n<p>Wenn ich dir helfen konnte <a href=\"\/de\/algorithmen\/binaerbaum-java\/\">Bin\u00e4rb\u00e4ume im Allgemeinen<\/a>, <a href=\"\/de\/algorithmen\/binaerer-suchbaum-java\/\">bin\u00e4re Suchb\u00e4ume<\/a>, <a href=\"\/de\/algorithmen\/avl-baum-java\/\">AVL-B\u00e4ume<\/a> und \u2013 in diesem Artikel \u2013 Rot-Schwarz-B\u00e4ume besser zu verstehen, freue ich mich \u00fcber einen Kommentar.<\/p>\n<aside><p>Wenn dir der Artikel weitergeholfen hat, w\u00fcrde ich mich sehr \u00fcber eine positive Bewertung auf meinem <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">ProvenExpert-Profil<\/a> freuen. Dein Feedback hilft mir, meine Inhalte weiter zu verbessern und motiviert mich, neue informative Artikel zu schreiben.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"https:\/\/www.provenexpert.com\/de-de\/sven-woltmann-happycoders-eu\/7smk\/\" target=\"_blank\" rel=\"noopener\">Bewertung abgeben<\/a><\/p>\r\n                        <p>M\u00f6chtest du auf dem Laufenden bleiben und informiert werden, wenn neue Artikel auf HappyCoders.eu ver\u00f6ffentlicht werden? Dann <a href=\"#\" data-formkit-toggle=\"d8ee997126\">klicke hier<\/a>, um dich f\u00fcr den HappyCoders-Newsletter anzumelden.<\/p>\r\n                        <p>\ud83d\udc49 <a href=\"#\" data-formkit-toggle=\"d8ee997126\">Newsletter-Anmeldung<\/a><\/p><\/aside>","protected":false},"excerpt":{"rendered":"<p>Was ist ein Rot-Schwarz-Baum? Wie werden Knoten eingef\u00fcgt, gesucht und gel\u00f6scht? Nach welchen Regeln wird er balanciert? Wie implementiert man einen Rot-Schwarz-Baum in Java? Und wie bestimmt man seine Zeitkomplexit\u00e4t?<\/p>\n","protected":false},"author":1,"featured_media":30734,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_seopress_robots_primary_cat":"none","_seopress_titles_title":"","_seopress_titles_desc":"Was ist ein Rot-Schwarz-Baum? Nach welchen Regeln wird er balanciert? Wie bestimmt man die Zeitkomplexit\u00e4t? Wie implementiert man ihn?","_seopress_robots_index":"","_uag_custom_page_level_css":"","_wp_convertkit_post_meta":{"form":"-1","landing_page":"","tag":"0","restrict_content":"0"},"_metis_text_type":"standard","_metis_text_length":50768,"_post_count":0,"footnotes":""},"categories":[127],"tags":[174],"class_list":["post-22336","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmen","tag-datenstrukturen-baeume"],"uagb_featured_image_src":{"full":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",1770,986,false],"thumbnail":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",150,84,false],"medium":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",300,167,false],"medium_large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",768,428,false],"large":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",1024,570,false],"feature_thumb_224":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-224x125.jpg",224,125,true],"feature_thumb_336":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-336x187.jpg",336,187,true],"feature_thumb_504":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-504x281.jpg",504,281,true],"feature_thumb_672":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-672x374.jpg",672,374,true],"half_400":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-400x223.jpg",400,223,true],"half_600":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-600x334.jpg",600,334,true],"full_800":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-800x446.jpg",800,446,true],"full_944":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-944x526.jpg",944,526,true],"full_1200":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-1200x668.jpg",1200,668,true],"wide_1180":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-1180x490.jpg",1180,490,true],"wide_1770":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1-1770x735.jpg",1770,735,true],"1536x1536":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",1536,856,false],"2048x2048":["https:\/\/www.happycoders.eu\/wp-content\/uploads\/2021\/09\/red-black-tree-1770x986-1.jpg",1770,986,false]},"uagb_author_info":{"display_name":"Sven Woltmann","author_link":"https:\/\/www.happycoders.eu\/de\/author\/sven\/"},"uagb_comment_info":0,"uagb_excerpt":"Was ist ein Rot-Schwarz-Baum? Wie werden Knoten eingef\u00fcgt, gesucht und gel\u00f6scht? Nach welchen Regeln wird er balanciert? Wie implementiert man einen Rot-Schwarz-Baum in Java? Und wie bestimmt man seine Zeitkomplexit\u00e4t?","public_identification_id":"6156662ebbc345a7bec9af35b95e6ca5","private_identification_id":"e3635ed75f1541e8b2bf5ad317ef91e1","_links":{"self":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/comments?post=22336"}],"version-history":[{"count":10,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22336\/revisions"}],"predecessor-version":[{"id":52488,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/posts\/22336\/revisions\/52488"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media\/30734"}],"wp:attachment":[{"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/media?parent=22336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/categories?post=22336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.happycoders.eu\/de\/wp-json\/wp\/v2\/tags?post=22336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}