private void doRedBlackDeleteFixup(final Node replacementNode,
final int index){
Commons Collections僥楼永芝?眉?(2)
扮寂:2011-07-20 鴬人坩 Phinecos
//嶷仟蕉何峠財碕菜峯
Node currentNode = replacementNode;
while ((currentNode != rootNode[index])
&& (isBlack(currentNode, index))) {
if (isLeftChild(currentNode, index)) {
Node siblingNode =
getRightChild(getParent(currentNode, index), index);
if (isRed(siblingNode, index)) {
makeBlack(siblingNode, index);
makeRed(getParent(currentNode, index), index);
rotateLeft(getParent(currentNode, index), index);
siblingNode = getRightChild(getParent(currentNode, index), index);
}
if (isBlack(getLeftChild(siblingNode, index), index)
&& isBlack(getRightChild(siblingNode, index),
index)) {
makeRed(siblingNode, index);
currentNode = getParent(currentNode, index);
} else {
if (isBlack(getRightChild(siblingNode, index), index)) {
makeBlack(getLeftChild(siblingNode, index), index);
makeRed(siblingNode, index);
rotateRight(siblingNode, index);
siblingNode =
getRightChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
index);
makeBlack(getParent(currentNode, index), index);
makeBlack(getRightChild(siblingNode, index), index);
rotateLeft(getParent(currentNode, index), index);
currentNode = rootNode[index];
}
} else {
Node siblingNode = getLeftChild(getParent(currentNode, index), index);
if (isRed(siblingNode, index)) {
makeBlack(siblingNode, index);
makeRed(getParent(currentNode, index), index);
rotateRight(getParent(currentNode, index), index);
siblingNode = getLeftChild(getParent(currentNode, index), index);
}
if (isBlack(getRightChild(siblingNode, index), index)
&& isBlack(getLeftChild(siblingNode, index), index)) {
makeRed(siblingNode, index);
currentNode = getParent(currentNode, index);
} else {
if (isBlack(getLeftChild(siblingNode, index), index)) {
makeBlack(getRightChild(siblingNode, index), index);
makeRed(siblingNode, index)
|
