Red-Black Trees

作者: 世界上的一道风 | 来源:发表于2019-08-11 19:00 被阅读0次

Red-Black Trees
14. Deletion in red-black trees
13. Red-Black Trees 1
红黑树
寄语
凹凸世界：玫瑰之恋
Trees
2015-10-16 Cohen Did I Ever Love
Tree
LeetCode题解

前言

二叉搜索树的缺点：当树的高度较高时，二叉搜索树的的操作可能并不比在链表上执行得快。
而红黑树是很多“平衡”搜索树中的一种，可以保证在最坏情况下基本动态集合操作的时间复杂度是 $O(\lg n)$ 。
红黑树的每个结点增加一个存储位表示颜色，red或者black；红黑树确保没有一条路径（最长的路径）会比其他路径（最短路径）长出2倍，因而是近似平衡。

红黑树的性质

结点信息里有key，color, left， right， p；
如算法导论说的一样，没有子结点或者父节点的这些节点的属性p指向一个公共的哨兵节点（记为T.nil），该哨兵节点的key，left， right， p可以是任意的，但是color属性是black；
从某一个节点 $x$ 出发（不含该节点），到达一个叶节点的任意简单路径上的黑色节点个数称为该节点的黑高，记为 $bh(x)$ 。红黑树的黑高为根节点的黑高。

一颗红黑树是满足如下红黑性质的二叉搜索树：
1、每个结点或是红色，或是黑色的；
2、根节点是黑色的；
3、每个叶节点（NIL）是黑色的；
4、如果一个节点是红色的，则它的两个子结点都是黑色的；
5、对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

如下图：（a）图中标记了每个节点的黑高；（b）图给出了标兵节点；

1.png

2.png

引理：一个有 $n$ 个内部节点的红黑树的高度至多为 $2\lg (n+1)$ 。
为了实现插入删除后维持红黑树的性质，需要进行的操作是：旋转、染色。

红黑树的旋转

左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
旋转的例子：旋转之后的树做中序遍历，产生相同的关键字列表；比如左旋之前的中序遍历是 $\alpha,x,\beta,y,\gamma$ ，进行左旋之后的中序遍历顺序还是一样。

3.png

伪代码：

红黑树的插入

红黑树的插入操作，仅可能破坏性质2和性质4，即：

2、根节点是黑色的；
4、如果一个节点是红色的，则它的两个子结点都是黑色的；

插入存在三种情况需要考虑：

case1：z的叔节点y是红色的；
case2：z的叔节点y是黑色的且z是一个右孩子
case3：z的叔节点y是红色的且z是一个做孩子

伪代码：

//向红黑树T插入z节点的伪代码
RE-INSERT(T,z)
    y=T.nil //标兵
    x=T.root //根节点
    while x!= T.nil //从根节点开始遍历，直到到达标兵处退出
        y = x //用y标记此轮x的节点，作为下一轮的父节点
        if z.key < x.key
            x = x.left //去左子树搜索
        else x = x.right //否则去右子树搜索
    z.p = y //设父节点为y
    if y==T.nil //若父节点为标兵，该树为空，插入z为根节点
        T.root = z
    else if z.key < y.key //左子树
        y.left = z 
    else y.right = z
    z.left = T.nil //旋转后设新插入节点的子节点为哨兵
    z.right = T.nil
    z.color = RED //设置为红色
    RE-INSERT-FIXUP(T, z)

//为保持红黑性质，对插入节点z做着色及旋转
RE-INSERT-FIXUP(T, z)
    while z.p.color == RED //若父节点为红色，违反红黑性质4
        if z.p == z.p.p.left // 若插入节点的父节点是父父节点的左节点
            y = z.p.p.right //标记父父节点右节点（也称为叔节点）位置为y
            if y.color == RED
                z.p.color = BLACK //case1;设置插入节点的父节点为黑色
                y.color = BLACK //case1; y为黑色
                z.p.p.color = RED //case1; 插入节点父父节点为红色
                z = z.p.p //case1;插入节点等于它的父父节点
            else if z == z.p.right //插入节点是父节点的右子节点
                z = z.p // case2;插入节点等于插入节点的父节点
                LEFT-TOTATE(T, z) //case2;左旋
                                //case2在左旋之后马上转变为case3
                    z.p.color = BLACK // case 3
                    z.p.p.color = RED // case 3
                        RIGHT-ROTATE(T, z.p.p) // case 3                
        else((交换上面的“right” 与“left”再做一次 ))
    T.root.color = BLACK

