高阶数据结构与算法——红黑树の奥秘

1.认识红黑树

1.1红黑树的概念

红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表⽰结点的颜⾊，可以是红⾊或者⿊⾊。通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的

1.2红黑树的规则

1. 每个结点不是红⾊就是⿊⾊

2. 根结点是⿊⾊的

3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点

4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点

1.2红黑树的效率:O(logN)

红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控制了平衡。红⿊树通过4条规则的颜 ⾊约束，间接的实现了近似平衡，他们效率都是同⼀档次，但是相对⽽⾔，插⼊相同数量的结点，红⿊树的旋转次数是更少的，因为他对平衡的控制没那么严格

2.红黑树的实现

2.1红黑树的基本框架

enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K,V>* _left;RBTreeNode<K,V>* _right;RBTreeNode<K,V>* _parent;Colour _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:
private:Node* _root = nullptr;
};

2.2红黑树的插入

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊，插⼊后我们只需要观察是否符合红⿊树的4条规则

2. 如果是空树插⼊，新增结点是⿊⾊结点。如果是⾮空树插⼊，新增结点必须红⾊结点，因为⾮空树插⼊，新增⿊⾊结点就破坏了规则4，规则4是很难维护的

3. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是⿊⾊的，则没有违反任何规则，插⼊结束

4. ⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3。进⼀步分析，c是红⾊，p为红，g必为⿊，这三个颜⾊都固定了，关键的变化看u的情况，需要根据u分为以下⼏种 情况分别处理。 说明：下图中假设我们把新增结点标识为c(cur)，c的⽗亲标识为p(parent)，p的⽗亲标识为 g(grandfather)，p的兄弟标识为u（uncle）   

2.2.1变色

c为红，p为红，g为⿊，u存在且为红，则将p和u变⿊，g变红。在把g当做新的c，继续往上更新分析：因为p和u都是红⾊，g是⿊⾊，把p和u变⿊，左边⼦树路径各增加⼀个⿊⾊结点，g再变红，相 当于保持g所在⼦树的⿊⾊结点的数量不变，同时解决了c和p连续红⾊结点的问题，需要继续往上更新是因为，g是红⾊，如果g的⽗亲还是红⾊，那么就还需要继续处理；如果g的⽗亲是⿊⾊，则处理结束了；如果g就是整棵树的根，再把g变回⿊⾊

2.2.2变色+单旋

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。 分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊

如果p是g的左，c是p的左，那么以g为旋转点进⾏右单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则

如果p是g的右，c是p的右，那么以g为旋转点进⾏左单旋，再把p变⿊，g变红即可。p变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为p的⽗亲是⿊⾊还是红⾊或者空都不违反规则

2.2.3变色+双旋

c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，则c⼀定是新增结点，u存在且为⿊，则 c⼀定不是新增，c之前是⿊⾊的，是在c的⼦树中插⼊，符合情况1，变⾊将c从⿊⾊变成红⾊，更新上来的。 分析：p必须变⿊，才能解决，连续红⾊结点的问题，u不存在或者是⿊⾊的，这⾥单纯的变⾊⽆法解决问题，需要旋转+变⾊

如果p是g的左，c是p的右，那么先以p为旋转点进⾏左单旋，再以g为旋转点进⾏右单旋，再把c变 ⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则

如果p是g的右，c是p的左，那么先以p为旋转点进⾏右单旋，再以g为旋转点进⾏左单旋，再把c变⿊，g变红即可。c变成课这颗树新的根，这样⼦树⿊⾊结点的数量不变，没有连续的红⾊结点了，且不需要往上更新，因为c的⽗亲是⿊⾊还是红⾊或者空都不违反规则

2.3验证一棵树是否为红黑树

规则1：枚举颜⾊类型，天然实现保证了颜⾊不是⿊⾊就是红⾊。

规则2：直接检查根即可

规则3：前序遍历检查，遇到红⾊结点查孩⼦不太⽅便，因为孩⼦有两个，且不⼀定存在，反过来检 查⽗亲的颜⾊就⽅便多了。

