天天说手撕红黑树？你真的能撕的下来吗？（详细解释+代码注释）

素颜马尾好姑娘i 2024-03-30 10:54 59阅读 0赞

**目录**

一、你还记得什么是红黑树吗？

二、AVL树与红黑树的比较

三、模拟实现红黑树

3.1、红黑树的定义

3.2、插入结点

3.2.1、情况一

3.2.2、情况二

3.2.3、情况三

四、红黑树的验证

4.1、检查中序遍历是否有序

3.2、检查是否出现两个连续的红色结点

4.3、检查每条路径的黑色结点数目是否相同

4.4、验证红黑树是否满足要求（综合）

五、完整红黑树代码

--------------------

## 一、你还记得什么是红黑树吗？ ##

红黑树是一种二叉搜索树，但在每个结点上又增加一个存储位表示颜色，可以是黑或红；由于**最长路径不超过最短路径的两倍**，因此，红黑树不像AVL树是绝对平衡的，而是相对平衡的；

![82fb32d4923c415093681561093104c0.png][]

> 性质：

1、每个结点颜色，非黑即红；

2、根节点是黑色的；

3、若一个结点时红色的，则他的两个孩子结点是黑色的；（没有两个连续的红色结点）

4、对于每一个结点，从该结点到所有后代叶节点的简单路径上，黑色结点的数目是相同的；

5、每个叶子结点都是黑色的NIL（空结点）；

> 为什么有这5点性质，就能保证红黑树，**最长路径不超过最短路径的两倍**？一张图让你明白，如下：

![7b080e01be7c49f9ba2ad590d73d5e0c.png][]

那么假设，一颗红黑树中有N个黑色结点，那么这颗树的结点数量的范围就是N~2N个，路径长度在logN ~ log2N之间；

--------------------

## 二、AVL树与红黑树的比较 ##

AVL树和红黑树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log2 N)，AVL树是绝对的平衡，而红黑树不是绝对的平衡，他只保证最长路径不超过最短路径的2倍，所以对比起来，降低了插入和删除的次数；

**应用场景：**如果是经常需要进行增删改查，更推荐使用红黑树（实际场合运用的最多的也是红黑树）；如果不经常进行增删改查，而是追求极致的查询效率，推荐使用AVL树；

--------------------

## 三、模拟实现红黑树 ##

### 3.1、红黑树的定义 ###

> 这里的定义和AVL树的定义差不多，唯一有区别的地方是红黑树多了一个颜色的定义，颜色的定义我们可以通过枚举类来实现，如下代码：

public enum COLOR {
        RED, BLACK
    }

> 注意：

**每次新增结点必须是红色的**，因为如果某一个分支上增加一个黑色结点，根据红黑树的特点，那么其他每一个分支上也必须都增加一个黑色结点，但实际上我需要增加一个结点，而为了满足红黑树特点多增加的这些结点是没有意义的；如果添加一个红色节点，我们只需要通过调整颜色，即可满足要求；不太理解的话可以看看下面这张图：

若新增结点是黑色的，需要继续添加一些无意义的结点满足红黑树要求，如下：

![d13bddc75d2e4b088480689372ee5bc9.png][]

若新增结点是红色的，只需要修改颜色即可，如下：

![2a94054b269141beabacf4761ae2cd38.png][]

###  ###

### 3.2、插入结点 ###

红黑树的插入结点和二叉搜索树的插入结点的方式是一样的，那么还有的代码对于AVL树来说就是需要调节平衡因子和旋转；对于红黑树来说就需要考虑颜色了，因为若新增结点是红色的，而他的父亲结点也是红色的，此时就违反了红黑树的性质，因此需要对颜色进行调整，具体调整方式，分为以下三种情况：

首先，这里约定：cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点；

#### 3.2.1、情况一 ####

> cur为红，p为红，g为黑，u存在且为红，如下：

![fc6e7415fbe44abb84afc4bfa8e12a9e.png][]