对应三种case的例子如下，建议看下算法导论原图：

s1.png

S2.png

红黑树的删除

保持红黑性质的几个情况：
case1：x的兄弟节点是红色的；
case2：x的兄弟节点是黑色的，而且w的两个子节点都是黑色；
case3：x的兄弟节点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的
case4：x的兄弟节点w是黑色的，且w的孩子是红色的。

b.png

伪代码：

//反转的操作
RB-TRANSPLANT(T, u, v)
    if u.p == T.nil //引用的哨兵
        T.root = v
    else if u== u.p.left //u是左子树
        u.p.left = v //使得v成为新的左子树
    else
        u.p.right = v
    v.p = u.p //v代替u的位置


/*
始终维持节点y为从树中删除的节点或者移动到树内的节点。
 */
RB-DELETE(T,z)
y=z
y-original-color = y.color //y的颜色可能变化，因此要记录它的原始的颜色
if z.left == T.nil  //z只有一个子节点时
    x = z.right
    RB-TRANSPLANT(T, z, z.right)
else if z.right == T.nil //z只有一个子节点时
    x = z.left
    RB-TRANSPLANT(T, z, z.left) 
else y = TREE-MINIMUM(z.right) //z有两个子节点时，移动y到树中z的位置
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
        if w.color == RED //case1:若兄第节点是红色，改变为黑色，同时删除节点x的父节点置为红色，左旋该父节点
            w.color = BLACK //case1
            x.p.color = RED //case1
            LEFT-ROTATE(T, x.p) //case1
            w = x.p.right //case1: 删除节点的兄第节点为w
        if w.left.color == BLACK and w.right.color == BLACK //case2:若兄第节点为黑色，且它的左右节点都为黑色
            w.color = RED //case2 :置兄第节点为红色，删除节点等于删除节点的父节点
            x = x.p //case2 
        else if w.right.color == BLACK //case3:若兄第节点为黑色，且它的右节点为黑色，左节点为红色;
            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
        w.right.color = BLACK
        LEFT-ROTATE(T, x.p)
        x = T.root
    else(交换"left"和"right"的方向)
x.color = BLACK

c++代码

*插入结果是对的，但是 remote-fixup 是写错了，以后有时间来改吧。知乎有别人分析的很好，知乎搜索下红黑树便可。

//
// Created by ZC on 2019-08-14.
//

#include "RedBlackTree.h"
#include<iostream>
#include<vector>
using namespace std;

template <typename T>
void RedBlackTree<T>::LeftRotate(RBNode<T> *x)
{
    RBNode<T>* y = x->right;
    x->right = y->left; //把x的右子树设为x的y的左子树（x的右子树的左子树）
    if(y->left != Nil) //y的左子树非空，连上它新的父节点x
        y->left->p = x;
    y->p=x->p; //y新的父节点是x以前的父节点
    if(x->p == Nil) //y如果旋转成为根节点，重置根节点指针的指向
        root = y;
    else if (x==x->p->left) //旋转的x是父亲的左节点，重换左节点为y
        x->p->left = y;
    else
    {
        x->p->right = y; //把x放到y的左边
    }
    y->left = x;
    x->p = y;
}

template <typename T>
void RedBlackTree<T>::RightRotate(RBNode<T> *x)
{
    RBNode<T>* y = x->left; //
    x->left = y->right;
    if(y->right != Nil)
    {
        y->right->p = x;
    }
    y->p = x->p;
    if(x->p == Nil) //x是根节点
        root = y;
    else if (x == x->p->left) //z在左节点
    {
        x->p->left = y;
    }
    else
    {
        x->p->right = y;
    }
    y->right = x;
    x->p = y;
}

