红黑二叉树原理与实现

R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。(确保没有一条路径会比其他路径长出俩倍。红黑树是相对是接近平衡的二叉树。)

黑高度:从该结点到其子孙结点中包含的黑结点数,用bh(x)表示。nil的黑高度为0。

红黑树的旋转

左旋

  1. 需要进行左旋的子树的根结点 x
  2. 找到该子树的根结点的右子树 y=x->right
  3. 将右子树y的左孩子(y->left)移动至子树x的右孩子处(x->right) x->right=y->left
  4. 如果子树x的右子树不是nil,需要重新连接右子树的父结点(双亲结点)为x x->right->p=x
  5. 设置右子树y的父结点(双亲结点)为子树x的父结点 y->p=x->p
  6. 设置y的父结点同y的连接有2种情况:
    • 原来子树x结点本身就是整颗树的根结点T,则T指向右子树y T->root=y
    • 根据右子树y中关键字同其父节点关键字的值的大小,判断y的父节点是左孩子还是右孩子 y->p->left=y or y->p->right=y
  7. 将x结点连接给y结点的左孩子处 y->left=x
  8. 设置x的双亲结点为y x->p=y

右旋

  1. 需要进行右旋的子树的根结点 x
  2. 找到该子树的根结点的左子树 y=x->left
  3. 将左子树y的右孩子(y->left)移动至子树x的左孩子处(x->left) x->left=y->right
  4. 如果子树x的左子树不是nil,需要重新连接左子树的父结点为x x->left->p=x
  5. 设置左子树y的父节点为子树x的父节点 y->p=x->p
  6. 设置y的父节点同y的连接有2种情况:
    • 原来子树x的结点本身就是整颗树的根结点T,则T指向左子树y T->root=y
    • 根据左子树y中关键字同其父节点关键字的值的大小,判断y的父节点是左孩子还是右孩子 y->p->left=y or y->p->right=y
  7. 将x结点连接给y结点的右孩子处 y->right=x
  8. 设置x的双亲结点为y x->p=y

红黑树中插入新结点

插入结点步骤

  1. 由于红黑树本身是一颗二叉查找树,在插入新结点时,完全按照二叉查找树插入结点的方法,找到新结点插入的位置。
  2. 将新插入的结点初始化,颜色设置为红色后插入到指定位置。(不会破坏第5条性质)
  3. 由于插入新的结点,可能会破坏红黑树的第4条性质,此时需要调整二叉查找树,通过选择以及修改树中结点的颜色,使其重新成为红黑树。

插入结点情况

  1. 插入位置为整颗树的树根。处理办法:只需将插入结点的颜色改为黑色。
  2. 插入位置的双亲结点的颜色为黑色。处理办法:不需要做任何操作。新插入结点不会破坏红黑树的性质。
  3. 插入位置的双亲结点的颜色为红色。插入结点和双亲结点的颜色都为红色,破坏了红黑树的第4条性质,此时需要结合其父节点和祖父结点的另一个孩子结点(叔叔结点)的状态分3种情况讨论:
    • 当前结点的父节点是红色,且“叔叔结点”也是红色。破坏了红黑树的第4条性质。解决方案:将父节点颜色改为黑色,叔叔结点颜色改为黑色,祖父结点改为红色。将祖父结点当做当前结点,继续判断。
    • 当前结点的父节点是红色,“叔叔结点”为黑色,且当前结点是父节点的右孩子。解决方案:将父节点作为当前结点做左旋操作。
    • 当前结点的父节点是红色,“叔叔结点”为黑色,且当前结点是父节点的左孩子。解决方案:将父节点改为黑色,祖父结点改为红色,从父节点处进行右旋处理。

红黑树中删除结点

删除结点步骤

  1. 将红黑树按照二叉查找树删除结点的方法删除指定结点。
  2. 重新调整删除结点后的树,使之重新成为红黑树。

删除结点情况

  1. 当该删除结点本身是叶子结点,则可以直接删除。
  2. 当只有一个孩子结点,则直接让其孩子结点顶替该删除结点。
  3. 当有两个孩子结点,则找到该结点的右子树中值最小的叶子结点来替换该结点,然后删除这个值最小的叶子结点。

