【数据结构】红黑树详解

目录

前言：

如果有需要文章源码的友友请前往：红黑树源码

找到RBTree即红黑树源码。

红黑树的概念：

红黑树（RBTree），是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

下图就是一颗红黑树。

红黑树的性质:

（1）最长路径最多是最短路径的2倍。

（2）每个结点不是红色就是黑色。

（3）根节点是黑色的 。

（4） 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有2个连续的红色节点） 

（5）对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

（6）每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。

红黑树节点的定义：

红黑树采用孩子双亲表示法，多了一个表示颜色的枚举类（只有BLACK和RED）.

public class RBTreeNode {
    public int val;
    public RBTreeNode left;
    public RBTreeNode right;
    public RBTreeNode parent;
    public COLOR color;
    public RBTreeNode(int val){
        this.val = val;
        color = COLOR.RED;
    }
}

其中COLOR是枚举类型具体代码如下： 

public enum COLOR{
    RED,BLACK
}

在看到上面红黑树的构造方法后，不知道友友们有没有对把新节点设置成红色感到疑惑尼？ 

提问：在节点的定义中，为什么要将节点的默认颜色给成红色的？

答：这是因为根据上面给出的性质（5），红黑树从某节点到其后代叶节点的路径上的黑色节点个数相同，那么这个时候如果直接插入一个黑色节点，那么为了维护性质（5）必须要在别的叶节点后面也插入黑色节点，但是我们本意是插入一个节点，故不能插入黑色节点。至于插入红色节点可能会违反性质（4）我们只要调节一下颜色即可。

红黑树的插入：

红黑树是在二叉搜索树的基础上，加上其平衡限制条件，因此红黑树的插入可分为两步：

（1）按照二叉搜索的树规则插入新节点。

（2）检测新节点插入后，红黑树的性质是否造到破坏。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整，但当新插入节点的双亲节点颜色为红色时，就违反了性质（4）不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

在这之前我们先来个规定🙌🙌🙌：

规定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点。

总共有三种情况具体如下：

情况1：cur为红，p为红，g为黑，u存在且为红

这里解释的cur在p的左边如果cur是在p的右边的情况可以把三种情况都看完，相信就明白啦👍👍👍

如下图：

那么我们要怎么调整才能使它符合红黑树的性质呢？

具体调整过程如下：

注意：这里看到的树，可能是一个完整的树，也可能是一颗子树。

（1）如果g是根节点，调整完成后，需要将g改成黑色。

（2）如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整。

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况2：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur都在其父亲节点同一侧）

说明：情况2可以根据u存不存在分为两种：

（1）如果u节点不存在，则cur一定是新插入节点（第二种情况的cur原本是黑色的，因为向上调整变成红色），因为如果cur不是新插入节点，则cur和p一定有一个节点的颜色是黑色，这样就不满足性质（5）：每条路径黑色节点个数相同。

（2）如果u节点存在，则其一定是黑色（情况规定），那么cur节点原来的颜色一定是黑色的，现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色变成红色。

第1种类型如下图：

如果对旋转不太清楚的话可以看看我的上一篇博客实现的很清楚了。AVL树

先进行把g右旋，在把p和g的颜色改一下就可以弄出符合6条性质的红黑树。 

第2种类型如下图：

第2种类型是在调整的过程中才会出现的如下图。

 出现第2中类型后我们先把g右旋，接着把p变黑，g变红。

情况2的总结：

p为g的左孩子，cur为p的左孩子，则进行右单旋转。

p为g的右孩子，cur为p的右孩子，则进行左单旋转。

p、g变色–》p变黑，g变红。

情况3：cur为红，p为红，g为黑，u不存在或者u为黑（p和cur在其父亲节点的不同侧）

单看名字可能觉得和情况2差不多，其实就是多了一层旋转，如果有学过AVL树的友友不难发现这其实和AVL树的双旋差不多（没学过也没关系啦👍👍👍）。

当u不存在的情况下：

我们可以看到先将p节点左旋，再把p和cur的指向互换，这样就变成情况2，接着我们按照情况2来处理即可。

当u存在的情况下：

先根据情况1调整接着把p节点左旋，并交换p和cur的指向。最后按照情况2的处理方式即可。

到这里我们插入的三种情况终于全部讲解完毕🎉🎉🎉 

注意：我们上面分析的三种情况都是parent在grandFather的左侧，由于文章篇幅有限且parent在grandFather的右侧分析和在左侧是一模一样的，故这里就不再过多赘述，画完图后我们就会发现parent在grandFather的右侧就是和在左侧相反的情况，即把代码中出现left的改为right，right改为left即可（旋转方法也是）。 

插入的具体源码如下：

旋转源码因为和上一章AVL树差不多如果有需要源码的友友在文章的开头有给出😎😎😎。

