数据结构之红黑树的 “奥秘“

目录：

一.红黑树概念

二. 红黑树的性质

三.红黑树的实现

四.红黑树验证 

五.AVL树和红黑树的比较

一.红黑树概念

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

二. 红黑树的性质:

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的【没有2个连续的红色节点】

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点也就是（每条路径的黑色节点数相等）

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

总结性质：最长路径最多是最短路径的2倍.

总结性质推导：

三.红黑树的实现：

1.红黑树节点的定义 :

这里注意我们定义一个枚举来储存红黑树节点的颜色

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;
}

 

2.红黑树的插入:

这里我们要围绕红黑树上面的几条性质构建红黑树；但是红黑树是在二叉搜索树的基础上加上其平衡限制条件，所有我们构建时可以借鉴二叉搜索树方式。

步骤一：和二叉二叉搜索树一样找到要插入的节点；

步骤二：调整插入的节点让其满足红黑树的性质；

所有我们构建红黑树总共有三种情况

这里注意：插入节点默认为红色节点，推导如下：

3.构建红黑树的有三种情况:

3.1.情况一: cur为红，p为红，g为黑，u存在且为红:

图解：

代码：

 //开始调整颜色
        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandParent = parent.parent;

            /**情况一：
             *
             * cur为红，p为红，g为黑，uncle存在且为红
             *
             *  parent在grandParent左边，uncle在grandParent右边
             */
            if (parent == grandParent.left) {
                RBTreeNode uncle = grandParent.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;

                    //预防grandParent的父亲为红色，就还有子树,继续向上修改
                    cur = grandParent;
                    parent = cur.parent;
                }

3.2.情况二: cur为红，p为红，g为黑，u不存在或者u为黑:

这里注意要先grandParent右旋，然后再调整颜色，parent改为 黑色，grandParent改为红色

 图解：

代码：

/** 情况二：
* cur为红，p为红，g为黑，uncle为黑色，或者uncle不存在
*
*  方法：
*  1.先右单旋
*  2.再改颜色
 */
rotateRight(grandParent);
parent.color = COLOR.BLACK;
grandParent.color = COLOR.RED;

3.3.情况三: 调整过程中，cur为红，p为红，g为黑，u不存在/u为黑：

这里先左旋parent，再把parent 和 cur 的引用交换变为和情况二类似，再当作情况二处理（右旋改颜色，图片上笔误是右旋）

代码：

/**
 * 情况三：
* 先左单旋parent
* 再交换parent和cur的引用,变成情况二处理
*/
if (parent.right == cur) {
rotateLeft(parent);
RBTreeNode tmp = parent;
parent = cur;
cur = tmp;

}//变成情况二

 

当parent == grandParent.right，和上面三种情况完全相反，为镜相关系。

插入全部代码如下：

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为空时，要把插入的节点变为黑色
            root.color = COLOR.BLACK;
            return true;
        }

        RBTreeNode cur = root;
        RBTreeNode parent = null;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }

        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        node.parent = parent;
        cur = node;//指向新插入的节点

        //开始调整颜色
        while (parent != null && parent.color == COLOR.RED) {
            RBTreeNode grandParent = parent.parent;

            /**情况一：
             *
             * cur为红，p为红，g为黑，uncle存在且为红
             *
             *  parent在grandParent左边，uncle在grandParent右边
             */
            if (parent == grandParent.left) {
                RBTreeNode uncle = grandParent.right;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;

                    //预防grandParent的父亲为红色，就还有子树,继续向上修改
                    cur = grandParent;
                    parent = cur.parent;
                } else {

                    /**
                     * 情况三：
                     * 先左单旋parent
                     * 再交换parent和cur的引用,变成情况二处理
                     */
                    if (parent.right == cur) {
                        rotateLeft(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;

                    }//变成情况二


                    /** 情况二：
                     * cur为红，p为红，g为黑，uncle为黑色，或者uncle不存在
                     *
                     *  方法：
                     *  1.先右单旋
                     *  2.再改颜色
                     */

                    rotateRight(grandParent);

                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            } else {


                //下面情况和上面情况完全相反


                //parent == grandParent.right
                RBTreeNode uncle = grandParent.left;
                if (uncle != null && uncle.color == COLOR.RED) {
                    parent.color = COLOR.BLACK;
                    uncle.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;

                    //预防grandParent的父亲为红色，就还有子树,继续向上修改
                    cur = grandParent;
                    parent = cur.parent;
                } else {

                    if (parent.left == cur) {
                        rotateRight(parent);
                        RBTreeNode tmp = parent;
                        parent = cur;
                        cur = tmp;

                    }
                    //变成情况二

                    rotateLeft(grandParent);
                    parent.color = COLOR.BLACK;
                    grandParent.color = COLOR.RED;
                }
            }
        }

        //当parent为空时，要把根节点变为黑色
        root.color = COLOR.BLACK;
        return true;
    }


        /**
         * 右单旋
         * @param parent
         */
        private void rotateRight (RBTreeNode parent){
            RBTreeNode subL = parent.left;
            RBTreeNode subRL = subL.right;

            parent.left = subRL;
            subL.right = parent;
            //如果旋转的整棵树也是一个子树，记录下原来该树的父亲，后续修改
            RBTreeNode pParent = parent.parent;

            if (subRL != null) {
                subRL.parent = parent;
            }
            parent.parent = subL;

            //看看整棵树是否也是一个子树
            if (parent == root) {
                root = subL;
                root.parent = null;
            } else {
                //是子树就确定这棵树是左子树还是右子树
                if (pParent.left == parent) {
                    pParent.left = subL;
                } else {
                    pParent.right = subL;
                }
            }
            subL.parent = pParent;

        }

        /**
         * 左单旋
         * @param parent
         */
        private void rotateLeft (RBTreeNode parent){
            RBTreeNode subR = parent.right;
            RBTreeNode subRL = subR.left;

            parent.right = subRL;
            subR.left = parent;
            RBTreeNode pParent = parent.parent;

            if (subRL != null) {
                subRL.parent = parent;
            }
            parent.parent = subR;

            //看看整棵树是否也是一个子树
            if (parent == root) {
                 root = subR;
                root.parent = null;
            } else {
                //是子树就确定这棵树是左子树还是右子树
                if (pParent.left == parent) {
                    pParent.left = subR;
                } else {
                    pParent.right = subR;
                }
            }
            subR.parent = pParent;
        }
}

