# Red Black Tree in C++

Sheeraz Gul Oct 12, 2023

This tutorial demonstrates the red-black tree in C++.

## Red Black Tree in C++

The red-black tree is considered a self-balancing binary search tree used where each node contains a distinct property denoting the node’s color. Red-Black has the following five properties.

1. `Red/Black` Property - Every node in the tree is colored, either red or black.
2. `Root` Property - The root is always black.
3. `Leaf` Property - Every leaf (`NIL`) is always black.
4. `Red` Property - All the red node children must be black if they have one.
5. `Depth` Property - Any path from one node to another descendant leaf will have the same black depth means as the number of black nodes.

If the above conditions don’t meet anywhere, then that tree cannot be a `red black tree`. See the structure of the red-black tree in the figure below. As we can see, each node has a `colour`, `key`, `left child`, `right child`, and a `parent` except the root node.

From the above properties, the red-black tree is meant to be the self-balancing tree because the limitation of the color of nodes ensures that any path from the root to a lead is not long more than twice, which helps the tree to keep balancing itself.

### Rotation of Sub Trees in a Red-Black Tree

In rotation, the positions of the nodes of subtrees are interchanged, which is used to maintain the properties of red-black trees as they are affected by other operations like insertion and deletion. The types of rotation are:

1. `Left Rotate` - In this type of rotation, the arrangement of nodes on the right is transformed into the arrangement on the left node.
2. `Right Rotate` - In this type of rotation, the arrangement of nodes on the left is transformed into the arrangement on the right node.
3. `Left-Right Rotate` - In this type of rotation, the arrangement will first be shifted to the left and then to the right.
4. `Right-Left Rotate` - In this type of rotation, the arrangement will first be shifted to the right and then to the left.
5. `Recolor` - In recolor, we flip the node’s color; for example, if a node is red, it becomes black or vice versa.

### Insertion

Follow the steps below to insert a node into the red-black tree.

1. Insert the node using the ordinary BST operation.
2. Colour the inserted node-red.
3. Finally, check if the insertion violated the red-black tree properties; if it did, we have to fix it.

Here is the pseudo-code for insertion in the red-black tree.

``````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
``````

### Deletion

The deletion operation is a bit trickier than insertion; to delete a node, we also have to follow the BST deletion first, which will ensure the node is either a single child or a leaf node.

The pseudo-code below shows the deletion operation in the red-black tree.

``````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
``````

As we understand a red-black tree’s rotation, insertion, and deletion, let’s try to implement it in C++.

``````#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();
}
``````

The code above will create a red-black tree and apply insertion, deletion and rotation operations.

Output:

``````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)
``````
Author: 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.