0
|
1 /*
|
|
2 * Copyright 2000 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
21 * have any 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 }
|