# Section 14.4. Red-Black Trees

[Page 389 ( continued )]

### 14.4. Red-Black Trees

A plain binary search tree (Section 11.3) performs poorly if the tree is not balanced. In the worst case, which occurs if the elements are inserted in order, the tree is linear, so search, insertion, and deletion take linear time. The variation described in this section, the red-black tree , ensures that the tree cannot become significantly imbalanced , so these operations run in logarithmic time in the worst case. In the Java collections framework, the classes TreeSet and TreeMap use red-black trees.

#### Properties of Red-Black Trees

A red-black tree (Figure 14-29) is a binary search tree in which each node has a color , either red or black. The tree has the following properties:

• The root is black.

• [Page 390]
• No red node has a red child.

• Consider each path from the root, through several descendants, down to a null child. These are the paths followed in unsuccessful searches. All such paths must contain the same number of black nodes.

##### Figure 14-29. In a red-black tree, every path from the root to a null child contains the same number of black nodes (for this tree, three). Lightly shaded nodes are red.

These properties ensure that the tree cannot be significantly imbalanced. Specifically, suppose the shortest path to a null child contains d nodes. The longest path can contain at most 2 d nodes. This happens when the short path is all black, while the long path alternates between black and red. It is not possible for one side of the tree (or any subtree ) to become very tall while the other side remains short.

It can be proven (although we will not bother to do so) that the height of a red-black tree containing n nodes is in O(log n ). The running times of search, insertion, and deletion are proportional to the height of the tree, so these operations run in logarithmic time. The challenge is to maintain the properties of the red-black tree while performing these operations.

#### Search

Search in red-black trees is identical to search in binary search trees.

#### Insertion

Insertion in a red-black tree starts out like insertion in a binary search tree. We start at the root and descend until we either find the target or try to descend from a leaf. In the latter case, the target is not present in the tree, so we attach a new, red leaf.

Unfortunately, this may invalidate the red-black tree. Specifically, the new node may be a child of another red node, which is illegal. We fix this by working our way back up the tree, changing colors and rearranging nodes. This repair operation, while complicated, takes time proportional to the height of the tree, so the total running time for insertion is still in O(log n ).

[Page 391]

A key step in tree repair is rotation (Figure 14-30). When we rotate, we replace a node with one of its children. This is a strictly local operation, affecting only a few nodes. The ordering of the nodes remains valid. In the Figure, the subtree rooted at 5 contains only values between 3 and 7, so it is in the correct position both before and after the rotation.

##### Figure 14-30. Rotation within the subtree rooted at 3. (3's parent, if any, and the proper descendants of 1, 5, and 9 are not shown.) Node 3 moves down to the left, while node 7 moves up. Only the three relationships shown by thick lines are changed; other nodes, such as node 5's proper descendants, are unaffected. Rotation is independent of color.

Color changes and rotations can be used to repair a red-black tree after inserting a new red node. The plan is to work back up the tree in several steps, performing color changes and rotations . Each step either fixes the tree or moves the problem closer to the root. If we get to the root and still have a red node, we can simply color it black. Since each step takes a constant amount of time, the whole repair process takes time proportional to the height of the tree.

