Ein rot -schwarzer Baum ist ein binär ausgewogener Suchbaum. Jeder Knoten hat ein Speicherbit, um die Farbe des Knotens darzustellen, der rot oder schwarz sein kann.
Rote und schwarze Bäume haben die folgenden Eigenschaften:
(1) Jeder Knoten ist rot oder schwarz
(2) Der Wurzelknoten ist schwarz
(3) Wenn ein Knoten rot ist, sind seine beiden Söhne schwarz
(4) Für jeden Knoten enthalten alle Pfade von diesem Knoten zu seinen Nachkommen die gleiche Anzahl schwarzer Knoten.
Durch die Eigenschaften des rot-schwarzen Baums ist es garantiert, dass alle rotschwarzen baumbasierten Implementierungen sicherstellen können, dass die Betriebslaufzeit logarithmisch ist (mit Ausnahme der Suchabschnitt. Die zusätzliche Zeit, die sie benötigt, ist proportional zur Anzahl der zurückgegebenen Schlüssel).
Javas Treemap wird durch rote und schwarze Bäume implementiert.
Wenn Sie kein Bild zeichnen, ist es einfach, verwirrt zu werden. Das Folgende ist ein Diagramm, das den Einfügungsbetrieb des roten und schwarzen Baumes veranschaulicht.
Nach dem Einfügen eines roten Knotens in den roten und schwarzen Baum wird 6 Situationen vorhanden: N repräsentiert den eingefügten Knoten, P repräsentiert den übergeordneten Knoten, U repräsentiert den Onkelknoten, g den Grandfather -Knoten und X repräsentiert den aktuellen Operationknoten.
Der Code ist wie folgt:
Public Class RedBlackBst <Key erweitert vergleichbar <schlüssel>, value> {private Knotenwurzel; private statische endgültige boolean rot = true; Private statische endgültige boolean schwarz = false; private Klasse Node {privater Schlüsselschlüssel; // privates Key -Wert Val; // Wert privater Knoten links, rechts, Eltern; // links und links Kinderbäume und Elternknoten privat boolesche Farbe; // Die Farbe des Links, auf den der öffentliche Knoten des übergeordneten Knotens (Schlüsselschlüssel, Value Val, Knoten übergeordnet ist, boolesche Farbe) {this.key = key; this.val = val; this.color = color; }} öffentlicher Wert get (Schlüsselschlüssel) {Knoten x = root; while (x! = null) {int cmp = key.comPareto (X.Key); if (cmp <0) x = x.left; sonst if (cmp> 0) x = x.Right; sonst geben Sie X.Val zurück; } return null; } public void put (Schlüsselschlüssel, Value val) {if (root == null) {// Wenn es sich um einen Root -Knoten handelt, erstellen Sie den Knoten als Black root = neuer Knoten (Schlüssel, Val, Null, Schwarz); zurückkehren; } // einen geeigneten Insertionspositionsknoten -Knoten übergeordnet = null; Node cur = root; while (cur! = null) {parent = cur; if (key.comPareto (cur.key)> 0) cur = cur.right; sonst cur = cur.left; } Knoten n = neuer Knoten (Schlüssel, val, übergeordnet, rot); // ord normaler neuer Knoten ist rot // Fügen Sie den neuen Knoten unter übergeordnet ein. sonst parent.left = n; // Nach dem Einsetzen eines neuen Knotens müssen Sie die Farben und Eigenschaften einiger Knoten im Baum anpassen, um sicherzustellen, dass die Merkmale des roten und schwarzen Baumes nicht zerstört werden. FixAfterInsertion (n); } private Knoten parentOf (Knoten x) {return (x == null? null: x.parent); } private boolean colorof (Knoten x) {return (x == null? null: x.Right); } privater Knoten links (Knoten x) {return (x == null? null: x.Right); } privater Knoten rechter (Knoten x) {return (x == null? null: x.Right); } private void setColor (Knoten x, boolesche Farbe) {if (x! = null) x.color = color; } private void fixAfFterInsertion (Knoten x) {while (x! Node Parent = parentof (x); if (parent == linksof (Opa)) {// Fall 1 || Case2 || Case3 Node Onkel = rightof (Opa); if (colorof (Onkel) == rot) {// case1, Onkel ist rotes SetColor (Elternteil, schwarz); // Der übergeordnete Knoten ist schwarzer SetColor (Onkel, schwarz); // Der Onkelknoten ist schwarzer SetColor (Opa, rot); // Der Großvaterknoten ist rot x = Opa; // Da der Großvaterknoten von schwarz bis rot rot ist, müssen die roten und schwarzen Attribute des übergeordneten Knotens und seiner Vorfahren neu eingestellt werden} else {// case2 || Case3, Onkel ist schwarz, wenn (x == rightof (übergeordnet)) {// case2 x = Eltern; rotateleft (x); } // case3 setColor (übergeordnet, schwarz); setColor (Opa, rot); Rotheright (Opa); }} else {// case4 || Fall 5 || Case6 -Knoten Onkel = linksof (Opa); if (colorof (Onkel) == rot) {// case4 || Fall 5 || Case6 setColor (Elternteil, schwarz); setColor (Onkel, schwarz); setColor (Opa, rot); x = Opa; } else {// case5 || Case6, Onkel ist schwarz, wenn (x == links von (übergeordnet)) {// Fall 5 x = Eltern; Rotheright (x); } // Case6 setColor (übergeordnet, schwarz); setColor (Opa, rot); Rotateleft (Opa); }}}} private void rotateleft (Knoten x) {if (x == null) return; Knoten y = x.Right; X.Right = Y.Left; if (y.left! = null) y.left.parent = x; y.left = x; y.Parent = x.Parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; } private void rotieright (Knoten x) {if (x == null) return; Knoten y = x.left; X.Left = Y.Right; if (y.right! = null) y.right.Parent = x; y.right = x; y.Parent = x.Parent; if (x.parent == null) {root = y; } else if (x.parent.left == x) {x.parent.left = y; } else {x.parent.right = y; } x.parent = y; }}Es ist notwendig, ein Diagramm für den oben Rotateleft und Rotheright zu zeichnen:
Der obige Artikel basiert auf dem Prinzip der rot -schwarzen Baumeinfügungsoperation und der Java -Implementierungsmethode (Sharing), die der gesamte Inhalt ist, den ich mit Ihnen teile. Ich hoffe, Sie können Ihnen eine Referenz geben und ich hoffe, Sie können wulin.com mehr unterstützen.