红黑树

    struct RBTree       //红黑树的数据结构
        color ;         //颜色,R:红色;B:黑色
        key ;           //关键字
        right ;         //右指针
        left ;          //左指针
        parent ;        //父指针

性质

  1. 每个节点或是红色,或是黑色
  2. 根节点是黑色
  3. 每个叶节点( nil[T] : 哨兵 )是黑色
  4. 如果一个节点是红色,则其左右孩子都是黑色
  5. 对于每个节点,从该节点到子孙节点的所有路径上包含相同的黑节点数量,即:黑高度相同

一棵红黑树的高度至多为 2lg(n+1)

二叉树的左旋和右旋

        |                                 |
        X         LeftRotate              Y
      /   \      --------------->       /   \
     a     Y    <---------------       X     c
         /   \    RightRotate        /   \
        b     c                     a     b

    LeftRotate( T, x )      //左旋(一定要有右子树)
        y = right[x] ;
        right[x] = left[y] ;
        left[y] && parent[left[y]] = x ;

        if parent[x]        //x不是树根
            left[parent[x]] == x and left[parent[x]] = y \
            or right[parent[x]] = y ;
        else
            root[T] = y ;

        parent[y] = parent[x] ;
        left[y] = x ;
        parent[x] = y ;

    /*
    右旋与左旋对称
    */

红黑树的插入

    RBTreeInsert( T, z )        //先将color[z]设为红色
        y = nil[T] ;            //再将z按二叉查找树的方法插入红黑树
        x = root[T] ;           //最后调用RBTreeInsertFixup恢复红黑树的性质

        while x != nil[T]
            y = x ;
            if key[x] > key[z]
                x = left[x] ;
            else
                x = right[x] ;

        if y = nil[T]
            root[T] = z ;
        else if key[y] > key[z]
            left[y] = z ;
        else
            right[y] = z ;

        parent[z] = y ;
        left[z] = nil[T] ;
        right[z] = nil[T] ;
        color[z] = red ;

        RBTreeInsertFixup( T, z ) ;

红黑树性质恢复函数(插入部分)

B为黑色节点,R为红色节点

  • 可以将红黑树看成是 2-3-4 B树
        B
      /   \      一个满的 2-3-4 树的节点,
     R     R     且黑节点为 2-3-4 树新节点的标志
    / \   / \

插入情况1

            1B
          /    \       #3R为新增节点
         2R      B     #这是由1B和2R组成的 2-3-4 节点还没有满
        /  \    / \    #将插入节点并入即可
       3R   a  b   c
      /  \
     d    e

             |
             |
             V

            2B           #右旋且重新着色后
          /    \         #将3R并入 2-3-4 平衡数
         3R    1R        #并将2R着色为2B,1B着色为1R
        /  \  /  \
       d   e  a   B
                 / \
                b   c

插入情况2

            1B
          /    \         #3R为新增节点   
         2R     B        #直接转化为情况1
        /  \   / \       #通过以 2R 为轴左旋  
       a   3R b   c     
          /  \
         d    e

             |
             |
             V

            1B
          /    \      
         3R      B    
        /  \    / \   
       2R   e  b   c
      /  \
     a    d

插入情况3

        1B       #3R为新增节点
      /    \     #这是无论新增节点是其父节点的左孩子还是右孩子 
     2R    4R    #只需将 1B 着色为 1R, 2R 和 4R 着色为 2B 和 4B
     |           #并将 3R 的指针指向 1R,重新进行红黑平衡即可
     3R

        |
        |
        V

        1R      
      /    \     #此时,此子树的黑高度+1
     2B    4B    #对于 2-3-4 树,子树高度+1
     |      
     3R

实现

    RBTreeInsertFixup( T, z )
        while color[parent[z]] == red
            if left[parent[parent[z]]] == parent[z]     //在其祖父的左子树上
            /*
            这时不用当心 parent[parent[z]] 会指向 nil[T] 
            因为, color[parent[z]] == red
            所以, parent[z] 不是根节点
            所以, 一定存在 parent[parent[z]] != nil[T]
            */
                y = right[parent[parent[z]]] ;

                if color[y] == red                          //情况3
                    color[parent[z]] = black ;
                    color[parent[parent[z]]] = red ;
                    color[y] = black ;
                    z = parent[parent[z]] ;
                else
                    if right[parent[z]] == z                //情况2
                        z = parent[z] ;
                        LeftRotate( T, z ) ;
                    color[parent[z]] = black ;              //情况1
                    color[parent[parent[z]]] = red ;
                    RightRotate( T, parent[parent[z]] ) ;
            else                                         //在其祖父的右子树上
                /*与左子树上的代码对称,仅需替换left,right*/
                ...

        color[root[T]] = black ;

