红黑树算法

前情提要

红黑树是AVL树里最流行的变种,有些资料甚至说自从红黑树出来以后,AVL树就被放到博物馆里了。红黑树是否真的有那么优秀,我们一看究竟。红黑树遵循以下5点规则,需要我们理解并熟记。

规则:

1.树节点要么是红的,要么是黑的

2.树的根节点是黑的

3.树的叶节点链接的空节点都是黑的,即nullNode为黑

4.红色节点的左右孩子必须是黑的

5.从某节点到null节点所有路径都包含相同数目的黑节点

正是因为作为二叉查找树的红黑树满足这些性质,才使得树的节点是相对平衡的。由归纳法得知,如果一颗子树的根到nullNode节点的路径都包含B个黑色节点,则这棵子树含有除nullNode节点外的2^B-1个节点,而由性质4得从根到nullNode节点的路径上至少有一半的节点是黑色的,从而得到树包含的节点数n>=2^(h/2)-1,h是树的深度,从而得到h<=2*log(n+1)。即可以保证红黑树的深度是对数的,可以保证对树的查找、插入删除等操作满足对数级的时间复杂度。

下边我们将讨论红黑树最主要的两个算法,插入和删除。

红黑树的插入

为了不违反规则5,所以我们将带插入的节点先染成红色,再进行调整以满足其他性质。为了能够清晰的解决问题,我们可以将红黑树的插入分为以下五种情况:

情况1:插入空树中,插入的节点是根节点

情况2:插入的节点的父亲是黑色的

情况3:插入的节点的父亲是红色的,而父节点的兄弟为黑色,且插入节点为外部节点(要找到它要么一直遍历做节点,要么一直遍历右节点)

情况4:插入的节点的父亲是红色的,而父节点的兄弟为黑色,且插入节点为内部节点(不是外外部节点的节点)

情况5:插入的节点的父亲是红色的,而父节点的兄弟也是红色的

对于第一种情况:插入后将根节点再染成黑色即可。

对于第二种情况:直接插入依然满足性质。首先设X是新增节点,P是其父节点,S是其父节点的兄弟节点,G是其的祖父节点。

对于第三种情况:违反了性质4,我们可以通过对P进行右旋和节点的重新着色对树进行修复(应对三、四两种情况我们的着色方式都是:在旋转前先将要旋转的根节点染红,然后旋转,最后将新的根节点染黑)见下面的“图2”。

对于第四种情况:亦是如此,只不过我们需要两次旋转,先对P做左旋再对G做右旋,并重新着色,见下面的“图3”。

对于第五种情况:我们如果按照三四两种情况的修复方式是无法满足性质的,我们就考虑旋转后将新的根节点染红,未插入之前的父节点的兄弟节点染红,新根节点的孩子节点染黑。这样出现的问题是新根节点的父节点可能是红的。此时,我们只能向着根的方向逐步过滤这种情况,不再有连续的两个红色节点或遇到根节点为止(把根重染成黑色)。这种策略自底向上,逐步递归完成,见下面的“图4”。

我们还有一种策略是自顶向下,如果遇到一个黑色节点有两个红色节点,我们将进行颜色翻转(如果节点X有两个红色孩子,我们将X染成红色,将它的两个孩子染成黑色),如果X的父节点也是红色的呢?我们这又归于3、4两种情况。X的父节点的兄弟节点会不会是红色的呢?答案是不会,应为我们自顶向下已经排除了这种情况。此时我们可以排除情况5,将所有情况都转换为情况一到四的处理,除了特殊情况,就剩下情况三和情况四了。

下边是Java代码具体实现:

public void insert(E item){
    current = parent = grand = header;
    nullNode.element = item;
    //当未找到正确插入位置时,一直向下查找,
    //并对树中一个黑节点有两个红节点的情况进行调整  
    while(compare(item,current)!=0){
        great = grand;
        grand = parent;
        parent = current;
        current = compare(item,current)<0?current.left:current.right;
        if(current.left.color==RED&t.right.color==RED)
        handleReorient(item);
    }

    if(current!=nullNode){
        System.out.println("该项已存在");
        return;
    }
    //创建节点并插入修复  
    current = new RedBlackNode<E>(item, nullNode, nullNode);
    if(compare(item,parent)<0){
        parent.left = current;
    }
    else{
        parent.right = current;
    }
    current.parent = parent;
    handleReorient(item);
    nullNode.element = null;
}

