红黑树

红黑树
一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：
1. 每个结点或者为黑色或者为红色。
2. 根结点为黑色。
3. 每个叶结点(NIL)都是黑色的。
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。
5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。
红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。
节点x的黑高度：从某个节点x到达一个叶结点的任意一条路径上包含的黑色结点（包括叶结点）数量。用bh(x)表示。另外规定叶结点的黑高度为0。
定理：一棵含有n个内结点的红黑树的树高至多为2log(n+1)
证明：先证以某一节点x为根的子树中至少包含2^bh(x) - 1个内节点。用归纳法：
(1)x的高度为0，则x为一叶节点，以x为根的子树中包含2^bh(x) - 1 = 2^0 - 1 = 0;
(2)考虑一个高度为正值的节点x，它是个内节点，且有两个子女，每个子女根据其自身的颜色是红或黑而有黑高度bh(x)或bh(x) - 1，由归纳假设，每个子女至少包含2^(bh(x) - 1) - 1个内节点。所以，以节点x为根的子树中至少包含(2^(bh(x) - 1) - 1) + (2^(bh(x) - 1) - 1) + 1 = 2^bh(x) - 1。命题得证。
设h为树的高度，根据性质4，从根到叶节点（不包括根）的任一条简单路径上，至少有一半的节点必是黑的。从而，根的黑高度至少为h / 2；故有 n>= 2^(h / 2) - 1 有lg(n + 1) >= h / 2 或(h <= 2lg(n +1))。
所以，命题得证。
由这个定理可知，动态集合操作Search, Minimum, Maximum, Successor, Predecessor可用红黑树在O(lg n)时间内实现。
但是操作TreeInsert、TreeDelete，有可能破坏了红黑树的性质。所以我们要做一些操作来把整棵树修补好。
节点的LeftRotate和RightRotate操作，所谓LeftRotate(x)就是把节点x向左下方向移动一格，然后让x原来的右子节点代替它的位置。而RightRotate当然就是把LeftRotate左、右互反一下。如下图：

注意，LeftRotate(x)后，x的右子树变成了原来y的左子树，RightRotate反之。思考一下，这样一次变换后，仍然满足二叉搜索树的性质。在红黑树的插入、删除中，要用到很多LeftRotate和RightRotate操作。
一、插入
首先是二叉搜索树的插入步骤，把新节点z插入到某一个叶节点的位置上，把z的颜色设成红色。如果z的父节点也是红色，我们要执行下面一个迭代的过程，称为InsertFixup，来修补这棵红黑树。
在InsertFixup中，每一次迭代的开始，指针z一定都指向一个红色的节点。如果z->p是黑色，那我们就大功告成了；如果z->p是红色，显然这就违返了红黑的树性质，那么我们要想办法把z或者z->p变成黑色，但这要建立在不破坏红黑树的其他性质的基础上。
在每一次迭代中，我们可能遇到以下三种情况。
Case 1: z's uncle y is red

Case 2: z's uncle y is black and z is a right child
Case 3: z's uncle y is black and z is a left child

反复迭代，直到某一次迭代开始时z->p为黑色而告终，也就是当遇到Case 3后，做完它而告终。
二、删除
红黑树中删除一个节点z的方法也是首先按部就班二叉搜索树的过程。如果删除的节点是黑色的，那么红黑树的性质就被破坏了。这时我们就要执行一个称为DeleteFixup的过程，来修补这棵树。
一个节点被删除之后，一定有一个它的子节点代替了它的位置。我们就设指针x指向这个代替位置的节点。显然，如果x是红色的，那么我们只要把它设成黑色，它所在的路径上就重新多出了一个黑色节点，那么红黑树的性质就满足了。然而，如果x是黑色的，那我们就要假想x上背负了2个单位的黑色。那么红黑树的性质也同样不破坏，但是我们要找到某一个红色的节点，把x上“超载”的这1个单位的黑色丢给它，这样才算完成.deleteFixup做的就是这个工作。
DeleteFixup同样是一个循环迭代的过程。每一次迭代开始时，如果指针x指向一个红色节点，把它设成黑色即告终。如果x黑色，那么我们就会面对以下4种情况。
Case 1: x's sibling w is red

Case 2: x's sibling w is black, and both of w's children are black

Case 3: x's sibling w is black, w's left child is red, and w's right child is black

Case 4: x's sibling w is black, and w's right child is red

Case 4 occurs when node x's sibling w is black and w's right child is red. By making some color changes and performing a left rotation on p[x], we can remove the extra black on x, making it singly black, without violating any of the red-black properties. Setting x to be the root causes the while loop to terminate when it tests the loop condition.