概述
红黑树是一种自平衡二叉查找树,它相对于二叉查找树性能会更加高效(查找、删除、添加等操作需要O(log n),其中n为树中元素的个数),但实现较为复杂(需要保持自身的平衡).
性质
情况4
P为红色,U为黑色,且N为P的左子节点,这种情况下,我们需要在G处进行一次右旋转,结果满足了性质4与性质5,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G，现在它们都通过以前的父节点P.
关于旋转操作,可以查看这篇文章《Algorithms,4th Edition》读书笔记-红黑二叉查找树.
情况5
P为红色,U为黑色,且N为P的右子节点,我们需要先在P处进行一次左旋转,这样就又回到了情况4.
代码
private void fixAfterInsertion(Node x) {
while (x != null && x != root && colorOf(parentOf(x)) == RED) {
if (parentOf(x) == grandpaOf(x).left) {
x = parentIsLeftNode(x);
} else {
x = parentIsRightNode(x);
}
fixSize(x);
}
setColor(root, BLACK);
}
private Node parentIsLeftNode(Node x) {
Node xUncle = grandpaOf(x).right;
// 情况3
if (colorOf(xUncle) == RED) {
x = uncleColorIsRed(x, xUncle);
} else {
// 情况5
if (x == parentOf(x).right) {
x = parentOf(x);
rotateLeft(x);
}
// 情况4
rotateRight(grandpaOf(x));
}
return x;
}
private Node parentIsRightNode(Node x) {
Node xUncle = grandpaOf(x).left;
if (colorOf(xUncle) == RED) {
x = uncleColorIsRed(x, xUncle);
} else {
if (x == parentOf(x).left) {
x = parentOf(x);
rotateRight(x);
}
rotateLeft(grandpaOf(x));
}
return x;
}
private Node uncleColorIsRed(Node x, Node xUncle) {
setColor(parentOf(x), BLACK);
setColor(xUncle, BLACK);
setColor(grandpaOf(x), RED);
x = grandpaOf(x);
return x;
}
删除
我们只考虑删除节点只有一个子节点的情况,且只有后继节点与删除节点都为黑色(如果删除节点为红色,从根节点到叶子节点的每条路径上少了一个红色节点并不会违反红黑树的性质,而如果后继节点为红色,只需要将它重新绘制为黑色即可).
先将删除节点替换为后继节点,且后继节点定义为N,它的兄弟节点为S.
情况1
N为新的根节点,在这种情况下只需要把根节点保持为黑色即可.
情况2
S为红色,只需要在P进行一次左旋转,接下来则继续按以下情况进行处理(尽管路径上的黑色节点数量没有改变,但N有了一个黑色的兄弟节点与红色的父节点).
情况3
S和它的子节点都是黑色的,而P为红色.这种情况下只需要将S与P的颜色进行交换
情况4
S和它的子节点都是黑色的,这种情况下需要把S重新绘制为红色.这时不通过N的路径都将少一个黑色节点(通过N的路径因为删除节点是黑色的也都少了一个黑色节点),这让它们平衡了起来.
但现在通过P的路径比不通过P的路径都少了一个黑色节点,所以还需要在P上继续进行调整.
情况5
S为黑色,它的左子节点为红色,右子节点为黑色.这种情况下,我们在S上做右旋转,这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个右儿子是红色的黑色兄弟，所以我们进入了情况6。N和P都不受这个变换的影响。
情况6
S是黑色，它的右子节点是红色,我们在N的父亲P上做左旋转.这样S成为N的父亲和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色,但是,N现在增加了一个黑色祖先.所以,通过N的路径都增加了一个黑色节点.此时,如果一个路径不通过N,则有两种可能性:
- 它通过
N的新兄弟.那么它以前和现在都必定通过S和N的父亲,而它们只是交换了颜色.所以路径保持了同样数目的黑色节点.
- 它通过
N的新叔父,S的右儿子.那么它以前通过S、S的父亲和S的右儿子,但是现在只通过S,它被假定为它以前的父亲的颜色,和S的右儿子,它被从红色改变为黑色.合成效果是这个路径通过了同样数目的黑色节点.
在任何情况下,在这些路径上的黑色节点数目都没有改变.所以我们恢复了性质4.在示意图中的白色节点可以是红色或黑色,但是在变换前后都必须指定相同的颜色.
代码
private void fixAfterDeletion(Node x) {
while (x != null && x != root && colorOf(x) == BLACK) {
if (x == parentOf(x).left) {
x = successorIsLeftNode(x);
} else {
x = successorIsRightNode(x);
}
}
setColor(x, BLACK);
}
private Node successorIsLeftNode(Node x) {
Node brother = parentOf(x).right;
// 情况2
if (colorOf(brother) == RED) {
rotateLeft(parentOf(x));
brother = parentOf(x).right;
}
// 情况3,4
if (colorOf(brother.left) == BLACK && colorOf(brother.right) == BLACK) {
x = brotherChildrenColorIsBlack(x, brother);
} else {
// 情况5
if (colorOf(brother.right) == BLACK) {
rotateRight(brother);
brother = parentOf(x).right;
}
// 情况6
setColor(brother.right, BLACK);
rotateLeft(parentOf(x));
x = root;
}
return x;
}
private Node brotherChildrenColorIsBlack(Node x, Node brother) {
setColor(brother, RED);
x = parentOf(x);
return x;
}
参考资料
本文作者为SylvanasSun(sylvanassun_xtz@163.com),转载请务必指明原文链接.
网友评论