《红黑树的原理与C++实现：详解平衡艺术的高效构建与操作》

前引：高效的数据结构是算法性能优化的关键。红黑树作为一种自平衡二叉搜索树，以其稳定的性能广泛应用于各类系统，如数据库索引、内存管理和高级语言的标准库 红黑树通过一组严格的规则确保树的高度始终保持在对数级别，从而保证搜索、插入和删除操作的时间复杂度为 O(log n)本文将深入探讨红黑树的核心性质、平衡调整策略以及实际实现，帮助读者全面理解这一经典数据结构的设计哲学和工程价值！无论是初学者还是有经验的开发者，掌握红黑树不仅能提升算法能力，还能优化高性能系统的设计。通过此篇，让你拿捏红黑树！此篇文章没有省略代码！皆在顺利的梳理逻辑！

目录

【一】红黑树介绍

【二】性质解析

【三】实现疑惑讲解

【四】红黑树节点结构

【五】insert插入

（1）uncle存在且为红

（2）uncle存在且为黑

（3）uncle不存在

旋转代码

（1）单左旋

（2）单右旋

（3）左右双旋

（4）右左双旋

【六】测试

【一】红黑树介绍

红黑树是一种自平衡的二叉搜索树，每个节点额外维护一个存储位表示颜色（红色或黑色）。通过对节点颜色的约束，红黑树确保树的高度近似平衡，从而保证基本操作（查找、插入、删除）的时间复杂度稳定在 O(logn)！

【二】性质解析

（1）每个节点不是红色就是黑色

理解：红黑树的每个节点都有颜色属性：红和黑。不允许出现其它颜色情况

（2）根节点是黑色的

理解：整棵红黑树的根节点必须是黑色

（3）如果一个节点是红色，则它的两个子节点必须是黑色的

理解：红父黑子，不能出现两个节点连续红色的情况

（4）每个节点到其所有后代叶子节点的简单路径上，包含相同数量的黑色节点（重要）

  • 简单路径​：树中不重复经过节点的路径（从当前节点到任意叶子节点的路径唯一）
  • ​黑高（记作 bh(x)​​：从节点 x 出发（不包含 x 自身），到其任意一个叶子节点（NIL节点）的简单路径上，​黑色节点的数量
  • 例如：（1）比如50：从50开始（不算50）到所有它的叶子结点路径，都是2个黑节点               （2）比如60：从60开始（不算60）到所有它的叶子结点路径上，都是2个黑节点

（5）每个叶子节点都是黑色的

理解：红黑树的叶子节点通常定义为 NIL（空节点），即使实际树中不画，需视为黑色节点

【三】实现疑惑讲解

理解：红黑树包含了之前的AVL树的四大旋转，它没有像AVL树那样严格的平衡，仅要求：最长路径不超过最短路径的两倍即可。插入节点是根据大小选择性的走左还是走右，我们是无法控制插入位置的，那么如何保证插入节点后依然属于红黑树？

节点命名：红黑树的实现我们需要借助四个逻辑关系节点来完成一系列操作 

根据性质我们知道：插入红色节点是不会去影响它的黑高的，而不能有连续的红节点，因此必然需要改变某个节点的颜色为黑色，而改为黑色后，该条路径就多了一个黑节点，为了平衡，我们需要将对称的红色节点改为黑色，例如：

为什么不去改变刚插入节点？因为插入的节点此时是树的底层，如果将这个节点改为黑色，那左右两边还没有节点，如何去调整平衡？同时红色节点是不会影响树的黑高的！

如果出现这种调色不能解决的，那我们只能旋转，例如：新插入的节点需要将uncle和parent变为黑，那么再上一个节点就要变为红，继续向上更新，但此时不满足最短路径与最长路径的倍数关系，需要旋转再变色，例如：

【四】红黑树节点结构

与AVL树类似，只将里面的平衡因子blance替换成了颜色（枚举）

//枚举
enum color
{Red,Black
};
//节点结构
template<class T,class V>
struct R_B_Node
{R_B_Node(const pair<T, V> date):_date(date),_parent(nullptr),_left(nullptr),_right(nullptr),_co(Red){ }//数据pair<T, V> _date;//节点R_B_Node<T, V>* _parent;R_B_Node<T, V>* _left;R_B_Node<T, V>* _right;//颜色enum color _co;
};

【五】insert插入

首先我们需要先找到那个插入位置：如果是根（颜色为黑）；如果是其它节点（颜色为红）

//如果是根节点
if (root == nullptr)
{root = new Node(date);root->_co = Black;return true;
}
//找插入位置
Node* cur = root;
Node* parent = nullptr;
while (cur)
{//如果插入的数据小于父节点，走左边否则走右边parent = cur;if (cur->_date.first > date.first){cur = cur->left;}else if (cur->_date.first < date.first){cur = cur->_right;}else{//如果数据相等，不符合唯一性return false;}
}
//插入+连接节点
cur = new Node(date);
if (parent->_date.first < date.first)
{parent->_right = cur;
}
else
{parent->_left = cur;
}
cur->_parent = parent;

