Red Black Tree Insertion
Written by
What is Red Black Tree ?
Insertion in Red Black Tree
Deletion in Red Black Tree
Red Black Tree Insertion
Insertion operation in a Red-black tree is quite similar to a standard binary tree insertion, it begins by adding a node at a time and by coloring it red.
The main difference that we can point out is that in a binary search tree, a new node is added as a leaf but in red-black tree leaf nodes don’t contain any info, so a new node replaces the existing leaf and then has two black leaves of its own added.
# Program to implement Red-Black Tree
#include <iostream>
using namespace std;
struct Node
{
int data;
Node * parent;
Node * left;
Node * right;
int color;
};
typedef Node * NodePtr;
class RedBlackTree
{
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent)
{
node - > data = 0;
node - > parent = parent;
node - > left = nullptr;
node - > right = nullptr;
node - > color = 0;
}
void preOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
cout << node - > data << " ";
preOrderTraversal(node - > left);
preOrderTraversal(node - > right);
}
}
void inOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
inOrderTraversal(node - > left);
cout << node - > data << " ";
inOrderTraversal(node - > right);
}
}
void postOrderTraversal(NodePtr node)
{
if (node != TNULL)
{
postOrderTraversal(node - > left);
postOrderTraversal(node - > right);
cout << node - > data << " ";
}
}
NodePtr searchTree(NodePtr node, int key)
{
if (node == TNULL || key == node - > data)
{
return node;
}
if (key < node - > data)
{
return searchTree(node - > left, key);
}
return searchTree(node - > right, key);
}
void rbTransplant(NodePtr u, NodePtr v)
{
if (u - > parent == nullptr)
{
root = v;
} else if (u == u - > parent - > left)
{
u - > parent - > left = v;
} else
{
u - > parent - > right = v;
}
v - > parent = u - > parent;
}
void insertFix(NodePtr k)
{
NodePtr u;
while (k - > parent - > color == 1)
{
if (k - > parent == k - > parent - > parent - > right)
{
u = k - > parent - > parent - > left;
if (u - > color == 1)
{
u - > color = 0;
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
k = k - > parent - > parent;
} else
{
if (k == k - > parent - > left)
{
k = k - > parent;
rightRotate(k);
}
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
leftRotate(k - > parent - > parent);
}
} else
{
u = k - > parent - > parent - > right;
if (u - > color == 1)
{
u - > color = 0;
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
k = k - > parent - > parent;
} else
{
if (k == k - > parent - > right)
{
k = k - > parent;
leftRotate(k);
}
k - > parent - > color = 0;
k - > parent - > parent - > color = 1;
rightRotate(k - > parent - > parent);
}
}
if (k == root)
{
break;
}
}
root - > color = 0;
}
void printTree(NodePtr root, string indent, bool last)
{
if (root != TNULL)
{
cout << indent;
if (last)
{
cout << "R----";
indent += " ";
} else
{
cout << "L----";
indent += "| ";
}
string sColor = root - > color ? "RED" : "BLACK";
cout << root - > data << "(" << sColor << ")" << endl;
printTree(root - > left, indent, false);
printTree(root - > right, indent, true);
}
}
public:
RedBlackTree()
{
TNULL = new Node;
TNULL - > color = 0;
TNULL - > left = nullptr;
TNULL - > right = nullptr;
root = TNULL;
}
void preorder()
{
preOrderTraversal(this - > root);
}
void inorder()
{
inOrderTraversal(this - > root);
}
void postorder()
{
postOrderTraversal(this - > root);
}
NodePtr searchTree(int k)
{
return searchTree(this - > root, k);
}
NodePtr minimum(NodePtr node)
{
while (node - > left != TNULL)
{
node = node - > left;
}
return node;
}
NodePtr maximum(NodePtr node)
{
while (node - > right != TNULL)
{
node = node - > right;
}
return node;
}
NodePtr successor(NodePtr x)
{
if (x - > right != TNULL)
{
return minimum(x - > right);
}
NodePtr y = x - > parent;
while (y != TNULL && x == y - > right)
{
x = y;
y = y - > parent;
}
return y;
}
NodePtr predecessor(NodePtr x)
{
if (x - > left != TNULL)
{
return maximum(x - > left);
}
NodePtr y = x - > parent;
while (y != TNULL && x == y - > left)
{
x = y;
y = y - > parent;
}
return y;
}
void leftRotate(NodePtr x)
{
NodePtr y = x - > right;
x - > right = y - > left;
if (y - > left != TNULL)
{
y - > left - > parent = x;
}
y - > parent = x - > parent;
if (x - > parent == nullptr)
{
this - > root = y;
} else if (x == x - > parent - > left)
{
x - > parent - > left = y;
} else
{
x - > parent - > right = y;
}
y - > left = x;
x - > parent = y;
}
void rightRotate(NodePtr x)
{
NodePtr y = x - > left;
x - > left = y - > right;
if (y - > right != TNULL)
{
y - > right - > parent = x;
}
y - > parent = x - > parent;
if (x - > parent == nullptr)
{
this - > root = y;
} else if (x == x - > parent - > right)
{
x - > parent - > right = y;
} else
{
x - > parent - > left = y;
}
y - > right = x;
x - > parent = y;
}
void insert(int key)
{
NodePtr node = new Node;
node - > parent = nullptr;
node - > data = key;
node - > left = TNULL;
node - > right = TNULL;
node - > color = 1;
NodePtr y = nullptr;
NodePtr x = this - > root;
while (x != TNULL)
{
y = x;
if (node - > data < x - > data)
{
x = x - > left;
} else
{
x = x - > right;
}
}
node - > parent = y;
if (y == nullptr)
{
root = node;
} else if (node - > data < y - > data)
{
y - > left = node;
} else
{
y - > right = node;
}
if (node - > parent == nullptr)
{
node - > color = 0;
return;
}
if (node - > parent - > parent == nullptr)
{
return;
}
insertFix(node);
}
NodePtr getRoot()
{
return this - > root;
}
void printTree()
{
if (root)
{
printTree(this - > root, "", true);
}
}
};
int main()
{
RedBlackTree bst;
bst.insert(55);
bst.insert(40);
bst.insert(65);
bst.insert(60);
bst.insert(75);
bst.insert(57);
bst.printTree();
}