**但是这样就够了吗？**

> 肯定是不够的，因为这里没有考虑 g 的父亲结点是什么颜色的，如果他的父亲结点是黑色，那么若只是单纯的将 p 和 u 修改成黑色，是有可能出问题的，如下：

![8b59b328f05545148ca0c601b1baf312.png][]

> 总结一下 ：

对于以上出现的所有情况，**将p 和 u 设置成黑色后，可以直接将结点 g 颜色修改成红色**；那如果g就是根节点呢？解决办法就是当所有情况处理完后，**无论根节点是什么颜色，都手动将他置为黑色；**

如果 g 上面的结点是红色的，那么就继续向上调整，此时 g 结点就相当于是cur结点，p 和 u 依次此向上类推即可，如下图：

![38a0018dec7349869f074ed1e233f055.png][]

> 那么情况一的代码就有啦，如下：

while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
                RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
                if(parent == grandFather.left) {
                    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是黑色的
                    }
                } else {
    
                }
            }

#### 3.2.2、情况二 ####

> cur为红，p为红，g为黑，u不存在/u为黑，处理方式如下：

![446d87ae88d94ad8b9a5332575daf62a.png][]

![e1d80e075748467b9a5526da6af1b6c8.png][]

而这里的右单旋具体讲解在讲解AVL树那一张就写过啦，没看过的小伙伴可以去看一看这篇：[http://t.csdn.cn/MNFBp][http_t.csdn.cn_MNFBp]

> 代码如下：

#### 3.2.3、情况三 ####

> cur为红，p为红，g为黑，u不存在/u为黑，如下：

![0106c1642a3949558bd31d1729b59fe8.png][]

![03b8a78ccb2d4a948a1f2516fddcf34d.png][]

仔细观察，这不就是 **情况二修改完颜色后的样子吗？唯一的差别只是cur和p的指向相互调换了**， 所以，这里只需要旋转后调整一下指向即可~

> 如下代码：

//红黑树需要调整颜色
            while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
                RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
                if(parent == grandFather.left) {
                    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是黑色的
                        //情况三：(这里只需要把情况三处理成情况二)
                        if(cur == parent.right) {
                            rotateLeft(parent);
                            //这里只需要交换一下cur和parent
                            RBTreeNode tmp = parent;
                            parent = cur;
                            cur = tmp;
                        }//走完这里，情况三就变成了情况二
    
                        //情况二：
                        //这里只需要先右旋，然后修改颜色即可
                        rotateRight(parent);
                        parent.color = COLOR.BLACK;
                        grandFather.color = COLOR.RED;
                    }
                } else {
    
                }
            }

以上所讲，都是处理grandFarther.left，接下来就需要处理最后一个else的情况grandFarcher.right，实际上和grandFarther.left几乎一样，需要处理的地方就是原本是右旋和左旋需要颠倒一下，以及parent的指向；

> 如下代码：

public class RBTree {
        static class RBTreeNode {
            public RBTreeNode left;
            public RBTreeNode right;
            public RBTreeNode parent;
            public int val;
            public COLOR color;
    
            public RBTreeNode(int val) {
                this.val = val;
                //新增结点，默认必须是红色
                this.color = COLOR.RED;
            }
        }
        public RBTreeNode root;//根节点
    
