Red Black Tree Insertion

Written by

Sonal Moga

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 - &gt; data = 0;

node - &gt; parent = parent;

node - &gt; left = nullptr;

node - &gt; right = nullptr;

node - &gt; color = 0;

}

void preOrderTraversal(NodePtr node)

{

if (node != TNULL)

{

  cout &lt;&lt; node - &gt; data &lt;&lt; " ";

  preOrderTraversal(node - &gt; left);

  preOrderTraversal(node - &gt; right);

}

}

void inOrderTraversal(NodePtr node)

{

if (node != TNULL)

{

  inOrderTraversal(node - &gt; left);

  cout &lt;&lt; node - &gt; data &lt;&lt; " ";

  inOrderTraversal(node - &gt; right);

}

}

void postOrderTraversal(NodePtr node)

{

if (node != TNULL)

{

  postOrderTraversal(node - &gt; left);

  postOrderTraversal(node - &gt; right);

  cout &lt;&lt; node - &gt; data &lt;&lt; " ";

}

}

NodePtr searchTree(NodePtr node, int key)

{

if (node == TNULL || key == node - &gt; data)

{

  return node;

}

if (key &lt; node - &gt; data)

{

  return searchTree(node - &gt; left, key);

}

return searchTree(node - &gt; right, key);

}

void rbTransplant(NodePtr u, NodePtr v)

{

if (u - &gt; parent == nullptr)

{

  root = v;

} else if (u == u - &gt; parent - &gt; left)

{

  u - &gt; parent - &gt; left = v;

} else

{

  u - &gt; parent - &gt; right = v;

}

v - &gt; parent = u - &gt; parent;

}

void insertFix(NodePtr k)

{

NodePtr u;

while (k - &gt; parent - &gt; color == 1)

{

  if (k - &gt; parent == k - &gt; parent - &gt; parent - &gt; right)

  {

    u = k - &gt; parent - &gt; parent - &gt; left;

    if (u - &gt; color == 1)

    {

      u - &gt; color = 0;

      k - &gt; parent - &gt; color = 0;

      k - &gt; parent - &gt; parent - &gt; color = 1;

      k = k - &gt; parent - &gt; parent;

    } else

    {

      if (k == k - &gt; parent - &gt; left)

      {

        k = k - &gt; parent;

        rightRotate(k);

      }

      k - &gt; parent - &gt; color = 0;

      k - &gt; parent - &gt; parent - &gt; color = 1;

      leftRotate(k - &gt; parent - &gt; parent);

    }

  } else

  {

    u = k - &gt; parent - &gt; parent - &gt; right;

    if (u - &gt; color == 1)

    {

      u - &gt; color = 0;

      k - &gt; parent - &gt; color = 0;

      k - &gt; parent - &gt; parent - &gt; color = 1;

      k = k - &gt; parent - &gt; parent;

    } else

    {

      if (k == k - &gt; parent - &gt; right)

      {

        k = k - &gt; parent;

        leftRotate(k);

      }

      k - &gt; parent - &gt; color = 0;

      k - &gt; parent - &gt; parent - &gt; color = 1;

      rightRotate(k - &gt; parent - &gt; parent);

    }

  }

  if (k == root)

  {

    break;

  }

}

root - &gt; color = 0;

}

void printTree(NodePtr root, string indent, bool last)

{

if (root != TNULL)

{

  cout &lt;&lt; indent;

  if (last)

  {

    cout &lt;&lt; "R----";

    indent += "   ";

  } else

  {

    cout &lt;&lt; "L----";

    indent += "|  ";

  }

  string sColor = root - &gt; color ? "RED" : "BLACK";

  cout &lt;&lt; root - &gt; data &lt;&lt; "(" &lt;&lt; sColor &lt;&lt; ")" &lt;&lt; endl;

  printTree(root - &gt; left, indent, false);

  printTree(root - &gt; right, indent, true);

}

}

public:

RedBlackTree()

{

TNULL = new Node;

TNULL - &gt; color = 0;

TNULL - &gt; left = nullptr;

TNULL - &gt; right = nullptr;

root = TNULL;

}

void preorder()

{

preOrderTraversal(this - &gt; root);

}

void inorder()

{

inOrderTraversal(this - &gt; root);

}

void postorder()

{

postOrderTraversal(this - &gt; root);

}

NodePtr searchTree(int k)

{

return searchTree(this - &gt; root, k);

}

NodePtr minimum(NodePtr node)

{

while (node - &gt; left != TNULL)

{

  node = node - &gt; left;

}

return node;

}

NodePtr maximum(NodePtr node)

{

while (node - &gt; right != TNULL)

{

  node = node - &gt; right;

}

return node;

}

NodePtr successor(NodePtr x)

{

if (x - &gt; right != TNULL)

{

  return minimum(x - &gt; right);

}

NodePtr y = x - &gt; parent;

while (y != TNULL &amp;&amp; x == y - &gt; right)

{

  x = y;

  y = y - &gt; parent;

}

return y;

}

NodePtr predecessor(NodePtr x)

{

if (x - &gt; left != TNULL)

{

  return maximum(x - &gt; left);

}

NodePtr y = x - &gt; parent;

while (y != TNULL &amp;&amp; x == y - &gt; left)

{

  x = y;

  y = y - &gt; parent;

}

return y;

}

void leftRotate(NodePtr x)

{

NodePtr y = x - &gt; right;

x - &gt; right = y - &gt; left;

if (y - &gt; left != TNULL)

{

  y - &gt; left - &gt; parent = x;

}

y - &gt; parent = x - &gt; parent;

if (x - &gt; parent == nullptr)

{

  this - &gt; root = y;

} else if (x == x - &gt; parent - &gt; left)

{

  x - &gt; parent - &gt; left = y;

} else

{

  x - &gt; parent - &gt; right = y;

}

y - &gt; left = x;

x - &gt; parent = y;

}

void rightRotate(NodePtr x)

{

NodePtr y = x - &gt; left;

x - &gt; left = y - &gt; right;

if (y - &gt; right != TNULL)

{

  y - &gt; right - &gt; parent = x;

}

y - &gt; parent = x - &gt; parent;

if (x - &gt; parent == nullptr)

{

  this - &gt; root = y;

} else if (x == x - &gt; parent - &gt; right)

{

  x - &gt; parent - &gt; right = y;

} else

{

  x - &gt; parent - &gt; left = y;

}

y - &gt; right = x;

x - &gt; parent = y;

}

void insert(int key)

{

NodePtr node = new Node;

node - &gt; parent = nullptr;

node - &gt; data = key;

node - &gt; left = TNULL;

node - &gt; right = TNULL;

node - &gt; color = 1;

NodePtr y = nullptr;

NodePtr x = this - &gt; root;

while (x != TNULL)

{

  y = x;

  if (node - &gt; data &lt; x - &gt; data)

  {

    x = x - &gt; left;

  } else

  {

    x = x - &gt; right;

  }

}

node - &gt; parent = y;

if (y == nullptr)

{

  root = node;

} else if (node - &gt; data &lt; y - &gt; data)

{

  y - &gt; left = node;

} else

{

  y - &gt; right = node;

}

if (node - &gt; parent == nullptr)

{

  node - &gt; color = 0;

  return;

}

if (node - &gt; parent - &gt; parent == nullptr)

{

  return;

}

insertFix(node);

}

NodePtr getRoot()

{

return this - &gt; root;

}

void printTree()

{

if (root)

{

  printTree(this - &gt; 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();

}

Red Black Tree Insertion