complicated red-black delete stuff. Based on Sun's TreeMap implementation, though it's barely recognizeable any more. This rebalances the tree (somewhat, as red-black trees are not perfectly balanced -- perfect balancing takes longer) @param replacement_node the node being replaced @param index _K
(Node replacement_node,
int index)
| 977 | * @param index _KEY or _VALUE |
| 978 | */ |
| 979 | private void doRedBlackDeleteFixup(Node replacement_node, |
| 980 | int index) |
| 981 | { |
| 982 | Node current_node = replacement_node; |
| 983 | |
| 984 | while ((current_node != _root[ index ]) |
| 985 | && (isBlack(current_node, index))) |
| 986 | { |
| 987 | if (isLeftChild(current_node, index)) |
| 988 | { |
| 989 | Node sibling_node = |
| 990 | getRightChild(getParent(current_node, index), index); |
| 991 | |
| 992 | if (isRed(sibling_node, index)) |
| 993 | { |
| 994 | makeBlack(sibling_node, index); |
| 995 | makeRed(getParent(current_node, index), index); |
| 996 | rotateLeft(getParent(current_node, index), index); |
| 997 | sibling_node = |
| 998 | getRightChild(getParent(current_node, index), index); |
| 999 | } |
| 1000 | if (isBlack(getLeftChild(sibling_node, index), index) |
| 1001 | && isBlack(getRightChild(sibling_node, index), index)) |
| 1002 | { |
| 1003 | makeRed(sibling_node, index); |
| 1004 | current_node = getParent(current_node, index); |
| 1005 | } |
| 1006 | else |
| 1007 | { |
| 1008 | if (isBlack(getRightChild(sibling_node, index), index)) |
| 1009 | { |
| 1010 | makeBlack(getLeftChild(sibling_node, index), index); |
| 1011 | makeRed(sibling_node, index); |
| 1012 | rotateRight(sibling_node, index); |
| 1013 | sibling_node = |
| 1014 | getRightChild(getParent(current_node, index), |
| 1015 | index); |
| 1016 | } |
| 1017 | copyColor(getParent(current_node, index), sibling_node, |
| 1018 | index); |
| 1019 | makeBlack(getParent(current_node, index), index); |
| 1020 | makeBlack(getRightChild(sibling_node, index), index); |
| 1021 | rotateLeft(getParent(current_node, index), index); |
| 1022 | current_node = _root[ index ]; |
| 1023 | } |
| 1024 | } |
| 1025 | else |
| 1026 | { |
| 1027 | Node sibling_node = |
| 1028 | getLeftChild(getParent(current_node, index), index); |
| 1029 | |
| 1030 | if (isRed(sibling_node, index)) |
| 1031 | { |
| 1032 | makeBlack(sibling_node, index); |
| 1033 | makeRed(getParent(current_node, index), index); |
| 1034 | rotateRight(getParent(current_node, index), index); |
| 1035 | sibling_node = |
| 1036 | getLeftChild(getParent(current_node, index), index); |
no test coverage detected