下面是红黑树的重点！仅需记住三大调整方向！以整棵右子树为例（完整版：左子树+右子树）

（1）uncle存在且为红

判断条件：uncle存在且为红

调整方法：仅需变色parent和uncle变为黑，grandfather变为红，然后向上继续调整，cur变为grandfather的位置

代码参考： 

parent->_co = Black;
uncle->_co = Black;
grandfather->_co = Red;
//如果grandfather为根节点，则设为黑色；否则向上调整
if (grandfather == root)
{grandfather->_co = Black;return true;
}
else
{cur = grandfather;parent = cur->_parent;grandfather = parent->_parent;
}
（2）uncle存在且为黑

判断条件：uncle存在且为黑

调整方法：根据cur的位置判断是单左旋还是右左双旋（旋转的本质：将与uncle冲突的parent的这个红色节点变为黑色，左右两个节点变为红色）

例如单左旋：

代码参考： 

if (uncle && uncle->_co == Black)
{//旋转+变色if (cur == parent->_right){//单左旋Whirl_L(grandfather);}else{//右左双旋Whirl_R_L(grandfather);}
}
（3）uncle不存在

判断条件：uncle不存在

调整方法：根据cur的位置选择左旋转还是右左双旋，将grandfather变为红色，parent变为黑色（旋转的本质：将中间节点变为黑色，左右两个节点变为红色）

代码参考：

//旋转+变色
if (cur == parent->_left)
{//左旋Whirl_L(grandfather);
}
else
{//右左双旋Whirl_R_L(grandfather);
}
旋转代码
（1）单左旋
//左旋
void Whirl_L(Node* parent)
{Node* cur = parent->_right;Node* ppnode = parent->_parent;Node* curleft = cur->_left;//连接parent和curcur->_left = parent;parent->_parent = cur;//连接curleft和parentparent->_right = curleft;if (curleft){curleft->_parent = parent;}//连接ppnode和curif (ppnode){cur->_parent = ppnode;if (ppnode->_left = parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}else{root = cur;cur->_parent = nullptr;}//更新颜色cur->_co = Black;parent->_co = Red;
}
（2）单右旋
//右旋
void Whirl_R(Node* parent)
{Node* cur = parent->_left;Node* ppnode = parent->_parent;Node* curright = cur->_right;//连接parent和curcur->_right = parent;parent->_parent = cur;//连接curright和parentparent->_left = curright;if (curright){curright->_parent = parent;}//连接ppnode和curif (ppnode){cur->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}else{root = cur;cur->_parent = nullptr;}//更新颜色parent->_co = Red;cur->_co = Black;
}
（3）左右双旋
//左右双旋
void Whirl_L_R(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;//左旋Whirl_L(cur);//右旋Whirl_R(parent);//更新颜色cur->_co = Red;parent->_co = Red;curright->_co = Black;
}
（4）右左双旋
//右左双旋
void Whirl_R_L(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;//右旋Whirl_R(cur);//左旋Whirl_L(parent);//更新颜色cur->_co = Red;parent->_co = Red;curleft->_co = Black;
}

【六】测试

我们来根据下面几个性质检测红黑树：

（1）根节点是否为黑色

（2）是否有连续的红色节点

（3）根据任意一条路径的黑色节点去测一棵树的黑高，看是否相等

测试代码：

bool Tree_High(Node* root,int count,int date)
{if (root == nullptr){if (date != count){return false;}return true;}//看是否是连续的红节点if (root->_co == Red && root->_parent && root->_parent->_co == Red){cout << root->_date.first << "与父节点出现连续的红色节点" << endl;return false;}//计算每条路径黑色节点if (root->_co == Black){date++;}return Tree_High(root->_left, count, date) && Tree_High(root->_right, count, date);
}
bool Test()
{return Test(root);
}
//测试
bool Test(Node* root)
{if (root == nullptr){return true;}//看根节点是不是黑色if (root->_co != Black){cout << "根节点错误" << endl;return false;}//计算一条路径的黑色节点int count = 0;int date = 0;Node* cur = root->_left;while (cur){if (cur->_co == Black){count++;}cur = cur->_left;}return Tree_High(root->_left, count, date) && Tree_High(root->_right, count, date);
}

效果展示：

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

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

相关文章

基于SpringBoot+Uniapp的非遗文化宣传小程序（AI问答、协同过滤算法、Echarts图形化分析）

基于SpringBoot+Uniapp的非遗文化宣传小程序（AI问答、协同过滤算法、Echarts图形化分析）

“ &#x1f388;系统亮点&#xff1a;AI问答、协同过滤算法、Echarts图形化分析”01系统开发工具与环境搭建前后端分离架构项目架构&#xff1a;B/S架构运行环境&#xff1a;win10/win11、jdk17小程序端&#xff1a;技术&#xff1a;Uniapp&#xff1b;UI库&#xff1a;colorU…
阅读更多...
【从零开始java学习|第四篇】IntelliJ IDEA 入门指南

【从零开始java学习|第四篇】IntelliJ IDEA 入门指南

