{"id":16121,"date":"2023-05-05T10:12:05","date_gmt":"2023-05-05T10:12:05","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=16121"},"modified":"2023-05-05T10:12:05","modified_gmt":"2023-05-05T10:12:05","slug":"red-black-tree-in-data-structure","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/","title":{"rendered":"Red Black Tree in Data Structure"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\" alt=\"\" \/><\/p>\n<p>Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. Let us first define a Binary Search Tree before diving into the red black tree. A BST (Binary Search Tree) is a non-linear data structure in which the nodes in the left subtree have values less than the root node and the nodes in the right subtree have values greater than the root node. In this article, we will go through the Red Black Tree in depth.<\/p>\n<h2>What is Red Black Tree in Data Structure<\/h2>\n<p>The red-black tree is a binary search tree in which each node is either red or black. It&#8217;s a self-balancing binary search tree. It has a low worst-case running time complexity. <\/p>\n<h3>Properties of a Red Black Tree in Data Structure<\/h3>\n<p>The Red-Black tree satisfies all of the properties of a binary search tree, as well as the following extra properties &#8211;<\/p>\n<ol>\n<li>The root is black in color.<\/li>\n<li><strong>External property:<\/strong> In the Red-Black tree, every leaf (Leaf is a NULL offspring of a node) is black.<\/li>\n<li><strong>Internal property:<\/strong> A red node&#8217;s children are black. As a result, the red node&#8217;s probable parent is a black node.<\/li>\n<li><strong>Depth property:<\/strong> The dark depth of all the leaves is the same.<\/li>\n<li><strong>Path property:<\/strong> There is the same number of black nodes on every simple path from the root to a descendant leaf node.<\/li>\n<\/ol>\n<p>The red black tree must obey some rules in addition to the given set of characteristics. Let&#8217;s talk about these rule sets. <\/p>\n<h3>Set of Rules for Red Black Tree in Data Structure<\/h3>\n<p>Every Red Black Tree must abide by the following rules:<\/p>\n<ul>\n<li>Every node has one of two colors: RED or BLACK.<\/li>\n<li>The tree&#8217;s root is always BLACK.<\/li>\n<li>There are no adjacent RED nodes, which means that a RED node cannot have a RED parent or a RED child.<\/li>\n<li>Every path that connects a node (including the root) to any of its descendants The number of NULL nodes is the same as the number of BLACK nodes.<\/li>\n<li>Every leaf, that is, every NULL node, must be coloured BLACK.<\/li>\n<\/ul>\n<h3>Why do we need the Red Black Tree?<\/h3>\n<p>Most BST operations (for example, search, max, min, insert, delete, etc.) take O(h) time, where h is the height of the BST. For a skewed Binary tree, the cost of these operations may become O(n). We can guarantee an upper bound of O(log n) for all of these operations if we ensure that the height of the tree remains O(log n) after every insertion and deletion. We can guarantee that all operations require O(log n) operations since the height of a Red-Black tree is always O(log n), where n is the number of nodes in the tree.<\/p>\n<p>The time complexity of each operation is shown below in tabular form:<\/p>\n<table>\n<thead>\n<tr>\n<th>S.No<\/th>\n<th>Operation<\/th>\n<th>Time Complexity<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>1<\/td>\n<td>Search<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>Insert<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>Delete<\/td>\n<td>O(log n)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>AVL Tree vs Red Black Tree in Data Structure<\/h3>\n<p>Let\u2019s discuss the difference between AVL tree and Red black tree in Data Structure:<\/p>\n<p><strong>What is AVL Tree in Data Structure?<\/strong><br \/>\nThe AVL Tree is a height-balanced binary search tree in which each node has a balancing factor that is derived by subtracting the height of its right subtree from the height of its left subtree.<br \/>\nIf the balance factor of each node is between -1 and 1, the tree is said to be balanced; otherwise, the tree is imbalanced and must be balanced.<\/p>\n<p><strong>Now, let us discuss some differences between AVL Tree and Red Black Tree.<\/strong> <\/p>\n<table>\n<thead>\n<tr>\n<th>Parameter<\/th>\n<th>Red Black Tree<\/th>\n<th>AVL Tree<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>Searching<\/td>\n<td>Searching is not efficient as they are not perfectly balanced.<\/td>\n<td>Searching is efficient as they are perfectly balanced.<\/td>\n<\/tr>\n<tr>\n<td>Insertion and deletion<\/td>\n<td>Insertion and deletion are easier in the Red Black tree as it requires fewer rotations to balance the tree.<\/td>\n<td>Insertion and deletion are complex in AVL tree as it requires multiple rotations to balance the tree.<\/td>\n<\/tr>\n<tr>\n<td>Color of the Node<\/td>\n<td>Red or Black<\/td>\n<td>No color<\/td>\n<\/tr>\n<tr>\n<td>Balance factor<\/td>\n<td>No balance factor<\/td>\n<td>Each node has a balance factor in the AVL tree whose value can be 1, 0, or -1.<\/td>\n<\/tr>\n<tr>\n<td>Strictly balanced<\/td>\n<td>Not strictly balanced<\/td>\n<td>Strictly balanced<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h2>Operations on a Red Black Tree in Data Structure<\/h2>\n<p>In a Red Black Tree, we can do certain operations, including :<\/p>\n<ol>\n<li>Rotating a sub-tree<\/li>\n<li>Insertion<\/li>\n<li>Deletion<\/li>\n<\/ol>\n<h3>Rotating a subtree in a Red Black Tree in Data Structure<\/h3>\n<p>The positions of a subtree&#8217;s nodes are swapped during the rotation operation. When other processes, such as insertion and deletion, violate the attributes of a red-black tree, the rotation operation is employed to restore them. Rotations are classified into two types:<\/p>\n<ul>\n<li>\n<p><strong>Left Rotation<\/strong><br \/>\nIn left-rotation, the arrangement of the nodes on the right is replaced by the arrangement of the nodes on the left.<\/p>\n<ul>\n<li>\n<p>Let the first tree be:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240506-1-01%20%2884%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>If y has a left subtree, make x the parent of y&#8217;s left subtree.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240509-1-02%20%2842%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>If the parent of x is NULL, make y the tree&#8217;s root.<\/p>\n<\/li>\n<li>\n<p>Otherwise, if x is p&#8217;s left child, make y p&#8217;s left child. <\/p>\n<\/li>\n<li>\n<p>Otherwise, make y the right child of p.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240509-1-03%20%2828%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>Make y the parent of x.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240536-1-04%20%2821%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p><strong>Right Rotation<\/strong><br \/>\nThe arrangement of the nodes on the left is changed into the arrangement of the nodes on the right in right-rotation.<\/p>\n<ul>\n<li>\n<p>Let the initial tree be:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240536-1-05%20%2815%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>If x has a right subtree, assign y as the parent of the right subtree of x.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240536-1-06%20%2811%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>If the parent of y is NULL, make x as the root of the tree.<\/p>\n<\/li>\n<li>\n<p>Else if y is the right child of its parent p, make x as the right child of p.<\/p>\n<\/li>\n<li>\n<p>Else assign x as the left child of p.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240536-1-07%20%2810%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>Make x as the parent of y.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240537-1-08%20%286%29.png\" alt=\"\" \/><\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<h3>Insertion in a Red Black Tree in Data Structure<\/h3>\n<p>When a new node is inserted, it is always inserted as a RED node. If the tree violates the properties of the red-black tree after insertion of a new node, we do the following activities.<\/p>\n<ol>\n<li>Recolor<\/li>\n<li>Rotation<\/li>\n<\/ol>\n<p><strong>Algorithm to Insert a Node in a Red Black Tree<\/strong><\/p>\n<ul>\n<li>Navigate the tree to determine the best location for the new node.<\/li>\n<li>Once you&#8217;ve found the right spot, insert the new node as a red node.<\/li>\n<li>If the new node&#8217;s parent is black, no additional action is required, and the tree remains a valid red-black tree.<\/li>\n<li>If the new node&#8217;s parent is red, there are three possibilities:\n<ul>\n<li>Case 1: The sibling of the parent is also red. In this scenario, color the parent and its sibling black, and the parent&#8217;s parent (grandparent) red in this scenario. Then, repeat the algorithm from the grandparent to ensure that the red-black tree properties are preserved.<\/li>\n<li>Case 2: The parent&#8217;s sibling is black, the new node is its parent&#8217;s right child, and the parent is its grandparent&#8217;s left child. Perform a left rotation on the parent in this case, so that the new node becomes the parent and the parent becomes the new node&#8217;s left child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.<\/li>\n<li>Case 3: The parent&#8217;s sibling is black, the new node is the parent&#8217;s left kid, and the parent is the grandparent&#8217;s left child. In this scenario, recolor the parent black and the grandparent red, and then right rotate the grandparent such that the parent becomes the grandparent&#8217;s right child and the grandparent becomes the parent&#8217;s right child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.<\/li>\n<li>Case 4: The parent&#8217;s sibling is black, the new node is its parent&#8217;s left child, and the parent is the right child of its grandparent. In this situation, right-rotate the parent such that the new node becomes the parent and the parent becomes the new node&#8217;s right child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.<\/li>\n<li>Case 5: The parent&#8217;s sibling is black, and the new node is the parent&#8217;s right kid, and the parent is the grandparent&#8217;s right child. In this scenario, recolor the parent black and the grandparent red, and then rotate the grandparent so that the parent becomes the grandparent&#8217;s left child and the grandparent becomes the parent&#8217;s left child. Then, repeat the algorithm from the parent to ensure that the red-black tree properties are preserved.<\/li>\n<\/ul>\n<\/li>\n<li>Continue the procedure until you reach the tree&#8217;s root, and then recolor it black to ensure it is always black.<\/li>\n<\/ul>\n<p><strong>Code Implementation<\/strong><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_16122 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_16122 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_16122 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_16122 .wpsm_nav-tabs > li.active > a, #tab_container_16122 .wpsm_nav-tabs > li.active > a:hover, #tab_container_16122 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_16122 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_16122 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_16122 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_16122 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_16122 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_16122 .wpsm_nav-tabs > li > a:hover , #tab_container_16122 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_16122 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_16122 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_16122 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_16122 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_16122 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_16122 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_16122 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_16122 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_16122 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_16122 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_16122 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_16122\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_16122\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_16122_1\" aria-controls=\"tabs_desc_16122_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_16122\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_16122_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\">\/*package whatever \/\/do not write package name here *\/\r\n\r\nimport java.io.*;\r\n\r\n\/\/ considering that you know what are red-black trees here is the implementation in java for insertion and traversal.\r\n\/\/ RedBlackTree class. This class contains subclass for node\r\n\/\/ as well as all the functionalities of RedBlackTree such as - rotations, insertion and\r\n\/\/ inoredr traversal\r\npublic class RedBlackTree\r\n{\r\n    public Node root;\/\/root node\r\n    public RedBlackTree()\r\n    {\r\n        super();\r\n        root = null;\r\n    }\r\n    \/\/ node creating subclass\r\n    class Node\r\n    {\r\n        int data;\r\n        Node left;\r\n        Node right;\r\n        char colour;\r\n        Node parent;\r\n\r\n        Node(int data)\r\n        {\r\n            super();\r\n            this.data = data; \/\/ only including data. not key\r\n            this.left = null; \/\/ left subtree\r\n            this.right = null; \/\/ right subtree\r\n            this.colour = 'R'; \/\/ colour . either 'R' or 'B'\r\n            this.parent = null; \/\/ required at time of rechecking.\r\n        }\r\n    }\r\n    \/\/ this function performs left rotation\r\n    Node rotateLeft(Node node)\r\n    {\r\n        Node x = node.right;\r\n        Node y = x.left;\r\n        x.left = node;\r\n        node.right = y;\r\n        node.parent = x; \/\/ parent resetting is also important.\r\n        if(y!=null)\r\n            y.parent = node;\r\n        return(x);\r\n    }\r\n    \/\/this function performs right rotation\r\n    Node rotateRight(Node node)\r\n    {\r\n        Node x = node.left;\r\n        Node y = x.right;\r\n        x.right = node;\r\n        node.left = y;\r\n        node.parent = x;\r\n        if(y!=null)\r\n            y.parent = node;\r\n        return(x);\r\n    }\r\n\r\n\r\n    \/\/ these are some flags.\r\n    \/\/ Respective rotations are performed during traceback.\r\n    \/\/ rotations are done if flags are true.\r\n    boolean ll = false;\r\n    boolean rr = false;\r\n    boolean lr = false;\r\n    boolean rl = false;\r\n    \/\/ helper function for insertion. Actually this function performs all tasks in single pass only.\r\n    Node insertHelp(Node root, int data)\r\n    {\r\n        \/\/ f is true when RED RED conflict is there.\r\n        boolean f=false;\r\n        \r\n        \/\/recursive calls to insert at proper position according to BST properties.\r\n        if(root==null)\r\n            return(new Node(data));\r\n        else if(data&lt;root.data)\r\n        {\r\n            root.left = insertHelp(root.left, data);\r\n            root.left.parent = root;\r\n            if(root!=this.root)\r\n            {\r\n                if(root.colour=='R' &amp;&amp; root.left.colour=='R')\r\n                    f = true;\r\n            }\r\n        }\r\n        else\r\n        {\r\n            root.right = insertHelp(root.right,data);\r\n            root.right.parent = root;\r\n            if(root!=this.root)\r\n            {\r\n                if(root.colour=='R' &amp;&amp; root.right.colour=='R')\r\n                    f = true;\r\n            }\r\n        \/\/ at the same time of insertion, we are also assigning parent nodes\r\n        \/\/ also we are checking for RED RED conflicts\r\n        }\r\n\r\n        \/\/ now lets rotate.\r\n        if(this.ll) \/\/ for left rotate.\r\n        {\r\n            root = rotateLeft(root);\r\n            root.colour = 'B';\r\n            root.left.colour = 'R';\r\n            this.ll = false;\r\n        }\r\n        else if(this.rr) \/\/ for right rotate\r\n        {\r\n            root = rotateRight(root);\r\n            root.colour = 'B';\r\n            root.right.colour = 'R';\r\n            this.rr = false;\r\n        }\r\n        else if(this.rl) \/\/ for right and then left\r\n        {\r\n            root.right = rotateRight(root.right);\r\n            root.right.parent = root;\r\n            root = rotateLeft(root);\r\n            root.colour = 'B';\r\n            root.left.colour = 'R';\r\n\r\n            this.rl = false;\r\n        }\r\n        else if(this.lr) \/\/ for left and then right.\r\n        {\r\n            root.left = rotateLeft(root.left);\r\n            root.left.parent = root;\r\n            root = rotateRight(root);\r\n            root.colour = 'B';\r\n            root.right.colour = 'R';\r\n            this.lr = false;\r\n        }\r\n        \/\/ when rotation and recolouring is done flags are reset.\r\n        \/\/ Now lets take care of RED RED conflict\r\n        if(f)\r\n        {\r\n            if(root.parent.right == root) \/\/ to check which child is the current node of its parent\r\n            {\r\n                if(root.parent.left==null || root.parent.left.colour=='B') \/\/ case when parent's sibling is black\r\n                {\/\/ perform certaing rotation and recolouring. This will be done while backtracking. Hence setting up respective flags.\r\n                    if(root.left!=null &amp;&amp; root.left.colour=='R')\r\n                        this.rl = true;\r\n                    else if(root.right!=null &amp;&amp; root.right.colour=='R')\r\n                        this.ll = true;\r\n                }\r\n                else \/\/ case when parent's sibling is red\r\n                {\r\n                    root.parent.left.colour = 'B';\r\n                    root.colour = 'B';\r\n                    if(root.parent!=this.root)\r\n                        root.parent.colour = 'R';\r\n                }\r\n            }\r\n            else\r\n            {\r\n                if(root.parent.right==null || root.parent.right.colour=='B')\r\n                {\r\n                    if(root.left!=null &amp;&amp; root.left.colour=='R')\r\n                        this.rr = true;\r\n                    else if(root.right!=null &amp;&amp; root.right.colour=='R')\r\n                        this.lr = true;\r\n                }\r\n                else\r\n                {\r\n                    root.parent.right.colour = 'B';\r\n                    root.colour = 'B';\r\n                    if(root.parent!=this.root)\r\n                        root.parent.colour = 'R';\r\n                }\r\n            }\r\n            f = false;\r\n        }\r\n        return(root);\r\n    }\r\n\r\n    \/\/ function to insert data into tree.\r\n    public void insert(int data)\r\n    {\r\n        if(this.root==null)\r\n        {\r\n            this.root = new Node(data);\r\n            this.root.colour = 'B';\r\n        }\r\n        else\r\n            this.root = insertHelp(this.root,data);\r\n    }\r\n    \/\/ helper function to print inorder traversal\r\n    void inorderTraversalHelper(Node node)\r\n    {\r\n        if(node!=null)\r\n        {\r\n            inorderTraversalHelper(node.left);\r\n            System.out.printf(\"%d \", node.data);\r\n            inorderTraversalHelper(node.right);\r\n        }\r\n    }\r\n    \/\/function to print inorder traversal\r\n    public void inorderTraversal()\r\n    {\r\n        inorderTraversalHelper(this.root);\r\n    }\r\n    \/\/ helper function to print the tree.\r\n    void printTreeHelper(Node root, int space)\r\n    {\r\n        int i;\r\n        if(root != null)\r\n        {\r\n            space = space + 10;\r\n            printTreeHelper(root.right, space);\r\n            System.out.printf(\"&#92;n\");\r\n            for ( i = 10; i &lt; space; i++)\r\n            {\r\n                System.out.printf(\" \");\r\n            }\r\n            System.out.printf(\"%d\", root.data);\r\n            System.out.printf(\"&#92;n\");\r\n            printTreeHelper(root.left, space);\r\n        }\r\n    }\r\n    \/\/ function to print the tree.\r\n    public void printTree()\r\n    {\r\n        printTreeHelper(this.root, 0);\r\n    }\r\n    public static void main(String[] args)\r\n    {\r\n        RedBlackTree t = new RedBlackTree();\r\n        int[] arr = {1,4,6,3,5,7,8,2,9};\r\n        for(int i=0;i&lt;9;i++)\r\n        {\r\n            t.insert(arr[i]);\r\n            System.out.println();\r\n            t.inorderTraversal();\r\n        }\r\n        t.printTree();\r\n    }\r\n}<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_16122 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_16122 a\"),jQuery(\"#tab-content_16122\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output<\/strong><\/p>\n<pre><code>1 \n1 4 \n1 4 6 \n1 3 4 6 \n1 3 4 5 6 \n1 3 4 5 6 7 \n1 3 4 5 6 7 8 \n1 2 3 4 5 6 7 8 \n1 2 3 4 5 6 7 8 9 <\/code><\/pre>\n<h3>Deletion in a Red Black Tree in Data Structure<\/h3>\n<ul>\n<li>Locate the node that needs to be deleted.<\/li>\n<li>Remove the node from the tree if it has no children.<\/li>\n<li>Replace the node with that child and recolor the replacement node black if the original node was black. Remove the initial node from the tree if it is red.<\/li>\n<li>If the node has two children, replace it with its inorder successor (the node with the smallest key in the right subtree of the node), then delete the inorder successor from its original location. Because the inorder successor can only have one child, we can handle this deletion case using case 2 or 3 from the insertion algorithm.\n<ul>\n<li>Find the inorder successor of the node to be deleted.<\/li>\n<li>Replace the node to be deleted with its inorder successor.<\/li>\n<li>Delete the inorder successor from its original location using cases 1, 2, or 3 from the insertion algorithm.<\/li>\n<\/ul>\n<\/li>\n<li>Check whether any of the red-black tree attributes have been violated after deleting the node, and repair any violations using the following cases:\n<ul>\n<li>If the node replaced during deletion is red, recolor it black.<\/li>\n<li>If the node replaced during deletion is black and its replacement is red, recolor the replacement black.<\/li>\n<li>If the node replaced during deletion is black and its replacement is black, then adjust the tree to restore the red-black tree properties by following one of the cases below:\n<ul>\n<li>If the deleted node&#8217;s sibling is red, recolor the sibling and its parent black and red, respectively, and then rotate the parent left or right (depending on whether the sibling is a left or right child).<\/li>\n<li>If the deleted node&#8217;s sibling is black and both of its children are black, recolor the sibling red and proceed with the algorithm from the sibling&#8217;s parent.<\/li>\n<li>If the deleted node&#8217;s sibling is black, its inner child is red, and its outer child is black, rotate the sibling and its inner child, and then continue the algorithm from the original sibling.<\/li>\n<li>If the deleted node&#8217;s sibling is black and its outer child is red, recolor the sibling to match its parent, recolor the parent black, recolor the outer child black, and rotate the parent.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li>Finally, recolor the root black to maintain the red-black tree properties.<\/li>\n<\/ul>\n<p><strong>Code Implementation<\/strong><\/p>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_16123 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_16123 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_16123 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_16123 .wpsm_nav-tabs > li.active > a, #tab_container_16123 .wpsm_nav-tabs > li.active > a:hover, #tab_container_16123 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_16123 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_16123 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_16123 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_16123 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_16123 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_16123 .wpsm_nav-tabs > li > a:hover , #tab_container_16123 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_16123 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_16123 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_16123 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_16123 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_16123 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_16123 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_16123 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_16123 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_16123 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_16123 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_16123 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_16123\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_16123\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_16123_1\" aria-controls=\"tabs_desc_16123_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_16123\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_16123_1\">\r\n\t\t\t\t\t\t\t\t<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">#include &lt;iostream&gt;\r\n#include &lt;queue&gt;\r\nusing namespace std;\r\n\r\nenum COLOR { RED, BLACK };\r\n\r\nclass Node {\r\npublic:\r\nint val;\r\nCOLOR color;\r\nNode *left, *right, *parent;\r\n\r\nNode(int val) : val(val) {\r\n    parent = left = right = NULL;\r\n\r\n    \/\/ Node is created during insertion\r\n    \/\/ Node is red at insertion\r\n    color = RED;\r\n}\r\n\r\n\/\/ returns pointer to uncle\r\nNode *uncle() {\r\n    \/\/ If no parent or grandparent, then no uncle\r\n    if (parent == NULL or parent-&gt;parent == NULL)\r\n    return NULL;\r\n\r\n    if (parent-&gt;isOnLeft())\r\n    \/\/ uncle on right\r\n    return parent-&gt;parent-&gt;right;\r\n    else\r\n    \/\/ uncle on left\r\n    return parent-&gt;parent-&gt;left;\r\n}\r\n\r\n\/\/ check if node is left child of parent\r\nbool isOnLeft() { return this == parent-&gt;left; }\r\n\r\n\/\/ returns pointer to sibling\r\nNode *sibling() {\r\n    \/\/ sibling null if no parent\r\n    if (parent == NULL)\r\n    return NULL;\r\n\r\n    if (isOnLeft())\r\n    return parent-&gt;right;\r\n\r\n    return parent-&gt;left;\r\n}\r\n\r\n\/\/ moves node down and moves given node in its place\r\nvoid moveDown(Node *nParent) {\r\n    if (parent != NULL) {\r\n    if (isOnLeft()) {\r\n        parent-&gt;left = nParent;\r\n    } else {\r\n        parent-&gt;right = nParent;\r\n    }\r\n    }\r\n    nParent-&gt;parent = parent;\r\n    parent = nParent;\r\n}\r\n\r\nbool hasRedChild() {\r\n    return (left != NULL and left-&gt;color == RED) or\r\n        (right != NULL and right-&gt;color == RED);\r\n}\r\n};\r\n\r\nclass RBTree {\r\nNode *root;\r\n\r\n\/\/ left rotates the given node\r\nvoid leftRotate(Node *x) {\r\n    \/\/ new parent will be node's right child\r\n    Node *nParent = x-&gt;right;\r\n\r\n    \/\/ update root if current node is root\r\n    if (x == root)\r\n    root = nParent;\r\n\r\n    x-&gt;moveDown(nParent);\r\n\r\n    \/\/ connect x with new parent's left element\r\n    x-&gt;right = nParent-&gt;left;\r\n    \/\/ connect new parent's left element with node\r\n    \/\/ if it is not null\r\n    if (nParent-&gt;left != NULL)\r\n    nParent-&gt;left-&gt;parent = x;\r\n\r\n    \/\/ connect new parent with x\r\n    nParent-&gt;left = x;\r\n}\r\n\r\nvoid rightRotate(Node *x) {\r\n    \/\/ new parent will be node's left child\r\n    Node *nParent = x-&gt;left;\r\n\r\n    \/\/ update root if current node is root\r\n    if (x == root)\r\n    root = nParent;\r\n\r\n    x-&gt;moveDown(nParent);\r\n\r\n    \/\/ connect x with new parent's right element\r\n    x-&gt;left = nParent-&gt;right;\r\n    \/\/ connect new parent's right element with node\r\n    \/\/ if it is not null\r\n    if (nParent-&gt;right != NULL)\r\n    nParent-&gt;right-&gt;parent = x;\r\n\r\n    \/\/ connect new parent with x\r\n    nParent-&gt;right = x;\r\n}\r\n\r\nvoid swapColors(Node *x1, Node *x2) {\r\n    COLOR temp;\r\n    temp = x1-&gt;color;\r\n    x1-&gt;color = x2-&gt;color;\r\n    x2-&gt;color = temp;\r\n}\r\n\r\nvoid swapValues(Node *u, Node *v) {\r\n    int temp;\r\n    temp = u-&gt;val;\r\n    u-&gt;val = v-&gt;val;\r\n    v-&gt;val = temp;\r\n}\r\n\r\n\/\/ fix red red at given node\r\nvoid fixRedRed(Node *x) {\r\n    \/\/ if x is root color it black and return\r\n    if (x == root) {\r\n    x-&gt;color = BLACK;\r\n    return;\r\n    }\r\n\r\n    \/\/ initialize parent, grandparent, uncle\r\n    Node *parent = x-&gt;parent, *grandparent = parent-&gt;parent,\r\n        *uncle = x-&gt;uncle();\r\n\r\n    if (parent-&gt;color != BLACK) {\r\n    if (uncle != NULL &amp;&amp; uncle-&gt;color == RED) {\r\n        \/\/ uncle red, perform recoloring and recurse\r\n        parent-&gt;color = BLACK;\r\n        uncle-&gt;color = BLACK;\r\n        grandparent-&gt;color = RED;\r\n        fixRedRed(grandparent);\r\n    } else {\r\n        \/\/ Else perform LR, LL, RL, RR\r\n        if (parent-&gt;isOnLeft()) {\r\n        if (x-&gt;isOnLeft()) {\r\n            \/\/ for left right\r\n            swapColors(parent, grandparent);\r\n        } else {\r\n            leftRotate(parent);\r\n            swapColors(x, grandparent);\r\n        }\r\n        \/\/ for left left and left right\r\n        rightRotate(grandparent);\r\n        } else {\r\n        if (x-&gt;isOnLeft()) {\r\n            \/\/ for right left\r\n            rightRotate(parent);\r\n            swapColors(x, grandparent);\r\n        } else {\r\n            swapColors(parent, grandparent);\r\n        }\r\n\r\n        \/\/ for right right and right left\r\n        leftRotate(grandparent);\r\n        }\r\n    }\r\n    }\r\n}\r\n\r\n\/\/ find node that do not have a left child\r\n\/\/ in the subtree of the given node\r\nNode *successor(Node *x) {\r\n    Node *temp = x;\r\n\r\n    while (temp-&gt;left != NULL)\r\n    temp = temp-&gt;left;\r\n\r\n    return temp;\r\n}\r\n\r\n\/\/ find node that replaces a deleted node in BST\r\nNode *BSTreplace(Node *x) {\r\n    \/\/ when node have 2 children\r\n    if (x-&gt;left != NULL and x-&gt;right != NULL)\r\n    return successor(x-&gt;right);\r\n\r\n    \/\/ when leaf\r\n    if (x-&gt;left == NULL and x-&gt;right == NULL)\r\n    return NULL;\r\n\r\n    \/\/ when single child\r\n    if (x-&gt;left != NULL)\r\n    return x-&gt;left;\r\n    else\r\n    return x-&gt;right;\r\n}\r\n\r\n\/\/ deletes the given node\r\nvoid deleteNode(Node *v) {\r\n    Node *u = BSTreplace(v);\r\n\r\n    \/\/ True when u and v are both black\r\n    bool uvBlack = ((u == NULL or u-&gt;color == BLACK) and (v-&gt;color == BLACK));\r\n    Node *parent = v-&gt;parent;\r\n\r\n    if (u == NULL) {\r\n    \/\/ u is NULL therefore v is leaf\r\n    if (v == root) {\r\n        \/\/ v is root, making root null\r\n        root = NULL;\r\n    } else {\r\n        if (uvBlack) {\r\n        \/\/ u and v both black\r\n        \/\/ v is leaf, fix double black at v\r\n        fixDoubleBlack(v);\r\n        } else {\r\n        \/\/ u or v is red\r\n        if (v-&gt;sibling() != NULL)\r\n            \/\/ sibling is not null, make it red\"\r\n            v-&gt;sibling()-&gt;color = RED;\r\n        }\r\n\r\n        \/\/ delete v from the tree\r\n        if (v-&gt;isOnLeft()) {\r\n        parent-&gt;left = NULL;\r\n        } else {\r\n        parent-&gt;right = NULL;\r\n        }\r\n    }\r\n    delete v;\r\n    return;\r\n    }\r\n\r\n    if (v-&gt;left == NULL or v-&gt;right == NULL) {\r\n    \/\/ v has 1 child\r\n    if (v == root) {\r\n        \/\/ v is root, assign the value of u to v, and delete u\r\n        v-&gt;val = u-&gt;val;\r\n        v-&gt;left = v-&gt;right = NULL;\r\n        delete u;\r\n    } else {\r\n        \/\/ Detach v from tree and move u up\r\n        if (v-&gt;isOnLeft()) {\r\n        parent-&gt;left = u;\r\n        } else {\r\n        parent-&gt;right = u;\r\n        }\r\n        delete v;\r\n        u-&gt;parent = parent;\r\n        if (uvBlack) {\r\n        \/\/ u and v both black, fix double black at u\r\n        fixDoubleBlack(u);\r\n        } else {\r\n        \/\/ u or v red, color u black\r\n        u-&gt;color = BLACK;\r\n        }\r\n    }\r\n    return;\r\n    }\r\n\r\n    \/\/ v has 2 children, swap values with successor and recurse\r\n    swapValues(u, v);\r\n    deleteNode(u);\r\n}\r\n\r\nvoid fixDoubleBlack(Node *x) {\r\n    if (x == root)\r\n    \/\/ Reached root\r\n    return;\r\n\r\n    Node *sibling = x-&gt;sibling(), *parent = x-&gt;parent;\r\n    if (sibling == NULL) {\r\n    \/\/ No sibling, double black pushed up\r\n    fixDoubleBlack(parent);\r\n    } else {\r\n    if (sibling-&gt;color == RED) {\r\n        \/\/ Sibling red\r\n        parent-&gt;color = RED;\r\n        sibling-&gt;color = BLACK;\r\n        if (sibling-&gt;isOnLeft()) {\r\n        \/\/ left case\r\n        rightRotate(parent);\r\n        } else {\r\n        \/\/ right case\r\n        leftRotate(parent);\r\n        }\r\n        fixDoubleBlack(x);\r\n    } else {\r\n        \/\/ Sibling black\r\n        if (sibling-&gt;hasRedChild()) {\r\n        \/\/ at least 1 red children\r\n        if (sibling-&gt;left != NULL and sibling-&gt;left-&gt;color == RED) {\r\n            if (sibling-&gt;isOnLeft()) {\r\n            \/\/ left left\r\n            sibling-&gt;left-&gt;color = sibling-&gt;color;\r\n            sibling-&gt;color = parent-&gt;color;\r\n            rightRotate(parent);\r\n            } else {\r\n            \/\/ right left\r\n            sibling-&gt;left-&gt;color = parent-&gt;color;\r\n            rightRotate(sibling);\r\n            leftRotate(parent);\r\n            }\r\n        } else {\r\n            if (sibling-&gt;isOnLeft()) {\r\n            \/\/ left right\r\n            sibling-&gt;right-&gt;color = parent-&gt;color;\r\n            leftRotate(sibling);\r\n            rightRotate(parent);\r\n            } else {\r\n            \/\/ right right\r\n            sibling-&gt;right-&gt;color = sibling-&gt;color;\r\n            sibling-&gt;color = parent-&gt;color;\r\n            leftRotate(parent);\r\n            }\r\n        }\r\n        parent-&gt;color = BLACK;\r\n        } else {\r\n        \/\/ 2 black children\r\n        sibling-&gt;color = RED;\r\n        if (parent-&gt;color == BLACK)\r\n            fixDoubleBlack(parent);\r\n        else\r\n            parent-&gt;color = BLACK;\r\n        }\r\n    }\r\n    }\r\n}\r\n\r\n\/\/ prints level order for given node\r\nvoid levelOrder(Node *x) {\r\n    if (x == NULL)\r\n    \/\/ return if node is null\r\n    return;\r\n\r\n    \/\/ queue for level order\r\n    queue&lt;Node *&gt; q;\r\n    Node *curr;\r\n\r\n    \/\/ push x\r\n    q.push(x);\r\n\r\n    while (!q.empty()) {\r\n    \/\/ while q is not empty\r\n    \/\/ dequeue\r\n    curr = q.front();\r\n    q.pop();\r\n\r\n    \/\/ print node value\r\n    cout &lt;&lt; curr-&gt;val &lt;&lt; \" \";\r\n\r\n    \/\/ push children to queue\r\n    if (curr-&gt;left != NULL)\r\n        q.push(curr-&gt;left);\r\n    if (curr-&gt;right != NULL)\r\n        q.push(curr-&gt;right);\r\n    }\r\n}\r\n\r\n\/\/ prints inorder recursively\r\nvoid inorder(Node *x) {\r\n    if (x == NULL)\r\n    return;\r\n    inorder(x-&gt;left);\r\n    cout &lt;&lt; x-&gt;val &lt;&lt; \" \";\r\n    inorder(x-&gt;right);\r\n}\r\n\r\npublic:\r\n\/\/ constructor\r\n\/\/ initialize root\r\nRBTree() { root = NULL; }\r\n\r\nNode *getRoot() { return root; }\r\n\r\n\/\/ searches for given value\r\n\/\/ if found returns the node (used for delete)\r\n\/\/ else returns the last node while traversing (used in insert)\r\nNode *search(int n) {\r\n    Node *temp = root;\r\n    while (temp != NULL) {\r\n    if (n &lt; temp-&gt;val) {\r\n        if (temp-&gt;left == NULL)\r\n        break;\r\n        else\r\n        temp = temp-&gt;left;\r\n    } else if (n == temp-&gt;val) {\r\n        break;\r\n    } else {\r\n        if (temp-&gt;right == NULL)\r\n        break;\r\n        else\r\n        temp = temp-&gt;right;\r\n    }\r\n    }\r\n\r\n    return temp;\r\n}\r\n\r\n\/\/ inserts the given value to tree\r\nvoid insert(int n) {\r\n    Node *newNode = new Node(n);\r\n    if (root == NULL) {\r\n    \/\/ when root is null\r\n    \/\/ simply insert value at root\r\n    newNode-&gt;color = BLACK;\r\n    root = newNode;\r\n    } else {\r\n    Node *temp = search(n);\r\n\r\n    if (temp-&gt;val == n) {\r\n        \/\/ return if value already exists\r\n        return;\r\n    }\r\n\r\n    \/\/ if value is not found, search returns the node\r\n    \/\/ where the value is to be inserted\r\n\r\n    \/\/ connect new node to correct node\r\n    newNode-&gt;parent = temp;\r\n\r\n    if (n &lt; temp-&gt;val)\r\n        temp-&gt;left = newNode;\r\n    else\r\n        temp-&gt;right = newNode;\r\n\r\n    \/\/ fix red red violation if exists\r\n    fixRedRed(newNode);\r\n    }\r\n}\r\n\r\n\/\/ utility function that deletes the node with given value\r\nvoid deleteByVal(int n) {\r\n    if (root == NULL)\r\n    \/\/ Tree is empty\r\n    return;\r\n\r\n    Node *v = search(n), *u;\r\n\r\n    if (v-&gt;val != n) {\r\n    cout &lt;&lt; \"No node found to delete with value:\" &lt;&lt; n &lt;&lt; endl;\r\n    return;\r\n    }\r\n\r\n    deleteNode(v);\r\n}\r\n\r\n\/\/ prints inorder of the tree\r\nvoid printInOrder() {\r\n    cout &lt;&lt; \"Inorder: \" &lt;&lt; endl;\r\n    if (root == NULL)\r\n    cout &lt;&lt; \"Tree is empty\" &lt;&lt; endl;\r\n    else\r\n    inorder(root);\r\n    cout &lt;&lt; endl;\r\n}\r\n\r\n\/\/ prints level order of the tree\r\nvoid printLevelOrder() {\r\n    cout &lt;&lt; \"Level order: \" &lt;&lt; endl;\r\n    if (root == NULL)\r\n    cout &lt;&lt; \"Tree is empty\" &lt;&lt; endl;\r\n    else\r\n    levelOrder(root);\r\n    cout &lt;&lt; endl;\r\n}\r\n};\r\n\r\nint main() {\r\nRBTree tree;\r\n\r\ntree.insert(7);\r\ntree.insert(3);\r\ntree.insert(18);\r\ntree.insert(10);\r\ntree.insert(22);\r\ntree.insert(8);\r\ntree.insert(11);\r\ntree.insert(26);\r\ntree.insert(2);\r\ntree.insert(6);\r\ntree.insert(13);\r\n\r\ntree.printInOrder();\r\ntree.printLevelOrder();\r\n\r\ncout&lt;&lt;endl&lt;&lt;\"Deleting 18, 11, 3, 10, 22\"&lt;&lt;endl;\r\n\r\ntree.deleteByVal(18);\r\ntree.deleteByVal(11);\r\ntree.deleteByVal(3);\r\ntree.deleteByVal(10);\r\ntree.deleteByVal(22);\r\n\r\ntree.printInOrder();\r\ntree.printLevelOrder();\r\nreturn 0;\r\n}\r\n<\/pre>\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_16123 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_16123 a\"),jQuery(\"#tab-content_16123\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<p><strong>Output<\/strong><\/p>\n<pre><code>Inorder:\n2 3 6 7 8 10 11 13 18 22 26\n\nLevel order:\n10 7 18 3 8 11 22 2 6 13 26\n\nDeleting 18, 11, 3, 10, 22\n\nInorder: \n2 6 7 8 13 26 \n\nLevel order: \n13 7 26 6 8 2 <\/code><\/pre>\n<p><strong>Conclusion<\/strong><br \/>\nIn this article, we have discussed the Red black tree in data structure. Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. We have also discussed the use cases of Red Black Tree in data structure. How insertion and deletion work, along with how we can rotate a subtree in a Red black data structure. <\/p>\n<h2>Frequently Asked Questions (FAQs)<\/h2>\n<p><strong>Q1. What is the purpose of the red-black tree?<\/strong><br \/>\n<strong>Ans.<\/strong> RB trees are used to construct associative arrays in functional programming. RB trees are used in conjunction with 2-4 trees, a self-balancing data structure in which each node has two, three, or four child nodes.<\/p>\n<p><strong>Q2. In terms of data structure complexity, what is a red-black tree?<\/strong><br \/>\n<strong>Ans.<\/strong> Red-black trees give a logarithmic average and worst-case time complexity for insertion, search, and deletion. Rebalancing has an average time complexity of O(1), with a worst-case complexity of O(log n). <\/p>\n<p><strong>Q3. What exactly is a red-black tree?<\/strong><br \/>\n<strong>Ans.<\/strong> A self-balancing binary search tree is a Red Black Tree. It was invented in 1972 by Rudolf Bayer and termed &quot;symmetric binary B-trees.&quot;<\/p>\n<p><strong>Q4. What exactly is the red-black tree sorting algorithm?<\/strong><br \/>\n<strong>Ans.<\/strong> The red-black tree algorithm is a method for balancing trees. The term is derived from the fact that each node is either red or black, and the color of the node is significant in defining the balance of the tree.<\/p>\n<p><strong>Q5. What is the highest point of the red-black tree algorithm?<\/strong><br \/>\n<strong>Ans.<\/strong> Because red nodes cannot have red children, the path&#8217;s nodes must alternate between red and black. As a result, the path can only be twice as long as the black depth of the tree. As a result, the worst-case height of the tree is O(2 log nb). A red-black tree&#8217;s height is O(log n).<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Red Black Tree is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times. Let us first define a Binary Search Tree before diving into the red black tree. A BST (Binary Search Tree) is a non-linear data structure in which [&hellip;]<\/p>\n","protected":false},"author":52,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[153],"tags":[],"class_list":["post-16121","post","type-post","status-publish","format-standard","hentry","category-tree"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Red Black Tree in Data Structure<\/title>\n<meta name=\"description\" content=\"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Red Black Tree in Data Structure\" \/>\n<meta property=\"og:description\" content=\"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2023-05-05T10:12:05+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\" \/>\n<meta name=\"author\" content=\"Prepbytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Prepbytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Red Black Tree in Data Structure\",\"datePublished\":\"2023-05-05T10:12:05+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\"},\"wordCount\":2152,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\",\"articleSection\":[\"Trees\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\",\"name\":\"Red Black Tree in Data Structure\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\",\"datePublished\":\"2023-05-05T10:12:05+00:00\",\"description\":\"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Trees\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/tree\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Red Black Tree in Data Structure\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Red Black Tree in Data Structure","description":"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/","og_locale":"en_US","og_type":"article","og_title":"Red Black Tree in Data Structure","og_description":"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.","og_url":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2023-05-05T10:12:05+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"10 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Red Black Tree in Data Structure","datePublished":"2023-05-05T10:12:05+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/"},"wordCount":2152,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg","articleSection":["Trees"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/","url":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/","name":"Red Black Tree in Data Structure","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg","datePublished":"2023-05-05T10:12:05+00:00","description":"Red Black Tree in is a type of balanced Binary Search Tree that uses a unique set of principles to ensure that the tree remains balanced at all times.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1683281240390-Red%20Black%20Tree%20in%20Data%20Structure.jpg"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/red-black-tree-in-data-structure\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Trees","item":"https:\/\/prepbytes.com\/blog\/category\/tree\/"},{"@type":"ListItem","position":3,"name":"Red Black Tree in Data Structure"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/16121","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=16121"}],"version-history":[{"count":2,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/16121\/revisions"}],"predecessor-version":[{"id":16162,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/16121\/revisions\/16162"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=16121"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=16121"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=16121"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}