四.红黑树验证：

1.红黑树的检测分为两步：

步骤一： 检测其是否满足二叉搜索树(中序遍历是否为有序序列）

步骤二：检测其是否满足红黑树的性质 

 

步骤一： 检测其是否满足二叉搜索树(中序遍历是否为有序序列）：

代码：

 /**1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)
     * 中序遍历：
     * @param root
     */
    public void inorder(RBTreeNode root){
        if(root == null){
            return;
        }

        inorder(root.left);
        System.out.print(root.val+ " ");
        inorder(root.right);
    }

步骤二：检测其是否满足红黑树的性质 :

//2.检测其是否满足红黑树的性质:
    public boolean isRBTree(){
        if(root == null){
            //空树也是红黑树
            return true;
        }

        if(root.color != COLOR.BLACK){
            System.out.println("违反了性质2：根节点不是黑色");
            return false;
        }


        RBTreeNode cur = root;
        //blackNum是事先计算好一边黑色节点的个数
        int blackNum = 0;
        while (cur != null){
            if (cur.color == COLOR.BLACK){
                blackNum++;
            }
            cur = cur.left;

        }
        //判断性质三有没有两个红色的节点 && 判断性质四：每条路径的黑色节点个数是否相等
        return checkRedColor(root) && checkBlackNum(root,blackNum,0);
    }

    /**
     * 判断性质三有没有两个红色的节点：
     * 思路：遍历当前二叉树节点如果是红色，则判断他的父亲节点是不是红色
     * @param root
     * @return
     */
    private boolean checkRedColor(RBTreeNode root){
        if(root == null){
            return true;
        }

        if (root.color == COLOR.RED){
            RBTreeNode parent = root.parent;
            if (parent != null && parent.color == COLOR.RED){
                System.out.println("违反了性质三: 连续出现两个红色的节点");
                return false;
            }
        }
       return checkRedColor(root.left) && checkRedColor(root.right);
    }


    /**
     *判断性质四：每条路径的黑色节点个数是否相等
     * @param root
     * @param blackNum:事先计算好黑色节点的个数
     * @param pathBlackNum：每次递归计算的黑色节点的个数
     * 思路：看 blackNum 和 pathBlackNum 的数量是否相等
     * @return
     */
    private boolean checkBlackNum(RBTreeNode root,int blackNum, int pathBlackNum){
        if(root == null){
            return true;
        }

        if (root.color == COLOR.BLACK){
            pathBlackNum++;
        }

        //blackNum 和 pathBlackNum 的数量是否相等就不满足性质
        if (root.left == null && root.right == null){
            if(pathBlackNum != blackNum){
                System.out.println("违反了性质四：每条路径的黑色节点个数不相等了！");
                return false;
            }
        }
        return checkBlackNum(root.left,blackNum,pathBlackNum)
                && checkBlackNum(root.right,blackNum,pathBlackNum);
    }

  

五.AVL树和红黑树的比较

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

 

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/875079.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

MySQL--库的操作

MySQL--库的操作

文章目录 1.创建数据库2.创建数据库案例3.字符集和校验规则3.1默认字符集3.2默认校验规则3.3查看系统默认字符集以及校验规则3.4查看数据库支持的字符3.5查看数据库支持的字符集校验规则3.6校验规则对数据库的影响不区分大小写查询&#xff1a;排序结果&#xff1a;区分大小写查…
阅读更多...
综合案例-数据可视化-地图

综合案例-数据可视化-地图

一、pyecharts—地图快速入门 假设我们要将6个地区的某种数量在地图上标注出来&#xff0c;首先导入pyecharts包内地图相关模块&#xff0c;然后准备地图数据&#xff08;数据类型是列表&#xff0c;列表的元素类型为元组&#xff09;&#xff0c;然后把准备好的数据添加进地图…
阅读更多...
51单片机个人学习笔记11（AT24C02-I2C总线）

51单片机个人学习笔记11（AT24C02-I2C总线）

前言 本篇文章属于STC89C52单片机&#xff08;以下简称单片机&#xff09;的学习笔记&#xff0c;来源于B站教学视频。下面是这位up主的视频链接。本文为个人学习笔记&#xff0c;只能做参考&#xff0c;细节方面建议观看视频&#xff0c;肯定受益匪浅。 [1-1] 课程简介_哔哩…
阅读更多...
Ubuntu查看系统用户信息

Ubuntu查看系统用户信息

0 Preface/Foreword 1 查看方式 1.1 查看系统用户 getent passwd getent: Get entries for Name Service Switch Libraries. 该命令会列出系统上所有用户的详细信息&#xff0c;包括用户名、密码、用户ID&#xff08;UID&#xff09;、组ID&#xff08;GID&#xff09;、用户描…
阅读更多...
0基础学习爬虫系列：程序打包部署

0基础学习爬虫系列：程序打包部署

1.目标 将已经写好的python代码&#xff0c;打包独立部署或运营。 2. 环境准备 1&#xff09;通义千问 &#xff1a;https://tongyi.aliyun.com/qianwen 2&#xff09;0基础学习爬虫系列–网页内容爬取&#xff1a;https://blog.csdn.net/qq_36918149/article/details/14199…
阅读更多...
Pytest-@pytest.fixture夹具篇（一）

Pytest-@pytest.fixture夹具篇（一）

一、定义 在Python的pytest测试框架中&#xff0c;pytest.fixture是一个&#xff08;不是唯一&#xff09;装饰器&#xff0c;用于定义一个测试夹具。 二、简单实例 使用参数autouserTrue pytest.fixture(autouseTrue) def my_fixture():print("Setup: 准备测试环境&q…
阅读更多...
前端框架有哪些？

前端框架有哪些？

前言 用户体验是每个开发网站的企业中的重中之重。无论后台有多方面的操作和功能&#xff0c;用户的视图和体验都必须是无缝的最友好的。这需要使用前端框架来简化交互式、以用户为中心的网站的开发。 前端框架是一种用于简化Web开发的工具&#xff0c;它提供了一套预定义的代…
阅读更多...
[环境配置]ubuntu20.04安装后wifi有图标但是搜不到热点解决方法

[环境配置]ubuntu20.04安装后wifi有图标但是搜不到热点解决方法

最近刚入手一台主机&#xff0c;暗影精灵8plus电竞主机&#xff0c;安装ubuntu后wifi怎么都搜不到热点&#xff0c;前后重装系统6次才算解决问题。这个心酸历程只有搞技术人才明白。下面介绍我解决过程。 首先主机到手后是个windows10系统&#xff0c;我用无线网连接了一下&am…
阅读更多...
基于SpringBoot+Vue+MySQL的垃圾分类回收管理系统

基于SpringBoot+Vue+MySQL的垃圾分类回收管理系统

系统展示 用户前台界面 管理员后台界面 系统背景 二十一世纪互联网的出现&#xff0c;改变了几千年以来人们的生活&#xff0c;不仅仅是生活物资的丰富&#xff0c;还有精神层次的丰富。在互联网诞生之前&#xff0c;地域位置往往是人们思想上不可跨域的鸿沟&#xff0c;信息的…
阅读更多...
Redis面试题整理

Redis面试题整理

Redis 1、Redis主从集群 1.1、搭建主从集群 单节点Redis的并发能力是有上限的&#xff0c;要进一步提高Redis的并发能力&#xff0c;就需要搭建主从集群&#xff0c;实现读写分离 1.2、主从同步原理 当主从第一次同步连接或断开重连时&#xff0c;从节点都会发送psync请求&…
阅读更多...
sass实现文字两侧横线

sass实现文字两侧横线

sass实现文字两侧横线 自我记录 mixin 的基本作用&#xff1a; 代码复用&#xff1a;把常用的样式封装在一起&#xff0c;不需要重复写相同的代码。参数化&#xff1a;可以通过参数动态生成样式&#xff0c;提高灵活性。逻辑处理&#xff1a;结合 Sass 的控制语句&#xff0…
阅读更多...
【最新华为OD机试E卷-支持在线评测】计算疫情扩散时间(200分)多语言题解-(Python/C/JavaScript/Java/Cpp)

【最新华为OD机试E卷-支持在线评测】计算疫情扩散时间(200分)多语言题解-(Python/C/JavaScript/Java/Cpp)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-E/D卷的三语言AC题解 💻 ACM金牌🏅️团队| 多次AK大厂笔试 ｜ 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 🍿 最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，…
阅读更多...
【JavaScript】LeetCode：31-35

【JavaScript】LeetCode：31-35

文章目录 31 反转链表32 回文链表33 环形链表34 环形链表Ⅱ35 合并两个有序链表 31 反转链表 初始化&#xff1a;cur head&#xff0c;pre null。pre和cur一起向前移。由于反转链表时&#xff0c;cur.next指向pre&#xff0c;导致cur在下次循环中就找不到了原来的cur.next&am…
阅读更多...
微擎忘记后台登录用户名和密码怎么办？解决方法

微擎忘记后台登录用户名和密码怎么办？解决方法

微擎忘记后台登录名和登录密码是很常见的&#xff0c;服务器百科网fwqbk.com告诉你找回后台登录用户名和密码的方法&#xff1a; 一&#xff1a;找回微擎后台用户名 &#xff08;如果只是忘记了后台登录密码&#xff0c;请忽略此步骤&#xff0c;跳转到第二步&#xff09; 通…
阅读更多...
2.ChatGPT的发展历程：从GPT-1到GPT-4（2/10）

2.ChatGPT的发展历程：从GPT-1到GPT-4（2/10）

引言 在人工智能领域&#xff0c;自然语言处理&#xff08;NLP&#xff09;是连接人类与机器的重要桥梁。随着技术的不断进步&#xff0c;我们见证了从简单的文本分析到复杂的语言理解的转变。ChatGPT&#xff0c;作为自然语言处理领域的一个里程碑&#xff0c;其发展历程不仅…
阅读更多...
C++ | Leetcode C++题解之第395题至少有K个重复字符的最长子串

C++ | Leetcode C++题解之第395题至少有K个重复字符的最长子串

题目&#xff1a; 题解&#xff1a; class Solution { public:int longestSubstring(string s, int k) {int ret 0;int n s.length();for (int t 1; t < 26; t) {int l 0, r 0;vector<int> cnt(26, 0);int tot 0;int less 0;while (r < n) {cnt[s[r] - a];…
阅读更多...
[Golang] goroutine

[Golang] goroutine

[Golang] goroutine 文章目录 [Golang] goroutine并发进程和线程协程 goroutine概述如何使用goroutine 并发 进程和线程 谈到并发&#xff0c;大多都离不开进程和线程&#xff0c;什么是进程、什么是线程&#xff1f; 进程可以这样理解&#xff1a;进程就是运行着的程序&…
阅读更多...
yolov5 +gui界面+单目测距 实现对图片视频摄像头的测距

yolov5 +gui界面+单目测距 实现对图片视频摄像头的测距

可实现对图片&#xff0c;视频&#xff0c;摄像头的检测 项目概述 本项目旨在实现一个集成了YOLOv5目标检测算法、图形用户界面&#xff08;GUI&#xff09;以及单目测距功能的系统。该系统能够对图片、视频或实时摄像头输入进行目标检测&#xff0c;并估算目标的距离。通过…
阅读更多...
基于vue框架的城市网约车管理系统v34td（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。

基于vue框架的城市网约车管理系统v34td（程序+源码+数据库+调试部署+开发环境）系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,司机,订单评价,完成订单,司机接单,打车订单 开题报告内容 基于Vue框架的城市网约车管理系统开题报告 一、研究背景与意义 1.1 研究背景 随着城市化进程的加速和互联网技术的飞速发展&#xff0c;网约车服务作为一种新兴的出行方…
阅读更多...
Java项目: 基于SpringBoot+mybatis+maven校园资料分享平台(含源码+数据库+答辩PPT+毕业论文)

Java项目: 基于SpringBoot+mybatis+maven校园资料分享平台(含源码+数据库+答辩PPT+毕业论文)

一、项目简介 本项目是一套基于SpringBootmybatismaven校园资料分享平台 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简…
阅读更多...
最新文章

Copyright @ 2022~2023