红黑树

红黑树的性质

红黑树中每个节点中增加了一个存储位来表示节点的颜色, 是RED或BLACK. 每个节点包含五个属性, color, key, left, right, p. 通过对任意一条路径上各个节点的颜色进行约束, 确保没有一条路径会比其他路径长两倍, 因此是近似与平衡的. 红黑树满足的性质:

1. 每个节点或红色或黑色.
2. 根节点是黑色
3. 每个页节点(NIL)是黑色. 叶节点均为NIL.
4. 如果一个节点是红色, 则它的两个子节点是黑色的.
5. 对于每个节点, 从该节点到其所以后代叶节点的简单路径上, 均包含相同数目的黑色节点.

为了便于处理红黑树边界问题, 使用一个哨兵来代表NIL.

黑高: 从某个节点出发(不包含该节点), 到达一个叶节点的任意一条路径上黑色节点数量叫做该节点的黑高. 记为bh(x).

红黑树还有一个重要性质为: 一个有n个节点内部节点的红黑树的高度至多为2log(n+1).

旋转

旋转是红黑树中最基本的操作, 这在插入删除中时常会用到. 旋转操作不会破坏红黑树性质, 旋转完成不用考虑维护红黑树性质的问题. 旋转分为左旋和右旋, 其效果如下图:

旋转分为左旋和右旋, 其效果如下图:

插入

无论是构建一棵红黑树还是在后续的使用中, 插入操作都发挥了至关重要的角色, 插入一个新节点时, 我们将新节点置为红色, 以右节点>父节点>左节点的性质进行插入. 插入后将会破坏红黑树的性质, 因此我们需要添加操作来维护其性质. 插入可能违反的性质是第四条, 即红色节点的子节点必须是黑色的. 因此我们需要不断旋转以并从下向上调整以维持其性质. 并且在调整的过程中, 一次调整之后保证子树的第四条原则成立的同时还可能破坏其父节点的第四条性质. 调整的终止条件即为, 调整后其父节点为黑色. 下图展示了插入节点破坏性质4的情况.

当前节点Z与其父节点由于不满足第四条性质而需要进行调整时, 可能出现六种情况, 其中前三种与后三种对称, 这取决于z的父节点是z的祖父节点的左孩子还是又孩子. 这里只讨论前三种情况.

情况一: z的叔父节点为红色

此时的处理相对简单, 由于z的叔父节点是红色, z的父节点也是红色, z本身也是红色, 只有z的祖父节点是黑色, 则只用将z的父节点与叔节点变换成黑色, 祖父节点变成红色(将祖父节点变红是为了维持第无条性质不变, 即路径中多了一个黑色节点, 就要将原来的一个黑色节点变红.). 这时, z和z的父节点和叔节点都满足性质, 于是将z上移两层, 使z指向原来z的祖父节点, 继续进行判断. 图示如下:

情况二: z的叔节点y为黑色, 且z是一个右孩子

对z进行一次左旋即变成情况三.

情况三: z的叔节点y为黑色, 且z是一个左孩子

此时, z和z的父节点为红色, z的叔节点为黑色. 我们只需要将z的父节点变成黑色, z的祖父节点变成黑色, 而后以祖父节点作为旋转点进行一次右旋即可. (右旋的目的是保持性质五不变, 将父节点变成黑色将导致祖父节点左子树的黑高比右子树的大, 进行一次旋转后则保证原来祖父位置的左右子树的黑高均不变.) 图示如下:

删除

删除操作应该是红黑树中最难的部分了, 应该是面试的重灾区. 其中处理的操作也是相当窒息, 不得不佩服先人的智慧. 下面进行详细介绍.

从红黑树中删除某个节点, 被删除节点状态有两种.

被删除节点状态一: 被删节点左右子节点至少有一个没有

此时比较简单, 只需要将存在子节点的那个子节点移到原来节点位置, 并将原来节点删除即可.

被删节点状态二: 被删节点左右均存在子节点

