Red-Black Trees
Red-black trees are one of many search-tree schemes that are balanced in order to guarantee that basic dynamic-set operations take $Θ(log_2 \;n)$ time in the worst case. [1] A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK. Every red-black tree should satisfy the following red-black properties: [1]
As a matter of convenience in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. Its color attribute is BLACK , and its other attributes - p, left, right, and key—can take on arbitrary values. Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, that approach would waste space. [1]
We can implement the dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR , and PREDECESSOR in $Θ(log_2 \;n)$ time on red-black trees. [1]
Because TREE-INSERT and TREE-DELETE routines modify the tree, the result may violate the red-black properties enumerated before. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure. We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. The pseudocode for LEFT-ROTATE is given below. [1]
However, I am not going to explain red-black tree INSERT, DELETE and other auxiliary procedures here, since the complete treatment of those algorithms is beyond the scope of this article. But the interested reader is directed to Introduction to Algorithms [1] which is the bible in the field. For the remainder of this article, I’ll walk you through a couple of exercises with a sample implementation of the red-black tree. This sample implementation allows us to insert values into the tree, delete values from the tree and print the tree structure in human readable format. This helps us to validate the output we get after executing the program. Here’s the sample code.
After inserting all the nodes, the resulting red-black tree should look like this.
And upon execution with the above input, our program prints this output.
38 is the BLACK color root
19 is the left child of 38 with color RED
12 is the left child of 19 with color BLACK
8 is the left child of 12 with color RED
31 is the right child of 19 with color BLACK
41 is the right child of 38 with color BLACK
That implies our program behaves as expected. Next let’s move on and delete few nodes from our red-black tree.
After deleting node with key 8, the resulting red-black tree should be something like this.
Delete 8:
And our program prints the same structure too.
38 is the BLACK color root
19 is the left child of 38 with color RED
12 is the left child of 19 with color BLACK
31 is the right child of 19 with color BLACK
41 is the right child of 38 with color BLACK
In subsequent deletion actions, I’ll just show you the expected red-black tree which preserves red-black properties along with what our program prints.
Delete 12:
38 is the BLACK color root
19 is the left child of 38 with color BLACK
31 is the right child of 19 with color RED
41 is the right child of 38 with color BLACK
Delete 19:
38 is the BLACK color root
31 is the left child of 38 with color BLACK
41 is the right child of 38 with color BLACK
Delete 31:
38 is the BLACK color root
41 is the right child of 38 with color RED
Delete 38:
41 is the BLACK color root
Delete 41:
NIL is the BLACK color root
Now let’s see how RB-DELETE-FIXUP restores red-black properties 2 and 4.
Case 1 transforms to 2, 3, 4. If case 2 terminates, the root of the subtree (the new x) is set to black. Case 3, transform to 4. In case 4, the root (the new x) is set to black.
Suppose that both x and x.p are red in RB-DELETE. This can only happen in the else-case of line 9. Since we are deleting from a red-black tree, the other child of y.p which becomes x's sibling in the call to RB-TRANSPLANT on line 14 must be black, so x is the only child of x.p which is red. The while-loop condition of RB-DELETE-FIXUP(T,x) is immediately violated so we simply set x.color = black, restoring property 4.
- Every node is either red or black.
- The root is black.
- Every leaf ( NIL ) is black.
- If a node is red, then both its children are black.
- For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
As a matter of convenience in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. Its color attribute is BLACK , and its other attributes - p, left, right, and key—can take on arbitrary values. Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, that approach would waste space. [1]
We can implement the dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR , and PREDECESSOR in $Θ(log_2 \;n)$ time on red-black trees. [1]
Because TREE-INSERT and TREE-DELETE routines modify the tree, the result may violate the red-black properties enumerated before. To restore these properties, we must change the colors of some of the nodes in the tree and also change the pointer structure. We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. The pseudocode for LEFT-ROTATE is given below. [1]
However, I am not going to explain red-black tree INSERT, DELETE and other auxiliary procedures here, since the complete treatment of those algorithms is beyond the scope of this article. But the interested reader is directed to Introduction to Algorithms [1] which is the bible in the field. For the remainder of this article, I’ll walk you through a couple of exercises with a sample implementation of the red-black tree. This sample implementation allows us to insert values into the tree, delete values from the tree and print the tree structure in human readable format. This helps us to validate the output we get after executing the program. Here’s the sample code.
Exercises
13.3-2
Show the red-black trees that result after successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty red-black tree. [1]After inserting all the nodes, the resulting red-black tree should look like this.
And upon execution with the above input, our program prints this output.
38 is the BLACK color root
19 is the left child of 38 with color RED
12 is the left child of 19 with color BLACK
8 is the left child of 12 with color RED
31 is the right child of 19 with color BLACK
41 is the right child of 38 with color BLACK
That implies our program behaves as expected. Next let’s move on and delete few nodes from our red-black tree.
13.4-3
In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys 41; 38; 31; 12; 19; 8 into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order 8; 12; 19; 31; 38; 41. [1]After deleting node with key 8, the resulting red-black tree should be something like this.
Delete 8:
And our program prints the same structure too.
38 is the BLACK color root
19 is the left child of 38 with color RED
12 is the left child of 19 with color BLACK
31 is the right child of 19 with color BLACK
41 is the right child of 38 with color BLACK
In subsequent deletion actions, I’ll just show you the expected red-black tree which preserves red-black properties along with what our program prints.
Delete 12:
38 is the BLACK color root
19 is the left child of 38 with color BLACK
31 is the right child of 19 with color RED
41 is the right child of 38 with color BLACK
Delete 19:
38 is the BLACK color root
31 is the left child of 38 with color BLACK
41 is the right child of 38 with color BLACK
Delete 31:
38 is the BLACK color root
41 is the right child of 38 with color RED
Delete 38:
41 is the BLACK color root
Delete 41:
NIL is the BLACK color root
Now let’s see how RB-DELETE-FIXUP restores red-black properties 2 and 4.
Exercises
13.4-1
Argue that after executing RB-DELETE-FIXUP, the root of the tree must be black. [1]Case 1 transforms to 2, 3, 4. If case 2 terminates, the root of the subtree (the new x) is set to black. Case 3, transform to 4. In case 4, the root (the new x) is set to black.
13.4-2
Argue that if in RB-DELETE both x and x.p are red, then property 4 is restored by the call to RB-DELETE-FIXUP(T, x). [1]Suppose that both x and x.p are red in RB-DELETE. This can only happen in the else-case of line 9. Since we are deleting from a red-black tree, the other child of y.p which becomes x's sibling in the call to RB-TRANSPLANT on line 14 must be black, so x is the only child of x.p which is red. The while-loop condition of RB-DELETE-FIXUP(T,x) is immediately violated so we simply set x.color = black, restoring property 4.
Comments
Post a Comment