//对要插入的节点的链进行调整修复  
private void handleReorient(E item){
    current.color = RED;
    current.left.color = BLACK;
    current.right.color = BLACK;

    if(parent.color == RED){
        grand.color = RED;//先把要旋转的树的根节点染红  
        // 如果不是外节点,则需要旋转两次,
        // 第一次旋转以parent为根,这里传过去的参数树根的父节点  
        if((compare(item,parent)<0)!=(compare(item,grand)<0))
        parent = rotate(item,grand);
        current = rotate(item,great);

        current.color = BLACK;//将新的根节点染黑  
    }
    header.right.color = BLACK;//将整棵树的根节点染黑  
}

/**
 * 明确旋转树在根的左边还是右边后,
 * 我们将旋转树父节点指向根,如果
 * 最终项在左边就右旋,在右边就左旋 
 * @param item 最终项  
 * @param parent 旋转树的根的父节点  
 * @return 旋转树的根节点
 */
private RedBlackNode<E> rotate(E item,RedBlackNode<E> parent){
    if(compare(item,parent)<0){
        parent.left = compare(item,parent.left)<0?
                rotateWithLeftChild(parent.left):rotateWithRightChild(parent.left);
        parent.left.parent = parent;
        return parent.left;
    }
    else{
        parent.right = compare(item,parent.right)<0?
                rotateWithLeftChild(parent.right):
                rotateWithRightChild(parent.right);
        parent.right.parent = parent;
        return parent.right;
    }
}
//以左孩子为支点旋转,即我们所说的右旋(形象理解
//为以支点为中心向右旋转),t1为旋转树的根.返回新根  
private RedBlackNode<E> rotateWithLeftChild(RedBlackNode t1){

    RedBlackNode<E> t2 = t1.left;//得到左孩子  
    t1.left = t2.right;//将左孩子的右子树作为原根的左子树  
    t2.right = t1;//此时t2作为新根  

    t1.parent = t2;
    t2.left.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}
//以右孩子为支点旋转,即左旋  
private RedBlackNode<E> rotateWithRightChild(RedBlackNode t1){
    RedBlackNode<E> t2 = t1.right;
    t1.right = t2.left;
    t2.left = t1;

    t1.parent = t2;
    t2.right.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}

红黑树的删除

1三种情况

红黑树的删除相对复杂些,但只要我们思路明确,问题就迎刃而解。我们先回忆普通二叉树的删除操作,可分为三种情况:

1.没有孩子节点:直接删掉该节点

2.只有一个孩子节点:将要删除节点的父节点直接与该孩子节点相链

3.有两个孩子节点:将中序遍历的后继,即待删除节点的右子树中的最小节点赋给待删除节点,然后将该后继删掉。实际最终都会归于1、2两种情况。

2三个问题

对于红黑树来说,我们不仅要满足二叉树的性质,而且要满足着色要求,所以讨论的情况会比较多,我们从简单的情况开始讨论。如果待删除的实际节点是红色的,我们可以用普通方法进行删除,因为删除过后树依然满足红黑树的性质。如果待删除的实际节点是黑色的,就会出现三个问题:

1.如果删除的节点是根节点,而他的红色孩子成了根节点,这就违反了“规则2”。

2.如果删除的节点的父节点是红色的,而该节点的孩子也是红色的,删除之后就会违反“规则4”。

3.删除了一个黑色节点后,包含该节点的任何路径黑色节点数都会少1,从而违反了“规则5”,我们的任务就是把这些问题解决。

3解决思路

百花齐放:

首先,我们解决问题的总体思路很简单:将节点删除,然后通过旋转和适当的着色来修复树使之重新满足红黑树的性质。我们的入手点就是我们之后所说的当前节点。我们知道实际删除的节点要么只有一个孩子,要么没有孩子,如果该删除节点有一个孩子,则将这个孩子作为当前节点,如果没有孩子,则将nullNode节点作为当前节点。当前节点的父节点就是原删除节点的父节点。我们第一次调整树就是从上边描述的当前节点x开始。(要记住第一个当前节点,要不然后边的描述会变得含糊不清)。

对于问题1我们很好解决,最后再把根节点涂黑即可。而对于问题2,我们可以把当前节点涂黑就可以让树满足红黑树的性质。现在我们需要关注的问题是问题3,即让删除节点后的树依然满足红黑树的性质5——各个节点到根节点到叶节点nullNode所包含的的黑节点数相同。

现在你有什么思路呢?如果像先前我们执行插入的思路那样,自顶向下,保证删除的节点是红色的,这看起来是可行的,但要怎么处理呢?要处理的情况是不是太多了?我们可不可以加上一些条件限制来减少对情况的处理,比如左节点不能是红色的?