目录 一、IDEA 概述 1.1 什么是 IntelliJ IDEA&#xff1f; 1.2 IDEA 的核心优势 1.3 版本选择&#xff1a;社区版 vs 旗舰版 二、IDEA 下载与安装 2.1 下载步骤 2.2 安装过程&#xff08;以 Windows 为例&#xff09; 2.3 首次启动与激活 三、在 IDEA 中编写第一个 Ja…
阅读更多...
什么是 Spring MVC？

什么是 Spring MVC？

题目详细答案Spring MVC 是 Spring 框架中的一个模块&#xff0c;用于构建基于 Web 的应用程序。它遵循 Model-View-Controller#&#xff08;MVC&#xff09;设计模式&#xff0c;将业务逻辑、用户界面和数据分离&#xff0c;以促进代码的可维护性和可扩展性。主要包含几个概念…
阅读更多...
MySQL User表入门教程

MySQL User表入门教程

一、User表概述 MySQL的user表位于mysql系统数据库中&#xff0c;是MySQL权限系统的核心&#xff0c;用于存储用户账户信息、认证方式和全局权限。通过操作此表&#xff0c;可实现用户创建、权限分配及安全审计。 二、User表核心字段解析字段名作用示例值Host用户允许连接的主机…
阅读更多...
iOS 编译 cpp 代码生成 .a 库备忘

iOS 编译 cpp 代码生成 .a 库备忘

第一步&#xff1a;下载ios-cmake ios-cmake 第二步&#xff1a;复制ios-cmake到cpp项目目录下&#xff0c;打开终端输入&#xff1a; cmake -B build/ios_arm64 \-DCMAKE_TOOLCHAIN_FILE$(pwd)/ios-cmake/ios.toolchain.cmake \-DPLATFORMOS64 \-DCMAKE_BUILD_TYPERelease …
阅读更多...
C++11-下

C++11-下

10. lambda表达式 10.1 C98中的一个例子 在C98中&#xff0c;如果想要对一个数据集合中的元素进行排序&#xff0c;可以使用std::sort方法。 #include <algorithm> #include <functional> int main() { int array[] {4,1,8,5,3,7,0,9,2,6}; // 默认按照小于比较…
阅读更多...
教程 | 用Parasoft SOAtest实现高效CI回归测试

教程 | 用Parasoft SOAtest实现高效CI回归测试

在现代软件开发实践中&#xff0c;持续集成&#xff08;CI&#xff09;已成为提升交付效率、优化代码质量的重要基石。然而&#xff0c;随着功能快速叠加与代码迭代加快&#xff0c;回归缺陷的风险也在同步增长。为了保障每次代码提交不会破坏既有功能&#xff0c;功能回归测试…
阅读更多...
Leetcode-138. 复制带随机指针的链表

Leetcode-138. 复制带随机指针的链表

我们用哈希表来解决这个问题 首先创建一个哈希表&#xff0c;再遍历原链表&#xff0c;遍历的同时再不断创建新节点 我们将原节点作为key&#xff0c;新节点作为value放入哈希表中"""# Definition for a Node.class Node:def __init__(self, x: int, next: Node…
阅读更多...
【MATLAB 2025a】安装离线帮助文档

【MATLAB 2025a】安装离线帮助文档

文章目录一、在 MATLAB 设置中安装二、从math works 网站下载ISO&#xff1a;适用于给无法联网的电脑安装或自定义路径三、startup文件说明四、重要说明&#x1f9e9;&#x1f9e9;【Matlab】最新版2025a发布&#xff0c;深色模式、Copilot编程助手上线&#xff01; 版本&#…
阅读更多...
JDK21虚拟线程和 Golang1.24协程的比较

JDK21虚拟线程和 Golang1.24协程的比较

文章目录前言1、技术原理与实现机制1.1、JDK21虚拟线程本质&#xff1a;调度机制&#xff1a;内存管理&#xff1a;编程模型&#xff1a;1.2. Go 1.24协程GMP调度模型&#xff1a;抢占式调度&#xff1a;内存优化&#xff1a;编程模型&#xff1a;2、性能对比分析2.1、CPU密集型…
阅读更多...
聊天室全栈开发-保姆级教程（Node.js+Websocket+Redis+HTML+CSS）

聊天室全栈开发-保姆级教程（Node.js+Websocket+Redis+HTML+CSS）

前言 最近在学习websocket全双工通信&#xff0c;想要做一个联机小游戏&#xff0c;做游戏之前先做一个聊天室练练手。 跟着本篇博客&#xff0c;可以从0搭建一个属于你自己的聊天室。 准备阶段 什么人适合学习本篇文章&#xff1f; 答&#xff1a;前端开发者&#xff0c;有一…
阅读更多...
Android Coil3视频封面抽取封面帧存Disk缓存，Kotlin

Android Coil3视频封面抽取封面帧存Disk缓存，Kotlin

Android Coil3视频封面抽取封面帧存Disk缓存&#xff0c;Kotlin <uses-permission android:name"android.permission.WRITE_EXTERNAL_STORAGE" /><uses-permission android:name"android.permission.READ_EXTERNAL_STORAGE" /><uses-permis…
阅读更多...
最新文章

Copyright @ 2022~2023