//1 BST方式的插入
//2 调整平衡
template <typename T>
bool RedBlackTree<T>::Insert(const T &val)
{
    RBNode<T> *y = Nil;//标兵
    RBNode<T> *x = root; //根节点
    while(x != Nil)
    {
        y = x;
        if(val == x->val)
        {
            cout << "insert error." << endl;
            return false;
        }
        else if(val < x->val)
            x = x->left;
        else
            x = x->right;
    }
    RBNode<T>* pInsertNode = NewNode(val);
    pInsertNode->p = y;
    if(y == Nil)
        root = pInsertNode;
    else if (pInsertNode->val < y->val)
        y->left = pInsertNode;
    else
        y->right = pInsertNode;
    pInsertNode->color = RED;
    //调整平衡
    Insert_Fixup(pInsertNode);
    return true;
}


template <typename T>
void RedBlackTree<T>::Insert_Fixup(RBNode<T> *z)
{
    RBNode<T> * uncle;//叔节点（父亲节点的兄弟节点）
    while (z->p->color == RED)
    {
        if(z->p == z->p->p->left)//违反红黑性质4
        {
            uncle = z->p->p->right; //叔节点位置
            if(uncle->color == RED) //叔节点为红色
            {
                //父节点和叔节点都变为黑色
                z->p->color = BLACK; //case1:
                uncle->color = BLACK; //case1:
                //祖父节点变为红色
                z->p->p->color = RED; //case1:
                //将fix指向祖父节点，下一次循环判断祖父节点是否为红色
                z = z->p->p; // case1:
            }
            else // 没有叔节点，或叔节点为黑色（多次循环，叔节点可能为黑）
            {
                if (z == z->p->right) //如果调整的节点在右节点
                {
                    z = z->p; //case2://先将fix指向它的父节点
                    LeftRotate(z);//case2: //在左转
                }
                //如果调整的的节点在左节点，将fix的副节点变为黑色，祖父节点变为红色，将fix的祖父节点右转
                z->p->color = BLACK; //case3
                z->p->p->color = RED; //case3
                RightRotate(z->p->p);
            }
        }
        else
        {
           if(z->p == z->p->p->right) //父节点是右节点
           {
               if(uncle->color == RED) //叔节点是红色
               {
                   //副节点和叔节点都变为黑色；
                   z->p->color = BLACK;
                   uncle->color = BLACK;
                   //祖父节点变为红色
                   z->p->p->color=RED;
                   //将fix指针指向祖父节点，下一次循环判断祖父节点的父节点是否为红色
                   z = z->p->p;
               }
               else//没有叔节点，或叔节点为黑色（多次循环叔节点可能为黑色）
               {
                   //如果调整的节点在左节点
                   if(z == z->p->left)
                   {
                       z = z->p;//先将fix指向fix的父节点
                       RightRotate(z);//再右转
                   }
                   //如果调整的节点在右节点，将fix的父节点变为黑色，将祖父节点变为红色，将fix的祖父节点右转
                   z->p->color = BLACK;
                   z->p->p->color = RED;
                   LeftRotate(z->p->p);
               }
           }
        }
    }
    root->color = BLACK;
}

template <typename T>
RBNode<T>* RedBlackTree<T>::Search(RBNode<T> *root, T val) const
{
    if(root == Nil) //root为空
    {
        return Nil;
    }

    if(root->val == val)
        return root;
    if(val < root->val)
        return Search(root->left, val);
    else
        return Search(root->right, val);
}

template <typename T>
void RedBlackTree<T>::Transplant(RBNode<T> *u, RBNode<T> *v)
{
    if(u->p == Nil) root = v;
    else if (u == u->p->left)
        u->p->left = v; //使得v成为新的左子树
    else
        u->p->right = v;
    v->p = u->p; //v代替u的位置
}