        public boolean insert(int val) {
            RBTreeNode node = new RBTreeNode(val);
            if(root == null) {
                root = node;
                root.color = COLOR.BLACK;//注意第一次插入根节点一定是黑色
                return true;
            }
            RBTreeNode parent = null;
            RBTreeNode cur = root;
            while(cur != null) {
                if(cur.val > val) {
                    //向左寻找
                    parent = cur;
                    cur = cur.left;
                } else if(cur.val == val) {
                    //相等就说明插入失败
                    return false;
                } else {
                    //向右寻找
                    parent = cur;
                    cur = cur.right;
                }
            }
            //cur == null
            if(parent.val > val) {
                parent.left = node;
            } else {
                parent.right = node;
            }
            node.parent = parent;
            cur = node;
    
            //红黑树需要调整颜色
            while (parent != null && parent.color == COLOR.RED) {//parent为红色，就是两个红色结点连在一起了
                RBTreeNode grandFather = parent.parent;//这个引用一定不为空，因为此时parent一定是红色！
                if(parent == grandFather.left) {
                    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是黑色的
                        //情况三：(这里只需要把情况三处理成情况二)
                        if(cur == parent.right) {
                            rotateLeft(parent);
                            //这里只需要交换一下cur和parent
                            RBTreeNode tmp = parent;
                            parent = cur;
                            cur = tmp;
                        }//走完这里，情况三就变成了情况二
    
                        //情况二：
                        //这里只需要先右旋，然后修改颜色即可
                        rotateRight(parent);
                        parent.color = COLOR.BLACK;
                        grandFather.color = COLOR.RED;
                    }
                } else {
                    //parent == grandFather.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是黑色的
                        //情况三：(这里只需要把情况三处理成情况二)
                        if(cur == parent.left) {
                            rotateRight(parent);
                            //这里只需要交换一下cur和parent
                            RBTreeNode tmp = parent;
                            parent = cur;
                            cur = tmp;
                        }//走完这里，情况三就变成了情况二
    
                        //情况二：
                        //这里只需要先右旋，然后修改颜色即可
                        rotateLeft(parent);
                        parent.color = COLOR.BLACK;
                        grandFather.color = COLOR.RED;
                    }
                }
            }
            root.color = COLOR.BLACK;
            return true;
        }
    
        //左单旋
        private void rotateLeft(RBTreeNode parent) {
            RBTreeNode subR = parent.right;
            RBTreeNode subRL = subR.left;
            parent.right = subRL;
    
            subR.left = parent;
    
            if(subRL != null) {
                subRL.parent = parent;
            }
            //必须先记录parent的父亲
            RBTreeNode pParent = parent.parent;
            parent.parent = subR;
            //检查parent是否为根节点
            if(parent == root) {
                root = subR;
                root.parent = null;
            } else {
                //不是根节点需要判断parent是左子树还是右子树
                if(pParent.left == parent) {
                    pParent.left = subR;
                } else {
                    pParent.right = subR;
                }
                subR.parent = pParent;
            }
        }
    
        //右单旋
        private void rotateRight(RBTreeNode parent) {
            RBTreeNode subL = parent.left;
            RBTreeNode subLR = subL.right;
            parent.left = subLR;
            subL.right = parent;
            if(subLR != null) {
                subLR.parent = parent;
            }
            //必须先记录parent的父亲
            RBTreeNode pParent = parent.parent;
            parent.parent = subL;
            //检查parent是否是根节点
            if(parent == root) {
                root = subL;
                root = null;
            } else {
                //不是根节点，判断parent是左子树还是右子树
                if(pParent.left == parent) {
                    pParent.left = subL;
                } else {
                    pParent.right = subL;
                }
                subL.parent = pParent;
            }
        }
    }

芜湖~这样整个插入就完成了~

--------------------

## 四、红黑树的验证 ##

验证是否为红黑树就是要看是否满足红黑树的特性；

### 4.1、检查中序遍历是否有序 ###

这个就是简单的中序遍历~

> 代码如下：

public void dfs(RBTreeNode root) {
            if(root == null) {
                return;
            }
            dfs(root.left);
            System.out.print(root.val + " ");
            dfs(root.right);
        }

### 3.2、检查是否出现两个连续的红色结点 ###

这里可以反向去检查，也就是说，当你遍历到一个红色结点时，只需要看一下他的父亲结点是否是黑色，若是黑色的就满足要求，若不是，就不是红黑树；

> 代码如下：

