红黑树的实现

✨前言✨

📘 博客主页:to Keep博客主页
🙆欢迎关注,👍点赞,📝留言评论
⏳首发时间:2024年5月7日
📨 博主码云地址:博主码云地址
📕参考书籍:《C++ Primer》《C++编程规范》
📢编程练习:牛客网+力扣网
**由于博主目前也是处于一个学习的状态,如有讲的不对的地方,请一定联系我予以改正!!!

红黑树

  • 1 红黑树的性质
  • 2 红黑树的插入
    • 2.1 叔叔节点存在,且为红色
    • 2.2 叔叔节点不存在,或者存在为黑色节点
  • 3 具体实现
  • 4 红黑树的验证
  • 5 红黑树与AVL树之间的比较

1 红黑树的性质

1️⃣一个节点不是红节点就是黑节点
2️⃣根节点一定是黑节点
3️⃣不存在连续的红节点
4️⃣对于每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点
5️⃣每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

通过以上几点性质,我们可以知道红黑树的核心思想就是最长路径最多为最短路径的两倍,并且此时在最极端的情况下,节点全部为黑色的路径是最短的,最长的就是一黑一红交错着的!与AVL树差不多,这里我们直接给出红黑树节点的定义:

//利用枚举,来表示两种颜色
enum Colour
{RED,BLACK
};template <class K,class V>
struct RBTreeNode
{	RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Colour _col;pair<K, V> _kv;RBTreeNode(pair<K,V> kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}};

2 红黑树的插入

首先,对于新插入进来的节点是红色节点还是黑色节点!这个我们必须想清楚了,显然,要插入的新节点必须得是红色节点,如果是黑色节点,那么我们就必须在其他路径上也要新增黑色节点,这样才能保证从当前节点到叶子结点的黑色节点个数是一样的!而插入红色节点,就不需要我们考虑其他路径上黑节点是否需要新增的问题了!第二个,如何变色的呢?在红黑树中,新增的节点,其父亲节点,祖父节点的颜色是确定的,如果父亲节点是黑色的,那就不用调整颜色了。但是如果父亲的颜色是红色的,那就需要调整了,而且叔叔节点的颜色是不确定的,所以我们变色的规则就要分开来讨论了!

2.1 叔叔节点存在,且为红色

如下简图所示:
在这里插入图片描述
此时我们只需要改变颜色就可以了,将parent和uncle的颜色改为黑色节点,grandfather节点的颜色改为红色,在让cur等于grandfather,继续往上进行更新,如果grandfather是根节点,那就需要把根节点的颜色改为黑色!

2.2 叔叔节点不存在,或者存在为黑色节点

在这里插入图片描述

在这里插入图片描述
此时我们可以看到叔叔节点不存在,或者叔叔节点的颜色是黑色,此时变色解决不了问题了,那么这个时候就需要我们进行旋转加变色就可以解决问题了!这里的旋转就是我们之前AVL树那一节所学过的!只不过里面没有平衡因子的改变了,只需要旋转就行了!图中只是描述了叔叔在右边的情况,当然还有叔叔在左边的情况,左边的情况是与右边的情况是相反的!

3 具体实现

有了上述的思路,我们可以很快的实现红黑树了