此时为了维护红黑树排序顺序, 应该将当前节点后继取出替换原来节点. 当前节点的后继一定满足左节点为空.此时需要将后继的右子树替换为后继原来的位置, 并将后继取出替换被删节点的位置.

删除节点后很有可能会破坏红黑树前述的五条性质, 此时为了能够统计进行修复, 我们应该合理设计上述的删除过程. 我们可以发现, 无论是情况一还是情况二, 在操作时均会有一步由子节点替换当前节点的操作. 即在情况一中, 被删节点存在的子节点替换当前节点, 在情况二中, 后继的右节点替换后继. 应该为了方便统一处理. 我们在情况二中, 在用后继替换被删节点时应该保证节点颜色同时替换, 此时可以看做应该删除位置实际没有变化, 变化只发生在后继节点的位置(从颜色上看, 可以简单的认为其实被删除节点是后继节点), 这将方便我们后续的修复红黑树性质的操作.

而后我们分析进行上述操作后将会破坏哪些性质. 当被删除节点为红色时, 所以性质均不会被破坏. 只有当被删节点为黑色时性质会被破坏, 且必然被破坏. 由于被删除节点可能是根节点, 因此子节点上移可能是一个红色节点上移, 因此性质二(根节点为黑色)可能被破坏. 当在子节点上移时, 如果子节点本身是红色的, 并且被删节点的父节点也是红色的, 则性质四(红色节点的子节点均为黑色)会被破坏, 由于删除了一个黑色节点, 其父代节点的黑高均会减少一, 此时性质五将会被破坏. 因此总共有三条性质可能被破坏.

当上移节点为红色时处理相对简单. 上移的节点均为红色, 此时我们只需要将上移的节点变成黑色即可维护红黑树性质.(此时根节点为黑色, 红色节点下也不会出现红色节点, 黑高减一也会由于上移的节点由红色变为黑色而恢复). 当上移节点为黑色时, 实际只有性质吴被破坏了, 但处理相对复杂.

下面就是最秀的操作了. 为了解决父辈黑高少一的问题, 我们在原本就是黑色节点上在加一层黑色(并不是要再在节点上添加一个元素, 而是以双重黑色看待这个节点), 并且这层黑色是可以传递的, 当我们将这个节点的黑心消去时, 对对应的就应该有一个组节点应该增加一个黑色. 如果对应的只有一个红色节点增加黑色, 则将该节点变成红色即可使红黑树性质得以恢复. 此时的处理又分为八种种情况(前四种与后四中对称). x为当前节点, w为兄弟节点. 注意, x为双重黑色节点.

情况一: x的兄弟节点w是红色的

此时, 我们将兄弟节点变成黑色的, 将父节点变成红色并绕着父节点右旋, 此时即将情况一转化为情况二,三,四中的一个.

情况二: x的兄弟节点w为黑色, 且w的两个子节点均为黑色

此时我们直接从当前节点和兄弟节点中退去一层黑色, 此时当前节点依然是黑色, 其兄弟节点变换成红色. 与之对应的, 父节点一个加一层黑色. 将当前节点指向父节点, 考察父节点情况.

情况三: x的兄弟节点w是黑色的, w的左孩子为红色的, w的左孩子为红色的, w的右孩子为黑色的.

我们可以交换w和其左孩子的颜色, 而后对w进行右旋而不违背红黑树任何性质. 此时我们就将情况三转变到情况四.

情况四: x的兄弟节w点是黑色的, 且w的右孩子为红色的.

此时, 我们将当前节点和其兄弟节点中去掉一层黑色, 此时我们让兄弟节点的右孩子变成黑色, 互换兄弟节点和父节点的颜色, 而后绕父节点左旋, 随后我们就可以去掉当前节点的一层黑色并且不违反任一性质. 此时变换即结束. 让当前节点指向根节点,在下一次循环即退出.

图示:

获取指定元素的左右边界

