红黑树

作者: MangK | 来源:发表于2016-09-26 23:29 被阅读432次

1 摘要

红黑树(Red Black Tree) 是一种自平衡二叉搜索树,它是在1972年由Rudolf Bayer发明的,当时被称为平衡二叉B树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树确保没有一条路径会比其他路径长出两倍。这个树大致上是平衡的,因此,插入、删除和查找操作在最坏情况下都是高效的。

2 性质

在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

  • 性质1. 每个结点是红色或黑色
  • 性质2. 根结点是黑色
  • 性质3. 每个叶子结点(NIL节点,空节点)是黑色
  • 性质4. 每个红色结点的两个子结点是黑色(子结点是红色父结点一定是黑色)
  • 性质5. 从任意结点到其每个叶子结点的路径包含相同数目的黑色结点

结论(证明可查阅其他资料,这里不讨论):一棵有n个结点的红黑树的高度至多为为2lg(n+1)

数据结构定义

#include <stdio.h>
#include <stdlib.h>

//定义颜色类型
typedef enum Color
{
    RED = 0,
    BLACK = 1
}Color;

//定义结点结构
typedef struct Node //
{
    struct Node *parent;
    struct Node *left;
    struct Node *right;
    int value;
    Color color;
}Node, *Tree;

/*
 方便处理边界,结点NIL替代NULL
 所有空都指向它,可以看成外部结点
 */
Node *NIL=NULL;

3 旋转

当进行插入或删除操作时,可能导致新树不满足红黑树的性质,此刻需要适当的旋转来完成

左旋右旋示意图

3.1 左旋

  • 过程:x的右孩子指向y的左孩子,y的父结点指向x的父结点,y的左孩子指向x

code:

//左旋:将x的右子树y旋转成x的父母
void LeftRotate(Tree T, Node *x)
{
    if(x->right != NIL) {
        Node *y=x->right;
        //1.修改x的右孩子与y的左孩子的父结点的指针
        x->right=y->left;
        if(y->left != NIL) {
            y->left->parent=x;
        }
        //2.修改y的父结点与x父结点的孩子结点的指针
        y->parent=x->parent;
        if(x->parent == NIL){
            T=y;
        }else{
            if(x == x->parent->left) {
                x->parent->left=y;
            }else{
                x->parent->right=y;
            }
        }
        //3.修改y的左孩子与x的父结点的指针
        y->left=x;
        x->parent=y;
    } else {
        printf("can't execute left rotate due to null right child/n");
    }
}

3.2 右旋

  • 过程:y的左孩子指向x的右孩子,x的父结点指向y的父结点,x的右孩子指向y

code:

//右旋:将x的左子树y旋转成x的父母
void RightRotate(Tree T, Node *x)
{
    if( x->left != NIL ) {
        Node *y=x->left;
        //1.修改x的左孩子与y的右孩子的父结点的指针
        x->left=y->right;
        if( y->right != NIL ) {
            y->right->parent=x;
        }
        //2.修改y的父结点与x父结点的孩子结点的指针
        y->parent=x->parent;
        if( x->parent == NIL ) {
            T=y;
        } else {
            if(x == x->parent->left) {
                x->parent->left=y;
            } else {
                x->parent->right=y;
            }
        }
        //3.修改y的右孩子与x的父结点的指针
        y->right=x;
        x->parent=y;
    } else {
        printf("can't execute right rotate due to null left child/n");
    }
}

4 插入

4.1 插入过程

红黑树的插入过程是在二叉搜索树插入的基础上改进的,具体过程是先按照二叉搜索树的插入过程插入并标记红色,然后对插入的结点进行调整

code:

void Insert(Tree T, int val)
{
    if(T == NULL) {
        T=(Tree)malloc(sizeof(Node));
        NIL=(Node*)malloc(sizeof(Node));
        NIL->color=BLACK;
        T->left=NIL;
        T->right=NIL;
        T->parent=NIL;
        T->value=val;
        T->color=BLACK;
    }else{
        Node *x=T;
        Node *p=NIL;
        while(x != NIL) {
            p=x;
            if(val < x->value){
                x=x->left;
            }else if(val > x->value){
                x=x->right;
            }else{
                printf("duplicate value %d/n",val);
                return;
            }
        }
        x=(Node*)malloc(sizeof(Node));
        x->color=RED;
        x->left=NIL;
        x->right=NIL;
        x->parent=p;
        x->value=val;
        if(val < p->value){
            p->left = x;
        }else{
            p->right = x;
        }
        //从x开始调整
        InsertFixup(T, x);
    }
}

4.2.调整过程

4.2.1 分析