bool Insert(pair<K,V> kv)
{//1 寻找要插入的位置if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = _root;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}if (cur)cur->_parent = parent;}cur = new Node(kv);if (kv.first > parent->_kv.first){parent->_right = cur;}else {parent->_left = cur;}cur->_parent = parent;//开始改变颜色while (parent && parent->_col==RED){Node* grandfather = parent->_parent;//parent节点在祖父节点的左边if (parent==grandfather->_left){//第一种情况,需要变色处理Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//第二种情况 uncle节点为空或者是黑色节点if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(parent);RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//由于根节点变成了黑色,那就不用再往上判断了break;}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){uncle->_col = BLACK;parent->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//第二种情况 uncle节点为空或者是黑色节点if (cur == parent->_left){RotateR(parent);RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}//由于根节点变成了黑色,那就不用再往上判断了break;}}}//将根节点的颜色变成黑色就行了_root->_col = BLACK;return true;}

4 红黑树的验证

1️⃣验证是否符合中序遍历是否有序
2️⃣验证是否满足红黑树的性质

注意,不可以用最长路径不超过最短路径的两倍这一思想来验证,如果你这个红黑树不满足所有性质条件,并且也满足了以上两个条件,那么这样一棵树,并不是红黑树!所以我们验证的思想就是取其中一个路径,遍历一遍,比较其他路径中黑色节点数是否与这条路径上的数量相等!判断子节点与父节点是否为联系的红色节点!具体的实现代码如下所示:

	bool IsRBTree(){if (_root == nullptr)return true;Node* tmp = _root;int Countnum = 0;while (tmp){if (tmp->_col == BLACK){Countnum++;}tmp = tmp->_left;}return check(_root,0,Countnum);}bool check(Node* root, int comparenum,int  Countnum){if (root == nullptr){if (Countnum != comparenum)return false;return true;}if (root->_col == BLACK)comparenum++;if (root->_parent)if (root->_col == RED && root->_parent->_col == root->_col)return false;return check(root->_left, comparenum, Countnum) && check(root->_right, comparenum, Countnum);}

5 红黑树与AVL树之间的比较

红黑树相比较于AVL树,树的高度会高一点,但是相差不大,可以有效的减少旋转次数!查询的时间复杂度依然是O(lgN)。红黑树的应用比AVL树的应用要广的多,例如:C++ STL库 – map/set、mutil_map/mutil_set,以及Linux内核等,底层所采用的数据结构就是红黑树!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

PMP培训一般要多久?

考过PMP很久了&#xff0c;学习时长还是记得很清楚的。因为有一部分的项目经验&#xff0c;报了威班PMP的培训&#xff0c;看了宣传是50天通过PMP&#xff0c;但是我仅仅用了一个月出头就搞定了&#xff0c;算下来才四十天不到就已经学完在准备冲刺参加考试了&#xff0c;最后5…

数字旅游以科技创新为核心竞争力:推动旅游服务的智能化、高效化,满足游客日益增长的旅游需求

一、引言 随着科技的飞速发展&#xff0c;数字旅游作为旅游业与信息技术结合的产物&#xff0c;正以其独特的魅力改变着传统旅游业的格局。科技创新作为数字旅游的核心竞争力&#xff0c;不仅推动了旅游服务的智能化、高效化&#xff0c;更满足了游客日益增长的旅游需求。本文…

了解TMS运输管理系统,实现物流高效运转

TMS运输管理系统&#xff08;Transportation Management System&#xff09;是一种集成物流和信息技术的解决方案&#xff0c;通过优化运输流程、实时跟踪货物信息和自动化管理操作&#xff0c;提高物流效率&#xff0c;降低运营成本&#xff0c;实现高效运输。 TMS运输管理系…

最常用的AI工具

在日常工作生活中&#xff0c;我试用了几十种AI人工智能工具&#xff0c;下面我来推荐下我最常使用&#xff0c;也是最方便快捷的AI工具。 1百度文心一言 文心一言是一个综合性的大语言模型&#xff0c;整合了很多优秀的提示词&#xff0c;尤其是文心4.0大模型&#xff0c;在中…

Android build.prop生成过程源码分析

Android的build.prop文件是在Android编译时刻收集的各种property【LCD density/语言/编译时间, etc.】&#xff1b;编译完成之后&#xff0c;文件生成在out/target/product/<board【OK1000】>/system/目录下&#xff1b;在Android运行时刻可以通过property_get()[c/c域] …

JAVA语言开发的(智慧校园系统源码)智慧校园的痛点、智慧校园的安全应用、智慧校园解决方案

一、智慧校园的痛点 1、信息孤岛问题&#xff1a;由于校园内各部门或系统独立开发&#xff0c;缺乏统一规划和标准&#xff0c;导致数据无法有效整合和共享&#xff0c;形成了信息孤岛。 2、技术更新与运维挑战&#xff1a;智慧校园的建设依赖于前沿的信息技术&#xff0c;如云…

Android Studio的笔记--布局文件

关于Layout布局文件的使用 LinearLayoutRelativeLayout之前文章的内容一些常见性质在android.graphics.Color中定义了12种常见的颜色常数线性布局LinearLayout 一些常见使用文本框TextView设置文本内容编辑框EditText获取文本内容按钮Button控件使用其他按钮修改图标及名称添加…

什么年代了,还在拿考勤说事

最近&#xff0c;看到了某公司的一项考勤规定&#xff1a;自然月内&#xff0c;事假累计超过3次或者累计请假时间超过8小时的&#xff0c;不予审批&#xff0c;强制休假的按旷工处理。 真的想吐槽&#xff0c;什么年代了&#xff0c;还在拿考勤说事&#xff0c;这是什么公司、什…

模拟电路设计与分析

&#x1f3ac; 秋野酱&#xff1a;《个人主页》 &#x1f525; 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 计算机工作原理存储单元 计算机工作原理 计算机最底层语言是二进制&#xff0c;和我们生活中使用的阿拉伯数字是十进制数&#x…

百度文库AI中文成语点选识别

最近百度文库又出了新验证码。在出现AI旋转验证码之后&#xff0c;又出现了AI中文成语点选。看样子验证码的未来发展路径是全面走向AI。出现这样的情况是谁都不想看到的。由于AI的随机性&#xff0c;未来识别可能会越来越难。 下图就是百度最新的AI中文成语点选的样例图 没有办…

pandas入门

pandas入门 一、pandas简介1.1 pandas介绍1.2 pandas的基本功能 二、pandas快速入门2.1 读取数据2.2 验证数据2.3 建立索引2.4 数据抽取2.4.1 选择列2.4.2 选择行2.4.3 指定行和列 2.5 排序2.6 分组聚合2.7 数据转置2.8 增加列2.9 统计分析 一、pandas简介 1.1 pandas介绍 pa…

深度学习之基于YOLOv5草莓成熟度目标检测系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 一、项目背景与意义 草莓作为一种广受欢迎的水果&#xff0c;其成熟度的判断对于保证草莓的品质和口感至关重要。然…

Redis-五大数据类型-Zset(有序集合)

五大数据类型-Zset&#xff08;有序集合&#xff09; 简介 Zset与Set非常相似&#xff0c;是一个没有重复元素的String集合。 不同之处是Zset的每个元素都关联了一个分数&#xff08;score&#xff09;&#xff0c;这个分数被用来按照从低分到高分的方式排序集合中的元素。集…

文献速递:深度学习医学影像心脏疾病检测与诊断--从SPECT/CT衰减图中深度学习冠状动脉钙化评分提高了对重大不良心脏事件的预测

Title 题目 Deep Learning Coronary Artery Calcium Scores from SPECT/CT Attenuation Maps Improve Prediction of Major Adverse Cardiac Events 从SPECT/CT衰减图中深度学习冠状动脉钙化评分提高了对重大不良心脏事件的预测 01 文献速递介绍 低剂量非门控CT衰减校正&am…

红黑树(RBTree)认识总结

一、认识红黑树 1.1 什么是红黑树&#xff1f; 红黑树是一种二叉搜索树&#xff0c;与普通搜索树不同的是&#xff0c;在每个节点上增加一个“颜色”变量 —— RED / BLACK 。 通过对各个节点颜色的限制&#xff0c;确保从 根 到 NIL &#xff0c;没有一条路径会比其他路径长出…

Golang | Leetcode Golang题解之第61题旋转链表

题目&#xff1a; 题解&#xff1a; func rotateRight(head *ListNode, k int) *ListNode {if k 0 || head nil || head.Next nil {return head}n : 1iter : headfor iter.Next ! nil {iter iter.Nextn}add : n - k%nif add n {return head}iter.Next headfor add > …

8.k8s中网络资源service

目录 一、service资源概述 二、service资源类型 1.ClusterIP类型 2.service的nodeport类型 3.service的loadbalancer类型&#xff08;了解即可&#xff09; 4.service的externalname类型&#xff08;了解即可&#xff09; 三、nodeport的端口范围设置和svc的endpoint列表 1.修…

spring高级篇(十)

1、内嵌tomcat boot框架是默认内嵌tomcat的&#xff0c;不需要手动安装和配置外部的 Servlet 容器。 简单的介绍一下tomcat服务器的构成&#xff1a; Catalina&#xff1a; Catalina 是 Tomcat 的核心组件&#xff0c;负责处理 HTTP 请求、响应以及管理 Servlet 生命周期。它包…

视频改字祝福/豪车装X系统源码/小程序uniapp前端源码

uniapp视频改字祝福小程序源码&#xff0c;全开源。创意无限&#xff01;AI视频改字祝福&#xff0c;豪车装X系统源码开源&#xff0c;打造个性化祝福视频不再难&#xff01; 想要为你的朋友或家人送上一份特别的祝福&#xff0c;让他们感受到你的真诚与关怀吗&#xff1f;现在…

Linux-信号概念

1. 什么是信号 信号本质是一种通知机制&#xff0c;用户or操作系统通过发送信号通知进程&#xff0c;进程进行后续处理 在日常生活中就有很多例子&#xff0c;比如打游戏方面王者荣耀的“进攻”&#xff0c;“撤退”&#xff0c;“请求集合”&#xff0c;“干得漂亮&#xff01…