在set中, 我们可以查找指定元素的做哟边界, 这里我们也尝试实现这一功能. 这里我设计里两个函数, 分别是Right_side_min以及Left_side_max分别表示获取右边最小值(后继)以及左边最大值(前驱).

在查找边界时, 对于Right_side_min是寻找第一个大于指定元素的节点, Left_side_max是小于指定元素的最后一个. 此时我们可以使用两个指针进行操作, 对于Right_side_min, 第一个指针记录搜索到当前遇到的大于指定节点的最后一个, 第二个指针表示当前搜索到达位置, 对于Left_side_max来说, 第一个表示搜索到当前遇到的小于指定元素的最后一个, 第二个指针表示当前搜索到达位置. 搜索终止条件为遇到与指定元素值相同的元素或者搜索到哨兵节点(即最终也未找到对应元素). 对应于这两个结果, 处理策略也不同.

树中存在节点与指定值一致

此时, 我们应该考虑其是否存在子节点, 对于Right_side_min来说, 如果存在右子树, 则应该是右子树中最小值.如果没有右子树则一个返回第一个指定记录的大于当前节点的最后一个. 对于Left_side_max来说, 如果存在左子树, 则应该是左子树中最小的一个, 如果不存在左子树, 应该是第一个指针中记录的小于当前节点的最后一个.

树中不存在节点与指定值一致

此时, 不用考虑子树问题了, 因为搜索的终止条件为到达树的末端, 此时对于两个来说都是直接返回第一个指针即可.

code

#define BLACK 0
#define RED 1

// 节点类
template<class T>
struct node
{
    bool color;
    T key;
    node *Right;
    node *Left;
    node *Parent;
};

// 红黑树模板, 将类内函数调用的函数分装成private类型, 只开放接口函数. 实现了接近set的功能, 不能输入key值是非法的. 会在某些地方出现错误
template<class T>
class RB_TREE
{
    node<T> *Root;
    node<T> *Sentry;
    void Left_Rotate(node<T> *);
    void Right_Rotate(node<T> *);
    void RB_INSERT_FIX(node<T> *);
    void RB_DELETE_FIX(node<T> *);
    node<T>* min(node<T> *);
    node<T>* max(node<T>* );
    void RB_TRANSPLANT(node<T>*, node<T> *);

public:
    RB_TREE();
    node<T>* insert(T);
    node<T>* to_delete(T);
    node<T>* find(T);
    node<T>* Right_side_min(T);
    node<T>* Left_side_max(T);
    node<T>* get_max();
    node<T>* get_min();
    void print();
};

// 初始化, 哨兵节点Sentry为黑色
template<class T>
RB_TREE<T>::RB_TREE()
{
    Sentry = new node<T>;
    Sentry->Parent = Sentry;
    Sentry->color = BLACK;
    Root = Sentry;
}

// 左旋
template<class T>
void RB_TREE<T>::Left_Rotate(node<T> *x)
{
    node<T> *y = x->Right;
    x->Right = y->Left;
    if(y->Left != Sentry)
        y->Left->Parent = x;
    y->Parent = x->Parent;
    if(x->Parent == Sentry)
        Root = y;
    else
    {
        if(x->Parent->Left == x)
            x->Parent->Left = y;
        else x->Parent->Right = y;
    }
    y->Left = x;
    x->Parent = y;
}

// 右旋
template<class T>
void RB_TREE<T>::Right_Rotate(node<T> *x)
{
    node<T> *y = x->Left;
    x->Left = y->Right;
    if(y->Right!=Sentry)
        y->Right->Parent = x;
    y->Parent = x->Parent;
    if(x->Parent == Sentry)
        Root = y;
    else
    {
        if(x->Parent->Left == x)
            x->Parent->Left = y;
        else x->Parent->Right = y;
    }
    y->Right = x;
    x->Parent = y;
}