当插入一个新的结点(红色),至多违反一个性质,可能违反性质2或性质4。 ① 如果违反性质2,新增的结点z必定是根,此树只有一个结点,直接将根结点置黑即可。 ② 如果违反性质4,此时z与其父结点都为红色,根据红黑树的性质,z的祖父结点一定是黑色。我们再根据z的父结点是z的祖父结点的左孩子还是右孩子进行讨论。由于左右是对称的,这里只讨论z的父结点是z的祖父的左孩子进行讨论,分为3种情况:

  • 情况1:z的叔叔结点y是RED
    处理:将y与z的父结点着为BLACK,z的祖父着为红色,此时z的祖父可能违反性质3,将z上移至祖父结点
情况1
  • 情况2:z的叔叔结点y是BLACK,z是右孩子
    处理:将z上移到父结点,对z左旋,转化为情况3
情况2
  • 情况3:z的叔叔结点y是BLACK,z是左孩子
    处理:将z的父结点着为BLACK,z的祖父结点着为RED,对z的祖父结点右旋
情况3
4.2.2 过程模拟

插入过程请点击这里

code:

void InsertFixup(Tree T, Node *z) {
    Node *y;
    //插入结点的父结点为红色时,违反性质4
    while( z->parent->color == RED ) {
        if( z->parent->parent->left == z->parent ) {
            //y指向z的叔叔结点
            y=z->parent->parent->right;
            /*
             情况1:如果y为RED,将y与z的父结点着为BLACK,z的祖父着为红色,此时z的祖父可能违反性质3,将z上移至祖父结点
             */
            if(y->color == RED) {
                y->color=BLACK;
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                z=z->parent->parent;
            } else {
                /*
                 情况2:如果y为BLACK,且z是右孩子,将z上移到父结点,对z左旋,转化为情况3
                 */
                if(z == z->parent->right) {
                    z=z->parent;
                    LeftRotate(T, z);
                }
                /*
                 情况3:如果y为BLACK,且z是左孩子,将z的父结点着为BLACK,z的祖父结点着为RED,对z的祖父结点右旋
                 */
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                RightRotate(T,z->parent->parent);
            }
        } else {
            //对称,左右替换即可
            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;
                    RightRotate(T,z);
                }
                z->parent->color=BLACK;
                z->parent->parent->color=RED;
                LeftRotate(T,z->parent->parent);
            }
        }
    }
    T->color=BLACK;
}

5 删除

5.1 删除过程

红黑树的删除过程同样是在二叉搜索树删除的基础上改进的。二叉搜索树的删除过程分为3种情况:①无左右孩子 ②有左孩子或右孩子 ③既有左孩子又有右孩子。在删除过程中,如果删除的结点为RED,并没有破坏红黑树的性质;如果删除的结点为BLACK,破坏了红黑树的性质,需要调整,从删除结点y的唯一孩子结点x或是NIL处开始调整(这里做了转换,实际删除的是右子树最小结点或左子树最大结点)

code:

//右子树最小结点
Node* Successor(Tree T, Node *x)
{
    if(x->right != NIL) {
        Node *p=x->right;
        while( p->left != NIL ) {
            p=p->left;
        }
        //右孩子中最小的结点
        return p;
    }
    return x;
}

void Delete(Tree T, Node *z) {
    Node *y;//指向将要被删除的结点
    Node *x;//指向将要被删除的结点的唯一儿子
    //如果有一个子结点为NIL,删除当前结点
    if(z->left == NIL || z->right == NIL){
        y=z;
    } else {
        //删除左子树的最大结点或右子树最小结点
        y=Successor(T, z);//这里是右子树最大结点
    }
    
    //开始删除
    if(y->left != NIL) {
        x=y->left;
    } else {
        x=y->right;
    }
    if (x != NIL){
        x->parent=y->parent;
    }
    if( y->parent == NIL ) {
        T=x;
    } else {
        if( y == y->parent->left ) {
            y->parent->left=x;
        } else {
            y->parent->right=x;
        }
    }
    //交换值
    if( y != z ) {
        z->value=y->value;
    }
    //如果删除的是黑色结点,进行调整
    if( y->color == BLACK ) {
        //没有修改y结点,任意属性的值,可以使用
        DeleteFixup(T,NIL!=x ? x:y);
    }
}

5.2 调整过程

5.2.1 分析

如果被删除结点y是黑色会产生的问题:①如果y是根,y的红色孩子成为新根,违反性质2。 ②如果x与y的父结点都是红色,违反性质4。 ③删除y会导致之前包含y的任意路径上的黑色结点少1,违反性质5。
恢复过程需要根据x是左孩子还是右孩子进行恢复,由于左右是对称的,这里只讨论x是左孩子的恢复过程

具体过程如下:从x结点开始循环,直到:

  • ① x指向一个RED结点,此时将x着为BLACK
  • ② x指向根,x若为RED,着为BLACK
  • ③ 修改颜色 & 进行旋转

