do a rotate right. standard fare in the world of balanced trees @param node the node to be rotated @param index _KEY or _VALUE
(Node node, int index)
| 775 | * @param index _KEY or _VALUE |
| 776 | */ |
| 777 | private void rotateRight(Node node, int index) |
| 778 | { |
| 779 | Node left_child = node.getLeft(index); |
| 780 | |
| 781 | node.setLeft(left_child.getRight(index), index); |
| 782 | if (left_child.getRight(index) != null) |
| 783 | { |
| 784 | left_child.getRight(index).setParent(node, index); |
| 785 | } |
| 786 | left_child.setParent(node.getParent(index), index); |
| 787 | if (node.getParent(index) == null) |
| 788 | { |
| 789 | |
| 790 | // node was the root ... now its left child is the root |
| 791 | _root[ index ] = left_child; |
| 792 | } |
| 793 | else if (node.getParent(index).getRight(index) == node) |
| 794 | { |
| 795 | node.getParent(index).setRight(left_child, index); |
| 796 | } |
| 797 | else |
| 798 | { |
| 799 | node.getParent(index).setLeft(left_child, index); |
| 800 | } |
| 801 | left_child.setRight(node, index); |
| 802 | node.setParent(left_child, index); |
| 803 | } |
| 804 | |
| 805 | /** |
| 806 | * complicated red-black insert stuff. Based on Sun's TreeMap |