get the next larger node from the specified node @param node the node to be searched from @param index _KEY or _VALUE @return the specified node
(Node node, int index)
| 527 | * @return the specified node |
| 528 | */ |
| 529 | static Node nextGreater(Node node, int index) |
| 530 | { |
| 531 | Node rval = null; |
| 532 | |
| 533 | if (node == null) |
| 534 | { |
| 535 | rval = null; |
| 536 | } |
| 537 | else if (node.getRight(index) != null) |
| 538 | { |
| 539 | |
| 540 | // everything to the node's right is larger. The least of |
| 541 | // the right node's descendents is the next larger node |
| 542 | rval = leastNode(node.getRight(index), index); |
| 543 | } |
| 544 | else |
| 545 | { |
| 546 | |
| 547 | // traverse up our ancestry until we find an ancestor that |
| 548 | // is null or one whose left child is our ancestor. If we |
| 549 | // find a null, then this node IS the largest node in the |
| 550 | // tree, and there is no greater node. Otherwise, we are |
| 551 | // the largest node in the subtree on that ancestor's left |
| 552 | // ... and that ancestor is the next greatest node |
| 553 | Node parent = node.getParent(index); |
| 554 | Node child = node; |
| 555 | |
| 556 | while ((parent != null) && (child == parent.getRight(index))) |
| 557 | { |
| 558 | child = parent; |
| 559 | parent = parent.getParent(index); |
| 560 | } |
| 561 | rval = parent; |
| 562 | } |
| 563 | return rval; |
| 564 | } |
| 565 | |
| 566 | /** |
| 567 | * copy the color from one node to another, dealing with the fact |