Section 14.4. Red-Black Trees
14.4.
|
1 /** Node in a RedBlackTree. */ 2 public class RedBlackNode<E extends Comparable<E>> { 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<E> left ; 18 19 /** Parent of this node. */ 20 private RedBlackNode<E> parent ; 21 22 /** Right child of this node. */ 23 private RedBlackNode<E> 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<E> sentinel) { 36 color = RED; 37 this.item = item; 38 left = sentinel; 39 right = sentinel; 40 } 41 42 /** 43 * Return this node's left (if direction is negative) or right 44 * (otherwise) child. 45 */ 46 public RedBlackNode<E> 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<E> getLeft () { 65 return left; 66 } 67 68 /** Return this node's parent. */ 69 public RedBlackNode<E> getParent () { 70 return parent; 71 } 72 73 /** Return this node's right child. */ 74 public RedBlackNode<E> 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 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<E> 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<E> parent) { 122 this.parent = parent; 123 } 124 125 /** Make this node red. */ 126 public void setRed () { 127 color = RED; 128 } 129 130 } |
The trivial
Figure 14-40. Easy parts of the RedBlackTree class.
1 /** A red-black tree of Comparables. */ 2 public class RedBlackTree<E extends Comparable<E>> 3 implements Set<E> { 4 5 /** The root node of this tree. */ 6 private RedBlackNode<E> root ; 7 8 /** All "null" node references actually point to this node. */ 9 private RedBlackNode<E> sentinel ; 10 11 /** The tree is initially empty. */ 12 public RedBlackTree () { 13 sentinel = new RedBlackNode<E>(); 14 root = sentinel; 15 } 16 17 public int |
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<E> node = root; 3 while (node != sentinel) { 4 int comparison = target.compareTo(node.getItem()); 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<E> targetNode 3 = new RedBlackNode<E>(target, sentinel); 4 RedBlackNode<E> parent = sentinel; 5 RedBlackNode<E> 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<E> child, 27 RedBlackNode<E> 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 } |
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<E> parent, 6 RedBlackNode<E> child, 7 int dir) { 8 parent.setChild(dir, child); 9 child.setParent(parent); 10 } |
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<E> node) { 3 while (node.getParent().isRed()) { 4 RedBlackNode<E> parent = node.getParent(); 5 RedBlackNode<E> grandparent = parent.getParent(); 6 RedBlackNode<E> 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 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<E> node) { 33 RedBlackNode<E> child = node.getChild(dir); 34 RedBlackNode<E> 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<E> inorderSuccessor (RedBlackNode<E> node) { 3 RedBlackNode<E> 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<E> 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<E> successor = inorderSuccessor(node); 20 node.setItem(successor.getItem()); 21 spliceOut(successor); 22 } 23 return; 24 } else { 25 node = node.getChild(comparison); 26 } 27 } 28 } 29 30 /** Splice node out of the tree. */ 31 protected void spliceOut (RedBlackNode<E> node) { 32 RedBlackNode<E> 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<E> node) { 3 while ((node != root) && (node.isBlack())) { 4 RedBlackNode<E> parent = node.getParent(); 5 int comparison = compare(node, parent); 6 RedBlackNode<E> 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); 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 |
|
| 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.20 |
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?) |