删除结点时是否会破坏红黑树的性质

  1. 如果删除结点的颜色为红色,则不会破坏。
  2. 如果删除结点的颜色为黑色,则肯定会破坏红黑树的第5条性质,此时就需要对树进行调整。
    • 删除结点的兄弟结点颜色是红色。调整措施为:将兄弟结点颜色改为黑色,父亲结点改为红色,以父亲结点来进行左旋操作,同时更新删除结点的兄弟结点(左旋后兄弟结点发生了变化
    • 删除结点的兄弟结点及其孩子全部是黑色的。调整措施为:将删除结点的兄弟结点设为红色,同时设置删除结点的父结点标记为新的结点,继续判断。
    • 删除结点的兄弟结点是黑色,其左孩子是红色,右孩子是黑色。调整措施为:将兄弟结点设为红色,兄弟结点的左孩子结点设为黑色,以兄弟结点为准进行右旋操作,最终更新删除结点的兄弟结点。
    • 删除结点的兄弟结点是黑色,其右孩子是红色,左孩子是黑色。调整措施为:将删除结点的父结点的颜色赋值给其兄弟结点,然后再设置父结点颜色为黑色,兄弟结点的右孩子结点为黑色,根据其父结点做左旋操作,最后设置替换删除结点的结点为根结点。

关键部分实现

结构体

ypedef enum{RED, BLACK}ColorType;

typedef struct RB_TREE{
    int key;
    struct RB_TREE * left;
    struct RB_TREE * right;
    struct RB_TREE * p;
    ColorType color;
}RB_TREE;

typedef struct RBT_Root{
    RB_TREE * root;
    RB_TREE * nil;
}RBT_Root;

旋转

//T 表示为树根,x 表示需要进行左旋的子树的根结点
void rbTree_left_rotate( RBT_Root* T, RB_TREE* x)
{
    RB_TREE* y = x->right;//找到根结点的右子树
    x->right = y->left;//将右子树的左孩子移动至结点x 的右孩子处
    if(x->right != T->nil)
    {//如果x 的右子树不是nil,需重新连接右子树的双亲结点为x
        x->right->p = x;
    }
    y->p = x->p;//设置y 的双亲结点为x 的双亲结点
    //重新设置y 的双亲结点同y 的连接,分为2 种情况:
    //1、原x 结点本身就是整棵树的数根结点,此时只需要将T 指针指向y;
    //2、根据y 中关键字同其父结点关键字的值的大小,判断y 是父结点的左孩子还是右孩子
    if(y->p == T->nil)
    {
        T->root = y;
    }else if(y->key < y->p->key)
    {
        y->p->left = y;
    }else
    {
        y->p->right = y;
    }
    y->left = x;//将x 连接给y 结点的左孩子处
    x->p = y;//设置x 的双亲结点为y。
}

void rbTree_right_rotate( RBT_Root* T, RB_TREE* x)
{
    RB_TREE * y = x->left;
    x->left = y->right;
    if(T->nil != x->left)
    {
        x->left->p = x;
    }
    y->p = x->p;
    if(y->p == T->nil)
    {
        T->root = y;
    }else if(y->key < y->p->key)
    {
        y->p->left= y;
    }else
    {
        y->p->right = y;
    }
    y->right = x;
    x->p = y;
}

插入

void RB_Insert_Fixup(RBT_Root* T, RB_TREE* x)
{
    //首先判断其父结点颜色为红色时才需要调整;为黑色时直接插入即可,不需要调整
    while (x->p->color == RED) 
    {
        //由于还涉及到其叔叔结点,所以此处需分开讨论,确定父结点是祖父结点的左孩子还是右孩子
        if (x->p == x->p->p->left) 
        {
            RB_TREE * y = x->p->p->right;//找到其叔叔结点
            //如果叔叔结点颜色为红色,此为第1 种情况,处理方法为:父结点颜色改为黑色;叔叔结点颜色改为黑色;祖父结点颜色改为红色,将祖父结点赋值为当前结点,继续判断;
            if (y->color == RED) 
            {
                x->p->color = BLACK;
                y->color = BLACK;
                x->p->p->color = RED;
                x = x->p->p;
            }
            else
            {
                //反之,如果叔叔结点颜色为黑色,此处需分为两种情况:
                //1、当前结点时父结点的右孩子;
                //2、当前结点是父结点的左孩子
                if (x == x->p->right) 
                {
                    //第2 种情况:当前结点时父结点的右孩子。解决方案:将父结点作为当前结点做左旋操作。
                    x = x->p;
                    rbTree_left_rotate(T, x);
                }
                else
                {
                    //第3 种情况:当前结点是父结点的左孩子。解决方案:
                    //将父结点颜色改为黑色,祖父结点颜色改为红色,从祖父结点处进行右旋处理。
                    x->p->color = BLACK;
                    x->p->p->color = RED;
                    rbTree_right_rotate(T, x->p->p);
                }
            }
        }
        else
        {//如果父结点时祖父结点的右孩子,换汤不换药,只需将以上代码部分中的left 改为right 即可,道理是一样的。
            RB_TREE * y = x->p->p->left;
            if (y->color == RED) 
            {
                x->p->color = BLACK;
                y->color = BLACK;
                x->p->p->color = RED;
                x = x->p->p;
            }
            else
            {
                if (x == x->p->left) 
                {
                    x = x->p;
                    rbTree_right_rotate(T, x);
                }
                else
                {
                    x->p->color = BLACK;
                    x->p->p->color = RED;
                    rbTree_left_rotate(T, x->p->p);
                }
            }
        }
    }
    T->root->color = BLACK;
}

//插入操作分为3 步:1、将红黑树当二叉查找树,找到其插入位置;
//2、初始化插入结点,将新结点的颜色设为红色;
//3、通过调用调整函数,将二叉查找树重新改为红黑树
void rbTree_insert(RBT_Root**T, int k)
{
    //1、找到其要插入的位置。解决思路为:从树的根结点开始,通过不断的同新结点的值进行比较,最终找到插入位置
    RB_TREE * x, *p;
    x = (*T)->root;
    p = x;
    while(x != (*T)->nil)
    {
        p = x;
        if(k<x->key)
        {
            x = x->left;
        }else if(k>x->key)
        {
            x = x->right;
        }else
        {
            printf("\n%d 已存在\n",k);
            return;
        }
    }
    //初始化结点,将新结点的颜色设为红色
    x = (RB_TREE *)malloc(sizeof(RB_TREE));
    x->key = k;
    x->color = RED;
    x->left = x->right =(*T)->nil;
    x->p = p;
    //对新插入的结点,建立与其父结点之间的联系
    if((*T)->root == (*T)->nil)
    {
        (*T)->root = x;
    }else if(k < p->key)
    {
        p->left = x;
    }else
    {
        p->right = x;
    }
    //3、对二叉查找树进行调整
    RB_Insert_Fixup((*T),x);
}

删除

void rbTree_transplant(RBT_Root* T, RB_TREE* u, RB_TREE* 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->p = u->p;
}

void RB_Delete_Fixup(RBT_Root**T,RB_TREE*x)
{
    while(x != (*T)->root && x->color == BLACK)
    {
        if(x == x->p->left)
        {
            RB_TREE* w = x->p->right;
            //第1 种情况:兄弟结点是红色的
            if(RED == w->color)
            {
                w->color = BLACK;
                w->p->color = RED;
                rbTree_left_rotate((*T),x->p);
                w = x->p->right;
            }
            //第2 种情况:兄弟是黑色的,并且兄弟的两个儿子都是黑色的。
            if(w->left->color == BLACK && w->right->color == BLACK)
            {
                w->color = RED;
                x = x->p;
            }
            //第3 种情况
            if(w->left->color == RED && w->right->color == BLACK)
            {
                w->left->color = BLACK;
                w->color = RED;
                rbTree_right_rotate((*T),w);
                w = x->p->right;
            }
            //第4 种情况
            if (w->right->color == RED)
            {
                w->color = x->p->color;
                x->p->color = BLACK;
                w->right->color = BLACK;
                rbTree_left_rotate((*T),x->p);
                x = (*T)->root;
            }
        }
        else
        {
            RB_TREE* w = x->p->left;
            //第1 种情况
            if(w->color == RED)
            {
                w->color = BLACK;
                x->p->color = RED;
                rbTree_right_rotate((*T),x->p);
                w = x->p->left;
            }
            //第2 种情况
            if(w->left->color == BLACK && w->right->color == BLACK)
            {
                w->color = RED;
                x = x->p;
            }
            //第3 种情况
            if(w->left->color == BLACK && w->right->color == RED)
            {
                w->color = RED;
                w->right->color = BLACK;
                w = x->p->left;
            }
            //第4 种情况
            if (w->right->color == BLACK)
            {
                w->color=w->p->color;
                x->p->color = BLACK;
                w->left->color = BLACK;
                rbTree_right_rotate((*T),x->p);
                x = (*T)->root;
            }
        }
    }
    x->color = BLACK;//最终将根结点的颜色设为黑色
}

void rbTree_delete(RBT_Root* *T, int k)
{
    if(NULL == (*T)->root)
    {
        return ;
    }
    //找到要被删除的结点
    RB_TREE * toDelete = (*T)->root;
    RB_TREE * x = NULL;
    //找到值为k 的结点
    while(toDelete != (*T)->nil && toDelete->key != k)
    {
        if(k<toDelete->key)
        {
            toDelete = toDelete->left;
        }else if(k>toDelete->key)
        {
            toDelete = toDelete->right;
        }
    }
    if(toDelete == (*T)->nil)
    {
        printf("\n%d 不存在\n",k);
        return;
    }
    //如果两个孩子,就找到右子树中最小的结点,将之代替,然后直接删除该结点即可
    if(toDelete->left != (*T)->nil && toDelete->right != (*T)->nil)
    {
        RB_TREE* alternative = rbt_findMin((*T), toDelete->right);
        k = toDelete->key = alternative->key;//这里只对值进行复制,并不复制颜色,以免破坏红黑树的性质
        toDelete = alternative;
    }
    //如果只有一个孩子结点(只有左孩子或只有右孩子),直接用孩子结点顶替该结点位置即可(没有孩子结点的也走此判断语句)。
    if(toDelete->left == (*T)->nil)
    {
        x = toDelete->right;
        rbTree_transplant((*T),toDelete,toDelete->right);
    }else if(toDelete->right == (*T)->nil)
    {
        x = toDelete->left;
        rbTree_transplant((*T),toDelete,toDelete->left);
    }
    //在删除该结点之前,需判断此结点的颜色:如果是红色,直接删除,不会破坏红黑树;若是黑色,删除后会破坏红黑树的第5 条性质,需要对树做调整。
    if(toDelete->color == BLACK)
    {
        RB_Delete_Fixup(T,x);
    }
    //最终可以彻底删除要删除的结点,释放其占用的空间
    free(toDelete);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据