private void doRedBlackInsert(final Node insertedNode, final int index)
{//进行红黑树节点插入后的调整
Node currentNode = insertedNode;//新插入节点置为当前节点
makeRed(currentNode, index);//标记新节点为红色
while ((currentNode != null) && (currentNode != rootNode[index])&& (isRed(currentNode.getParent(index), index)))
{//确保当前节点父节点为红色才继续处理
if (isLeftChild(getParent(currentNode, index), index))
{//父节点是祖父节点的左孩子
Node y = getRightChild(getGrandParent(currentNode, index),index);//叔节点是祖父节点的右孩子
if (isRed(y, index))
{//红叔(图4)
makeBlack(getParent(currentNode, index), index);//标记父节点为黑色
makeBlack(y, index);//标记叔节点为黑色
makeRed(getGrandParent(currentNode, index), index);//标记祖父节点为红色
currentNode = getGrandParent(currentNode, index);//置祖父节点为当前节点
}
else
{//黑叔(对应图5和图6)
if (isRightChild(currentNode, index))
{//当前节点是父节点的右孩子(图6)
currentNode = getParent(currentNode, index);//置父节点为当前节点
rotateLeft(currentNode, index);//左旋
}
makeBlack(getParent(currentNode, index), index);//当前节点的父节点置为黑色
makeRed(getGrandParent(currentNode, index), index);//祖父节点置为红色
if (getGrandParent(currentNode, index) != null)
{//对祖父节点进行右旋
rotateRight(getGrandParent(currentNode, index),index);
}
}
} else
{//父节点是祖父节点的右孩子
Node y = getLeftChild(getGrandParent(currentNode, index),index);//叔节点是祖父节点的左孩子
if (isRed(y, index))
{//红叔(图4)
makeBlack(getParent(currentNode, index), index);//标记父节点为黑色
makeBlack(y, index);//标记叔节点为黑色
makeRed(getGrandParent(currentNode, index), index);//标记祖父节点为红色
currentNode = getGrandParent(currentNode, index);//置祖父节点为当前节点
}
else
{//黑叔(对应图7和图8)
if (isLeftChild(currentNode, index))
{//当前节点是父节点的左孩子(图8)
currentNode = getParent(currentNode, index);//置父节点为当前节点
rotateRight(currentNode, index);//右旋
}
makeBlack(getParent(currentNode, index), index);//当前节点的父节点置为黑色
makeRed(getGrandParent(currentNode, index), index);//祖父节点置为红色
if (getGrandParent(currentNode, index) != null)
{//对祖父节点进行左旋
rotateLeft(getGrandParent(currentNode, index), index);
}
}
}
}
makeBlack(rootNode[index], index);//标记根节点为黑色
}
private void doRedBlackDelete(final Node deletedNode)
{//在红黑树中删除指定节点
for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
// if deleted node has both left and children, swap with
// the next greater node
if ((deletedNode.getLeft(index) != null)
&& (deletedNode.getRight(index) != null)) {
swapPosition(nextGreater(deletedNode, index), deletedNode,
index);
}
Node replacement = ((deletedNode.getLeft(index) != null)
? deletedNode.getLeft(index)
: deletedNode.getRight(index));
if (replacement != null) {
replacement.setParent(deletedNode.getParent(index), index);
if (deletedNode.getParent(index) == null) {
rootNode[index] = replacement;
} else if (deletedNode
== deletedNode.getParent(index).getLeft(index)) {
deletedNode.getParent(index).setLeft(replacement, index);
} else {
deletedNode.getParent(index).setRight(replacement, index);
}
deletedNode.setLeft(null, index);
deletedNode.setRight(null, index);
deletedNode.setParent(null, index);
if (isBlack(deletedNode, index)) {
doRedBlackDeleteFixup(replacement, index);
}
} else {
// replacement is null
if (deletedNode.getParent(index) == null) {
// empty tree
rootNode[index] = null;
} else {
// deleted node had no children
if (isBlack(deletedNode, index)) {
doRedBlackDeleteFixup(deletedNode, index);
}
if (deletedNode.getParent(index) != null) {
if (deletedNode
== deletedNode.getParent(index)
.getLeft(index)) {
deletedNode.getParent(index).setLeft(null, index);
} else {
deletedNode.getParent(index).setRight(null,
index);
}
deletedNode.setParent(null, index);
}
}
}
}
shrink();
}
private void doRedBlackDeleteFixup(final Node replacementNode,
final int index){//重新局部平衡红黑树
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);
rotateLeft(siblingNode, index);
siblingNode =
getLeftChild(getParent(currentNode, index), index);
}
copyColor(getParent(currentNode, index), siblingNode,
index);
makeBlack(getParent(currentNode, index), index);
akeBlack(getLeftChild(siblingNode, index), index);
rotateRight(getParent(currentNode, index), index);
currentNode = rootNode[index];
}
}
}
makeBlack(currentNode, index);
}
责任编辑：小草
