红黑树学习笔记
麦兜 / 2020-04-17 / 数据结构 / 阅读量 290

红黑树特性

(1)每个结点或者是黑色,或者是红色。
(2)根结点是黑色。
(3)每个叶子结点(NIL)是黑色。 (这里的NIL结点非空 结点,是一个实实在在的结点 用于删除的方便)
(4)如果一个结点是红色的,则它的子结点必须是黑色的。
(5)从一个结点到该节点的子孙节点的所有路径上包含相同数目的黑结点。

简易说明:红黑树由黑高来和旋转操作置底向上来维护的。

阅读建议:

​ 1、读者储备二分搜索树的增删改树的旋转知识。

​ 2、更多细节希望去读《算法导论》此文章仅作为参考笔记。

统一名称:

​ PP: 为祖父结点

​ P:为父结点

​ Y:为叔结点

​ Z:当前结点

INSERT

红黑树插入结点会影响到他的结构特性,所以分成三种情况来处理。

情况1(P和Y结点为红色)

当D插入了就违法了第4个特性,就需要把P结点Y结点变黑色。

PP结点变成红色当成新结点指针Z指向PP

​ 1、如果PP结点不为根节点就继续往上维护。

​ 2、如果PP结点为根结点就变黑色即可。

情况2(子结点插入在P结点的右边并且P结点为红色,Y结点为黑色或无)

当D插入违反了第4个特性,而且它存在P结点的右边只需要把D向左炫转即可(成为第三种情况)。

情况3(子结点插入在P结点的左边并且P结点为红色,Y结点为黑色或无)

当D插入或者第2种情况旋转违反了第4个特性,而且它存在P结点的左边需要把P结点变成黑色PP结点变成红色然后右旋转即可。

代码

/*伪代码*/

//树结构
T{
    root //根节点
    P //父结点
    C //颜色
    V //存储值
    L,R //左右结点
}

T.nil{
    
    P=T.nil //父结点
    C=Black //颜色
    V//存储值
    L=T.nil,R=T.nil //左右结点
}


//T.nil 是一个普通结点而且仅有一个值随意代表为叶子结点或为空,颜色为黑色
INSERT(T,Z)
{
    y=T.nil
    x=T.root
    //找插入结点
    while (x!=T.nil)
    {
        y=x
        if(z.v<x.v)
            x=x.L
         else x=x.R
    }
    z.P=y
   //首次插入节点
    if(y==T.nil)
        T.root=z
     else if(z.v<y.v)
         y.L=z
     else y.R=z
     
     z.L=T.nil
     z.r=T.nil
     z.c=Red
   //维护结构     
   INSERT-FIX-UP(T,z)
}

INSERT-FIX-UP(T,z)
{
    while (z.P.C==Red)
    {
        //判断当前p是否在pp的左边
        if(z.P==z.P.P.L)
        {
            //因为旋转会跟Y结点有关 所以需要保存下来
            y=z.P.P.R
                
            //第一种情况
            if(y.c==Red)
            {
                z.P.color=Black
                y.C=Black
                z.P.P.C=Red
                z=z.P.P
            }
            //第二种情况
            else if(z==z.p.R)
            {
               //左旋转成为第三种情况
            }
            //第三中情况
            z=z.P
            z.P.C=Black
            z.P.P.C=Red
        }
        else{
            //和p在pp左边一样 只是改成右旋转 Y结点指向z.P.P.L
        }
    }
    T.root.c=Black //把根节点变回黑色
}

DELETE

又应该复习一遍红黑树得特性。

(1)每个结点或者是黑色,或者是红色。
(2)根结点是黑色。
(3)每个叶子结点(NIL)是黑色。
(4)如果一个结点是红色的,则它的子结点必须是黑色的。
(5)从一个结点到该节点的子孙节点的所有路径上包含相同数目的黑结点。

因为红黑树删除结点比插入结点复杂的多,所以需要思维图总结一下。

伪代码参考

1 + 9 =
快来做第一个评论的人吧~