{"id":357,"date":"2018-07-19T06:17:07","date_gmt":"2018-07-19T06:17:07","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=357"},"modified":"2018-12-12T10:39:04","modified_gmt":"2018-12-12T10:39:04","slug":"red-black-trees-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/red-black-trees-i\/","title":{"rendered":"Red Black Trees -I"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of balanced binary search trees and discussed one such tree \u2013 the AVL tree. In this module we will discuss another balanced binary search tree \u2013 the Red Black tree.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand the concept of Red Black Trees\r\n\r\n\u2022 To discuss the properties of Red Black Trees\r\n\r\n\u2022 To describe rotation of Red Black Trees\r\n\r\n\u2022 To explain the Insertion into Red Black Trees\r\n\r\n \r\n\r\n25.1 Introduction to Red Black Trees<\/strong>\r\n\r\n \r\n

Red-black trees are a variation of binary search trees to ensure that the tree is balanced<\/em><\/strong>. In this case as in balanced trees the height is of the O<\/em>(log n<\/em>), where n <\/em>is the number of nodes. Hence the operations associated with Red-black trees take O<\/em>(log n<\/em>) time in the worst case. However in the case of Red-black trees each node requires an extra bit when compared to binary search trees since each node is now associated with a bit indicating the color attribute which can be either red<\/strong> or black<\/strong>. The nodes of Red-black trees inherit all the other attributes associated with a node of the binary search tree such as key, and pointers to the left sub-tree, right sub-tree and the parent. Now in the case of Red-black trees all empty trees (leaves) are colored black. This is normally carried out by setting the single sentinel associated with color as nil<\/em>, for all the leaves of red-black tree T<\/em>, with color<\/em>[nil<\/em>] = black. Here we assume that the leaf nodes null nodes are set as nil. The parent of the root is also set to nil.<\/p>\r\n \r\n\r\n25.2 Red-black Properties<\/strong>\r\n\r\n \r\n

As we have already discussed the Red-black tree data structure requires an extra one-bit color field in each node. Every node is either red or black. Some of the properties associated with the Red-black tree are:<\/p>\r\n \r\n

    \r\n \t
  1. Every node in a Red-black tree is either red or black<\/li>\r\n \t
  2. The root is black<\/strong> and every leaf (<\/span>nil<\/em>) is <\/span>black.<\/strong> We assume that every node that is not a leaf has 2 children (one or both of which may be nil nodes)<\/span><\/li>\r\n \t
  3. If a node is red<\/strong>, then its parent is <\/span>black<\/strong>. In other words, if a node is <\/span>red<\/strong>, then both of its children are\u00a0<\/span>black.<\/strong> This means that Red-black trees do not allow 2 consecutive red nodes on a path.<\/span><\/li>\r\n \t
  4. All simple paths from any node x<\/em> to a descendant leaf have the same number of black nodes = black-Height(<\/span>x<\/em>).<\/span><\/li>\r\n<\/ol>\r\n<\/div>\r\n
    \r\n\r\n \r\n\r\n25.2.1 Red-black Tree \u2013 Example<\/strong>\r\n\r\n \r\n

    Now let us understand the properties of Red-black trees using an example (Figure 25.1). For convenience we use a sentinel NIL[T] to represent all the NIL nodes at the leafs. NIL[T] has the same fields as an ordinary node. As we have discussed all leaf nodes are colored black.<\/p>\r\n \r\n\r\nColor[NIL[T]] = BLACK\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

    Figure 25.2 shows the properties for a given Red-black tree. As you can see all nodes of the tree are colored as either red or black (property 1). The root node (10<\/strong>) and all leaf nodes are colored black (property 2). All the red nodes 1, 5, 3, 25 and 60<\/strong> have black parents (property 3). In addition as per property 4 all these red nodes have both<\/p>\r\n\r\n<\/div>\r\n \r\n

    \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

    children black and these red nodes cannot occur consequently on a path in the Red-black tree. Moreover the number of black nodes on a simple path from any black node to a descendent leaf node is the same (property 5). Example the number of black nodes from 10<\/strong> to leaf node through any path (10-7-3-1-Nil, 10-7-8-Nil, 10-7-3-5-Nil) <\/strong>is 3 where the count does not include the node itself.<\/p>\r\n \r\n\r\n25.2.3 Black-Height of a Node<\/strong>\r\n\r\n \r\n

    Based on property 5, we can also define the black-height of a node. In general the height of a nodeis defined as the number of edges in the longest path to a leaf.<\/p>\r\n \r\n

    Black-height of a node x: bh(x) is the number of black nodes (including NIL) on the path from x to a leaf, without counting node x. In the example shown in Figure 25.3 the red node 50 has both height and black-height as 1 but 47 has height 2 and black height as 1 since there is only one black node (Nil) in the path from 47 (47-50-Nil)<\/strong> to the leaf excluding 47.<\/strong><\/p>\r\n\"\"\r\n\r\n \r\n\r\n25.3 Implementing Red-black Operations<\/strong>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n

    As in any data structure we can classify the operations associated with it as access operations and update operations. Access operations include searching for an element, finding the minimum or maximum element in the red-black tree, finding the predecessor, successor etc. Update operations include inserting elements into and deleting elements from the red-black tree. Remember that a red-black tree is basically a binary search tree (BST) and we can use all the BST algorithms without change by simply ignoring the colors associated with each node. The worst-case time complexity depends on h, the height of the tree O(h) = O(log n). Now after performing the BST operations, we have to ensure that the modified tree will still obey the red-black tree properties. In order to maintain the red-black tree properties we need to carry out some rotations of the nodes of the tree.<\/p>\r\n \r\n\r\n25.4 Rotations <\/strong>and Red-Black-Trees<\/strong>\r\n\r\n \r\n

    Rotations are the basic tree-restructuring operation for almost all balanced<\/em> search trees for the purpose of rebalancing a balanced tree. These operations are necessary for re-structuring the red-black tree after insert and delete operations on red-black trees. The local operation in a search tree should ensure the binary search tree property.<\/p>\r\n \r\n

    Rotations take a red-black-tree and a node within the tree and together with some node re-coloring they help restore the red-black-tree property. These rotations change some of the connections between nodes and also ensure that the binary-search tree property is maintained. Rotation takes a red-black-tree and a node, appropriately changes pointers to change the local structure, and ensures that the binary-search-tree property is not violated. There are two types of rotations left rotation and right rotation which are inverse of each other. As is shown in Figure 25.4 during Left-Rotate(T,x), x is rotated to the left and now becomes the left sub-tree of y which now becomes the root. The left sub-tree \u03b2 of y becomes the new right sub-tree of x. Now the inverse of the left rotate is right rotate where Right-Rotate (T,y) right rotates about the node y. Rotate operations are used for restructuring the tree after insert and delete operations on red-black trees. These rotations are general rotations discussed in earlier modules.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

    \r\n

    Figure 25.4 Left and Right Rotate<\/strong><\/p>\r\n \r\n\r\n25.4.1 Left Rotations<\/strong>\r\n\r\n \r\n

    When performing left rotation on a node x we assume that the right child of x (y) is not NIL. The basic idea is to pivot around the link from x to y where y is the root of the right sub-tree of the node x. We make y the new root of the sub-tree and x becomes y\u2019s left child while y\u2019s left child becomes x\u2019s right child.<\/p>\r\n\"\"\r\n\r\n \r\n\r\n25.4.1.1<\/strong>\u00a0\u00a0\u00a0\u00a0 Example of Left Rotation<\/strong>\r\n\r\n \r\n

    Figure 25.6 shows an example of left rotation of 12 with 9 as the pivot. Now 12 is rotated left and now becomes the left sub-tree of 9\u2019s parent 7. The left sub-tree of 12 rooted at 11 now becomes the right sub-tree of 9.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n 25.4.2 Right Rotation<\/strong>\r\n\r\n \r\n

    In general, rotation of a node for re-balancing a balanced tree involves pointer manipulation. In the case of right rotation of node x about y where x is left sub-tree of y (Figure 25.5). We assume that for a right rotation on a node x, the left child of x of y is not NIL. When we pivot around the link from y to x, we make x the new root of the sub-tree and y becomes x\u2019s right child and x\u2019s right child becomes y\u2019s left child.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

    \r\n\r\n25.5 Modifying Operations<\/strong>\r\n\r\n \r\n

    As is generally the case the operations INSERT and DELETE cause modifications to the red-black tree. After we carry out the operation, we need to change color and restructure the links of the tree via \u201crotations\u201d<\/em><\/strong> we have discussed in the previous section.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n25.6 Insertion \u2013 Red-Black Tree<\/strong>\r\n\r\n \r\n

    We need to insert a new node z into a red-black-tree. The first step is the insertion of the node z into the tree as is done for an ordinary binary search tree. We color the new node as red and then go on to restore the red-black-tree properties. Now let us consider how to color the new node. Let us consider the example given in Figure 25.9. Let us assume that we have inserted 35 and colored it red . We see that property 4 is violated. As we know property 4 states that If a node is red<\/strong>, then both of its children should be black<\/strong> and Red-black trees do not allow 2 consecutive red nodes on a path \u2013 38 and 35 two consecutive red nodes. Let us assume that we have inserted 14 and colored it black, in this case property 5 which states that all\u00a0paths from a node to its leaves contain the same number of black nodes is violated.<\/span><\/p>\r\n\r\n<\/div>\r\n

    \r\n\r\n \r\n\r\nHence we need to carry out modifications to restore the red-black tree property.\r\n\r\n \r\n\r\n\"\"\r\n\r\n25.6.1 Insertion in Detail<\/strong>\r\n\r\n \r\n

    The first step of insertion is creation of a new node with the data element and insertion of the new node into the Red-black tree using the binary search tree insertion module. Next the new node needs to be assigned a color. If we make the node black there may be the case of one root-to-external-node path has an extra black node (black pointer). This particular type of problem is hard to rectify. We could make the node red there may be the case of one root-to-external-node path may have two consecutive red nodes (pointers). This problem can be remedied by color flips and\/or a rotation. In case there is a violation of property, we move this violation of property 3 up the tree, by recoloring until it can be fixed with rotations and recoloring.<\/p>\r\n \r\n\r\n25.6.2 Red-Black Trees: The Problem with Insertion<\/strong>\r\n\r\n \r\n

    Let us assume that we are going to insert 8 (Figure 25.10), the place where it is inserted is decided by the binary search property and let us color it red.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n

    Let us assume that now we want to insert 11, it cannot be colored red (violation of property 3) and cannot be colored black (violation of property 4). The solution is to rotate and recolor the node black as shown in Figure 25.11. In the following section we will discuss the different methods needed for rebalancing.<\/p>\r\n\r\n<\/div>\r\n \r\n

    \r\n\r\n\"\"\r\n\r\n \r\n\r\n \r\n\r\n25.7 Red-Black Tree \u2013 Rebalancing after Insertion<\/strong>\r\n\r\n \r\n

    Now in order to explain the cases of rebalancing we will define the concept of uncle of a node x is the sibling of the parent of x. Now there are 3 cases where rebalancing will be carried out<\/p>\r\n \r\n\r\n25.7.1 Case 1<\/strong>\r\n\r\n \r\n\r\nConditions for case 1 (Figure 25.12 (a))<\/strong>\r\n