template <typename T>
void RedBlackTree<T>::Remove(RBNode<T> *z)
{
    RBNode<T>* x = Nil;
    RBNode<T>* y = z;
    Color ycolor = y->color; //y的颜色可能要变，因此要记录它的原始的颜色
    if(z->left == Nil) //z只有一个子节点时
    {
        x = z->right;
        Transplant(z, z->right);
    }
    else if (z->right == Nil)
    {
        x = z->left;
        Transplant(z, z->left);
    }
    else//z有两个子节点时，移动y到树z的位置
    {
        y = Minimum(z->right);
        ycolor = y->color;
        x = y->right;
        if (y->p == z)
            x->p = y;
        else
        {
            Transplant(y, y->right);
            y->right = z->right;
            y->right->p = y;
        }
        Transplant(z, y);//改变指向
        y->left = z->left;
        y->left->p = y;
        ycolor = z->color;
    }
    if (ycolor == BLACK)
        Remove_Fixup(x);
}

template <typename T>
void RedBlackTree<T>::Remove_Fixup(RBNode<T> *x)
{
    while(x!= root && x->color == BLACK)
    {
        if(x==x->p->left)
        {
            RBNode<T>* w = x->p->right;
            if(w->color == RED) //case1:若兄弟节点是红色，改变为黑色，同时节点x的父置为红色，左旋该父节点
            {
                w->color = BLACK; //case1
                x->p->color = RED; //case1
                LeftRotate(x->p);//case1
                w = x->p->right;//case1
            }
            if (w->left!=nullptr && w->left->color == BLACK && w->right->color == BLACK) //case2:若兄弟节点是黑色，且它的左右节点都为黑色
            {
                w->color = RED; //case2
                x = x->p; //case2
            }
            else
            {
                if((w->right!=nullptr) && w->right->color == BLACK) //case3:
                {
                    w->left->color = BLACK; //case3
                    w->color = RED; //case3
                    RightRotate(w); //case3
                    w = x->p->right; //case3
                }
                w->color = x->p->color; //case4
                x->p->color = BLACK;
                w->right->color = BLACK;
                LeftRotate(x->p);
                x = root;
            }
        }
        else  //x在右子树上
        {
            RBNode<T>* w = x->p->left;
            if(w->color == RED) //case1
            {
                w->p->color =RED;
                w->color = BLACK;
                RightRotate(x->p);
                w = x->p->left;
            }
            if((w->right!=nullptr) && w->right->color == BLACK && w->right->color == BLACK) //case2
            {
                w->color = RED;
                x = x->p;
            }
            else
            {
                if((w->left!=nullptr) && w->left->color == BLACK) //case3
                {
                    w->right->color = BLACK;
                    w->color = RED;
                    LeftRotate(w);
                    w = x->p->left;
                }
                w->color = x->p->color; //case4
                w->p->color = BLACK;
                w->left->color = BLACK;
                RightRotate(x->p);
                x = root; // 结束循环
            }
        }
    }
    x->color = BLACK;
}

int main(){
    RedBlackTree<int> rb;
    int arr[] = {10, 7, 8, 15, 5, 6, 11, 13, 2};
    int n = sizeof(arr) / sizeof(int);
    for(int i=0; i<n; ++i) {
        rb.Insert(arr[i]);
    }
    cout << "finish insert" << endl;
    rb.PostOrderPrintColor();
    cout << endl;
    rb.Remove(10);
    cout << "Poster order after delelte 10:" << endl;
    rb.PostOrderPrintColor();
    cout << "Order after delelte 21:" << endl;
    rb.Remove(21);
    rb.PostOrderPrintColor();

}

Reference:
算法导论
https://zhuanlan.zhihu.com/p/31805309

Red-Black Trees
前言二叉搜索树的缺点：当树的高度较高时，二叉搜索树的的操作可能并不比在链表上执行得快。而红黑树是很多“平衡”搜...
14. Deletion in red-black trees
Preparation Suppose we delete a node z, and there are 3 c...
13. Red-Black Trees 1
DefinitionA red-black tree (RBT) is a binary search tree ...
红黑树
Red-Black Tree Red-Black Tree is a self-balancing Binary ...
寄语
Trees do not want trees into shade, shade trees do not se...
凹凸世界：玫瑰之恋
There are trees on the hill , the trees have branches , h...
Trees
Trees Binary Search Tree Searching Binary Search Trees
2015-10-16 Cohen Did I Ever Love
the lemon trees blossom the almond trees wither was i eve...
Tree
There are many trees in our school.Some trees are thick.S...
LeetCode题解
1、Merge Two Binary Trees Given two binary trees and imagi...