要点核心:

这里的处理的思路是:既然删除节点后经过该节点的路径上黑色节点都少一个,我们可不可以将这黑色下推到他的子节点,这样子节点就有了两重颜色。这样就可以满足性质5了。而又违反了性质1,即节点要么是红色的要么是黑色的。我们要做的在保持性质的情况下去掉。(实际上这一层黑色是我们处理问题所转换的标记,并非节点的颜色属性,当前节点指向谁,谁就有了这一层黑色,最终我们在保证基本性质的情况下去掉这一层黑色的影响,问题解决)要想去掉这一层黑色,我们处理的方式有:

1.将这层黑色推向一个包含删除节点路径上的一个红色节点,在满足其他性质的情况下将其染成黑色。

2.一直推至根节点,减掉这层黑色。(因为我们每次的调整最后都是满足性质的)

3.在某些情况下,通过调整和重新着色,我们就可以保住性质,当然这一点有点难以凭空想象,那就看看下边的情况分析吧。

具体操作:

首先我们可以将情况分为两类,即当前节点是其父节点的右节点或左节点,他们是对称的,只需要对一种情况进行详细讨论,另一种情况也就是以此类推了。一般的资料都是对当前节点x是做节点的情况进行分析,在这里我们就先对x是右节点的情况一一画图进行分析。这里先对图中的标记进行解释:x表示当前节点,w表示当前节点的,p表示x的父节点,c表示某个确定的颜色(可能是红,也可能是黑,就看实际情况了)对应于逻辑中的存在,c'表示任意颜色(才不管你是什么颜色咧,对讨论无影响)对应于逻辑中的任意。

情况1:

当前节点x的兄弟w是红色的。这种情况我们可以确定x的父节点为黑色,w的两个孩子为黑。如图所示,我们先对p染红,再将w染黑,然后对p进行一次右旋,红黑性质得以保持。而这时新的兄弟节点是黑色的,进而可以将情况一转换成情况2、3、4中的一种。

情况2:

当前节点x的兄弟节点w是黑色的,且w的两个孩子都是黑色的。这种情况我们无法确定父节点p的颜色,所以其颜色标记为c,情况3、4同。在这个情况下,我们可以将x、w同时去掉一层黑色,将这一层黑色指向根节点p,p变成新的当前节点x。此时如果该标记颜色c为红色,则可以将节点染成黑色,此时指针x的那一层黑色被去掉,同时红黑性质得到满足,调整完毕;如果c为黑色,则需要对新的当前节点x的情况进行处理,直到调整完毕。

情况3:

当前节点x的兄弟节点为黑色,且w的左孩子是黑色,右孩子是红色的。在这种情况下,我们将w和其右孩子的颜色交换,并对w进行左转,红黑性质得以保持。此时已将情况3转换成情况4。

情况4:

当前节点x的兄弟节点w为黑色,且w的左孩子是红的,有孩子可以为任意颜色。将p的颜色赋给w,然后将p,和w的左节点染黑,并对p做右旋转。这是可以去掉x的额外的黑色,而且可以保持红黑性质。最后将树的根赋给x后,调整结束。

我们发现,情况1、3、4最多经过三次旋转调整就可以结束。情况二在最坏的情况下一直向上推最多也是树的层数log(n),这就是红黑树删除操作的性能优势。

4Java代码实现

/**
 * 1.没有孩子节点:直接删掉该节点 
 * 2.只有一个孩子节点:将要删除节点的
      父节点直接与该孩子节点相链 
 * 3.有两个孩子节点:将中序遍历的后继,即待删除节点的右
     子树中的最小节点赋给待删除节点,然后将该后继删掉。 
 * @param e 要删除的元素 
 * @param t 删除元素的树的根节点 
 * @return  被删除的节点
 */
