红黑树

之前讲过二叉搜索树，可以支持任何一种基本动态集合操作，而且时间复杂度都是O(h)，所以在树高比较低的时候，这些操作会执行的很快，而且树的高度很高的时候，执行速度不比链表上执行的快。红黑树是“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度是O(lg n)。

红黑树的性质

红黑树是一种特殊的二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以使红或者黑。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长两倍，所以是近似于平衡的。

树中每个结点有5个属性：color（颜色）, key（关键字）, left, right, p（父结点）。如果一个结点没有子结点或者父结点，则该结点相应的指针属性值为NIL。

红黑树满足的性质：

• 每个结点是红色的或者黑色的
• 根节点是黑色的
• 叶结点是黑色的
• 如果一个结点是红色的，则它的两个子结点都是黑色的
• 对每个结点，从该点到其他所有后代叶结点的简单路径上，均包含相同数目的黑色结点

为了便于处理红黑树代码中的边界条件，使用一个哨兵来表示NIL。对于一棵红黑树T，哨兵T.nil是一个与树中普通结点有相同属性的对象。它的color属性为BLACK，其他属性可以设为任意值。

使用哨兵以后就可以把NIL视为普通结点。

从某个结点x出发到达一个叶结点的任意一条简单路径上的黑色结点个数成为该结点的黑高，记为bh(x)，又由红黑树的性质决定，该结点出发的所有简单路径的黑高都相同，所以从根结点出发的黑高是红黑树的黑高。

一棵有n个内部结点的红黑树的高度至多为 2 lg( n+1 )。

旋转

对搜索树进行插入和删除操作的时候有可能破坏红黑树的性质，为了维护这些性质必须对某些指针结构进行修改。指针结构的修改是通过旋转来完成的。

旋转分两种：左旋和右旋。

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
    else x.p.right = y
    y.left = x
    x.p = y

右旋的代码与左旋是对称的，两种操作都在O(1)时间内完成。只有指针发生改变，其他属性都保持不变。

插入

和之前二叉搜索树的插入大体差不多，不过有些不同。

RE-INSERT(T,z)
    y = T.nil
    x = T.root
    while x != T.nil
        y = x
        if z.key < x.key
            x = x.left
        else x = x.right
    z.p = y
    if y == T.nil
        T.root == z
    elseif z.key < y.key
        y.left = z
    else y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = RED
    RB-INSERT-FIXUP(T,z)

RB-INSERT-FIXUP(T,z)
    while z.p.color == RED
        if z.p == z.p.p.left
            y == z.p.p.left
            if y.color == RED
                z.p.color = BLACK
                y.color = BLACK
                z.p.p.color = RED
                z = z.p.p
            elseif z == z.p.right
                z = z.p
                LEFT-ROTATE(T,z)
            z.p.color = BLACK
            z.p.p.color = RED
            RIGHT-ROTATE(T,z.p.p)
        else （left <-> right）
    T.root.color = BLACK

新插入的结点为红色，RB-INSERT-FIXUP用来保持红黑树的性质。

在插入的时候，破坏红黑树性质只有两种情况：插入结点为根结点，而z被着色为红色，则破坏了根结点为黑色的性质；如果插入结点的父结点是红色，则破坏了红色结点子结点都为黑色的性质。

删除

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-original-color = y.color
    if z.left == T.nil
        x = z.right
        RB-TRANSPLANT(T,x,z.right)
    elseif z.right == T.nil
        x = z.left
        RB-TRANSPLANT(T,z,z.left)
    else y = TREE-MINIMUM(z.right)
        y-original-color = y.color
        x = y.right
        if y.p == z
            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)

RB-DELETE-FIXUP(T,x)
    while x != T.root and x.color == BLACK
        if x == x.p.left
            w = x.p.right
            x.p.color = RED
            LEFT-ROTATE(T,x,p)
            w = x.p.right
        if w.left.color == BLACK and w.right.color == BLACK
            w.color = RED
            x = x.p
        else if w.right.color == BLACK
            w.left.color = BLACK
            w.color = RED
            RIGHT-ROTATE(T,w)
            w = x.p.right
        w.color = x.p.color
        x.p.color = BLACK
        w.right.color = BLACK
        LEFT-ROTATE(T,x,p)
        x = T.root
    else(left <-> right)
    x.color = BLACK