Let node be the newly added node. Suppose node is red and has a red parent. How do we fix this? There are three cases to consider, depending on the color of node 's parent's sibling (that is, node 's aunt) and on whether node is a left or right child. We describe the cases below in order of increasing complexity.

First, if node has a red aunt, we simply change the colors of node 's parent, aunt, and grandparent (Figure 14-31). This makes the grandparent red (see Exercise 14.19). Since the great-grandparent may also be red, we may have to do some repair there, too, but we're getting closer to the root.

##### (This item is displayed on page 392 in the print version)

Second, suppose node has a black aunt. If node and its parent are both left children (or both right children), we call node an outer child . In this case, we change the colors of the parent and grandparent, then rotate the grandparent in the other direction (Figure 14-32). No further work is necessary at this point.

##### (This item is displayed on page 392 in the print version)

The third case occurs when node has a black aunt and is an inner child for example, if node is a right child but its parent is a left child (Figure 14-33). A rotation makes the parent an outer child of node . This new outer child is red and has a red parent, so we repair it as before.

[Page 393]

#### Deletion

We now move on to deletion from a red-black tree. This is even more complicated than insertion, but the idea is the same: perform the operation as usual, then repair the tree if necessary.

Splicing out a red node can never cause any problems. If we splice out a black node, on the other hand, search paths that used to lead through this node now have one fewer black node than other search paths. Let node be the child of the node that was spliced out. If node is red, we can simply color it black to cancel out the problem. Otherwise , we work up the tree looking for a red node. There are four cases to consider this time.

In the first case, if node 's sibling is black and has two black children, we color the sibling red (Figure 14-34). Now both the subtree rooted at node and the subtree rooted at its sibling are short a black node. In other words, the subtree rooted at node 's parent is short a black node. We may have to make repairs there. That's closer to the root, so we're making progress.

##### Figure 14-34. Repairing after deletion when node 's sibling is black and has two black children. The parent, which may be of either color, becomes the new node .

In the second case, node 's sibling is black and the sibling's outer child is red (Figure 14-35). Some color changes and a rotation here completely eliminate the problem.

##### Figure 14-35. Repairing after deletion when node 's sibling is black and has a red outer child. The sibling gets the parent's color, the parent and outer child become black, and there is a rotation.

[Page 394]

In the third case, node 's sibling is black, has a black outer child, and has a red inner child (Figure 14-36). Color changes and a rotation transform this into the red outer child situation just covered.

##### Figure 14-36. Repairing after deletion when node 's sibling is black, has a black outer child, and has a red inner child (left). Color changes and a rotation transform this into the red outer child case (middle), which is handled as before (right).

The fourth case occurs when node 's sibling is red (Figure 14-37). Color changes and a rotation transform this into one of the other cases.

#### Implementation

The code for red-black trees is fairly complicated. In order to simplify things, we employ a couple of special tricks.

First, in place of null , we use references to a special black node called a sentinel (Figure 14-38). The sentinel indicates that we can't go any farther, but it is an actual node, so we can invoke methods on it. Thus, for example, we can ask for the color of a node's left child and get an answer even if the node doesn't really have a left child. Thus, we can say

[Page 395]

```if (node.getLeft().isBlack()) {
```

```if ((node.getLeft() == null)  (node.getLeft().isBlack())) {
```

To save space, we use a single sentinel instance to represent all nonexistent children.

##### Figure 14-38. A red-black tree (upper left) and its implementation. Each node has references to its children and its parent. Where there is no child or parent, references are to a sentinel node (shaded).

Second, we keep track of the parent of each node. This is similar to the idea of a doubly linked list (Section 6.1). The root's parent is the sentinel.

[Page 396]

The code for the RedBlackNode class is given in Figure 14-39. Some methods, such as isRed() and getColor() , are somewhat redundant, but they make the code in RedBlackTree easier to understand.

##### Figure 14-39. The RedBlackNode class.
 ``` 1 /** Node in a RedBlackTree. */ 2 public class RedBlackNode> { 3 4 /** Black node color. */ 5 public static final boolean BLACK = false; 6 7 /** Red node color. */ 8 public static final boolean RED = true; 9 10 /** Color of this node, BLACK or RED. */ 11 private boolean color ; 12 13 /** Item associated with this node. */ 14 private E item ; 15 16 /** Left child of this node. */ 17 private RedBlackNode left ; 18 19 /** Parent of this node. */ 20 private RedBlackNode parent ; 21 22 /** Right child of this node. */ 23 private RedBlackNode right ; 24 25 /** Used for constructing a sentinel. */ 26 protected RedBlackNode () { 27 color = BLACK; 28 // All other fields are irrelevant 29 } 30 31 /** 32 * The new node is red and both of its children are sentinel. 33 * The node's parent is NOT set by this constructor. 34 */ 35 public RedBlackNode (E item, RedBlackNode sentinel) { 36 color = RED; 37 this.item = item; 38 left = sentinel; 39 right = sentinel; 40 } 41 ``` [Page 397] ``` 42 /** 43 * Return this node's left (if direction is negative) or right 44 * (otherwise) child. 45 */ 46 public RedBlackNode getChild (int direction) { 47 if (direction < 0) { 48 return left; 49 } 50 return right; 51 } 52 53 /** Return the color of this node. */ 54 public boolean getColor () { 55 return color; 56 } 57 58 /** Return the item associated with this node. */ 59 public E getItem () { 60 return item; 61 } 62 63 /** Return this node's left child. */ 64 public RedBlackNode getLeft () { 65 return left; 66 } 67 68 /** Return this node's parent. */ 69 public RedBlackNode getParent () { 70 return parent; 71 } 72 73 /** Return this node's right child. */ 74 public RedBlackNode getRight () { 75 return right; 76 } 77 78 /** Return true if this node has two black children. */ 79 public boolean hasTwoBlackChildren () { 80 return left.isBlack() && right.isBlack(); 81 } 82 83 /** Return true if this node is black. */ 84 public boolean isBlack () { 85 return color == BLACK; 86 } 87 ``` [Page 398] ``` 88 /** Return true if this node is red. */ 89 public boolean isRed () { 90 return color == RED; 91 } 92 93 /** 94 * Set this node's left (if direction is negative) or right 95 * (otherwise) child. 96 */ 97 public void setChild (int direction, RedBlackNode child) { 98 if (direction < 0) { 99 left = child; 100 } else { 101 right = child; 102 } 103 } 104 105 /** Make this node black. */ 106 public void setBlack () { 107 color = BLACK; 108 } 109 110 /** Set the color of this node. */ 111 public void setColor (boolean color) { 112 this.color = color; 113 } 114 115 /** Set the item associated with this node. */ 116 public void setItem (E item) { 117 this.item = item; 118 } 119 120 /** Set the parent of this node. */ 121 public void setParent (RedBlackNode parent) { 122 this.parent = parent; 123 } 124 125 /** Make this node red. */ 126 public void setRed () { 127 color = RED; 128 } 129 130 } ```

The trivial parts of the RedBlackTree class are given in Figure 14-40. When the tree is empty, the root is the sentinel.

[Page 399]
##### Figure 14-40. Easy parts of the RedBlackTree class.
 ``` 1 /** A red-black tree of Comparables. */ 2 public class RedBlackTree> 3 implements Set { 4 5 /** The root node of this tree. */ 6 private RedBlackNode root ; 7 8 /** All "null" node references actually point to this node. */ 9 private RedBlackNode sentinel ; 10 11 /** The tree is initially empty. */ 12 public RedBlackTree () { 13 sentinel = new RedBlackNode(); 14 root = sentinel; 15 } 16 17 public int size () { 18 return size(root); 19 } 20 21 /** Return the size of the subtree rooted at node. */ 22 protected int size (RedBlackNode node) { 23 if (node == sentinel) { 24 return 0; 25 } else { 26 return 1 + size(node.getLeft()) + size(node.getRight()); 27 } 28 } 29 30 } ```

The code for the RedBlackTree version of contains() (Figure 14-41) is somewhat shorter than the binary search tree version, because the RedBlackNode class provides a method getChild() which accepts a direction as an argument.

##### Figure 14-41. The contains() method from the RedBlackTree class.
 ``` 1 public boolean contains(E target) { 2 RedBlackNode node = root; 3 while (node != sentinel) { 4 int comparison = target.compareTo(node.getItem()); ``` [Page 400] ``` 5 if (comparison == 0) { 6 return true; 7 } else { 8 node = node.getChild(comparison); 9 } 10 } 11 return false; 12 } ```

Insertion in a red-black tree starts out like insertion in a binary search tree (Figure 14-42). We start at the root and descend until we either find the target or reach the sentinel. We then attach a new, red node at this point.

##### Figure 14-42. The add() and compare() methods from the RedBlackTree class. The compare() method makes the code slightly clearer. Lines 2631 are there so that compare() works even if child is the sentinel, which has a null item.
 ``` 1 public void add (E target) { 2 RedBlackNode targetNode 3 = new RedBlackNode(target, sentinel); 4 RedBlackNode parent = sentinel; 5 RedBlackNode node = root; 6 int comparison = 0; 7 while (node != sentinel) { 8 parent = node; 9 comparison = compare(targetNode, node); 10 if (comparison == 0) { 11 return; 12 } 13 node = node.getChild(comparison); 14 } 15 linkParentAndChild(parent, targetNode, comparison); 16 if (parent == sentinel) { 17 root = targetNode; 18 } 19 repairAfterInsertion(targetNode); 20 } 21 22 /** 23 * Return a negative number if child is to the left of parent, 24 * positive otherwise. 25 */ 26 protected int compare (RedBlackNode child, 27 RedBlackNode parent) { 28 if (child == parent.getLeft()) { 29 return -1; 30 } 31 if (child == parent.getRight()) { 32 return 1; 33 } 34 return child.getItem().compareTo(parent.getItem()); 35 } ```

[Page 401]

The linkParentAndChild() method is given in Figure 14-43. The argument dir allows us to specify whether child should become a left or right child of parent .

##### Figure 14-43. The linkParentAndChild() method from RedBlackTree.
 ``` 1 /** 2 * Set child to be the left (if dir is negative) or right 3 * (otherwise) child of parent. 4 */ 5 protected void linkParentAndChild (RedBlackNode parent, 6 RedBlackNode child, 7 int dir) { 8 parent.setChild(dir, child); 9 child.setParent(parent); 10 } ```
{% if main.adsdop %}{% include 'adsenceinline.tpl' %}{% endif %}

The code for repairAfterInsertion() and rotate() is given in Figure 14-44. The loop runs until node has a black parent. If node is the root (whose parent is the black sentinel), we have to color node black, since the root of a red-black tree must be black.

##### Figure 14-44. The repairAfterInsertion() method is aided by rotate() .
 ``` 1 /** Restore the tree to validity after inserting a node. */ 2 protected void repairAfterInsertion (RedBlackNode node) { 3 while (node.getParent().isRed()) { 4 RedBlackNode parent = node.getParent(); 5 RedBlackNode grandparent = parent.getParent(); 6 RedBlackNode aunt 7 = grandparent.getChild(-compare(parent, grandparent)); 8 if (aunt.isRed()) { // Red aunt 9 parent.setBlack(); 10 aunt.setBlack(); 11 grandparent.setRed(); 12 node = grandparent; 13 } else { 14 int nodeComparison = compare(node, parent); 15 int parentComparison = compare(parent, grandparent); 16 if (nodeComparison != parentComparison) { // Inner child 17 rotate(nodeComparison, parent); 18 node = parent; 19 } 20 node.getParent().setBlack(); // Outer child 21 node.getParent().getParent().setRed(); 22 rotate(parentComparison, node.getParent().getParent()); 23 } 24 } 25 root.setBlack(); 26 } 27 ``` [Page 402] ``` 28 /** 29 * Move node's left (if dir is negative) or right (otherwise) 30 * child up into its place. Move node down on the other side. 31 */ 32 protected void rotate (int dir, RedBlackNode node) { 33 RedBlackNode child = node.getChild(dir); 34 RedBlackNode parent = node.getParent(); 35 if (node.getParent() == sentinel) { 36 root = child; 37 } 38 linkParentAndChild(node, child.getChild(-dir), dir); 39 linkParentAndChild(parent, child, compare(node, parent)); 40 linkParentAndChild(child, node, -dir); 41 } ```

We now move on to deletion from a red-black tree. This is even more complicated than insertion, but the idea is the same: perform the operation as usual, then repair the tree if necessary. The easy parts are shown in Figure 14-45.

##### Figure 14-45. The remove() method invokes spliceOut() , which may invoke repairAfterDeletion() .
 ``` 1 /** Return the inorder successor of node. */ 2 protected RedBlackNode inorderSuccessor (RedBlackNode node) { 3 RedBlackNode descendant = node.getRight(); 4 while (descendant.getLeft() != sentinel) { 5 descendant = descendant.getLeft(); 6 } 7 return descendant; 8 } 9 10 public void remove (E target) { 11 RedBlackNode node = root; 12 while (node != sentinel) { 13 int comparison = target.compareTo(node.getItem()); 14 if (comparison == 0) { 15 if ((node.getLeft() == sentinel) 16 (node.getRight() == sentinel)) { 17 spliceOut(node); 18 } else { 19 RedBlackNode successor = inorderSuccessor(node); 20 node.setItem(successor.getItem()); 21 spliceOut(successor); 22 } 23 return; ``` [Page 403] ``` 24 } else { 25 node = node.getChild(comparison); 26 } 27 } 28 } 29 30 /** Splice node out of the tree. */ 31 protected void spliceOut (RedBlackNode node) { 32 RedBlackNode child; 33 if (node.getLeft() != sentinel) { 34 child = node.getLeft(); 35 } else { 36 child = node.getRight(); 37 } 38 linkParentAndChild(node.getParent(), 39 child, 40 compare(node, node.getParent())); 41 if (node == root) { 42 root = child; 43 } 44 if (node.isBlack()) { 45 repairAfterDeletion(child); 46 } 47 } ```

The code for repairAfterDeletion() is given in Figure 14-46.

##### Figure 14-46. The repairAfterDeletion() method.
 ``` 1 /** Restore the tree to validity after a deletion. */ 2 protected void repairAfterDeletion(RedBlackNode node) { 3 while ((node != root) && (node.isBlack())) { 4 RedBlackNode parent = node.getParent(); 5 int comparison = compare(node, parent); 6 RedBlackNode sibling = parent.getChild(-comparison); 7 if (sibling.isRed()) { // Red sibling 8 sibling.setBlack(); 9 parent.setRed(); 10 rotate(-comparison, parent); 11 sibling = node.getParent().getChild(-comparison); ``` [Page 404] ``` 12 } 13 if (sibling.hasTwoBlackChildren()) { // Two black children 14 sibling.setRed(); 15 node = node.getParent(); 16 } else { 17 if (sibling.getChild(-comparison).isBlack()) { 18 // Red inner child 19 sibling.getChild(comparison).setBlack(); 20 sibling.setRed(); 21 rotate(comparison, sibling); 22 sibling = parent.getChild(-comparison); 23 } 24 sibling.setColor(parent.getColor()); // Red outer child 25 parent.setBlack(); 26 sibling.getChild(-comparison).setBlack(); 27 rotate(-comparison, parent); 28 node = root; 29 } 30 } 31 node.setBlack(); 32 } ```

#### Exercises

 14.17 Prove that a red node must have either zero or two children. 14.18 What is the tallest possible linear red-black tree? 14.19 If a newly inserted node's parent is red (before repairing the tree), its grandparent must be black. Why? 14.2 The deletion repair case shown in Figure 14-37 makes node lower in the tree. Why is there no danger that this could lead to an infinite loop, where no progress is made toward the root? (Hint: What is the color of node 4's right child?)