//检查是否出现俩个连续的红色结点
        private boolean checkRedColor(RBTreeNode root) {
            if(root == null) {
                return true;
            }
            if(root.color == COLOR.RED) {
                RBTreeNode parent = root.parent;
                if(parent.color == COLOR.RED) {
                    System.out.println("不是红黑树，违反了性质：不可以出现两个连续的红色结点");
                    return false;
                }
            }
            return checkRedColor(root.left) && checkRedColor(root.right);

### 4.3、检查每条路径的黑色结点数目是否相同 ###

可以通过递归遍历每一个结点，创建一个计数器，一旦遍历到黑色结点计数器就加一，若当前结点的左右子树都为空，说明一条路径已经遍历完了，这个适合就可以对比黑色结点数目相同，满足要求；

> 代码如下：

/**
         *
         * @param root
         * @param pathBlackNum 递归时每条路径上的黑色结点个数
         * @param BlackNum 以及计算好的黑色结点个数
         * @return
         */
        private boolean checkBlackNum(RBTreeNode root, int pathBlackNum, int BlackNum) {
            if(root == null) {
                return true;
            }
            if(root.color == COLOR.BLACK) {
                pathBlackNum++;
            }
            if(root.left == null && root.right == null) {
                if(pathBlackNum != BlackNum) {
                    System.out.println("不是红黑树，违反了性质：每条路径上的黑色结点个数相同");
                    return false;
                }
            }
            return checkBlackNum(root.left, pathBlackNum, BlackNum) &&
                    checkBlackNum(root.left, pathBlackNum, BlackNum);
    
        }

### 4.4、验证红黑树是否满足要求（综合） ###

这里除了要综合以上的检查方法，同时还要判断根节点的颜色，若根节点的颜色不是黑色，则说明不满足要求；

> 代码如下：

//验证红黑树(就是要满足红黑树的性质)
        public boolean isRBTree(RBTreeNode root) {
            if(root == null) {
                return true;
            }
            if (root.color != COLOR.BLACK) {
                System.out.println("不是红黑树，违反了性质：根节点是黑色的");
            }
            int BlackNum = 0;
            RBTreeNode cur = root;
            while(root != null) {
                if(root.color == COLOR.BLACK) {
                    BlackNum++;
                }
                root = root.left;
            }
            // 检查是否出现俩个连续的红色结点 && 检查每条路径黑色结点数是否相同
            return checkRedColor(root) && checkBlackNum(root, 0, BlackNum);

--------------------

## 五、完整红黑树代码 ##

--------------------

![ef98fa1af66d44fcbd1e640065760f62.gif][]

[82fb32d4923c415093681561093104c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f3bba81ec49c45d79f87c897dc8ee266.png
[7b080e01be7c49f9ba2ad590d73d5e0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9de350d6d7544d2587d6eb83933edb96.png
[d13bddc75d2e4b088480689372ee5bc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3e5071015d97444680ff8eac79c6bc4d.png
[2a94054b269141beabacf4761ae2cd38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b84eaa0e67f84b019e34f3d6dd7e3f55.png
[fc6e7415fbe44abb84afc4bfa8e12a9e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a767855137474a0f9f0dca7401e012fe.png
[8b59b328f05545148ca0c601b1baf312.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b052c9072f0147bfb4865b80173b4739.png
[38a0018dec7349869f074ed1e233f055.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/470695bcfff84262aea89d00502700d8.png
[446d87ae88d94ad8b9a5332575daf62a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6f5584f5a6fe4ceea724f84177aa7aa9.png
[e1d80e075748467b9a5526da6af1b6c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fb28928a9c2d4ac49049b27692c4c488.png
[http_t.csdn.cn_MNFBp]: http://t.csdn.cn/MNFBp
[0106c1642a3949558bd31d1729b59fe8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8a59eabd1d004294b9e728b2395a4095.png
[03b8a78ccb2d4a948a1f2516fddcf34d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/880a0b824565477e90373b7efcd72068.png
[ef98fa1af66d44fcbd1e640065760f62.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/61df7396e54446578302668de35b564f.gif