红黑树性质
红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位用来表示结点颜色，可以是Red或者Black。通过对任意一条从根到叶子的简单路径上各个结点颜色的约束，红黑树可以确保没有一条路径会比其它路径长出2倍，因而是近似于平衡的。
红黑树满足下面的性质：
- 每个结点要么是红色的，要么是黑色的。
- 根结点是黑色的。
- 每个叶结点（NIL）是黑色的。
- 如果一个结点是红色的，那么它的两个子结点都是黑色的。
- 对每个结点，从该结点开始到其所有后代叶结点的简单路径上，包含的黑色结点的数目相同。
树高
定义：从某个结点(x)出发（不包含该结点），达到其后代叶节点的简单路径上包含的黑色结点的数目为黑高（black-height），记为(bh(x))，由性质5可知这一定义是明确的。
引理：一棵有n个内部结点（不包含NIL叶结点）的红黑树的高度至多为(2lg(n+1))。
证明： 先证明以(x)为根的子树中至少包含(2^{bh(x)}-1)个内部结点。这里采用归纳法证明。
当(x)的高度为0时，(x)是叶结点，黑高(bh(x)=0)，所以至少包含(2^0-1=0)个内部结点，满足条件。
当(x)的高度大于0时，(x)的两个子结点的黑高要么为(bh(x))，要么为(bh(x)-1)，取决于子结点是红色还是黑色，所以以(x)为根的子树至少包含((2^{bh(x)-1}-1)+(2^{bh(x)-1}-1)+1=2^{bh(x)}-1)个内部结点。
所以以(x)为根的子树中至少包含(2^{bh(x)}-1)个内部结点。
为了完成引理的证明，设(h)为树的高度，由性质4可知黑高至少为(frac{h}{2})，于是有：
推出
即得证
旋转
红黑树通过旋转（rotation）来修改指针结构，通过左旋（left-rotation）和右旋（right-rotation）来重新均衡一下左右子树的高度：
LEFT-ROTATE(T, x)
// 假设x.right不为NIL，且根节点的父节点为NIL
y = x.right
// y的左儿子变为x的右儿子
x.right = y.left
if y.left != T.nil
y.left.p = x
// y变成x父节点的儿子
y.p = x.p
if x.p == T.nil
T.root = y
else if x == x.p.left
x.p.left = y
else
x.p.right = y
// x变为y的左儿子
y.left = x
x.p = y
RB-INSERT-FIXUP
当新插入一个红色结点后有可能违反红黑树的性质，需要调用RB-INSERT-FIXUP函数重新修复红黑树的性质：
RB-INSERT-FIXUP(T, z)
while z.p.color == RED
// 由于根节点是黑色，所以z.p.p一定存在
if z.p == z.p.p.left
y = z.p.p.right
if y.color == RED
z.p.color = BLACK // case1
y.color = BLACK // case1
z.p.p.color = RED // case1
z = z.p.p // case1
else
if z == z.p.right
z = z.p // case2
LEFT-ROTATE(T, z) // case2
z.p.color = BLACK // case3
z.p.p.color = RED // case3
RIGHT-ROTATE(T, z.p.p) // case3
else
same as above with "left" and "right" exchanged
T.root.color = BLACK
情况1：z的叔结点y是红色的
情况2：z的叔结点y是黑色的，且z是一个右孩子
情况3：z的叔结点y是黑色的，且z是一个左孩子
分析：对于情况1，每次z指针沿着树提升2层，对于情况2和情况3最多执行一次，因为情况2可以转化到情况3，情况3执行完就恢复红黑树的性质了，所以最多发生2次旋转操作。
删除
要删除红黑树的一个结点z时，并不是直接删除结点z，而是删除一个用来替代z的结点y，当z没有子结点时，y就是z本身；当z只有一个子结点时，y就是z的子结点；当z有两个子结点时，y就是结点z的后继结点。当结点y被删除后，由结点x来接替y空缺的位置。
// 将v移植到u的父节点下替代u
RB-TRANSPLANT(T, u, v)
if u.p == T.nil
T.root = v
else if u == u.p.left
u.p.left = v
else
u.p.right = v
// 这里v可以为T。nil
v.p = u.p
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
// 没有子结点或者只有右子结点
x = z.right
RB-TRANSPLANT(T, z, z.right)
else if z.right == T.nil
// 只有左子结点
x = z.left
RB-TRANSPLANT(T, z, z.left)
else
// 有两个子结点，那么找出后继y
y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
// x可以为T.nil
x.p = y
else
RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
当删除了一个黑色结点之后，结点x就需要被当作红黑结点，或者双重黑色结点来看待，才能符合黑高一致的性质，下面需要用RB-DELETE-FIXUP函数来进行修复：
RB-DELETE-FIXUP(T, x)
while x != T.root and x.color == BLACK
if x == x.p.left
// 由于x是双重黑色的结点，所以兄弟结点w不为nil
w = x.p.right
if w.color == RED
w.color = BLACK // case1
x.p.color = RED // case1
LEFT-ROTATE(T, x.p) // case1
w = x.p.right // case1
if w.left.color == BLACK and w.right.color == BLACK
w.color = RED // case2
x = x.p // case2
else
if w.right.color == BLACK
w.left.color = BLACK // case3
w.color = RED // case3
RIGHT-ROTATE(T, w) // case3
w = x.p.right // case3
w.color = x.p.color // case4
x.p.color = BLACK // case4
w.right.color = BLACK // case4
LEFT-ROTATE(T, x.p) // case4
x = T.root // case4
else
same as above with "left" and "right" exchanged
x.color = BLACK
情况1：x的兄弟结点w是红色的
情况2：x的兄弟结点w是黑色的，且w的两个子结点也是黑色的
情况3：x的兄弟结点w是黑色的，且w的左孩子是红色的，右孩子是黑色的
情况4：x的兄弟结点w是黑色的，且w的右孩子是红色的
下图中，黑色表示黑色结点，深色阴影表示红色结点，浅色阴影（没有阴影）表示既可以为黑色也可以为红色的结点：
分析：：情况1可以转换为情况2，3，4，并且情况1转换之后新的结点x将为红色，会终止循环；只有情况2会继续循环，并且每一次将x指针沿着树提升1层；执行完情况3和情况4之后就恢复红黑树性质了，所以最多执行3次旋转操作。