complicated red-black delete stuff. Based on Sun's TreeMap implementation, though it's barely recognizeable any more @param deleted_node the node to be deleted
(Node deleted_node)
| 886 | * @param deleted_node the node to be deleted |
| 887 | */ |
| 888 | void doRedBlackDelete(Node deleted_node) |
| 889 | { |
| 890 | for (int index = _MINIMUM_INDEX; index < _INDEX_COUNT; index++) |
| 891 | { |
| 892 | |
| 893 | // if deleted node has both left and children, swap with |
| 894 | // the next greater node |
| 895 | if ((deleted_node.getLeft(index) != null) |
| 896 | && (deleted_node.getRight(index) != null)) |
| 897 | { |
| 898 | swapPosition(nextGreater(deleted_node, index), deleted_node, |
| 899 | index); |
| 900 | } |
| 901 | Node replacement = ((deleted_node.getLeft(index) != null) |
| 902 | ? deleted_node.getLeft(index) |
| 903 | : deleted_node.getRight(index)); |
| 904 | |
| 905 | if (replacement != null) |
| 906 | { |
| 907 | replacement.setParent(deleted_node.getParent(index), index); |
| 908 | if (deleted_node.getParent(index) == null) |
| 909 | { |
| 910 | _root[ index ] = replacement; |
| 911 | } |
| 912 | else if (deleted_node |
| 913 | == deleted_node.getParent(index).getLeft(index)) |
| 914 | { |
| 915 | deleted_node.getParent(index).setLeft(replacement, index); |
| 916 | } |
| 917 | else |
| 918 | { |
| 919 | deleted_node.getParent(index).setRight(replacement, |
| 920 | index); |
| 921 | } |
| 922 | deleted_node.setLeft(null, index); |
| 923 | deleted_node.setRight(null, index); |
| 924 | deleted_node.setParent(null, index); |
| 925 | if (isBlack(deleted_node, index)) |
| 926 | { |
| 927 | doRedBlackDeleteFixup(replacement, index); |
| 928 | } |
| 929 | } |
| 930 | else |
| 931 | { |
| 932 | |
| 933 | // replacement is null |
| 934 | if (deleted_node.getParent(index) == null) |
| 935 | { |
| 936 | |
| 937 | // empty tree |
| 938 | _root[ index ] = null; |
| 939 | } |
| 940 | else |
| 941 | { |
| 942 | |
| 943 | // deleted node had no children |
| 944 | if (isBlack(deleted_node, index)) |
| 945 | { |
no test coverage detected