{"post":"

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:

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.
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.
\n $\"\"$
If both L & C are black, the child node becomes double black after the removal of a black node.
\n $\"\"$

// Program to show Deletion in red-black tree\n#include <iostream>
\nusing namespace std;
\nstruct Node
\n{
\nint data;
\nNode * parent;
\nNode * left;
\nNode * right;
\nint color;
\n};
\ntypedef Node * NodePtr;
\nclass RedBlackTree
\n{
\nprivate:
\nNodePtr root;\n
\nNodePtr TNULL;
\nvoid initializeNULLNode(NodePtr node, NodePtr parent)
\n{
\nnode - &gt; data = 0;\n\nnode - &gt; parent = parent;\n\nnode - &gt; left = nullptr;\n\nnode - &gt; right = nullptr;\n\nnode - &gt; color = 0;\n
\n}
\nvoid preOrderTraversal(NodePtr node)
\n{
\nif (node != TNULL)\n\n{\n\n  cout &lt;&lt; node - &gt; data &lt;&lt; \" \";\n\n  preOrderTraversal(node - &gt; left);\n\n  preOrderTraversal(node - &gt; right);\n\n}\n
\n}
\nvoid inOrderTraversal(NodePtr node)
\n{
\nif (node != TNULL)\n\n{\n\n  inOrderTraversal(node - &gt; left);\n\n  cout &lt;&lt; node - &gt; data &lt;&lt; \" \";\n\n  inOrderTraversal(node - &gt; right);\n\n}\n
\n}
\nvoid postOrderTraversal(NodePtr node)
\n{
\nif (node != TNULL)\n\n{\n\n  postOrderTraversal(node - &gt; left);\n\n  postOrderTraversal(node - &gt; right);\n\n  cout &lt;&lt; node - &gt; data &lt;&lt; \" \";\n\n}\n
\n}
\nNodePtr searchTreeTraversal(NodePtr node, int key)
\n{
\nif (node == TNULL || key == node - &gt; data)\n\n{\n\n  return node;\n\n}\n\nif (key &lt; node - &gt; data)\n\n{\n\n  return searchTreeTraversal(node - &gt; left, key);\n\n}\n\nreturn searchTreeTraversal(node - &gt; right, key);\n
\n}
\nvoid deleteFix(NodePtr x)
\n{
\nNodePtr s;\n\nwhile (x != root && x - &gt; color == 0)\n\n{\n\n  if (x == x - &gt; parent - &gt; left)\n\n  {\n\n    s = x - &gt; parent - &gt; right;\n\n    if (s - &gt; color == 1)\n\n    {\n\n      s - &gt; color = 0;\n\n      x - &gt; parent - &gt; color = 1;\n\n      leftRotate(x - &gt; parent);\n\n      s = x - &gt; parent - &gt; right;\n\n    }\n\n    if (s - &gt; left - &gt; color == 0 && s - &gt; right - &gt; color == 0)\n\n    {\n\n      s - &gt; color = 1;\n\n      x = x - &gt; parent;\n\n    } else\n\n    {\n\n      if (s - &gt; right - &gt; color == 0)\n\n      {\n\n        s - &gt; left - &gt; color = 0;\n\n        s - &gt; color = 1;\n\n        rightRotate(s);\n\n        s = x - &gt; parent - &gt; right;\n\n      }\n\n      s - &gt; color = x - &gt; parent - &gt; color;\n\n      x - &gt; parent - &gt; color = 0;\n\n      s - &gt; right - &gt; color = 0;\n\n      leftRotate(x - &gt; parent);\n\n      x = root;\n\n    }\n\n  } else\n\n  {\n\n    s = x - &gt; parent - &gt; left;\n\n    if (s - &gt; color == 1)\n\n    {\n\n      s - &gt; color = 0;\n\n      x - &gt; parent - &gt; color = 1;\n\n      rightRotate(x - &gt; parent);\n\n      s = x - &gt; parent - &gt; left;\n\n    }\n\n    if (s - &gt; right - &gt; color == 0 && s - &gt; right - &gt; color == 0)\n\n    {\n\n      s - &gt; color = 1;\n\n      x = x - &gt; parent;\n\n    } else\n\n    {\n\n      if (s - &gt; left - &gt; color == 0)\n\n      {\n\n        s - &gt; right - &gt; color = 0;\n\n        s - &gt; color = 1;\n\n        leftRotate(s);\n\n        s = x - &gt; parent - &gt; left;\n\n      }\n\n      s - &gt; color = x - &gt; parent - &gt; color;\n\n      x - &gt; parent - &gt; color = 0;\n\n      s - &gt; left - &gt; color = 0;\n\n      rightRotate(x - &gt; parent);\n\n      x = root;\n\n    }\n\n  }\n\n}\n\nx - &gt; color = 0;\n
\n}
\nvoid rbTransplant(NodePtr u, NodePtr v)
\n{
\nif (u - &gt; parent == nullptr)\n\n{\n\n  root = v;\n\n} else if (u == u - &gt; parent - &gt; left)\n\n{\n\n  u - &gt; parent - &gt; left = v;\n\n} else\n\n{\n\n  u - &gt; parent - &gt; right = v;\n\n}\n\nv - &gt; parent = u - &gt; parent;\n
\n}
\nvoid deleteNodeHelper(NodePtr node, int key)
\n{
\nNodePtr z = TNULL;\n\nNodePtr x, y;\n\nwhile (node != TNULL)\n\n{\n\n  if (node - &gt; data == key)\n\n  {\n\n    z = node;\n\n  }\n\n  if (node - &gt; data &lt;= key)\n\n  {\n\n    node = node - &gt; right;\n\n  } else\n\n  {\n\n    node = node - &gt; left;\n\n  }\n\n}\n\nif (z == TNULL)\n\n{\n\n  cout &lt;&lt; \"Key not found in the tree\" &lt;&lt; endl;\n\n  return;\n\n}\n\ny = z;\n\nint y_original_color = y - &gt; color;\n\nif (z - &gt; left == TNULL)\n\n{\n\n  x = z - &gt; right;\n\n  rbTransplant(z, z - &gt; right);\n\n} else if (z - &gt; right == TNULL)\n\n{\n\n  x = z - &gt; left;\n\n  rbTransplant(z, z - &gt; left);\n\n} else\n\n{\n\n  y = minimum(z - &gt; right);\n\n  y_original_color = y - &gt; color;\n\n  x = y - &gt; right;\n\n  if (y - &gt; parent == z)\n\n  {\n\n    x - &gt; parent = y;\n\n  } else\n\n  {\n\n    rbTransplant(y, y - &gt; right);\n\n    y - &gt; right = z - &gt; right;\n\n    y - &gt; right - &gt; parent = y;\n\n  }\n\n  rbTransplant(z, y);\n\n  y - &gt; left = z - &gt; left;\n\n  y - &gt; left - &gt; parent = y;\n\n  y - &gt; color = z - &gt; color;\n\n}\n\ndelete z;\n\nif (y_original_color == 0)\n\n{\n\n  deleteFix(x);\n\n}\n
\n}
\nvoid insertFix(NodePtr k)
\n{
\nNodePtr u;\n\nwhile (k - &gt; parent - &gt; color == 1)\n\n{\n\n  if (k - &gt; parent == k - &gt; parent - &gt; parent - &gt; right)\n\n  {\n\n    u = k - &gt; parent - &gt; parent - &gt; left;\n\n    if (u - &gt; color == 1)\n\n    {\n\n      u - &gt; color = 0;\n\n      k - &gt; parent - &gt; color = 0;\n\n      k - &gt; parent - &gt; parent - &gt; color = 1;\n\n      k = k - &gt; parent - &gt; parent;\n\n    } else\n\n    {\n\n      if (k == k - &gt; parent - &gt; left)\n\n      {\n\n        k = k - &gt; parent;\n\n        rightRotate(k);\n\n      }\n\n      k - &gt; parent - &gt; color = 0;\n\n      k - &gt; parent - &gt; parent - &gt; color = 1;\n\n      leftRotate(k - &gt; parent - &gt; parent);\n\n    }\n\n  } else\n\n  {\n\n    u = k - &gt; parent - &gt; parent - &gt; right;\n\n    if (u - &gt; color == 1)\n\n    {\n\n      u - &gt; color = 0;\n\n      k - &gt; parent - &gt; color = 0;\n\n      k - &gt; parent - &gt; parent - &gt; color = 1;\n\n      k = k - &gt; parent - &gt; parent;\n\n    } else\n\n    {\n\n      if (k == k - &gt; parent - &gt; right)\n\n      {\n\n        k = k - &gt; parent;\n\n        leftRotate(k);\n\n      }\n\n      k - &gt; parent - &gt; color = 0;\n\n      k - &gt; parent - &gt; parent - &gt; color = 1;\n\n      rightRotate(k - &gt; parent - &gt; parent);\n\n    }\n\n  }\n\n  if (k == root)\n\n  {\n\n    break;\n\n  }\n\n}\n\nroot - &gt; color = 0;\n
\n}
\nvoid printHelper(NodePtr root, string indent, bool last)
\n{
\nif (root != TNULL)\n\n{\n\n  cout &lt;&lt; indent;\n\n  if (last)\n\n  {\n\n    cout &lt;&lt; \"R----\";\n\n    indent += \"   \";\n\n  } else\n\n  {\n\n    cout &lt;&lt; \"L----\";\n\n    indent += \"|  \";\n\n  }\n\n  string sColor = root - &gt; color ? \"RED\" : \"BLACK\";\n\n  cout &lt;&lt; root - &gt; data &lt;&lt; \"(\" &lt;&lt; sColor &lt;&lt; \")\" &lt;&lt; endl;\n\n  printHelper(root - &gt; left, indent, false);\n\n  printHelper(root - &gt; right, indent, true);\n\n}\n
\n}
\npublic:
\nRedBlackTree()\n
\n{
\nTNULL = new Node;\n\nTNULL - &gt; color = 0;\n\nTNULL - &gt; left = nullptr;\n\nTNULL - &gt; right = nullptr;\n\nroot = TNULL;\n
\n}
\nvoid preorder()
\n{
\npreOrderTraversal(this - &gt; root);\n
\n}
\nvoid inorder()
\n{
\ninOrderTraversal(this - &gt; root);\n
\n}
\nvoid postorder()
\n{
\npostOrderTraversal(this - &gt; root);\n
\n}
\nNodePtr searchTree(int k)
\n{
\nreturn searchTreeTraversal(this - &gt; root, k);\n
\n}
\nNodePtr minimum(NodePtr node)
\n{
\nwhile (node - &gt; left != TNULL)\n\n{\n\n  node = node - &gt; left;\n\n}\n\nreturn node;\n
\n}
\nNodePtr maximum(NodePtr node)
\n{
\nwhile (node - &gt; right != TNULL)\n\n{\n\n  node = node - &gt; right;\n\n}\n\nreturn node;\n
\n}
\nNodePtr successor(NodePtr x)
\n{
\nif (x - &gt; right != TNULL)\n\n{\n\n  return minimum(x - &gt; right);\n\n}\n\nNodePtr y = x - &gt; parent;\n\nwhile (y != TNULL && x == y - &gt; right)\n\n{\n\n  x = y;\n\n  y = y - &gt; parent;\n\n}\n\nreturn y;\n
\n}
\nNodePtr predecessor(NodePtr x)
\n{
\nif (x - &gt; left != TNULL)\n\n{\n\n  return maximum(x - &gt; left);\n\n}\n\nNodePtr y = x - &gt; parent;\n\nwhile (y != TNULL && x == y - &gt; left)\n\n{\n\n  x = y;\n\n  y = y - &gt; parent;\n\n}\n\nreturn y;\n
\n}
\nvoid leftRotate(NodePtr x)
\n{
\nNodePtr y = x - &gt; right;\n\nx - &gt; right = y - &gt; left;\n\nif (y - &gt; left != TNULL)\n\n{\n\n  y - &gt; left - &gt; parent = x;\n\n}\n\ny - &gt; parent = x - &gt; parent;\n\nif (x - &gt; parent == nullptr)\n\n{\n\n  this - &gt; root = y;\n\n} else if (x == x - &gt; parent - &gt; left)\n\n{\n\n  x - &gt; parent - &gt; left = y;\n\n} else\n\n{\n\n  x - &gt; parent - &gt; right = y;\n\n}\n\ny - &gt; left = x;\n\nx - &gt; parent = y;\n
\n}
\nvoid rightRotate(NodePtr x)
\n{
\nNodePtr y = x - &gt; left;\n\nx - &gt; left = y - &gt; right;\n\nif (y - &gt; right != TNULL)\n\n{\n\n  y - &gt; right - &gt; parent = x;\n\n}\n\ny - &gt; parent = x - &gt; parent;\n\nif (x - &gt; parent == nullptr)\n\n{\n\n  this - &gt; root = y;\n\n} else if (x == x - &gt; parent - &gt; right)\n\n{\n\n  x - &gt; parent - &gt; right = y;\n\n} else\n\n{\n\n  x - &gt; parent - &gt; left = y;\n\n}\n\ny - &gt; right = x;\n\nx - &gt; parent = y;\n
\n}
\nvoid insert(int key)
\n{
\nNodePtr node = new Node;\n\nnode - &gt; parent = nullptr;\n\nnode - &gt; data = key;\n\nnode - &gt; left = TNULL;\n\nnode - &gt; right = TNULL;\n\nnode - &gt; color = 1;\n\nNodePtr y = nullptr;\n\nNodePtr x = this - &gt; root;\n\nwhile (x != TNULL)\n\n{\n\n  y = x;\n\n  if (node - &gt; data &lt; x - &gt; data)\n\n  {\n\n    x = x - &gt; left;\n\n  } else\n\n  {\n\n    x = x - &gt; right;\n\n  }\n\n}\n\nnode - &gt; parent = y;\n\nif (y == nullptr)\n\n{\n\n  root = node;\n\n} else if (node - &gt; data &lt; y - &gt; data)\n\n{\n\n  y - &gt; left = node;\n\n} else\n\n{\n\n  y - &gt; right = node;\n\n}\n\nif (node - &gt; parent == nullptr)\n\n{\n\n  node - &gt; color = 0;\n\n  return;\n\n}\n\nif (node - &gt; parent - &gt; parent == nullptr)\n\n{\n\n  return;\n\n}\n\ninsertFix(node);\n
\n}
\nNodePtr getRoot()
\n{
\nreturn this - &gt; root;\n
\n}
\nvoid deleteNode(int data)
\n{
\ndeleteNodeHelper(this - &gt; root, data);\n
\n}
\nvoid printTree()
\n{
\nif (root)\n\n{\n\n  printHelper(this - &gt; root, \"\", true);\n\n}\n
\n}
\n};
\nint main()
\n{
\nRedBlackTree bst;
\nbst.insert(55);
\nbst.insert(40);
\nbst.insert(65);
\nbst.insert(60);
\nbst.insert(75);
\nbst.insert(57);
\nbst.printTree();
\ncout << endl
\n&lt;&lt;\n\"After deleting\" &lt;&lt; endl;\n
\nbst.deleteNode(40);
\nbst.printTree();
\n}

\n","title":"Red Black Tree Deletion","authorDetails":{"name":"Sonal Moga","slug":"sonal-moga"},"description":"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.","slug":"data-structure/red-black-tree-deletion/","articleId":"636a83417bb1ce5072622b37","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}