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