Red Black Tree
红黑树的定义、性质及相关证明
定义
红黑树(red-black tree)的众多平衡树中的一种。可以保证在基本动态集合操作的时间复杂度为 \(O(log(n))\)
其相较于普通树，在每个结点上添加了一个存储位来表示结点的颜色，仅能为Red或者Black，通过对任一从根到叶子节点的简单路径上的节点颜色进行约束，从而保证没有哪条路径会比其他路径长2倍，故近似平衡。
每个节点包含至少5个属性：颜色 color, 值 key, 左子树 left, 右子树 right, 父结点 p。如果没有父结点(根结点)或子结点，则指向NIL。
则根据此定义，红黑树的叶结点为NIL。
红黑树的红黑性质如下，用于维护平衡性：
- 每个结点要么红色，要么黑色
- 根节点黑色
- 每个页结点(NIL)黑色
- 如果一个节点红色，则其两个子结点黑
- 对每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
下面给出本文中涉及到的代码的一些定义：
#define NodeColor int
#define Red 1
#define Black 0
#define ElementType std::string
struct node {
NodeColor color;
ElementType value;
struct node *parent;
struct node *left;
struct node *right;
};
typedef struct node *Node;
typedef struct node *RBTree;
性质
定义某个结点x的黑高为 \(bh(x)\): \(x\) 到其任一叶结点的简单路径上黑结点的数目。
- 任一结点 \(x\) 为根的子树中，至少包含 \(2^{bh(x)} - 1\) 个内部结点
采用数学归纳法进行证明：
\[\mbox{Assume the number of inner node is }inner\_node \\ \mbox{If the height of x is 0, it means x is the nil, and }bh(x) = 1 \\ \mbox{Therefore, } inner\_node \ge 2^{bh(x) - 1} = 0 \mbox{ satisfaction} \\ \mbox{When the height of x is not 0, the black height of its subtree is } bh(x) \mbox{ or } bh(x) - 1\\ \mbox{Therefore, } inner\_node\_single\_sub\_tree \ge 2^{bh(x)} - 1 \\ \mbox{then, } inner\_node \ge (2^{bh(x)} - 1) + (2^{bh(x)} - 1) + 1 = 2^{bh(x)} - 1\]由第一数学归纳法，得证
- 一颗有n个内部节点的红黑树高度至多为 \(2log(n+1)\)
设树高h,由性质4，从根节点到叶结点的任一简单路径，至少有一半的结点是黑色。因此，根节点的黑高至少为 \(\frac{h}{2}\), 故
\[n \ge 2^{\frac{h}{2}} - 1 \Rightarrow h \le 2log(n+1)\]因此，在红黑树上的查找可在 \(O(log(n))\) 内完成。
相关操作
在搜索时，红黑树由其良好的性质能够提供很好的速度。但是当执行插入或删除操作时，就有可能破坏红黑性质。因此为了维护这些性质，必须提供一些操作用于改变树中某些结点的颜色以及指针结构
树的旋转
指针结构的修改是通过树的旋转(rotation)完成的。其能够在变换节点相关指针的情况下保证二叉搜索树的性质。
旋转有两种，分别为左旋(left rotation)和右旋(right rotation)。如下图所示：
以右旋为例，观察树中 \(\alpha, \beta, \gamma\) 整体在旋转后深度的变化：
- \(\alpha\): 减1
- \(\beta\): 不变
- \(\gamma\): 加1
因此，在当 \(\alpha\) 过深的时候，可以通过右旋进行调整，使整棵树保持平衡。左旋情况同理。
下面给出树的右旋的代码：
RBTree rightRotation(Node node) {
if (node == nullptr || node->left == nullptr) {
return node;
}
Node y = node, x = node->left, beta = x->right, elderParent = node->parent;
// change the elder parent
// it means node isn't the 'node' of the whole RB-tree
if (elderParent != nullptr) {
if (elderParent->left == node) {
elderParent->left = x;
} else if (elderParent->right == node) {
elderParent->right = x;
} else {
// error
throw std::exception();
}
}
// change x
x->right = y;
x->parent = y->parent;
// change y
y->parent = x;
y->left = beta;
// change beta if it is not nil
if (beta != nullptr) {
beta->parent = y;
}
return x;
}
插入
在插入一个新结点时，和二叉搜索树类似。但是为了维持红黑树的红黑性质，需要在插入节点后调用一个辅助函数，用于对结点进行重新着色并旋转。
相关代码如下：
RBTree rbInsert(RBTree root, Node z) {
Node x = root, y = nullptr;
// get the parent node of z, keeping BST property
while (x != nullptr) {
y = x;
if (z->value > x->value) {
x = x->right;
} else {
x = x->left;
}
}
// if y is nullptr, it means x is nullptr, which means the rb tree is empty. so z is the root node
// else insert z as a child of y depending on the values of y and z
if (y == nullptr) {
root = z;
} else if (z->value > y->value) {
y->right = z;
} else {
y->left = z;
}
z->parent = y;
z->left = nullptr;
z->right = nullptr;
// always colored red at first
z->color = Red;
// repainting the node and rotation.
rbInsertFixUp(root, z);
return root;
}
注意到在刚插入z的时候，总是将z着红色。这样做的原因是它可以更方便的维护红黑性质。
考虑因为插入而可能产生变化的红黑性质：
2.根节点黑色 4.如果一个节点红色，则其两个子结点黑 5.对每个结点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
- 插入红结点有更小的可能性改变红黑性质
插入黑结点 必然会改变性质5，使不同路径的黑高不同。但是插入红结点不会改变树的黑高。当树非空时，只会有一半左右的几率破坏性质4
- 插入红结点破坏的性质更容易修复
相较于修复不同路径黑高的不同，修复对性质4——红结点的后代只能为黑结点——的破坏更为容易。
红黑树中插入的关键便在于对可能存在的性质2, 4的破坏的修复，即上述代码中的rbInsertFixUp函数
修复可能被破坏的红黑性质
首先对结点名称做如下相关规定：结点z，父结点，祖父结点和叔结点。
在rbInsertFixUp(rbTree T, node z)中，在执行每次操作前，保证如下3个部分不变式：
- 节点z是红结点
- 如果
z->parent是根结点，则z->parent是黑结点 - 如果有任何红黑性质的破坏，则至多只有一条被破坏，或是性质2,或是性质4.
如果被破坏的是性质2, 则原因只能为z是根节点且是红结点。 如果被破坏的是性质4,则原因只能是z和
z->parent均为红结点。
此处先给出相关伪代码：
rbInsertFixUp(T, z){
while z.parent.color == Red {
if z.parent == z.parent.parent.left {
y = z.parent.parent.right
if y.color == Red{
z.parent = Black
y.color = Black
z.parent.parent.color = Red
z = z.parent.parent
}elif z == z.parent.right {
z = z.parent
leftRotation(T, z)
}
z.parent.color = Black
z.parent.parent.color = Red
rightRotation(T, z.parent.parent)
}else {
// same as then clause with "right" and "left" exchanged
}
}
T.root.color = Black
}
注意到当z为红色时，如果z为根结点，则其父结点为NIL，黑色，仅需要将z着黑即可
当z不为根结点时，如果z的父结点为黑结点，则没有破坏任何红黑性质。如果z的父结点为红色，则有可能破坏了性质4。且由于根结点为黑色，故z的父结点必然不为根结点，即z必有祖父结点。
由于树的对称性，6种对红黑性质的破坏方式可以归约为如下3种：
- 情况1： z的叔结点y是红色的
如下图所示，由于循环总的条件是z.parent为红色，故如果会破坏红黑性质，则仅有一种可能：破坏了性质4
此时仅需要将父结点与叔结点全部着黑，并将祖父结点着红，则以祖父节点为根的子树满足红黑性质。
因此若祖父结点为根节点，则破坏了性质2, 否则，则有可能破坏了性质4. 因此将祖父结点作为新的结点z，向上递归操作直至根节点。
考虑从根结点到叶结点的任一简单路径，虽然原本结点C有黑色变为红色，但由于其左右子树的根结点均为黑色，因此并未改变其黑高。
- 情况2: z的叔结点y是黑色的且z是一个右孩子
- 情况3: z的叔结点y是黑色的且z是一个左孩子
情况二与情况三本质上是相同的。如下图所示，情况2可以通过对z的父结点进行一次简单的左旋转变成情况3，且由于z和z->parent均为红结点，故不改变黑高，也不会破坏任何红黑性质。
通过对情况三下的祖父结点C进行一次右旋操作，并将B着黑色，C着红色，使得红色结点的父子关系，变成了兄弟关系，从而不会违反性质4。
且原本C节点所在位置的颜色仍然为黑色未变，因此没有改变黑高。
复杂度分析
一棵有n个结点的红黑树，高度为 \(O(log(n))\)，在while循环时，仅当情况1发生时，指针z才会向上爬升2层，且循环继续。情况2和3会直接终止循环。
因此while循环可能执行的总次数为 \(O(log(n))\)。而无论是情况1，还是情况2，3，在执行时都只消耗常数时间。
故rbInsert的总时间复杂度为 \(O(log(n))\)
删除
黑树上的删除比插入麻烦一些。
首先定义如下函数rbTransplant(rbTree T, node u, node v),该函数的作用是将红黑树T中，以u为根的子树替换为以v为根的子树。
rbTransplant(T, u ,v){
// it means u is the root
if u.parent == NIL{
T.root = v
}
elif (u == u.parent.left){
u.parent.left = v
}else{
u.parent.right = v
}
if (v != NIL){
v.parent = u.parent
}
}
对于删除操作，首先考虑普通的二叉搜索树(BST)的删除操作的如何进行的，此处，取要被删除的节点为z：
- 如果z的子结点全为NIL，则直接删除z即可
- 如果z仅有一个子结点，则删除z，并让z的非NIL子结点取代z的位置即可
- 如果z有两个子结点，考虑到要维持BST的有序性，则必须取z的后继(BST中比z大的第一个数)y，使其代替z的位置，并将z的左右子树分别作为该后继的左右子树。
再考虑红黑树的特性：红黑性质。
执行删除操作时，可能破坏的性质除了着色外，如果被删除的结点是黑色，则还有可能破坏黑高。
考虑可能会破坏黑高的情况如下：
- z至多只有一个子结点: 当z的颜色为黑时，会破坏黑高
- z有两个子结点: 当y的颜色为黑时，会破坏黑高
因此需要缓存z的颜色或者y的颜色。
而后在执行完类似BST中删除操作后，通过调用一个rbDeleteFixUp函数去重新着色或者进行旋转从而调整以保持红黑性质。
下面给出红黑树删除的伪代码：
rbDelete(T, z){
y = z;
// assume y does not exist at first.
y-origin-color = z.color;
if (z.left == NIL){
x = z.right;
rbTransplant(T, z, z,right);
}elif (z.right == NIL){
x = z.left;
rbTransplant(T, z, z.left);
}else {
// put y into the position of z and adjust relative variables
y = treeMinimum(z.right);
y-origin-color = y.color;
x = y.right;
if(y.parent == z && x != NIL){
x.parent = y;
}else {
rbTransplant(T, y, y.right);
y.right = z.right;
y.right.parent = y;
}
rbTransplant(T, z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (y-origin-color == Black){
rbDeleteFixUp(T, x);
}
}
对于z有两个子树的情况，在执行rbDeleteFixUp操作前，已经将y重新着色为z的颜色。因此y本身是不会破坏红黑树的任何性质。这很类似于仅仅将z的值修改为y的值，而后删除y。因此可能会破坏黑高的一步在令y的右子树替换y的时候，即x的颜色。
然后，仔细地讨论当y为黑色时，可能破坏红黑性质的几种情况：
- 如果y是根结点，则破坏了性质2——根结点必须为黑色。
- 如果x和x.parent均为红色，则破坏了性质4——如果一个节点红色，则其两个子结点黑。
- 删除y使得任一包含y的简单路径上的黑高-1，因此y的任何一个祖先都不满足性质5——黑高相等。
对于性质5的破坏，可以采用如下一种特殊的机制进行调整：
y原来的位置如今由x代替。在x上额外加上一层黑色，以此代替被删除的结点y。如此一来性质5便没有被破坏。但是此时结点x的颜色就变成了红黑色或者黑黑色，违背了性质1——结点颜色要么黑，要么红。
因此需要将多出的一种颜色进行反馈、修正，从而维持红黑性质。
注意，
x.color属性并不会因为这一层额外的黑色而改变。”加上”这一层额外的黑色是方便于调整。因为重新重新染色的操作比起调整每一条简单路径上的黑高要简单得多。
下面给出rbDeleteFixUp相关伪代码:
rbDeleteFixUp(T, x){
while (x != T.root && x.color == Black){
if (x == x.parent.left) {
// w is the brother node of x
w = x.parent.right;
if (w.clolor == Red){
w.color = Black;
x.parent.color = Red;
LeftRotation(T, x.parent);
w = x.parent.right;
}else {
if (w.left.color == Black && w.right == Black){
w.color = Red;
x = x.parent;
}else {
if (w.right.color == Black){
w.left.color = Black;
w.color = Red;
rightRotation(T, w);
w = x.parent.right;
}
w.color = x.parent.color;
x.parent.color = Black;
w.right.color = Black;
leftRotation(T, x.parent);
x = T.root;
}
}
}else {
// same as then clause with "right" and "left" exchanged;
}
}
x.color = Black;
}
对于红黑色而言，可以简单地将红色抹去，改为黑色，而不会破坏任何性质。
对于黑黑色而言，则将多出的黑色不断向上移动，直到多出的黑色遇见红色结点，将其染黑，或者直到根结点，此时可以直接抹除多余的黑色。
因此在while循环体中，始终保持x指向一个非根黑黑结点。由于x为黑黑色，因此x的兄弟w结点必然不为空（否则不满足性质5黑高相等）。
而此时破坏红黑性质的情况有8种，由于树的对称性，因此可以被归约如下为4种。
结点颜色由深到浅分别代表：黑色，红色，任意颜色无影响
- 情况1: x的兄弟结点w是红色的
因为x此时为黑黑色，因此w必有黑结点，否则黑高不等。因此可以通过对w和x.parent重着色并旋转，相当于在x子树上添加一个红结点，在w子树上删除一个红结点。因此不会破坏任何性质。
这么做的目的是使x的兄弟结点为黑色，转化为下面三种情况中的一种。
- 情况2: x的兄弟结点w是黑色的，且w的两个子结点都是黑色的
因为x,w均黑色，因此可以在x,w上都去掉一重黑色，使得x只有一重黑色，而w转为红色。而w的两个孩子均为黑色，不违背性质4。
为了补偿失去的一个黑高，在x.parent上添加一重黑色，即此时将x指向x.parent。
- 情况3: x的兄弟结点w是黑色的，且w的左孩子是红色的，w的右孩子是黑色的
此时考虑将w与其左儿子w.left交换颜色，并执行右旋操作。该操作并不会改变任一简单路径上的黑高。此时该情况转为情况4
- 情况4: x的兄弟结点w是黑色的，且w的右孩子是红色的
将x的兄弟结点w重着色为x.parent的颜色，而后将x.parent着黑色，对x.parent执行一次左旋操作。此时可以在不改变黑高的情况下， 将x的双重黑色去掉。
考虑 \(\alpha, \beta, \gamma, \delta, \epsilon, \zeta\),在x为黑黑时，他们的黑高相同。如上图所示，对 \(\gamma, \delta, \epsilon, \zeta\) 而言，旋转前后，他们的黑高无任何改变。对 \(\alpha \beta\) 而言，在旋转前，其在x结点上黑高+2（因为x是黑黑结点），在旋转后，x和x.parent均为黑色(即图中A, B)，其均为黑结点，仍然是黑高+2。因此在变化前后，\(\alpha, \beta, \gamma, \delta, \epsilon, \zeta\) 的黑高没有任何改变，即满足红黑性质。
因此，此时整棵树无任何红黑性质的违反。故将x赋值为T.root从而跳出循环。
复杂度分析
树的高度为 \(O(log(n))\) ，除去rbTreeFixUp外，时间复杂度为 \(O(log(n))\) 。在rbTreeFixUp函数中，x最多在while循环中上升 \(O(log(n))\) 次到根，因此，总的时间复杂度为 \(O(log(n))\).
总结
红黑树通过对结点引入颜色这个概念，从而实现了对某一子树过深的探测，并通过旋转、重着色进行修复。以此保证了树的查找、增加、删除的时间开销均维持在 \(O(log(n))\)