循环过程中,w为x的兄弟结点,由于x处之前删除过黑色结点,所以w不可能为NIL,这里分为4种情况

  • 情况1:x的兄弟w为RED
    处理:由于x为BLACK且删除了一个BLACK结点,所以w必有BLACK孩子。此时将w着为BLACK,x父结点着为RED,对x的父结点左旋。x的新兄弟结点w是BLACK,情况1转换为情况2、3或4
情况1
  • 情况2:x的兄弟w为BLACK,且w的两个孩子都为BLACK
    处理:w着为RED,x上移至父结点
情况2
  • 情况3:x的兄弟w为BLACK,且w的左孩子为RED,右孩子为BLACK
    处理:交换w与其左孩子的color,对w进行右旋。旋转后x的新兄弟w是一个有RED右孩子的BLACK结点,转换成情况4
情况3
  • 情况4:x的兄弟w为BLACK,且w的右孩子为RED
    处理:将w着为x父结点的颜色,x父结点着为BLACK,w右孩子着为BLACK,对x的父结点左旋,x设为根结点(结束调整)
情况4
5.2.2 过程模拟

插入过程请点击这里

code:

void DeleteFixup(Tree T, Node *x) {
    //x是RED直接跳出
    while( x != T && x->color == BLACK ) {
        //x为左子树
        if(x == x->parent->left) {
            //w为x的兄弟结点
            Node *w=x->parent->right;
            /*
             情况1:如果w为RED,由于x为BLACK且删除了一个BLACK结点,所以w必有BLACK孩子。
             此时将w着为BLACK,x父结点着为RED,对x的父结点左旋。x的新兄弟结点w是BLACK,情况1转换为情况2、3或4
            */
            if(w->color == RED){
                w->color=BLACK;
                x->parent->color=RED;
                LeftRotate(T, x->parent);
                w=x->parent->right;
            }
            /*
             情况2:如果w为BLACK,w的左右孩子为BLACK。w着为RED,x上移至父结点
             */
            if(w->left->color == BLACK && w->right->color == BLACK) {
                w->color=RED;
                x=x->parent;
            } else {
                /*
                 情况3:如果w为BLACK,w的左孩子为RED,右孩子为BLACK。
                 交换w与其左孩子的color,对w进行右旋。旋转后x的新兄弟w是一个有RED右孩子的BLACK结点,转换成情况4
                 */
                if(w->right->color == BLACK) {
                    w->color=RED;
                    w->left->color=BLACK;
                    RightRotate(T, w);
                    w=x->parent->right;
                }
                /*
                 情况4:如果w为BLACK,w的右孩子为RED。
                 将w着为x父结点的颜色,x父结点着为BLACK,w右孩子着为BLACK,对x的父结点左旋,x设为根结点
                 */
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->right->color=BLACK;
                LeftRotate(T,x->parent);
                x=T;
            }
        } else {
            //与前面对称,不再详述
            Node *w=x->parent->left;
            if(w->color == RED) {
                w->color=BLACK;
                x->parent->color=RED;
                RightRotate(T, x->parent);
                w=x->parent->left;
            }
            if(w->left->color == BLACK && w->right->color == BLACK) {
                w->color=RED;
                x=x->parent;
            } else {
                if(w->left->color == BLACK) {
                    w->color=RED;
                    w->right->color=BLACK;
                    LeftRotate(T, w);
                    w=x->parent->left;
                }
                w->color=x->parent->color;
                x->parent->color=BLACK;
                w->left->color=BLACK;
                RightRotate(T,x->parent);
                x=T;
            }
        }
    }
    x->color=BLACK;
}

相关文章

  • 数据结构—树—红黑树

    红黑树概述 红黑树的插入 红黑树的删除

  • TreeMap

    需要先了解红黑树,这是之前分析红黑树的文章。之前在分析红黑树时,我认为红黑树=二叉查找树+红黑平衡,关于二叉查找树...

  • 数据结构与算法-AVL 红黑树

    AVL树AVL树 算法红黑树红黑树 B站

  • [转载]红黑树

    https://zhuanlan.zhihu.com/p/24367771红黑树简介红黑树插入红黑树删除

  • 拿下红黑树

    红黑树 红黑树、2-3树的简单定义: 实现红黑树的基本结构以及添加操作(维护定义,左旋、右旋、颜色反转) 红黑树与...

  • 红黑树

    啥是红黑树,红黑树 = 二叉树

  • 彻底理解红黑树(二)之 插入

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的插入情况...

  • 彻底理解红黑树(三)之 删除

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的删除情况...

  • Golang红黑树

    红黑树 红黑树是每个节点都带有颜色属性(红色或黑色)的二叉查找树。红黑树也属于自平衡二叉查找树。 红黑树具有如下性...

  • 数据结构红黑树添加、修改原理分析

    源码分析大纲 数据结构解析 红黑树试下原理刨析 数据结构解析 1.红黑树 1.1 红黑树概念 红黑树(Red Bl...

网友评论

    本文标题:红黑树

    本文链接:https://www.haomeiwen.com/subject/zwpxyttx.html