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>\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 searchTree(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 searchTree(node - &gt; left, key);\n\n}\n\nreturn searchTree(node - &gt; right, key);\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 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 printTree(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  printTree(root - &gt; left, indent, false);\n\n  printTree(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 searchTree(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 printTree()
\n{
\nif (root)\n\n{\n\n  printTree(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();
\n}
\n","title":"Red Black Tree Insertion","authorDetails":{"name":"Sonal Moga","slug":"sonal-moga"},"description":null,"slug":"data-structure/red-black-tree-insertion/","articleId":"636a83417bb1ce5072622b38","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}