- 红黑树的性质
- 旋转
- 插入
- 删除
#1. 红黑树的性质
红黑树是一棵二叉搜索树，它在每个结点上增加一个存储位来表示结点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似平衡的。
树中的每个结点包含5个属性：color、key、left、right和p。如果一个结点没有子结点或父结点，则该结点相应指针属性值为NIL。
一棵红黑树是满足下面红黑性质的二叉搜索树：
- 每个结点或是红色，或是黑色的。
- 根结点是黑色的。
- 每个叶结点（NIL）是黑色的。
- 如果一个结点是红色的，则它的两个子结点都是黑色的（红结点无红孩子）。
- 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
#2. 旋转
搜索树的插入和删除操作在含n个关键字的红黑树上，运行花费时间O(lgn)。由于这两个操作对数做了修改，结果可能违反红黑树的基本性质。为了维护这些性质，必须要改变树中某些结点的颜色以及指针结构。
指针结构的修改是通过旋转来完成的。这是一种能保持二叉搜索树性质的搜索树局部操作。如图给出了两种旋转：左旋和右旋。当在某个结点x上做左旋时，假设它的右孩子为y而不是T.nil；x可以为其右孩子不是T.nil结点的树内任意结点。左旋以x到y的链为“支轴”进行。它是y成为该子树新的根结点，x成为y的左孩子，y的左孩子成为x的右孩子。
rotation.png
在LEFT_ROTATE的伪代码中，假设x.right!=T.nil且根结点的父结点为T.nil。
LEFT_ROTATE(T,x) {
y = x.right
x.right = y.left
if(y.left != T.nil)
y.left.p = x
y.p = x.p
if(x.p == T.nil)
T.root = y
elseif x == x.p.left
x.p.left = y
y.left = x
x.p = x
}
RIGHT_ROTATE操作的代码是对称的。LEFT_ROTATE和RIGHT_ROTATE都在O(1)时间内运行完成的。
#3. 插入
红黑树的插入过程大致可分为两个步骤：第一，红黑树本身也是二叉搜索树，所以插入过程与二叉搜索树一致；第二，红黑树插入过程可能可能会打破红黑平衡，这时候需要借助额外的颜色修正算法。我们可以在O(lgn)时间内完成向一棵含有n个结点的红黑树中插入一个结点。插入的结点默认为红色。伪代码大致如下：
RB_INSERT(T,z) {
y = T.nil //设置safe-guard
x = T.root //结点插入从树根开始，记为x
while(x != T.nil) //如果树根不为空，此时while循环查找合适的插入位置
y = x //记录当前x的位置，为以后插入结点的父结点
if(z.key < x.key) //如果待插入结点z的关键字值小于根的关键字值，往左，否则往右
x = x.left //往左子树
else x = x.right //往右子树
z.p = y //到这一步说明，前面要么已经找到了合适的插入点，要么树为空
if(y == T.nil) //树为空，设置当前待插入的结点为树根
T.root = z
esleif z.key < y.key //根据关键字值判断挂载点是左子树还是右子树
y.left = z
else y.right = z
z.left = T.nil
z.right = T.nil
z.color = RED //保证插入结点z默认为红色
RB_INSERT_FIXUP(T,z) //颜色辅助修正算法
}
以下是RB_INSERT_FIXUP的伪代码：
RN_INSERT_FIXUP(T,z) {
while(z.p.color == RED)
if(z.p == z.p.p.left) //如果当前结点的父亲是祖父的左孩子
y = z.p.p.right //记录叔叔
if(y.color == RED) //如果叔叔为红色，平衡策略为交换颜色（case_uncle_red）
z.p.color = BLACK //设置父亲的颜色为黑色
y.color = BLACK //设置叔叔的颜色为黑色
z.p.p.color = RED //设置祖父的颜色为红色
z = z.p.p //改变z为z的祖父
else if z == z.p.right //叔叔的颜色为黑色（case_uncle_black）sub-case-left-right
z = z.p //改变z的父亲，为的是对其进行左旋
LEFT_ROTATE(T,z) //左旋
z.p.color = BLACK //交换p和g的颜色，设置p为黑色 sub-case-left-left
z.p.p.color = RED //设置g为红色
RIGHT_ROTATE(T,z.p.p) //右旋g
else //当前结点的父亲是祖父的右孩子
y = z.p.p.left //记录叔叔
if(y.color == RED) //如果叔叔为红色，平衡策略为交换颜色（case_uncle_red）
z.p.color = BLACK //设置父亲的颜色为黑色
y.color = BLACK //设置叔叔的颜色为黑色
z.p.p.color = RED //设置祖父的颜色为红色
z = z.p.p //改变z为z的祖父
else if z == z.p.left//叔叔的颜色为黑色（case_uncle_black）sub-case-right-left
z = z.p //改变z的父亲，为的是对其进行右旋
RIGHT_ROTATE(T,z) //右旋
z.p.color = BLACK //交换p和g的颜色，设置p为黑色 sub-case-right-right
z.p.p.color = RED //设置g为红色
LEFT_ROTATE(T,z.p.p) //左旋g
T.root.color = BLACK
}
红黑树的插入过程大致如下（假设待插入结点为z）：
- 执行标准的BST插入过程，待插入的红黑树的结点默认为红色。
- 如果待插入的结点为根结点，改变待插入结点的颜色为黑色。
- 如果待插入结点的父结点不为空，并且不是树根的位置具体分以下情况：
a) 如果z的叔叔为红色
i) 改变父结点和叔叔结点的颜色为黑色。
ii) 改变祖父结点的颜色为红色
iii) 改变z=z's grandparent，对于新的x结点重复步骤2和3
case_uncle_red.png
b) 如果z的叔叔为黑色
i) 左左--父亲是祖父的左孩子，当前结点是父亲的左孩子
ii) 左右--父亲是祖父的左孩子，当前结点是父亲的右孩子
iii) 右右--父亲是祖父的右孩子，当前结点是父亲的右孩子
iv) 右左--父亲是祖父的右孩子，当前结点是父亲的左孩子
左左
case_left_left.png
左右
case_left_right.png
右右
case_right_right.png
右左
case_right_left.png
插入案列分析
insert_sample.jpg
新插入结点z(结点4)，其父亲结点5为红色，违反了性质4（红结点无红孩子）。此时z的叔叔y(结点8)也为红色--case uncle red。解决方案为重新着色，平衡后z沿树上升到祖父的位置（结点7），从情况（a）转换为情况（b）。情况（b）中z的父亲仍为红色，违反了性质4需要平衡，此时z的叔叔y（结点14）为黑色--case uncle black。此时z的父亲（结点2）是z的祖父（结点14）的左孩子，z是z的父亲（结点2）的右孩子--case left right。left right情况的平衡思路为，先转变left right为left left。所以情况（b）中左旋z的父亲（结点2），旋转完成后变为情况（c）--left left。情况（c）中对z的祖父（结点11）进行右旋。旋转和交换颜色后达到情况（d）此时完成平衡。
rbtree_insert.png
#4. 删除
跟插入一样，重新着色和旋转是平衡红黑树的两种重要方式。在插入操作中，通过检查叔叔结点的颜色来决定不同的策略，在删除操作中，通过校验兄弟结点的颜色来决定不同的情形。
删除的大致思路：
- 执行标准的二叉搜索树删除流程。
- 借助辅助修正算法来平衡修改后的红黑树。
删除的伪代码如下：
RB_TRANSPLANT(T,u,v) {
if(u.p == T.nil)
T.root = v
elseif u == u.p.left
u.p.left = v
else u.p.right = v
v.p = u.p
}
RB_DELETE(T,z) {
y = z //y为带删除的结点
y.original-color = y.color //记录原始颜色
if(z.left == T.nil) //如果左孩子为空，需要转移z的右孩子（如果存在）
x = z.right //x此时表示待转移的目标
RB_TRANSPLANT(T,z,x)
elseif z.right == T.nil
x = z.left
RB_TRANSPLANT(T,z,x)
else y = TREE_MINIMUM(z.right) //寻找successor替代待删点，找到后继后，y需要更新
y.original-color = y.color //更新y的颜色
x = y.right //后继没有左孩子，可能有右孩子，那么其右孩子需要替代后继
if(y.p == z) //后继的父亲就是待删结点，说明后继无左子树
x.p = y
else RB_TRANSPLANT(T,y,x) //用后继的右孩子替代后继，x替代y
y.right = z.right //更新y的右子树，y需要替换z
y.right.p = y
RB_TRANSPLANT(T,z,y) //用y替换z
y.left = z.left //更新y的左子树
y.left.p = y
y.color = z.color
//如果待删除点的颜色为黑色或者后继的颜色为黑色，需要进行颜色修正
//为红色不需要修正，不影响黑高
if(y.original-color == BLACK)
RB_DELETE_FIXUP(T,x)
}
RB_DELETE_FIXUP(T,x) { //x此时为double black
while(x != T.root and x.color == BLACK)
if(x == x.p.left)
w = x.p.right //w为x的兄弟结点，w当前是右孩子
if(w.color == RED) //兄弟为红色(case-sibling-red)
w.color = BLACK
x.p.color = RED
LEFT_ROTATE(T,x.p)
w = x.p.right
//(case-sibling-red-two-children-black)
if(w.left.color == BLACK and w.right.color == BLACK)
w.color = RED
x = x.p
//case-sibling-black-right-left(one of children is red)
elseif(w.right.color == BLACK)
w.left.color = BLACK
w.color = RED
RIGHT_ROTATE(T,w)
w = x.p.right
w.color = x.p.color //case-sibling-black-right-right
x.p.color = BLACK
w.right.color = BLACK
LEFT_ROTATE(T,x.p)
x = T.root
else(same as then clause with "right" and "left" exchanged)
x.color = BLACK
}
关于RB_DELETE的几点说明：
- 始终维持结点y为树中待删除的结点或者移至树内的结点。当z的孩子结点小于2个时，y指向z，待删除；当z有两个子结点时，y指向z的后继，将y移至树中z的位置。
- 由于y的颜色可能改变，y.original-color记录了y改变前的颜色。当z有两个子结点时，则y!=z且结点y移至红黑树中结点z的原始位置；y.color = z.color给y赋予和z一样的颜色。前面我们保存过y的原始颜色，以判断是否需要进行平衡修正。如果它是黑色，那么删除或移动y会引起红黑性质的破坏。
- 结点x是为了将其保存的点移至y的原始位置。
- 如果结点y是黑色，就有可能已经引入一个或多个红黑性质被破坏的情况，所以需要借助辅助修正算法来重新平衡红黑树。
关于结点y为黑色，引发不平衡的说明：
- 如果y是原来的根结点，而y的一个红色孩子成为新的根结点，违反性质2（根结点为黑）。
- 如果x和x.p是红色的，违反性质4（红结点无红孩子）
- 在树中移动y将导致先前包含y的任何简单路径上黑结点个数少1。因此，y的任何祖先都不满足性质5。
下图是删除的过程中可能发生的几种可能的case：
delete_cases.png
图中灰色表示：或黑或红
删除示例：
delete_sample.png
网友评论