红黑树的删除

  • 先像删除普通二叉查找树一样,删除节点
  • 如果删除的节点是黑节点,调用 RBTreeDeleteFixup 恢复红黑书性质
    RBTreeDelete( T, z )
    //普通的二叉查找树删除
        if left[z] == nil[T] or right[z] == nil[T]
            y = z ;
        else
            y = BinTreeSuccessor( z ) ;

        if left[y] != nil[T]
            x = left[y] ;
        else
            x = right[y] ;

        if x != nil[T]
            parent[x] = parent[y] ;

        if parent[p] != nil[T]
            if left[parent[y]] == y
                left[parent[y]] = x ;
            else
                right[parent[y]] = x ;
        else
            root[T] = x ;

        if y != z
            copy y to z except( left, right, parent ) ;
        //普通二叉查找树删除 end

        if color[y] == black 
            RBTreeDeleteFixup( T, x ) ;

        return y ; 

红黑数性质恢复函数(删除部分)

当切仅当被删除的节点是黑色,才需要进行红黑书性质的恢复

        |
        R       #x的父节点是R红色,即原y的父节点
      /   \     #则a一定不是nil[T],且颜色为B,因为y是黑节点
     x     a
    / \
   b   c

删除情况1(x为R):

      y       #以 2-3-4 树的观点来看,被删除的y有一个红孩子
    /        
   x(R)       #则将其(x)的颜色变为B,过程结束

删除情况2(x为B):

x(y)的父节点元素未满(2-3-4 树),且x(y)的兄弟节点(z)只有一个元素
        1(B)        #前面已经证明过z不可能为nil[T]
       /    \       #将z着色为红色,以1为根的整个子树高度 -1
      x      z(B)   #用1继续进行红黑平衡
x(y)的兄弟节点有2个以上元素(2-3-4 树)
       ... F(B) ...             #...表示有R元素或者没有元素    
        /        \              #从x的兄弟节点中哪一个元素到父节点中   
       x        1 - 2 ...       #再从x的父节点中分裂一个元素出来形成新的节点
     /   \     /  |  \          #x成为新节点的子节点
    a     b   c   d   ?

            |
            |
            V

       ... 1(B) ...             
        /        \              
       F(B)      2 ...
     /   \     /  | 
    x     c   d   ?   
   / \
  a   b
x(y)的兄弟节点只有一个元素,但父节点有两个以上元素( 2-3-4 树)
            F1 - F2 ...         #从x(y)的父节点中分裂一个元素出来
          /    |    \           #与x(y)的兄弟节点B合并组成一个新的节点
         x     B     a          #将x变成这个新节点的子节点
        / \   / \
       c   d e   f

                |
                |
                V

                 F2 ...    
               /    \      
            F1- B    a     
           /  |  \
          x   e   f
         / \  
        c   d

实现

    RBTreeDeleteFixup( T, x )
        while x != root[T] and color[x] == black
            if x == left[parent[x]]
                w = right[parent[x]] ;
                
                if color[w] == red          //父节点有两个元素
                    color[w] = black ;      //并将父节点中
                    color[parent[x]] = red ;//关键字较小元素置为红色
                    LeftRotate( T, parent[x] ) ;
                    w = right[parent[x]] ;

                if color[left[w]] == black and color[right[w]] == black
                //兄弟节点只有一个元素,与x的父节点合并
                    color[w] = red ;        //子树高度-1
                    x = parent[x] ;         //以x的父节点重新进行红黑平衡
                else
                //兄弟节点有两个以上元素
                    if color[right[w]] == black //调整x的兄弟节点中元素的顺序
                        color[left[w]] = black ;
                        color[w] = red ;
                        RightRotate( T, w ) ;
                        w = right[parent[x]] ;

                    //从x的兄弟节点中分裂一个元素到父节点
                    //父节点在分裂一个元素出来组成新的节点
                    //新的节点将成为x的父节点
                    color[w] = color[parent[x]] ;
                    color[parent[x]] = black ;
                    color[right[x]] = blach ;
                    LeftRotate( T, parent[x] ) ;
                    x = root[T] ;

            else //在其父节点的右子树上
                /*与左子树上的代码对称,仅需替换left,right*/
                ...

        color[x] = black ;