public boolean insert(int val) {
        //1.按照二叉搜索树的方式插入节点
        RBTreeNode node = new RBTreeNode(val);
        if (root == null) {
            root = node;
            root.color = COLOR.BLACK;
            return true;
        }
        RBTreeNode parent = null;
        RBTreeNode cur = root;
        //记得要及时更新parent节点
        while (cur != null) {
            if (val > cur.val) {
                parent = cur;
                cur = cur.right;
            } else if (val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else {
                System.out.println("存在重复节点");
                return false;
            }
        }
        if (val < parent.val) {
            parent.left = node;
        } else {
            parent.right = node;
        }
        //千万要记得我们还要把node的parent指回去。
        node.parent = parent;
        cur = node;
        //进行红黑树的调整
        while (parent != null && parent.color == COLOR.RED) {
            //注意进入这个while循环这里的grandFather是必定存在的，
            //因为parent为红色，但是我们的根节点只能是黑色
            RBTreeNode grandFather = parent.parent;
            if (grandFather.left == parent) {
                RBTreeNode uncle = grandFather.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                } else {
                    //uncle不存在或者uncle为黑色
                    //经过分别画图uncle不存在和uncle为黑色的情况分析发现处理方式是一样的
                    //只要区分cur在parent的左侧还是右侧即可
                    //和AVL树的思路差不多先旋转预处理一下，再来一次旋转搞定。
                    //即转化为cur和parent在同一侧的情况。
                    if (cur == parent.right) {
                        rotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //转换成一侧的情况
                    rotateRight(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }
            } else {
                //grandFather.right == parent
                //这里就只要把上面的代码对应反着来就行
                //就是把上面代码里面出现right变成left，left变成right，方法也要变
                RBTreeNode uncle = grandFather.left;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandFather.color = COLOR.RED;
                    cur = grandFather;
                    parent = cur.parent;
                } else {
                    //uncle不存在或者uncle为黑色
                    //经过分别画图uncle不存在和uncle为黑色的情况分析发现处理方式是一样的
                    //只要区分cur在parent的左侧还是右侧即可
                    //和AVL树的思路差不多先旋转预处理一下，再来一次旋转搞定。
                    //即转化为cur和parent在同一侧的情况。
                    if (cur == parent.left) {
                        rotateRight(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;
                    }
                    //转换成一侧的情况
                     rotateLeft(grandFather);
                    grandFather.color = COLOR.RED;
                    parent.color = COLOR.BLACK;
                }

            }

        }
        root.color = COLOR.BLACK;
        return true;
    }

红黑树验证：

写完代码那就肯定要验证一下下啦❤️❤️❤️

红黑树的检测分为两步：

（1）检测其是否满足二叉搜索树 (中序遍历是否为有序序列)。

（2）检测其是否满足红黑树的性质。

中序遍历代码简单我就不贴了。

空树也是红黑树。

根节点的颜色是黑色。

判断没有两个连续的红色节点（checkRedNode）和每条路径上黑色节点数相同（checkBlackNum）

public boolean isValidRBTree(){
        //1.红的节点后面只能是黑色节点
        //2.所有节点到其后代叶子节点的路径上的黑色节点个数相同
        //3.根节点必须是黑色节点
        if(root == null){
            return true;
        }
        if(root.color != COLOR.BLACK){
            System.out.println("违反了根节点必须是黑色的特性");
            return false;
        }
        int tempBlackNum = 0;
        RBTreeNode cur = root;
        while(cur != null){
            if(cur.color == COLOR.BLACK){
                tempBlackNum++;
            }
            cur = cur.left;
        }
        return checkRedNode(root) && checkBlackNum(root,0,tempBlackNum);
    }

要想确定每一条路径上黑色节点个数相同那么我们就要先找一条路径来作参照，至于正不正确我们不关心只要保证黑色节点数相同即可。

找参照黑色节点数在外面找这里看上面代码我找的是最左边的那条路。

checkBlackNum源码如下：

private boolean checkBlackNum(RBTreeNode root,int path,int tempBlackNum){
        if(root == null){
            return true;
        }
        //要先加在判断，根据实际情况来
        if(root.color == COLOR.BLACK){
            path++;
        }
        if(root.left == null && root.right == null){
            if(path != tempBlackNum){
                System.out.println("违反了每条路径上的黑色节点数是一样的");
                return false;
            }
        }
        return checkBlackNum(root.left,path,tempBlackNum) && checkBlackNum(root.right,path,tempBlackNum);
    }

checkRedNode源码如下：

这里root的颜色如果是红色的话那么其父亲节点必定存在，因为根节点是黑色的所以不用判断是否为空。可以看到在树的各类方法中递归是非常参见的，写递归时我们关注某一个子问题做什么就好了。

private boolean checkRedNode(RBTreeNode root){
        if(root == null){
            return true;
        }
        if(root.color == COLOR.RED){
            if(root.parent.color == COLOR.RED){
                System.out.println("违反了两个红色节点不能连续出现");
                return false;
            }
        }
        return checkRedNode(root.left) && checkRedNode(root.right);
    }

这里也建议大家拿这个这个测试用例去跑一跑。

不仅要返回true还要调试一遍看看和自己手动画的图是不是一样的，下面我给出测试用例的红黑树的图，也希望友友们能自己画出来。 

红黑树的删除本文章不做讲解，有兴趣的同学可参考：《算法导论》

作者准备学了（希望不要入门到入土😭😭😭），后续有需要的话可能会单独出一篇👌👌👌。

AVL树和红黑树的比较：

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(logN)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树应用：

1. java集合框架中的：TreeMap、TreeSet底层使用的就是红黑树。

2. C++ STL库 — map/set、mutil_map/mutil_set。

3. linux内核：进程调度中使用红黑树管理进程控制块，epoll在内核中实现时使用红黑树管理事件块。

4. 其他一些库：比如nginx中用红黑树管理timer等。

结语：

其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。