[数据结构]红黑树，详细图解插入

目录

一、红黑树的概念

二、红黑树的性质

三、红黑树节点的定义

四、红黑树的插入（步骤）

1.为什么新插入的节点必须给红色？

2、插入红色节点后，判定红黑树性质是否被破坏

五、插入出现连续红节点情况分析+图解（看uncle节点）

5.1、uncle存在且为红

5.2、uncle不存在

1、单旋

2、双旋

5.3、uncle存在且为黑

1、单旋

2、双旋

六、插入总结

1、红黑树插入的两种步骤

 2、插入代码

七、红黑树总结及代码

一、红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，

红黑树确保——没有一条路径会比其他路径长出两倍，因而是接近平衡的

二、红黑树的性质

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

2. 根节点是黑色的 

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

4. 从任一结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点 

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

        最优情况：全黑或每条路径都是一黑一红的满二叉树，高度logN

        最差情况：每颗子树左子树全黑，右子树一黑一红。高度2*logN。

        可以发现，最坏情况的时间复杂度和AVL树一样，都是O(logN)，但是红黑树这种近似平衡的结构减少了大量旋转，综合性能优于AVL树。

三、红黑树节点的定义

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

四、红黑树的插入（步骤）

1.为什么新插入的节点必须给红色？

（1）新节点给红色，可能出现连续红节点

（2）如果新节点给黑色，必定会违反性质4（其每条路径的黑色节点数量相同）

2、插入红色节点后，判定红黑树性质是否被破坏

因为新节点的默认颜色是红色，所以

（1）双亲节点的颜色是黑色，没有违反红黑树任何 性质，则不需要调整；

（2）双亲节点为红色，就会出现连续的红节点，此时需要对红黑树分情况来讨论：见下一部分

五、插入出现连续红节点情况分析+图解（看uncle节点）

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

下面的分析都是以p为g的左孩子为例

5.1、uncle存在且为红

cur插入后，p和u变黑，g变红

（1）g没有父亲，g为根，g变黑

（2）g有父亲。其为黑，结束；其为红，后把g当成cur，继续向上调整

5.2、uncle不存在

u不存在，则cur一定是新插入的节点。

（如果cur不是新插入的节点，则cur和p一定有一个节点是黑色，否则每条路径黑色节点不相同）

下图为解释：

1、单旋

右单旋

2、双旋

 左单旋 + 右单旋 

5.3、uncle存在且为黑

uncle存在且为黑，是情况一变来的，所以cur原来的节点一定是黑色的。

现在其是红色的原因是，cur的子树在调整过程中将cur的颜色由黑变红。

1、单旋

右单旋

2、双旋

左单旋 + 右单旋

六、插入总结

1、红黑树插入的两种步骤

1、uncle存在且为红

2、uncle不存在 或者 uncle存在且为黑

通过分析，

uncle不存在的单旋 和 uncle存在且为黑的单旋 可以写在一起，

uncle不存在的双旋 和 uncle存在且为黑的双旋 可以写在一起，

不论uncle存在或者不存在，都不影响此步的单旋或者双旋。

当p为g的右孩子时，操作都相反。

详细步骤见其中while (parent && parent->_col == RED)这一步。

 2、插入代码

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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//p为g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况1：u存在且为红 if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//情况2.1 ， 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p为g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;
}

七、红黑树总结及代码

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