// 插入
template<class T>
node<T>* RB_TREE<T>::insert(T a)
{
    node<T> *z = new node<T>;
    z->key = a;
    node<T> *y = Sentry;
    node<T> *x = Root;
    while(x!=Sentry)
    {
        y = x;
        if(a>x->key)
            x = x->Right;
        else
        {
            x = x->Left;
        }
    }
    z->Parent = y;
    if(y == Sentry)
    {
        Root = z;
    }
    else
    {
        if(a>y->key)
            y->Right = z;
        else y->Left = z;
    }
    z->Left = Sentry;
    z->Right = Sentry;
    z->color = RED;
    RB_INSERT_FIX(z);
    return z;
}

// 修复由于插入导致的性质破坏
template<class T>
void RB_TREE<T>::RB_INSERT_FIX(node<T> *z)
{
    while(z->Parent->color == RED)
    {
        if(z->Parent == z->Parent->Parent->Left)
        {
            node<T> *y = z->Parent->Parent->Right;
            if(y->color == RED)
            {
                y->color = BLACK;
                z->Parent->color = BLACK;
                z->Parent->Parent->color = RED;
                z = z->Parent->Parent;
            }
            else
            {
                if(z == z->Parent->Right)
                {
                    z = z->Parent;
                    Left_Rotate(z);
                }
                z->Parent->color = BLACK;
                z->Parent->Parent->color = RED;
                Right_Rotate(z->Parent->Parent);
            }
        }
        else
        {
            node<T> *y = z->Parent->Parent->Left;
            if(y->color == RED)
            {
                y->color = BLACK;
                z->Parent->color = BLACK;
                z->Parent->Parent->color = RED;
                z = z->Parent->Parent;
            }
            else
            {
                if(z == z->Parent->Left)
                {
                    z =z->Parent;
                    Right_Rotate(z);
                }
                z->Parent->color = BLACK;
                z->Parent->Parent->color = RED;
                Left_Rotate(z->Parent->Parent);
            }
            
        }
    }
    Root->color = BLACK;
}

// 寻找指定key对应元素
template<class T>
node<T>* RB_TREE<T>::find(T a)
{
    node<T>* x = Root;
    while(x!=Sentry)
    {
        if(x->key == a)
            return x;
        else
        {
            if(x->key > a)
            {
                x = x->Left;
            }
            else x = x->Right;
        }
        
    }
    return x;
}

// 寻找指定子树中最大值
template<class T>
node<T>* RB_TREE<T>::max(node<T> *x)
{
    while(x->Right!=Sentry)
    {
        x = x->Right;
    }
    return x;
}

// 寻找指定子树中最小值
template<class T>
node<T>* RB_TREE<T>::min(node<T> *x)
{
    while(x->Left!=Sentry)
    {
        x = x->Left;
    }
    return x;
}

// 寻找整个树最大值
template<class T>
node<T>* RB_TREE<T>::get_max()
{
    return max(Root);
}

// 寻找整个树的最小值
template<class T>
node<T>* RB_TREE<T>::get_min()
{
    return min(Root);
}

// 实现节点间转移
// 此处转移中, dst为目标位置的节点,src为原来位置的节点,dst是随后要被销毁或者后续处理的对象,
// 因此不用考虑dst的问题, 只需建立src与dst->Parent的关系即可.
template<class T>
void RB_TREE<T>::RB_TRANSPLANT(node<T>*dst, node<T>*src)
{
    if(dst == Root)
    {
        Root = src;
    }
    else
    {
        if(dst == dst->Parent->Left)
        {
            dst->Parent->Left = src;
        }
        else dst->Parent->Right = src;
    }
    src->Parent = dst->Parent;
    
}

