Roter schwarzer Baum in C++
Sheeraz Gul
15 Februar 2024
Dieses Tutorial demonstriert den Rot-Schwarz-Baum in C++.
Roter schwarzer Baum in C++
Der Rot-Schwarz-Baum wird als selbstausgleichender binärer Suchbaum betrachtet, der verwendet wird, wenn jeder Knoten eine eindeutige Eigenschaft enthält, die die Farbe des Knotens angibt. Rot-Schwarz hat die folgenden fünf Eigenschaften.
Rot/Schwarz-Eigenschaft – Jeder Knoten im Baum ist farbig, entweder rot oder schwarz.Root-Eigenschaft – Die Wurzel ist immer schwarz.- Eigenschaft
Blatt- Jedes Blatt (NIL) ist immer schwarz. Rot-Eigenschaft – Alle roten untergeordneten Knoten müssen schwarz sein, wenn sie einen haben.Tiefen-Eigenschaft – Jeder Pfad von einem Knoten zu einem anderen Nachkommenblatt hat die gleiche schwarze Tiefenmittelung wie die Anzahl der schwarzen Knoten.
Wenn die oben genannten Bedingungen nirgendwo zutreffen, dann kann dieser Baum kein Rot-Schwarz-Baum sein. Siehe die Struktur des rot-schwarzen Baums in der folgenden Abbildung.
Wie wir sehen können, hat jeder Knoten außer dem Wurzelknoten eine Farbe, einen Schlüssel, ein linkes Kind, ein rechtes Kind und ein Elternteil.
Aufgrund der oben genannten Eigenschaften soll der rot-schwarze Baum der selbstausgleichende Baum sein, da die Begrenzung der Farbe der Knoten sicherstellt, dass jeder Pfad von der Wurzel zu einem Lead nicht länger als zweimal lang ist, was dem Baum hilft, ihn zu halten selbst ausgleichen.
Rotation von Teilbäumen in einem Rot-Schwarz-Baum
Bei der Rotation werden die Positionen der Knoten von Teilbäumen vertauscht, was dazu verwendet wird, die Eigenschaften von Rot-Schwarz-Bäumen beizubehalten, da sie von anderen Operationen wie Einfügen und Löschen beeinflusst werden. Die Rotationsarten sind:
Linksrotation- Bei dieser Rotationsart wird die Anordnung der Knoten rechts in die Anordnung am linken Knoten transformiert.Rechtsrotation- Bei dieser Rotationsart wird die Anordnung der Knoten links in die Anordnung am rechten Knoten transformiert.Left-Right Rotate- Bei dieser Rotationsart wird die Anordnung zuerst nach links und dann nach rechts verschoben.Rechts-Links-Rotation- Bei dieser Rotationsart wird die Anordnung zuerst nach rechts und dann nach links verschoben.Recolor- Beim Recolor kehren wir die Farbe des Knotens um; Wenn beispielsweise ein Knoten rot ist, wird er schwarz oder umgekehrt.
Einfügen
Führen Sie die folgenden Schritte aus, um einen Knoten in den rot-schwarzen Baum einzufügen.
- Fügen Sie den Knoten mit der normalen BST-Operation ein.
- Färben Sie den eingefügten Knoten rot.
- Überprüfen Sie schließlich, ob die Einfügung die Eigenschaften des rot-schwarzen Baums verletzt hat; Wenn ja, müssen wir es reparieren.
Hier ist der Pseudo-Code zum Einfügen in den Rot-Schwarz-Baum.
RB - INSERT(Tree, n) BST -
INSERT(Tree, n) // ordinary BST insertion
while n.parent.color
== RED if n.parent == n.parent.parent.right u =
n.parent.parent
.left // uncle
if u.color
== RED u.color = BLACK n.parent.color = BLACK n.parent.parent.color =
RED n = n.parent.parent else if n == n.parent.left n =
n.parent LEFT -
ROTATE(Tree,
n) n.parent.color = BLACK n.parent.parent.color =
RED RIGHT -
ROTATE(Tree, n.parent.parent) else(
same with "left" and
"right" exchanged) Tree.root.color = BLACK
Streichung
Der Löschvorgang ist etwas kniffliger als das Einfügen; Um einen Knoten zu löschen, müssen wir auch zuerst der BST-Löschung folgen, wodurch sichergestellt wird, dass der Knoten entweder ein einzelnes Kind oder ein Blattknoten ist.
Der folgende Pseudo-Code zeigt die Löschoperation im rot-schwarzen Baum.
RB-DELETE(Tree, n)
BST-DELETE(Tree, n)
while n ≠ Tree.root and n.color == BLACK
if n == n.parent.left
s = n.parent.right
if s.color == RED
s.color = BLACK
n.parent.color = RED
LEFT-ROTATE(Tree, n.parent)
s = n.parent.right
if s.left.color == BLACK and s.right.color == BLACK
s.color = RED
n = n.parent
else if s.right.color == BLACK
s.left.color = BLACK
s.color = RED
RIGHT-ROTATE(Tree, s)
s = n.parent.right
s.color = n.parent.right
n.parent.color = BLACK
s.right.color = BLACK
LEFT-ROTATE(Tree, n.parent)
n = Tree.root
else (same as with "right" and "left" exchanged)
n.color = BLACK
Da wir Rotation, Einfügung und Löschung eines rot-schwarzen Baums verstehen, wollen wir versuchen, ihn in C++ zu implementieren.
#include <iostream>
using namespace std;
struct Node {
int NodeData;
Node *parentNode;
Node *leftNode;
Node *rightNode;
int NodeColor;
};
typedef Node *NodePtr;
class REDBLACKTREE {
private:
NodePtr root;
NodePtr TNULL;
void INITIALIZENULLNode(NodePtr node, NodePtr parentNode) {
node->NodeData = 0;
node->parentNode = parentNode;
node->leftNode = nullptr;
node->rightNode = nullptr;
node->NodeColor = 0;
}
// The Preorder
void PREORDERHELPER(NodePtr node) {
if (node != TNULL) {
cout << node->NodeData << " ";
PREORDERHELPER(node->leftNode);
PREORDERHELPER(node->rightNode);
}
}
// The Inorder
void INORDERHELPER(NodePtr node) {
if (node != TNULL) {
INORDERHELPER(node->leftNode);
cout << node->NodeData << " ";
INORDERHELPER(node->rightNode);
}
}
// the Post order
void POSTORDERHELPER(NodePtr node) {
if (node != TNULL) {
POSTORDERHELPER(node->leftNode);
POSTORDERHELPER(node->rightNode);
cout << node->NodeData << " ";
}
}
NodePtr SEARCHTREEHELPER(NodePtr node, int key) {
if (node == TNULL || key == node->NodeData) {
return node;
}
if (key < node->NodeData) {
return SEARCHTREEHELPER(node->leftNode, key);
}
return SEARCHTREEHELPER(node->rightNode, key);
}
// For balancing the tree after deletion
void DELETEFIX(NodePtr x) {
NodePtr s;
while (x != root && x->NodeColor == 0) {
if (x == x->parentNode->leftNode) {
s = x->parentNode->rightNode;
if (s->NodeColor == 1) {
s->NodeColor = 0;
x->parentNode->NodeColor = 1;
LEFTROTATE(x->parentNode);
s = x->parentNode->rightNode;
}
if (s->leftNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
s->NodeColor = 1;
x = x->parentNode;
} else {
if (s->rightNode->NodeColor == 0) {
s->leftNode->NodeColor = 0;
s->NodeColor = 1;
RIGHTNODEROTATE(s);
s = x->parentNode->rightNode;
}
s->NodeColor = x->parentNode->NodeColor;
x->parentNode->NodeColor = 0;
s->rightNode->NodeColor = 0;
LEFTROTATE(x->parentNode);
x = root;
}
} else {
s = x->parentNode->leftNode;
if (s->NodeColor == 1) {
s->NodeColor = 0;
x->parentNode->NodeColor = 1;
RIGHTNODEROTATE(x->parentNode);
s = x->parentNode->leftNode;
}
if (s->rightNode->NodeColor == 0 && s->rightNode->NodeColor == 0) {
s->NodeColor = 1;
x = x->parentNode;
} else {
if (s->leftNode->NodeColor == 0) {
s->rightNode->NodeColor = 0;
s->NodeColor = 1;
LEFTROTATE(s);
s = x->parentNode->leftNode;
}
s->NodeColor = x->parentNode->NodeColor;
x->parentNode->NodeColor = 0;
s->leftNode->NodeColor = 0;
RIGHTNODEROTATE(x->parentNode);
x = root;
}
}
}
x->NodeColor = 0;
}
void RBTRANSPLANT(NodePtr u, NodePtr v) {
if (u->parentNode == nullptr) {
root = v;
} else if (u == u->parentNode->leftNode) {
u->parentNode->leftNode = v;
} else {
u->parentNode->rightNode = v;
}
v->parentNode = u->parentNode;
}
void DELETENODEHELPER(NodePtr node, int key) {
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL) {
if (node->NodeData == key) {
z = node;
}
if (node->NodeData <= key) {
node = node->rightNode;
} else {
node = node->leftNode;
}
}
if (z == TNULL) {
cout << "The Key is not found in the tree" << endl;
return;
}
y = z;
int y_original_NodeColor = y->NodeColor;
if (z->leftNode == TNULL) {
x = z->rightNode;
RBTRANSPLANT(z, z->rightNode);
} else if (z->rightNode == TNULL) {
x = z->leftNode;
RBTRANSPLANT(z, z->leftNode);
} else {
y = minimum(z->rightNode);
y_original_NodeColor = y->NodeColor;
x = y->rightNode;
if (y->parentNode == z) {
x->parentNode = y;
} else {
RBTRANSPLANT(y, y->rightNode);
y->rightNode = z->rightNode;
y->rightNode->parentNode = y;
}
RBTRANSPLANT(z, y);
y->leftNode = z->leftNode;
y->leftNode->parentNode = y;
y->NodeColor = z->NodeColor;
}
delete z;
if (y_original_NodeColor == 0) {
DELETEFIX(x);
}
}
// balance the tree after insertion
void INSERTFIX(NodePtr k) {
NodePtr u;
while (k->parentNode->NodeColor == 1) {
if (k->parentNode == k->parentNode->parentNode->rightNode) {
u = k->parentNode->parentNode->leftNode;
if (u->NodeColor == 1) {
u->NodeColor = 0;
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
k = k->parentNode->parentNode;
} else {
if (k == k->parentNode->leftNode) {
k = k->parentNode;
RIGHTNODEROTATE(k);
}
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
LEFTROTATE(k->parentNode->parentNode);
}
} else {
u = k->parentNode->parentNode->rightNode;
if (u->NodeColor == 1) {
u->NodeColor = 0;
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
k = k->parentNode->parentNode;
} else {
if (k == k->parentNode->rightNode) {
k = k->parentNode;
LEFTROTATE(k);
}
k->parentNode->NodeColor = 0;
k->parentNode->parentNode->NodeColor = 1;
RIGHTNODEROTATE(k->parentNode->parentNode);
}
}
if (k == root) {
break;
}
}
root->NodeColor = 0;
}
void PRINTHELPER(NodePtr root, string indent, bool last) {
if (root != TNULL) {
cout << indent;
if (last) {
cout << "R-----";
indent += " ";
} else {
cout << "L-----";
indent += "| ";
}
string sNodeColor = root->NodeColor ? "RED" : "BLACK";
cout << root->NodeData << "(" << sNodeColor << ")" << endl;
PRINTHELPER(root->leftNode, indent, false);
PRINTHELPER(root->rightNode, indent, true);
}
}
public:
REDBLACKTREE() {
TNULL = new Node;
TNULL->NodeColor = 0;
TNULL->leftNode = nullptr;
TNULL->rightNode = nullptr;
root = TNULL;
}
void preorder() { PREORDERHELPER(this->root); }
void inorder() { INORDERHELPER(this->root); }
void postorder() { POSTORDERHELPER(this->root); }
NodePtr searchTree(int k) { return SEARCHTREEHELPER(this->root, k); }
NodePtr minimum(NodePtr node) {
while (node->leftNode != TNULL) {
node = node->leftNode;
}
return node;
}
NodePtr maximum(NodePtr node) {
while (node->rightNode != TNULL) {
node = node->rightNode;
}
return node;
}
NodePtr successor(NodePtr x) {
if (x->rightNode != TNULL) {
return minimum(x->rightNode);
}
NodePtr y = x->parentNode;
while (y != TNULL && x == y->rightNode) {
x = y;
y = y->parentNode;
}
return y;
}
NodePtr predecessor(NodePtr x) {
if (x->leftNode != TNULL) {
return maximum(x->leftNode);
}
NodePtr y = x->parentNode;
while (y != TNULL && x == y->leftNode) {
x = y;
y = y->parentNode;
}
return y;
}
void LEFTROTATE(NodePtr x) {
NodePtr y = x->rightNode;
x->rightNode = y->leftNode;
if (y->leftNode != TNULL) {
y->leftNode->parentNode = x;
}
y->parentNode = x->parentNode;
if (x->parentNode == nullptr) {
this->root = y;
} else if (x == x->parentNode->leftNode) {
x->parentNode->leftNode = y;
} else {
x->parentNode->rightNode = y;
}
y->leftNode = x;
x->parentNode = y;
}
void RIGHTNODEROTATE(NodePtr x) {
NodePtr y = x->leftNode;
x->leftNode = y->rightNode;
if (y->rightNode != TNULL) {
y->rightNode->parentNode = x;
}
y->parentNode = x->parentNode;
if (x->parentNode == nullptr) {
this->root = y;
} else if (x == x->parentNode->rightNode) {
x->parentNode->rightNode = y;
} else {
x->parentNode->leftNode = y;
}
y->rightNode = x;
x->parentNode = y;
}
// Inserting a node
void INSERTNODE(int key) {
NodePtr node = new Node;
node->parentNode = nullptr;
node->NodeData = key;
node->leftNode = TNULL;
node->rightNode = TNULL;
node->NodeColor = 1;
NodePtr y = nullptr;
NodePtr x = this->root;
while (x != TNULL) {
y = x;
if (node->NodeData < x->NodeData) {
x = x->leftNode;
} else {
x = x->rightNode;
}
}
node->parentNode = y;
if (y == nullptr) {
root = node;
} else if (node->NodeData < y->NodeData) {
y->leftNode = node;
} else {
y->rightNode = node;
}
if (node->parentNode == nullptr) {
node->NodeColor = 0;
return;
}
if (node->parentNode->parentNode == nullptr) {
return;
}
INSERTFIX(node);
}
NodePtr getRoot() { return this->root; }
void DELETENODE(int NodeData) { DELETENODEHELPER(this->root, NodeData); }
void printTree() {
if (root) {
PRINTHELPER(this->root, "", true);
}
}
};
int main() {
REDBLACKTREE DEMOBST;
DEMOBST.INSERTNODE(51);
DEMOBST.INSERTNODE(44);
DEMOBST.INSERTNODE(62);
DEMOBST.INSERTNODE(34);
DEMOBST.INSERTNODE(85);
DEMOBST.INSERTNODE(54);
DEMOBST.printTree();
cout << endl << "After deleting" << endl;
DEMOBST.DELETENODE(62);
DEMOBST.printTree();
}
Der obige Code erstellt einen rot-schwarzen Baum und wendet Einfüge-, Lösch- und Rotationsvorgänge an.
Ausgang:
R-----51(BLACK)
L-----44(BLACK)
| L-----34(RED)
R-----62(BLACK)
L-----54(RED)
R-----85(RED)
After deleting
R-----51(BLACK)
L-----44(BLACK)
| L-----34(RED)
R-----85(BLACK)
L-----54(RED)
Autor: Sheeraz Gul
Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.
LinkedIn Facebook