using namespace std;enum Colour
{RED,BLACK
};template<class K, class V>
struct RBTreeNode
{RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;pair<K, V> _kv;Colour _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}};template<class K, class V>
struct 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->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent && parent->_col == RED){Node* grandfather = parent->_parent;//p为g左孩子if (parent == grandfather->_left){Node* uncle = grandfather->_right;// 情况1：u存在且为红 if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{//情况2.1 ， 3.1if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//情况2.2 , 3.2{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}//p为g右孩子else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)return false;return true;}if (root->_col == BLACK){++blacknum;}if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

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

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

相关文章

java练习（28）

java练习（28）

ps&#xff1a;练习来自力扣 给定一个二叉树&#xff0c;判断它是否是平衡二叉树 // 定义二叉树节点类 class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.va…
阅读更多...
Java并发编程6--重排序

Java并发编程6--重排序

重排序是指 编译 器和 处 理器 为 了 优 化程序性能而 对 指令序列 进 行重新排序的一种手段。 1.数据依赖性 如果两个操作 访问 同一个 变 量&#xff0c;且 这 两个操作中有一个 为 写操作&#xff0c;此 时这 两个操作之 间就存在数据 依赖性。 数据依赖的类型 上面 3 种情…
阅读更多...
ElasticSearch映射分词

ElasticSearch映射分词

目录 弃用Type why 映射 查询 mapping of index 创建 index with mapping 添加 field with mapping 数据迁移 1.新建 一个 index with correct mapping 2.数据迁移 reindex data into that index 分词 POST _analyze 自定义词库 ik分词器 circuit_breaking_excep…
阅读更多...
Python 面向对象的三大特征

Python 面向对象的三大特征

前言&#xff1a;本篇讲解面向对象的三大特征&#xff08;封装&#xff0c;继承&#xff0c;多态&#xff09;&#xff0c;还有比较细致的&#xff08;类属性类方法&#xff0c;静态方法&#xff09;&#xff0c;分步骤讲解&#xff0c;比较适合理清楚三大特征的思路 面向对象的…
阅读更多...
deepseek多列数据对比，联想到excel的高级筛选功能

deepseek多列数据对比，联想到excel的高级筛选功能

目录 1 业务背景 ​2 deepseek提示词输入 ​3 联想分析 4 EXCEL高级搜索 1 业务背景 系统上线的时候经常会遇到一个问题&#xff0c;系统导入的数据和线下的EXCEL数据是否一致&#xff0c;如果不一致&#xff0c;如何快速找到差异值&#xff0c;原来脑海第一反应就是使用公…
阅读更多...
俄罗斯方块游戏完整代码示例

俄罗斯方块游戏完整代码示例

以下是一个基于Cocos Creator引擎开发的俄罗斯方块游戏的完整代码示例。该游戏实现了俄罗斯方块的基本功能&#xff0c;并且代码整合在单个文件中&#xff0c;无需任何外部依赖&#xff0c;可以直接在浏览器中运行。 1. 创建Cocos Creator项目 首先&#xff0c;确保你已经安装了…
阅读更多...
java后端开发day16--字符串（二）

java后端开发day16--字符串（二）

&#xff08;以下内容全部来自上述课程&#xff09; 1.StringBuilder 因为StringBuilder是Java已经写好的类。 java在底层对他进行了一些特殊处理。 打印对象不是地址值而是属性值。 1.概述 StringBuilder可以看成是一个容器&#xff0c;创建之后里面的内容是可变的。 作用…
阅读更多...
【AI实践】deepseek支持升级git

【AI实践】deepseek支持升级git

当前Windows 11 WSL的git是2.17&#xff0c;Android Studio提示需要升级到2.19版本 网上找到指导文章 安装git 2.19.2 cd /usr/src wget https://www.kernel.org/pub/software/scm/git/git-2.19.2.tar.gz tar xzf git-2.19.2.tar.gz cd git-2.19.2 make prefix/usr/l…
阅读更多...
从零复现R1之路[3/3]：一文速览Open R1——对DeepSeek R1训练流程前两个阶段的复现(SFT和GRPO训练)

从零复现R1之路[3/3]：一文速览Open R1——对DeepSeek R1训练流程前两个阶段的复现(SFT和GRPO训练)

前言 根据R1的GitHub可知 类别开源内容未开源内容模型权重R1、R1-Zero 及蒸馏模型权重&#xff08;MIT 协议&#xff09;原始训练数据 未公开冷启动数据、RL 训练数据集或合成数据的具体内容&#xff0c;仅提供依赖的公开数据集名称&#xff08;如 AI-MO、NuminaMath-TIR&…
阅读更多...
大语言模型简史：从Transformer（2017）到DeepSeek-R1（2025）的进化之路

大语言模型简史：从Transformer（2017）到DeepSeek-R1（2025）的进化之路

2025年初&#xff0c;中国推出了具有开创性且高性价比的「大型语言模型」&#xff08;Large Language Model — LLM&#xff09;DeepSeek-R1&#xff0c;引发了AI的巨大变革。本文回顾了LLM的发展历程&#xff0c;起点是2017年革命性的Transformer架构&#xff0c;该架构通过「…
阅读更多...
在线考试系统(代码+数据库+LW)

在线考试系统(代码+数据库+LW)

摘 要 使用旧方法对在线考试系统的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在在线考试系统的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误不能及时纠正等问题。这次开发的在线考试…
阅读更多...
2025百度快排技术分析：模拟点击与发包算法的背后原理

2025百度快排技术分析：模拟点击与发包算法的背后原理

一晃做SEO已经15年了&#xff0c;2025年还有人问我如何做百度快速排名&#xff0c;我能给出的答案就是&#xff1a;做好内容的前提下&#xff0c;多刷刷吧&#xff01;百度的SEO排名算法一直是众多SEO从业者研究的重点&#xff0c;模拟算法、点击算法和发包算法是百度快速排名的…
阅读更多...
【Spring+MyBatis】留言墙的实现

【Spring+MyBatis】留言墙的实现

目录 1. 添加依赖 2. 配置数据库 2.1 创建数据库与数据表 2.2 创建与数据库对应的实体类 3. 后端代码 3.1 目录结构 3.2 MessageController类 3.3 MessageService类 3.4 MessageMapper接口 4. 前端代码 5. 单元测试 5.1 后端接口测试 5.2 使用前端页面测试 在Spri…
阅读更多...
EtherNet/IP转Modbus TCP：新能源风电监控与分析实用案例

EtherNet/IP转Modbus TCP：新能源风电监控与分析实用案例

EtherNet/IP转Modbus TCP&#xff1a;新能源风电监控与分析实用案例 一、案例背景 在某新能源汽车电池生产线上&#xff0c;需要将采用EtherNet/IP协议的电池检测设备与采用ProfiNet协议的生产线控制系统进行集成&#xff0c;以实现对电池生产过程的全面监控和数据采集。 二、…
阅读更多...
管理WSL实例 以及安装 Ubuntu 作为 WSL 子系统 流程

管理WSL实例 以及安装 Ubuntu 作为 WSL 子系统 流程

安装ubuntu wsl --install -d Ubuntu分类命令说明安装相关wsl --install在 Windows 10/11 上以管理员身份在 PowerShell 中运行此命令&#xff0c;可安装 WSLwsl --install -d <distribution name>在 PowerShell 中使用此命令安装特定版本的 Linux 发行版&#xff0c;如…
阅读更多...
Spring框架中都用到了哪些设计模式？

Spring框架中都用到了哪些设计模式？

大家好&#xff0c;我是锋哥。今天分享关于【Spring框架中都用到了哪些设计模式&#xff1f;】面试题。希望对大家有帮助&#xff1b; Spring框架中都用到了哪些设计模式&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 Spring框架中使用了大量的设计模…
阅读更多...
最新VS code配置C/C++环境(tasks.json, launch.json,c_cpp_properties.json)及运行多个文件、配置Cmake

最新VS code配置C/C++环境(tasks.json, launch.json,c_cpp_properties.json)及运行多个文件、配置Cmake

目录 一、VScode配置C/C环境&#xff0c;需设置tasks.json, launch.json文件 二、安装C/C扩展&#xff0c;配置tasks.json、launch.json、c_cpp_properties.json文件 (1)安装c/c扩展 (2)配置tasks.json文件 (3)配置launch.json文件 (4)配置中的参数(属性)说明 (5)运行程序(运行…
阅读更多...
Java零基础入门笔记：(3)程序控制

Java零基础入门笔记：(3)程序控制

前言 本笔记是学习狂神的java教程&#xff0c;建议配合视频&#xff0c;学习体验更佳。 【狂神说Java】Java零基础学习视频通俗易懂_哔哩哔哩_bilibili Scanner对象 之前我们学的基本语法中我们并没有实现程序和人的交互&#xff0c;但是Java给我们提供了这样一个工具类&…
阅读更多...
Spring Boot 原理分析

Spring Boot 原理分析

spring-boot.version&#xff1a;2.4.3.RELEASE Spring Boot 依赖管理 spring-boot-starter-parent 配置文件管理 <resources> <resource> <directory>${basedir}/src/main/resources</directory> <filtering>true&l…
阅读更多...
Word中接入大模型教程

Word中接入大模型教程

前言 为什么要在word中接入大模型呢&#xff1f; 个人觉得最大的意义就是不用来回切换与复制粘贴了吧。 今天分享一下昨天实践的在word中接入大模型的教程。 在word中接入大模型最简单的方式就是使用vba。 vba代码要做的事&#xff0c;拆分一下就是&#xff1a; 获取用户…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023