// 删除key值指定的节点
template<class T>
node<T>* RB_TREE<T>::to_delete(T a)
{
    node<T> *x = find(a);
    if(x == Sentry)
    {
        return x;
    }
    node<T> *y = x;
    node<T> *z;
    int save_color = x->color;
    if(x->Left == Sentry)
    {
        z = x->Right;
        RB_TRANSPLANT(x, x->Right);
    }
    else
    {
        if(x->Right == Sentry)
        {
            z = x->Left;
            RB_TRANSPLANT(x, x->Left);
        }
        else
        {
            y = min(x->Right);
            save_color = y->color;
            z = y->Right;
            //如果后继不是被删节点的右孩子,则构建出被删节点更新后的右子树, 即将后继的右孩子上移, 并将后继连接到被删节点的右孩子上.
            if(y!=x)
            {
                RB_TRANSPLANT(y, y->Right);
                y->Right = x->Right;
                y->Right->Parent = y;
            }
            // 将新的右子树绑定到被删节点原来的位置.
            RB_TRANSPLANT(x, y);
            y->Left = x->Left;
            y->Left->Parent = y;
            y->color = x->color; // 使被删节点的颜色在替换后不变, 方便维护红黑树性质.
        }  
    }
    if(save_color == BLACK)
    {
        RB_DELETE_FIX(z);
    }
    return x;
}

// 修复由于删除导致的性质破坏
template<class T>
void RB_TREE<T>::RB_DELETE_FIX(node<T> *x)
{
    while(x!=Root && x->color == BLACK)
    {
        if(x == x->Parent->Left)
        {
            node<T> *w = x->Parent->Right;
            if(w->color == RED)
            {
                w->color = BLACK;
                x->Parent->color = RED;
                Left_Rotate(x->Parent);
            }
            else
            {
                if(w->Left->color == BLACK && w->Right->color == BLACK)
                {
                    w->color = RED;
                    x = x->Parent;
                }
                else
                {
                    if(w->Left->color == RED && w->Right->color == BLACK)
                    {
                        swap(w->color, w->Left->color);
                        Right_Rotate(w);
                    }
                    else
                    {
                        w->Right->color = BLACK;
                        swap(w->color, x->Parent->color);
                        Left_Rotate(x->Parent);
                    }
                    
                }
                
            }
            
        }
        else
        {
            node<T> *w = x->Parent->Left;
            if(w->color == RED)
            {
                w->color = BLACK;
                x->Parent->color = RED;
                Right_Rotate(x->Parent);
            }
            else
            {
                if(w->Left->color == BLACK && w->Right->color == BLACK)
                {
                    w->color = RED;
                    x = x->Parent;
                }
                else
                {
                    if(w->Left->color == BLACK && w->Right->color == RED)
                    {
                        w->color = RED;
                        w->Right->color = BLACK;
                        Left_Rotate(w);
                    }
                    else
                    {
                        w->Left->color = BLACK;
                        swap(x->Parent->color, w->color);
                        Right_Rotate(x->Parent);
                        x = Root;
                    }
                    
                }
                
            }
            
        }
        
    }
    x->color = BLACK;
}

// 按先序遍历输出
template<class T>
void RB_TREE<T>::print()
{
    if(Root == Sentry)
        return;
    stack< node<T>* > w;
    node<T> *t;
    w.push(Root);
    while (!w.empty())
    {
        t = w.top();
        cout<<t->key<<" ";
        w.pop();
        if(t->Left != Sentry)
            w.push(t->Left);
        if(t->Right != Sentry)
            w.push(t->Right);
    }
    cout<<endl;
}

// 寻找指定key值有右边界, 即后继
template<class T>
node<T>* RB_TREE<T>::Right_side_min(T a)
{
    node<T>*y = Sentry;
    node<T>*x = Root;
    while(x!=Sentry&&x->key!=a)
    {
        if(x->key>a)
        {
            y = x;
            x = x->Left;
        }
        else x = x->Right;
    }
    if(x == Sentry || x->Right == Sentry)
        return y;
   return min(x->Right);
}

// 寻找指定key的左边界, 即前驱
template<class T>
node<T>* RB_TREE<T>::Left_side_max(T a)
{
    node<T>*y = Sentry;
    node<T>*x = Root;
    while(x!=Sentry&&x->key!=a)
    {
        if(x->key<a)
        {
            y = x;
            x = x->Right;
        }
        else x = x->Left;
    }
    if(x == Sentry || x->Left == Sentry)
        return y;
   return max(x->Left);
}