规则4：前序遍历，遍历过程中⽤形参记录跟到当前结点的blackNum(⿊⾊结点数量)，前序遍历遇到 ⿊⾊结点就++blackNum，⾛到空就计算出了⼀条路径的⿊⾊结点数量。再任意⼀条路径⿊⾊结点数量作为参考值，依次⽐较即可 

bool Check(Node* root, int blacknum, const int retnum)
{if (root == nullptr){if (blacknum != retnum){cout << "有路径的黑色节点个数与其他路径不相同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, retnum)&& Check(root->_right, blacknum, retnum);
}
bool IsBalance()
{if (_root == nullptr){return true;}if (_root->_col == BLACK){return false;}int retnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){retnum++;}cur = cur->_left;}return Check(_root, 0, retnum);
}

所有代码如下 

#pragma once
#include<iostream>enum Colour
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K,V>* _left;RBTreeNode<K,V>* _right;RBTreeNode<K,V>* _parent;Colour _col;RBTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr){}
};template<class K,class V>
class RBTree
{typedef RBTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv){if (_root == nullptr){//根节点为黑色节点_root = new Node(kv);_root->_col = BLACK;return true;}Node* parent = nullptr;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;}}cur = new Node(kv);cur->_col = RED;if (cur->_parent.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//当父节点存在且是红色while (parent && parent->_col == RED){//当父节点为爷爷节点的左节点//     g//   p    uNode* grandfather = parent->_parent;if (parent == grandfather->_left){//当叔叔节点存在且也为红色，则将父节点与叔叔节点均置为红色//将爷爷节点置为黑色，然后向上依次处理Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}//叔叔节点不存在或者叔叔节点为黑色//需要旋转+变色else{//    g//  p    u//c//新增节点在父节点左边if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;//    p//c       g//            u}//    g//  p    u//    celse{RotateL(parent);//     g//   c    u//pRotateR(grandfather);//     c//  p      g//             ugrandfather->_col = RED;cur->_col = BLACK;}break;}}//父节点在爷爷节点的右边//      g//   u      pelse{//当叔叔节点存在且为红色Node* uncle = grandfather->_left;if (uncle && uncle->_col == RED){//将叔叔节点与父亲节点置为黑色，爷爷节点置为红色uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//向上处理cur = grandfather;parent = cur->_parent;}//当叔叔节点不存在或者存在但为黑色else{//     g// u       p//             cif (cur == parent->_right){RorateL(grandfather);//左旋//      p//   g     c//uparent->_col = BLACK;grandfather->_col = RED;}//     g// u       p//      celse{//右旋RotateR(parent);//   g//u     c//         p//左旋RotateL(grandfather);//     c//   g    p//ugrandfather->_col = RED;cur->_col = BLACK;}break;}}}_root->_col = BLACK;return true;}//右单旋void RotateR(Node* parent){//subL代表根节点的左子树,subLR则代表该左子树的右子树Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;//避免访问空节点if (subLR){subLR->_parent = parent;}//如果传入的根节点是一个子树的根节点则需要将旋转后的根节点重新接入原来的节点Node* pParent = parent->_parent;//换根,将原来根节点的左节点换为根节点subL->_right = parent;parent->_parent = subL;if (pParent == nullptr){_root = subL;//根节点的父亲节点为空subL->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}//重新接入原来的节点subL->_parent = pParent;}}//左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* pParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (pParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}subR->_parent = pParent;}}bool IsBalance(){if (_root == nullptr){return true;}if (_root->_col == BLACK){return false;}int retnum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK){retnum++;}cur = cur->_left;}return Check(_root, 0, retnum);}
private:bool Check(Node* root, int blacknum, const int retnum){if (root == nullptr){if (blacknum != retnum){cout << "有路径的黑色节点个数与其他路径不相同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blacknum++;}return Check(root->_left, blacknum, retnum)&& Check(root->_right, blacknum, retnum);}
private:Node* _root = nullptr;
};

 

 

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

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

相关文章

“我们为什么缺少科学精神”演讲内容拆解

“我们为什么缺少科学精神”演讲内容拆解

演讲人张双南&#xff0c;视频链接&#xff1a; https://tv.cctv.com/2017/04/23/VIDEdqzdpmxStYXAmYBdgDP7170423.shtml
阅读更多...
PicGo+Gitee搭建Typora图床

PicGo+Gitee搭建Typora图床

PicGoGitee搭建Typora图床 下载PicGo 下载链接&#xff1a;https://picgo.github.io/PicGo-Doc/zh/guide/#%E4%B8%8B%E8%BD%BD%E5%AE%89%E8%A3%85 配置PicGo 插件安装 在PicGo的【插件设置】中搜索gitee-uploader插件并安装 在【图床设置】下配置Gitee repo&#xff1a;用…
阅读更多...
车载 3D 地图如何从技术上实现渲染品质的全面提升？

车载 3D 地图如何从技术上实现渲染品质的全面提升？

随着汽车由单纯的交通工具、“硬件为主”的工业产品向智能化终端、“第三空间”转变。3D HMI 已成为整车厂打造极致沉浸感与数字豪华感的“标配”。实时光影、昼夜交替、天气变化、地面反射、动态植被……高沉浸感、自然交互的 3D 地图为驾驶者营造身临其境的视觉享受&#xff…
阅读更多...
VMware免安装直接使用Win7成品虚拟机

VMware免安装直接使用Win7成品虚拟机

VM虚拟机免安装直接使用Win7 下载文件 Win7成品虚拟机下载 ⏬下载链接⏬ 下载链接 使用虚拟机打开成品虚拟机
阅读更多...
【前端】制作属于自己的网页（1）

【前端】制作属于自己的网页（1）

好的&#xff01;你可以使用以下的HTML代码创建一个简单的网页&#xff0c;标题为“第一个网页”&#xff1a; html <!DOCTYPE html> <html lang"zh"> <head> <meta charset"UTF-8"> <meta name"viewport" conten…
阅读更多...
动态网站及爬虫技术应用（题目）

动态网站及爬虫技术应用（题目）

/*T26:HTTP响应消息的状态代码为500时表示&#xff08; &#xff09;: HTTP响应消息的状态代码为500时表示服务器内部错误&#xff08;Internal Server Error&#xff09;。这通常意味着服务器在处理请求时遇到了意外的情况&#xff0c;导致无法完成该请求。这种错误可能是由于…
阅读更多...
Linux--多路转接之epoll

Linux--多路转接之epoll

上一篇:Linux–多路转接之select epoll epoll 是 Linux 下多路复用 I/O 接口 select/poll 的增强版本&#xff0c;它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统 CPU 利用率。它是 Linux 下多路复用 API 的一个选择&#xff0c;相比 select 和 poll&#xff0c…
阅读更多...
Linux性能调优，还可以从这些方面入手

Linux性能调优，还可以从这些方面入手

linux是目前最常用的操作系统&#xff0c;下面是一些常见的 Linux 系统调优技巧&#xff0c;在进行系统调优时&#xff0c;需要根据具体的系统负载和应用需求进行调整&#xff0c;并进行充分的测试和监控&#xff0c;以确保系统的稳定性和性能。同时&#xff0c;调优过程中要谨…
阅读更多...
【云原生技术】Docker容器进阶知识

【云原生技术】Docker容器进阶知识

文章目录 namespace概述一、namespace的基本概念二、namespace的主要作用三、namespace的类型四、namespace的操作五、namespace在容器技术中的应用 cgroup一、cgroup的基本概念二、cgroup的主要功能三、cgroup的子系统介绍四、cgroup的应用场景五、cgroup的使用与管理 cgroup和…
阅读更多...
.ts文件编译为.js文件

.ts文件编译为.js文件

.ts文件如何编译为.js文件 首先安装了tsc $ npm install -g typescript可以使用如下命令检查是否安装tsc,出现版本号则说明安装成功 tsc -v创建.ts文件 创建 1.ts&#xff0c;编写代码如下&#xff1a; function test(a:string):string{return a }编译为.js文件 执行如下…
阅读更多...
Spring Cloud环境搭建

Spring Cloud环境搭建

一.开发环境推荐 JDK建议使用JDK17。 因为SpringCloud是基于SpringBoot进行开发的&#xff0c;SpringBoot3.X以下的版本&#xff0c;Spring官方已经不再维护了&#xff08;还可以继续使用&#xff09;&#xff0c;SpringBoot3.X的版本使用的JDK版本基线是17&#xff0c;而且1…
阅读更多...
IPv 4

IPv 4

IP协议 网络层主要由IP&#xff08;网际协议&#xff09;和ICMP&#xff08;控制报文协议&#xff09;构成&#xff0c;对应OSI中的网络层&#xff0c;网络层以实现逻辑层面点对点通信为目的。目前应用最广泛的IP协议为IPv4 基本概念给出 主机&#xff1a;配有IP地址但不具有路…
阅读更多...
live2d 实时虚拟数字人形象页面显示，对接大模型

live2d 实时虚拟数字人形象页面显示，对接大模型

live2dSpeek 测试不用gpu可以正常运行 https://github.com/lyz1810/live2dSpeek 运行的话还需要额外下载https://github.com/lyz1810/edge-tts支持语音 ## 运行live2dSpeek >npm install -g http-server >http-server . ## 运行edge-tts python edge-tts.py
阅读更多...
SpringMVC(看这一篇就够了)

SpringMVC(看这一篇就够了)

目录&#xff1a; SpringMVC什么是MVC模型SpringMVC案例SpringMVC执行流程SpringMVC封装参数简单数据类型简单对象关联对象简单数据类型集合Map集合参数类型转换器编码过滤器Servlet原生对象 SpringMVC处理响应视图解析器返回值为void返回值为ModelAndView向request域设置数据向…
阅读更多...
止步阿里一面。。。

止步阿里一面。。。

时间过的真快&#xff0c;转眼间国庆已经过去一周了&#xff0c;又到了新的一周&#xff0c;继续分享最新的面经。 今天分享的是粉丝在阿里巴巴的一面&#xff0c;考察了数据库、redis、kafka、ES和项目&#xff0c;数据库和redis不用多说&#xff0c;项目必用面试必考&#x…
阅读更多...
【Python时序数据系列】基于LSTM模型实现时序数据二分类（案例+源码）

【Python时序数据系列】基于LSTM模型实现时序数据二分类（案例+源码）

这是我的第366篇原创文章。 一、引言 前面我介绍了单变量时序预测和多变量时序预测&#xff0c;都是回归任务。 相关链接&#xff1a; 时序预测系列文章 本文将介绍时序分类任务-基于LSTM模型进行时序数据二分类。 二、实现过程 2.1 准备数据 df1 pd.read_table("t…
阅读更多...
python yolov8半自动标注

python yolov8半自动标注

首先标注一部分图片&#xff0c;进行训练&#xff0c;生成模型&#xff0c;标注文件为xml方便后面统一做处理。 1、标注数据&#xff08;文件为xml, 转为txt用于训练&#xff0c;保留xml标签文件&#xff09; 2、模型训练&#xff08;训练配置、训练代码、&#xff09; 3、使用…
阅读更多...
ShardingJDBC分库分表实战

ShardingJDBC分库分表实战

目录 一、第一个分库分表的案例 1、快速搭建基础JDBC应用 2、引入ShardingJDBC快速实现分库分表 二、理解分库分表的核心概念 1、ShardingSphere分库分表的核心概念 2、垂直分片和水平分片 三、ShardingJDBC常见数据分片策略实战 1、INLINE简单分片 2、STANDARD标准分片…
阅读更多...
ubuntu下实时查看CPU，内存（Mem）和GPU的利用率

ubuntu下实时查看CPU，内存（Mem）和GPU的利用率

一、实时查看CPU和内存&#xff08;Mem&#xff09;利用率 htop官网&#xff1a;htop - an interactive process viewer sudo apt-get install htop htop ①. 顶部状态栏&#xff08;System Metrics Overview&#xff09; 这个区域显示系统的全局资源使用情况&#xff0c;包括…
阅读更多...
深入解析 Harris 角点检测算法：从孔径问题到响应函数的完整推导

深入解析 Harris 角点检测算法：从孔径问题到响应函数的完整推导

在图像处理中&#xff0c;角点是非常重要的特征。为了快速、准确地检测角点&#xff0c;Harris 提出了 Harris 角点检测算法&#xff0c;它基于局部窗口内图像梯度的变化来判断角点。本文将从最基础的孔径问题&#xff08;Aperture Problem&#xff09;入手&#xff0c;通过泰勒…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023