Red Black Tree Deletion

Written by

Sonal Moga

What is Red Black Tree ?

Insertion in Red Black Tree

Deletion in Red Black Tree

Red Black Tree Deletion

The deletion of an element from a tree means the removal of a node from a tree. The process of deleting a node from a Red-black tree is complex than insertion. In the removal of a node, the notion of double black is followed.

 Following steps are followed for deleting a node from Red-Black Tree:

  1. Standard BST removal: in this case, we delete a node that is either a leaf or has only one child. We will consider node to be deleted as L and node that replaces it as C.
  2. Simple case: Either L or C is red, we color the replaced child as black. Both the L and C nodes cannot be red as two consecutive red nodes are not allowed in a Red-Black Tree.
  3. If both L & C are black, the child node becomes double black after the removal of a black node.

 

// Program to show Deletion in 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 searchTreeTraversal(NodePtr node, int key)

{

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

{

  return node;

}

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

{

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

}

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

}

void deleteFix(NodePtr x)

{

NodePtr s;

while (x != root &amp;&amp; x - &gt; color == 0)

{

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

  {

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

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

    {

      s - &gt; color = 0;

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

      leftRotate(x - &gt; parent);

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

    }

    if (s - &gt; left - &gt; color == 0 &amp;&amp; s - &gt; right - &gt; color == 0)

    {

      s - &gt; color = 1;

      x = x - &gt; parent;

    } else

    {

      if (s - &gt; right - &gt; color == 0)

      {

        s - &gt; left - &gt; color = 0;

        s - &gt; color = 1;

        rightRotate(s);

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

      }

      s - &gt; color = x - &gt; parent - &gt; color;

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

      s - &gt; right - &gt; color = 0;

      leftRotate(x - &gt; parent);

      x = root;

    }

  } else

  {

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

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

    {

      s - &gt; color = 0;

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

      rightRotate(x - &gt; parent);

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

    }

    if (s - &gt; right - &gt; color == 0 &amp;&amp; s - &gt; right - &gt; color == 0)

    {

      s - &gt; color = 1;

      x = x - &gt; parent;

    } else

    {

      if (s - &gt; left - &gt; color == 0)

      {

        s - &gt; right - &gt; color = 0;

        s - &gt; color = 1;

        leftRotate(s);

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

      }

      s - &gt; color = x - &gt; parent - &gt; color;

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

      s - &gt; left - &gt; color = 0;

      rightRotate(x - &gt; parent);

      x = root;

    }

  }

}

x - &gt; color = 0;

}

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 deleteNodeHelper(NodePtr node, int key)

{

NodePtr z = TNULL;

NodePtr x, y;

while (node != TNULL)

{

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

  {

    z = node;

  }

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

  {

    node = node - &gt; right;

  } else

  {

    node = node - &gt; left;

  }

}

if (z == TNULL)

{

  cout &lt;&lt; "Key not found in the tree" &lt;&lt; endl;

  return;

}

y = z;

int y_original_color = y - &gt; color;

if (z - &gt; left == TNULL)

{

  x = z - &gt; right;

  rbTransplant(z, z - &gt; right);

} else if (z - &gt; right == TNULL)

{

  x = z - &gt; left;

  rbTransplant(z, z - &gt; left);

} else

{

  y = minimum(z - &gt; right);

  y_original_color = y - &gt; color;

  x = y - &gt; right;

  if (y - &gt; parent == z)

  {

    x - &gt; parent = y;

  } else

  {

    rbTransplant(y, y - &gt; right);

    y - &gt; right = z - &gt; right;

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

  }

  rbTransplant(z, y);

  y - &gt; left = z - &gt; left;

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

  y - &gt; color = z - &gt; color;

}

delete z;

if (y_original_color == 0)

{

  deleteFix(x);

}

}

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 printHelper(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;

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

  printHelper(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 searchTreeTraversal(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 deleteNode(int data)

{

deleteNodeHelper(this - &gt; root, data);

}

void printTree()

{

if (root)

{

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

cout << endl

&lt;&lt;
"After deleting" &lt;&lt; endl;

bst.deleteNode(40);

bst.printTree();

}

Red Black Tree Deletion