private RedBlackNode<E> remove(E e,RedBlackNode<E> t){
    if(t==nullNode)
        return null;
    //找到要删除的节点  
    while(compare(e,t)!=0){
        if(compare(e,t)<0&&t.left!=nullNode)
            t = t.left;
        else if(compare(e,t)>0&&t.right!=nullNode)
            t = t.right;
        else
            return null;
    }
    RedBlackNode<E> x;//当前节点  
    RedBlackNode<E> y;//要删除的节点  
    //如果待删除节点只有一个孩子或没有孩子,则实际删除的节点
      //就是所指节点,如果有两个孩子则实际删除节点是右子树的最小项  
    //先确定删除节点  
    if(t.left==nullNode||t.right==nullNode)
        y = t;
    else
        y = findMin(t.right);
     //再确定当前节点,如果实际删除节点的左节点不为nullNode,
      //则当前节点为左节点,如果删除节点只有右节点或没有孩子  
    //我们都将右孩子赋给他,因为没有孩子时右节点为nullNode  
    if(y.left!=nullNode)
        x = y.left;
    else
        x = y.right;
    //当前节点的父亲指向删除节点的父亲  
    x.parent = y.parent;

    //我们根据删除节点在其父节点的子树方向,将父节点直接链接到当前节点  
   //需要注意的是我们引用的伪根节点就是为了减少对特殊情况的讨论,
    //不然有这行代码if(y.parent==header)header.right = x;  
    if(y==y.parent.left)
        y.parent.left = x;
    else
        y.parent.right = x;
    //如果实际删除的节点不是我们找到的具有该键的节点,它属于有两个
     //孩子的情况,我们将实际删除的节点的值赋给它  
    if(y!=t)
        t.element = y.element;
    if(y.color==BLACK)
        removeFixUp(x);
    return y;
}

/**
 * 删除修复方法 
 * @param x 当前节点 
 */
private void removeFixUp(RedBlackNode<E> x){
    RedBlackNode<E> w;
    while(x!=header.right&&x.color==BLACK){
            //当前节点是父节点的左节点  
    if(x==x.parent.left){
          w = x.parent.right;
          //case1,如上详细分析,如果x的兄弟节点为红色,
          //调整后是兄弟节点为黑后再往下走  
       if(w.color==RED){
          x.parent.color = RED;
          w.color = BLACK;
          rightRotate(x.parent,x.parent.parent);
          w = x.parent.right;
       }
          //case2,新的x如果为红色,循环终止,否则继续循环  
    if(w.left.color==BLACK&&w.right.color==BLACK){
           w.color = RED;
           x = x.parent;
       }else {
          //case3,兄弟节点的右孩子是黑色的,
          //左孩子时红色的,调整后进入case4  
       if(w.right.color==BLACK){
           w.left.color = BLACK;
           w.color = RED;
           rightRotate(w, w.parent);
           w = x.parent.right;
       }
          //case4,调整完成,满足红黑性质  
           w.color = x.parent.color;
           x.parent.color = BLACK;
           w.right.color = BLACK;
      leftRotate(x.parent, x.parent.parent);
           x = header.right;
        }
        }else{
        //对称  
        }
        x.color = BLACK;
    }
}

原文发布于微信公众号 - 机器学习算法全栈工程师(Jeemy110)

原文发表时间:2017-08-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏海天一树

图的广度优先搜索

广度优先搜索算法是最简便的图的搜索算法之一,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索...

892
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

2685
来自专栏sunseekers

数据结构学习☞入门(一)算法数据结构

编程如果只是一个为了解决生活温饱的工具,那你可以完全忽略数据结构,算法,你的目标很容易实现;但如果你是热爱编程,把它当做对生活的追求,想在这一行走的更远,更久,...

703
来自专栏武培轩的专栏

Leetcode#53.Maximum Subarray(最大子序和)

题目描述 给定一个序列(至少含有 1 个数),从该序列中寻找一个连续的子序列,使得子序列的和最大。 例如,给定序列 [-2,1,-3,4,-1,2,1,-5,4...

3055
来自专栏bboysoul

1067: 成绩评估

描述:我们知道,高中会考是按等级来的。90~100为A; 80~89为B; 70~79为C; 60~69为D; 0~59为E。 编写一个程序,对输入的...

632
来自专栏算法修养

线性DP总结(LIS,LCS,LCIS,最长子段和)

做了一段时间的线性dp的题目是时候做一个总结 线性动态规划无非就是在一个数组上搞嘛, 首先看一个最简单的问题: 一,最长字段和 下面为状...

2527
来自专栏Golang语言社区

Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法

本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法。...

34210
来自专栏李蔚蓬的专栏

第12周Python学习周记

>>> b = a                                #没有创建新的对象

662
来自专栏前端杂货铺

JS的内建函数reduce

@(js) reduce函数,是ECMAScript5规范中出现的数组方法。在平时的工作中,相信大家使用的场景并不多,一般而言,可以通过reduce方法实现的逻...

3417
来自专栏决胜机器学习

PHP数据结构(十六) ——B树

PHP数据结构(十六)——B树 (原创内容,转载请注明来源,谢谢) 一、概述 B树在很多地方被称为“B-树”,因为B树的原英文名称为B-tre...

42911

扫码关注云+社区