View Javadoc
1   /*
2    * Copyright (c) 2000, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
5    * This code is free software; you can redistribute it and/or modify it
6    * under the terms of the GNU General Public License version 2 only, as
7    * published by the Free Software Foundation.
8    *
9    * This code is distributed in the hope that it will be useful, but WITHOUT
10   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11   * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12   * version 2 for more details (a copy is included in the LICENSE file that
13   * accompanied this code).
14   *
15   * You should have received a copy of the GNU General Public License version
16   * 2 along with this work; if not, write to the Free Software Foundation,
17   * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18   *
19   * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20   * or visit www.oracle.com if you need additional information or have any
21   * questions.
22   *
23   */
24  
25  package sun.jvm.hotspot.utilities;
26  
27  /** <P> This class implements a Red-Black tree as described in Cormen,
28      Leiserson, Rivest, <I>Introduction to Algorithms</I>, MIT Press:
29      Cambridge, MA, 1990. </P>
30  
31      <P> A property of this implementation is that it is designed to
32      allow straightforward augmentation of the data structure. A valid
33      augmentation is one in which a node contains auxiliary information
34      that can be computed by examining only this node and its left and
35      right children (see CLR, section 15.2). </P>
36  
37      <P> An RBTree is a structure of RBNodes, each of which contains a
38      user data element. When the user inserts a piece of data into the
39      tree, a new RBNode is constructed around it. </P>
40  
41      <P> An RBTree takes a Comparator as argument to its constructor
42      which is used internally to order the nodes in the tree. The
43      comparator's arguments are obtained by calling the routine
44      "getNodeData" on two nodes; the default implementaion returns the
45      node data. This Comparator is also used to perform the generic
46      "find" operation, which returns the RBNode containing user data
47      precisely equalling the query data. Different types of user data
48      will typically require different types of traversals as well as
49      additional comparison operations; these are left to the RBTree
50      subclass. </P>
51  
52  */
53  
54  import java.io.PrintStream;
55  import java.util.Comparator;
56  import java.util.Random;
57  
58  public class RBTree {
59    private RBNode root;
60    private Comparator comparator;
61    protected static final boolean DEBUGGING = true;
62    protected static final boolean VERBOSE   = true;
63    protected static final boolean REALLY_VERBOSE = false;
64  
65    public RBTree(Comparator comparator) {
66      this.comparator = comparator;
67    }
68  
69    public RBNode getRoot() {
70      return root;
71    }
72  
73    public void insertNode(RBNode x) {
74      treeInsert(x);
75  
76      x.setColor(RBColor.RED);
77      boolean shouldPropagate = x.update();
78  
79      if (DEBUGGING && REALLY_VERBOSE) {
80        System.err.println("RBTree.insertNode");
81      }
82  
83      RBNode propagateStart = x;
84  
85      // Loop invariant: x has been updated.
86      while ((x != root) && (x.getParent().getColor() == RBColor.RED)) {
87        if (x.getParent() == x.getParent().getParent().getLeft()) {
88          RBNode y = x.getParent().getParent().getRight();
89          if ((y != null) && (y.getColor() == RBColor.RED)) {
90            // Case 1
91            if (DEBUGGING && REALLY_VERBOSE) {
92              System.err.println("  Case 1/1");
93            }
94            x.getParent().setColor(RBColor.BLACK);
95            y.setColor(RBColor.BLACK);
96            x.getParent().getParent().setColor(RBColor.RED);
97            x.getParent().update();
98            x = x.getParent().getParent();
99            shouldPropagate = x.update();
100           propagateStart = x;
101         } else {
102           if (x == x.getParent().getRight()) {
103             // Case 2
104             if (DEBUGGING && REALLY_VERBOSE) {
105               System.err.println("  Case 1/2");
106             }
107             x = x.getParent();
108             leftRotate(x);
109           }
110           // Case 3
111           if (DEBUGGING && REALLY_VERBOSE) {
112             System.err.println("  Case 1/3");
113           }
114           x.getParent().setColor(RBColor.BLACK);
115           x.getParent().getParent().setColor(RBColor.RED);
116           shouldPropagate = rightRotate(x.getParent().getParent());
117           propagateStart = x.getParent();
118         }
119       } else {
120         // Same as then clause with "right" and "left" exchanged
121         RBNode y = x.getParent().getParent().getLeft();
122         if ((y != null) && (y.getColor() == RBColor.RED)) {
123           // Case 1
124           if (DEBUGGING && REALLY_VERBOSE) {
125             System.err.println("  Case 2/1");
126           }
127           x.getParent().setColor(RBColor.BLACK);
128           y.setColor(RBColor.BLACK);
129           x.getParent().getParent().setColor(RBColor.RED);
130           x.getParent().update();
131           x = x.getParent().getParent();
132           shouldPropagate = x.update();
133           propagateStart = x;
134         } else {
135           if (x == x.getParent().getLeft()) {
136             // Case 2
137             if (DEBUGGING && REALLY_VERBOSE) {
138               System.err.println("  Case 2/2");
139             }
140             x = x.getParent();
141             rightRotate(x);
142           }
143           // Case 3
144           if (DEBUGGING && REALLY_VERBOSE) {
145             System.err.println("  Case 2/3");
146           }
147           x.getParent().setColor(RBColor.BLACK);
148           x.getParent().getParent().setColor(RBColor.RED);
149           shouldPropagate = leftRotate(x.getParent().getParent());
150           propagateStart = x.getParent();
151         }
152       }
153     }
154 
155     while (shouldPropagate && (propagateStart != root)) {
156       if (DEBUGGING && REALLY_VERBOSE) {
157         System.err.println("  Propagating");
158       }
159       propagateStart = propagateStart.getParent();
160       shouldPropagate = propagateStart.update();
161     }
162 
163     root.setColor(RBColor.BLACK);
164 
165     if (DEBUGGING) {
166       verify();
167     }
168   }
169 
170   /** FIXME: this does not work properly yet for augmented red-black
171       trees since it doesn't update nodes. Need to figure out exactly
172       from which points we need to propagate updates upwards. */
173   public void deleteNode(RBNode z) {
174     // This routine splices out a node. Note that we may not actually
175     // delete the RBNode z from the tree, but may instead remove
176     // another node from the tree, copying its contents into z.
177 
178     // y is the node to be unlinked from the tree
179     RBNode y;
180     if ((z.getLeft() == null) || (z.getRight() == null)) {
181       y = z;
182     } else {
183       y = treeSuccessor(z);
184     }
185     // y is guaranteed to be non-null at this point
186     RBNode x;
187     if (y.getLeft() != null) {
188       x = y.getLeft();
189     } else {
190       x = y.getRight();
191     }
192     // x is the potential child of y to replace it in the tree.
193     // x may be null at this point
194     RBNode xParent;
195     if (x != null) {
196       x.setParent(y.getParent());
197       xParent = x.getParent();
198     } else {
199       xParent = y.getParent();
200     }
201     if (y.getParent() == null) {
202       root = x;
203     } else {
204       if (y == y.getParent().getLeft()) {
205         y.getParent().setLeft(x);
206       } else {
207         y.getParent().setRight(x);
208       }
209     }
210     if (y != z) {
211       z.copyFrom(y);
212     }
213     if (y.getColor() == RBColor.BLACK) {
214       deleteFixup(x, xParent);
215     }
216 
217     if (DEBUGGING) {
218       verify();
219     }
220   }
221 
222   public void print() {
223     printOn(System.out);
224   }
225 
226   public void printOn(PrintStream tty) {
227     printFromNode(root, tty, 0);
228   }
229 
230   //----------------------------------------------------------------------
231   // Functionality overridable by subclass
232   //
233 
234   protected Object getNodeValue(RBNode node) {
235     return node.getData();
236   }
237 
238   /** Verify invariants are preserved */
239   protected void verify() {
240     verifyFromNode(root);
241   }
242 
243   //----------------------------------------------------------------------
244   // Internals only below this point
245   //
246 
247   //
248   // Vanilla binary search tree operations
249   //
250 
251   private void treeInsert(RBNode z) {
252     RBNode y = null;
253     RBNode x = root;
254 
255     while (x != null) {
256       y = x;
257       if (comparator.compare(getNodeValue(z), getNodeValue(x)) < 0) {
258         x = x.getLeft();
259       } else {
260         x = x.getRight();
261       }
262     }
263     z.setParent(y);
264     if (y == null) {
265       root = z;
266     } else {
267       if (comparator.compare(getNodeValue(z), getNodeValue(y)) < 0) {
268         y.setLeft(z);
269       } else {
270         y.setRight(z);
271       }
272     }
273   }
274 
275   private RBNode treeSuccessor(RBNode x) {
276     if (x.getRight() != null) {
277       return treeMinimum(x.getRight());
278     }
279     RBNode y = x.getParent();
280     while ((y != null) && (x == y.getRight())) {
281       x = y;
282       y = y.getParent();
283     }
284     return y;
285   }
286 
287   private RBNode treeMinimum(RBNode x) {
288     while (x.getLeft() != null) {
289       x = x.getLeft();
290     }
291     return x;
292   }
293 
294   //
295   // Insertion and deletion helpers
296   //
297 
298   /** Returns true if updates must continue propagating up the tree */
299   private boolean leftRotate(RBNode x) {
300     // Set y.
301     RBNode y = x.getRight();
302     // Turn y's left subtree into x's right subtree.
303     x.setRight(y.getLeft());
304     if (y.getLeft() != null) {
305       y.getLeft().setParent(x);
306     }
307     // Link x's parent to y.
308     y.setParent(x.getParent());
309     if (x.getParent() == null) {
310       root = y;
311     } else {
312       if (x == x.getParent().getLeft()) {
313         x.getParent().setLeft(y);
314       } else {
315         x.getParent().setRight(y);
316       }
317     }
318     // Put x on y's left.
319     y.setLeft(x);
320     x.setParent(y);
321     // Update nodes in appropriate order (lowest to highest)
322     boolean res = x.update();
323     res = y.update() || res;
324     return res;
325   }
326 
327   /** Returns true if updates must continue propagating up the tree */
328   private boolean rightRotate(RBNode y) {
329     // Set x.
330     RBNode x = y.getLeft();
331     // Turn x's right subtree into y's left subtree.
332     y.setLeft(x.getRight());
333     if (x.getRight() != null) {
334       x.getRight().setParent(y);
335     }
336     // Link y's parent into x.
337     x.setParent(y.getParent());
338     if (y.getParent() == null) {
339       root = x;
340     } else {
341       if (y == y.getParent().getLeft()) {
342         y.getParent().setLeft(x);
343       } else {
344         y.getParent().setRight(x);
345       }
346     }
347     // Put y on x's right.
348     x.setRight(y);
349     y.setParent(x);
350     // Update nodes in appropriate order (lowest to highest)
351     boolean res = y.update();
352     res = x.update() || res;
353     return res;
354   }
355 
356   /** Restores red-black property to tree after splicing out node
357       during deletion. Note that x may be null, which is why xParent
358       must be specified. */
359   private void deleteFixup(RBNode x, RBNode xParent) {
360     while ((x != root) && ((x == null) || (x.getColor() == RBColor.BLACK))) {
361       if (x == xParent.getLeft()) {
362         // NOTE: the text points out that w can not be null. The
363         // reason is not obvious from simply examining the code; it
364         // comes about because of properties of the red-black tree.
365         RBNode w = xParent.getRight();
366         if (DEBUGGING) {
367           if (w == null) {
368             throw new RuntimeException("x's sibling should not be null");
369           }
370         }
371         if (w.getColor() == RBColor.RED) {
372           // Case 1
373           w.setColor(RBColor.BLACK);
374           xParent.setColor(RBColor.RED);
375           leftRotate(xParent);
376           w = xParent.getRight();
377         }
378         if (((w.getLeft()  == null) || (w.getLeft().getColor()  == RBColor.BLACK)) &&
379             ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK))) {
380           // Case 2
381           w.setColor(RBColor.RED);
382           x = xParent;
383           xParent = x.getParent();
384         } else {
385           if ((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) {
386             // Case 3
387             w.getLeft().setColor(RBColor.BLACK);
388             w.setColor(RBColor.RED);
389             rightRotate(w);
390             w = xParent.getRight();
391           }
392           // Case 4
393           w.setColor(xParent.getColor());
394           xParent.setColor(RBColor.BLACK);
395           if (w.getRight() != null) {
396             w.getRight().setColor(RBColor.BLACK);
397           }
398           leftRotate(xParent);
399           x = root;
400           xParent = x.getParent();
401         }
402       } else {
403         // Same as clause above with "right" and "left"
404         // exchanged
405 
406         // NOTE: the text points out that w can not be null. The
407         // reason is not obvious from simply examining the code; it
408         // comes about because of properties of the red-black tree.
409         RBNode w = xParent.getLeft();
410         if (DEBUGGING) {
411           if (w == null) {
412             throw new RuntimeException("x's sibling should not be null");
413           }
414         }
415         if (w.getColor() == RBColor.RED) {
416           // Case 1
417           w.setColor(RBColor.BLACK);
418           xParent.setColor(RBColor.RED);
419           rightRotate(xParent);
420           w = xParent.getLeft();
421         }
422         if (((w.getRight() == null) || (w.getRight().getColor() == RBColor.BLACK)) &&
423             ((w.getLeft()  == null) || (w.getLeft().getColor()  == RBColor.BLACK))) {
424           // Case 2
425           w.setColor(RBColor.RED);
426           x = xParent;
427           xParent = x.getParent();
428         } else {
429           if ((w.getLeft() == null) || (w.getLeft().getColor() == RBColor.BLACK)) {
430             // Case 3
431             w.getRight().setColor(RBColor.BLACK);
432             w.setColor(RBColor.RED);
433             leftRotate(w);
434             w = xParent.getLeft();
435           }
436           // Case 4
437           w.setColor(xParent.getColor());
438           xParent.setColor(RBColor.BLACK);
439           if (w.getLeft() != null) {
440             w.getLeft().setColor(RBColor.BLACK);
441           }
442           rightRotate(xParent);
443           x = root;
444           xParent = x.getParent();
445         }
446       }
447     }
448     if (x != null) {
449       x.setColor(RBColor.BLACK);
450     }
451   }
452 
453   // Returns the number of black children along all paths to all
454   // leaves of the given node
455   private int verifyFromNode(RBNode node) {
456     // Bottoms out at leaf nodes
457     if (node == null) {
458       return 1;
459     }
460 
461     // Each node is either red or black
462     if (!((node.getColor() == RBColor.RED) ||
463           (node.getColor() == RBColor.BLACK))) {
464       if (DEBUGGING) {
465         System.err.println("Verify failed:");
466         printOn(System.err);
467       }
468       throw new RuntimeException("Verify failed (1)");
469     }
470 
471     // Every leaf (null) is black
472 
473     if (node.getColor() == RBColor.RED) {
474       // Both its children are black
475       if (node.getLeft() != null) {
476         if (node.getLeft().getColor() != RBColor.BLACK) {
477           if (DEBUGGING) {
478             System.err.println("Verify failed:");
479             printOn(System.err);
480           }
481           throw new RuntimeException("Verify failed (2)");
482         }
483       }
484       if (node.getRight() != null) {
485         if (node.getRight().getColor() != RBColor.BLACK) {
486           if (DEBUGGING) {
487             System.err.println("Verify failed:");
488             printOn(System.err);
489           }
490           throw new RuntimeException("Verify failed (3)");
491         }
492       }
493     }
494 
495     // Every simple path to a leaf contains the same number of black
496     // nodes
497     int i = verifyFromNode(node.getLeft());
498     int j = verifyFromNode(node.getRight());
499     if (i != j) {
500       if (DEBUGGING) {
501         System.err.println("Verify failed:");
502         printOn(System.err);
503       }
504       throw new RuntimeException("Verify failed (4) (left black count = " +
505                                  i + ", right black count = " + j + ")");
506     }
507 
508     return i + ((node.getColor() == RBColor.RED) ? 0 : 1);
509   }
510 
511   /** Debugging */
512   private void printFromNode(RBNode node, PrintStream tty, int indentDepth) {
513     for (int i = 0; i < indentDepth; i++) {
514       tty.print(" ");
515     }
516 
517     tty.print("-");
518     if (node == null) {
519       tty.println();
520       return;
521     }
522 
523     tty.println(" " + getNodeValue(node) +
524                 ((node.getColor() == RBColor.RED) ? " (red)" : " (black)"));
525     printFromNode(node.getLeft(), tty, indentDepth + 2);
526     printFromNode(node.getRight(), tty, indentDepth + 2);
527   }
528 
529   //----------------------------------------------------------------------
530   // Test harness
531   //
532 
533   public static void main(String[] args) {
534     int treeSize = 10000;
535     int maxVal = treeSize;
536     System.err.println("Building tree...");
537     RBTree tree = new RBTree(new Comparator() {
538         public int compare(Object o1, Object o2) {
539           Integer i1 = (Integer) o1;
540           Integer i2 = (Integer) o2;
541           if (i1.intValue() < i2.intValue()) {
542             return -1;
543           } else if (i1.intValue() == i2.intValue()) {
544             return 0;
545           }
546           return 1;
547         }
548       });
549     Random rand = new Random(System.currentTimeMillis());
550     for (int i = 0; i < treeSize; i++) {
551       Integer val = new Integer(rand.nextInt(maxVal) + 1);
552       try {
553         tree.insertNode(new RBNode(val));
554         if ((i > 0) && (i % 100 == 0)) {
555           System.err.print(i + "...");
556           System.err.flush();
557         }
558       }
559       catch (Exception e) {
560         e.printStackTrace();
561         System.err.println("While inserting value " + val);
562         tree.printOn(System.err);
563         System.exit(1);
564       }
565     }
566     // Now churn data in tree by deleting and inserting lots of nodes
567     System.err.println();
568     System.err.println("Churning tree...");
569     for (int i = 0; i < treeSize; i++) {
570       if (DEBUGGING && VERBOSE) {
571         System.err.println("Iteration " + i + ":");
572         tree.printOn(System.err);
573       }
574       // Pick a random value to remove (NOTE that this is not
575       // uniformly distributed)
576       RBNode xParent = null;
577       RBNode x = tree.getRoot();
578       int depth = 0;
579       while (x != null) {
580         // Traverse path down to leaf
581         xParent = x;
582         if (rand.nextBoolean()) {
583           x = x.getLeft();
584         } else {
585           x = x.getRight();
586         }
587         ++depth;
588       }
589       // Pick a random height at which to remove value
590       int height = rand.nextInt(depth);
591       if (DEBUGGING) {
592         if (height >= depth) {
593           throw new RuntimeException("bug in java.util.Random");
594         }
595       }
596       // Walk that far back up (FIXME: off by one?)
597       while (height > 0) {
598         xParent = xParent.getParent();
599         --height;
600       }
601       // Tell the tree to remove this node
602       if (DEBUGGING && VERBOSE) {
603         System.err.println("(Removing value " + tree.getNodeValue(xParent) + ")");
604       }
605       tree.deleteNode(xParent);
606 
607       // Now create and insert a new value
608       Integer newVal = new Integer(rand.nextInt(maxVal) + 1);
609       if (DEBUGGING && VERBOSE) {
610         System.err.println("(Inserting value " + newVal + ")");
611       }
612       tree.insertNode(new RBNode(newVal));
613     }
614     System.err.println("All tests passed.");
615   }
616 }