引言

在计算机科学领域，数据结构是构建高效算法的基石。而在众多的数据结构中，平衡二叉搜索树因其优秀的查找、插入和删除性能而备受关注。红黑树（Red-Black Tree）作为一种自平衡的二叉搜索树，更是在 C++ 标准库（如 STL 中的 map 和 set）中得到了广泛应用。本文将深入探讨红黑树的原理、实现及应用，帮助读者全面掌握这一重要的数据结构。

红黑树的基本概念

红黑树是一种特殊的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色）。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

红黑树必须满足以下五个性质：

  1. 每个节点要么是红色，要么是黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL 节点，空节点）是黑色的。
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的。
  5. 对每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

这些性质的约束使得红黑树的高度始终保持在 O (log n)，从而保证了基本操作的高效性。

红黑树的操作

红黑树的基本操作包括插入、删除和查找。由于红黑树是二叉搜索树的一种，其查找操作与普通二叉搜索树相同，但插入和删除操作后需要通过旋转和变色来维持红黑树的性质。

插入操作

插入操作首先按照二叉搜索树的方式插入新节点，并将其着色为红色。然后通过一系列的旋转和颜色调整来修复红黑树的性质。插入操作的时间复杂度为 O (log n)。

插入修复主要分为三种情况：

  1. 情况 1：插入节点的父节点是红色，且叔叔节点（父节点的兄弟节点）也是红色。此时将父节点和叔叔节点变为黑色，祖父节点变为红色，然后继续处理祖父节点。
  2. 情况 2：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是父节点的右孩子。此时进行左旋操作，将问题转化为情况 3。
  3. 情况 3：插入节点的父节点是红色，叔叔节点是黑色，且插入节点是父节点的左孩子。此时将父节点变为黑色，祖父节点变为红色，然后进行右旋操作。
删除操作

删除操作同样首先按照二叉搜索树的方式删除节点，然后通过旋转和变色来修复红黑树的性质。删除操作的时间复杂度也为 O (log n)。

删除修复比插入修复更为复杂，主要分为四种情况，需要考虑兄弟节点的颜色以及兄弟节点子节点的颜色。

红黑树的 C++ 实现

下面是红黑树的 C++ 实现代码，包括节点结构、插入、删除、查找等基本操作：

#include "red_black_tree.hpp"
#include <iostream>
#include <cassert>int main() {RedBlackTree<int> tree;// 测试插入操作tree.insert(10);tree.insert(20);tree.insert(5);tree.insert(15);tree.insert(30);std::cout << "Inorder traversal after insertion: ";tree.inorder(); // 应输出 5 10 15 20 30// 测试查找操作assert(tree.contains(15) == true);assert(tree.contains(25) == false);std::cout << "Contains test passed." << std::endl;// 测试删除操作tree.remove(20);std::cout << "Inorder traversal after deleting 20: ";tree.inorder(); // 应输出 5 10 15 30assert(tree.contains(20) == false);// 测试大小assert(tree.size() == 4);std::cout << "Size after deletion: " << tree.size() << std::endl;// 测试空树RedBlackTree<int> emptyTree;assert(emptyTree.empty() == true);std::cout << "Empty tree test passed." << std::endl;std::cout << "All tests passed!" << std::endl;return 0;
}    
#ifndef RED_BLACK_TREE_HPP
#define RED_BLACK_TREE_HPP#include <iostream>
#include <memory>
#include <functional>
#include <cassert>template<typename T, typename Compare = std::less<T>>
class RedBlackTree {
private:enum class Color { RED, BLACK };struct Node {T data;Color color;std::unique_ptr<Node> left;std::unique_ptr<Node> right;Node* parent;Node(const T& value, Color nodeColor = Color::RED): data(value), color(nodeColor), left(nullptr), right(nullptr), parent(nullptr) {}};std::unique_ptr<Node> root;Compare compare;size_t treeSize;// 左旋操作void leftRotate(Node* x) {Node* y = x->right.get();x->right = std::move(y->left);if (y->left) {y->left->parent = x;}y->parent = x->parent;if (!x->parent) {root = std::unique_ptr<Node>(y);} else if (x == x->parent->left.get()) {x->parent->left = std::unique_ptr<Node>(y);} else {x->parent->right = std::unique_ptr<Node>(y);}y->left = std::move(x->right);x->parent = y;}// 右旋操作void rightRotate(Node* y) {Node* x = y->left.get();y->left = std::move(x->right);if (x->right) {x->right->parent = y;}x->parent = y->parent;if (!y->parent) {root = std::unique_ptr<Node>(x);} else if (y == y->parent->right.get()) {y->parent->right = std::unique_ptr<Node>(x);} else {y->parent->left = std::unique_ptr<Node>(x);}x->right = std::move(y->left);y->parent = x;}// 插入修复void insertFixup(Node* z) {while (z->parent && z->parent->color == Color::RED) {if (z->parent == z->parent->parent->left.get()) {Node* y = z->parent->parent->right.get();if (y && y->color == Color::RED) {z->parent->color = Color::BLACK;y->color = Color::BLACK;z->parent->parent->color = Color::RED;z = z->parent->parent;} else {if (z == z->parent->right.get()) {z = z->parent;leftRotate(z);}z->parent->color = Color::BLACK;z->parent->parent->color = Color::RED;rightRotate(z->parent->parent);}} else {Node* y = z->parent->parent->left.get();if (y && y->color == Color::RED) {z->parent->color = Color::BLACK;y->color = Color::BLACK;z->parent->parent->color = Color::RED;z = z->parent->parent;} else {if (z == z->parent->left.get()) {z = z->parent;rightRotate(z);}z->parent->color = Color::BLACK;z->parent->parent->color = Color::RED;leftRotate(z->parent->parent);}}}root->color = Color::BLACK;}// 查找最小节点Node* minimum(Node* node) const {while (node->left) {node = node->left.get();}return node;}// 查找最大节点Node* maximum(Node* node) const {while (node->right) {node = node->right.get();}return node;}// 查找后继节点Node* successor(Node* node) const {if (node->right) {return minimum(node->right.get());}Node* y = node->parent;while (y && node == y->right.get()) {node = y;y = y->parent;}return y;}// 查找前驱节点Node* predecessor(Node* node) const {if (node->left) {return maximum(node->left.get());}Node* y = node->parent;while (y && node == y->left.get()) {node = y;y = y->parent;}return y;}// 删除修复void deleteFixup(Node* x, Node* parent) {while (x != root.get() && (x == nullptr || x->color == Color::BLACK)) {if (x == parent->left.get()) {Node* w = parent->right.get();if (w->color == Color::RED) {w->color = Color::BLACK;parent->color = Color::RED;leftRotate(parent);w = parent->right.get();}if ((w->left == nullptr || w->left->color == Color::BLACK) &&(w->right == nullptr || w->right->color == Color::BLACK)) {w->color = Color::RED;x = parent;parent = x->parent;} else {if (w->right == nullptr || w->right->color == Color::BLACK) {if (w->left) w->left->color = Color::BLACK;w->color = Color::RED;rightRotate(w);w = parent->right.get();}w->color = parent->color;parent->color = Color::BLACK;if (w->right) w->right->color = Color::BLACK;leftRotate(parent);x = root.get();parent = nullptr;}} else {Node* w = parent->left.get();if (w->color == Color::RED) {w->color = Color::BLACK;parent->color = Color::RED;rightRotate(parent);w = parent->left.get();}if ((w->right == nullptr || w->right->color == Color::BLACK) &&(w->left == nullptr || w->left->color == Color::BLACK)) {w->color = Color::RED;x = parent;parent = x->parent;} else {if (w->left == nullptr || w->left->color == Color::BLACK) {if (w->right) w->right->color = Color::BLACK;w->color = Color::RED;leftRotate(w);w = parent->left.get();}w->color = parent->color;parent->color = Color::BLACK;if (w->left) w->left->color = Color::BLACK;rightRotate(parent);x = root.get();parent = nullptr;}}}if (x) x->color = Color::BLACK;}// 中序遍历辅助函数void inorderTraversal(Node* node) const {if (node) {inorderTraversal(node->left.get());std::cout << node->data << " ";inorderTraversal(node->right.get());}}// 查找节点辅助函数Node* findNode(const T& value) const {Node* current = root.get();while (current) {if (compare(value, current->data)) {current = current->left.get();} else if (compare(current->data, value)) {current = current->right.get();} else {return current;}}return nullptr;}public:RedBlackTree() : root(nullptr), compare(), treeSize(0) {}// 插入操作void insert(const T& value) {Node* z = new Node(value);Node* y = nullptr;Node* x = root.get();while (x) {y = x;if (compare(z->data, x->data)) {x = x->left.get();} else {x = x->right.get();}}z->parent = y;if (!y) {root = std::unique_ptr<Node>(z);} else if (compare(z->data, y->data)) {y->left = std::unique_ptr<Node>(z);} else {y->right = std::unique_ptr<Node>(z);}z->color = Color::RED;insertFixup(z);treeSize++;}// 删除操作bool remove(const T& value) {Node* z = findNode(value);if (!z) return false;Node* y = z;Node* x;Color yOriginalColor = y->color;if (!z->left) {x = z->right.get();transplant(z, std::move(z->right));} else if (!z->right) {x = z->left.get();transplant(z, std::move(z->left));} else {y = minimum(z->right.get());yOriginalColor = y->color;x = y->right.get();if (y->parent == z) {if (x) x->parent = y;} else {transplant(y, std::move(y->right));y->right = std::move(z->right);y->right->parent = y;}transplant(z, std::move(std::unique_ptr<Node>(y)));y->left = std::move(z->left);y->left->parent = y;y->color = z->color;}if (yOriginalColor == Color::BLACK) {deleteFixup(x, y->parent);}treeSize--;return true;}// 查找操作bool contains(const T& value) const {return findNode(value) != nullptr;}// 获取元素数量size_t size() const {return treeSize;}// 判断是否为空bool empty() const {return treeSize == 0;}// 中序遍历void inorder() const {inorderTraversal(root.get());std::cout << std::endl;}// 移植辅助函数void transplant(Node* u, std::unique_ptr<Node> v) {Node* uParent = u->parent;if (!uParent) {root = std::move(v);} else if (u == uParent->left.get()) {uParent->left = std::move(v);} else {uParent->right = std::move(v);}if (v) {v->parent = uParent;}}
};#endif // RED_BLACK_TREE_HPP

这段代码实现了一个模板类 RedBlackTree，包含了红黑树的基本操作。代码中使用了智能指针管理内存，确保内存安全。同时，通过插入修复和删除修复函数来维护红黑树的性质。

红黑树的应用

红黑树在计算机科学中有广泛的应用，主要包括：

  1. C++ 标准库：STL 中的 map 和 set 就是基于红黑树实现的，保证了元素的有序性和高效的插入、删除、查找操作。
  2. 操作系统：Linux 内核中的完全公平调度器（CFS）使用红黑树来管理进程调度。
  3. 数据库系统：许多数据库系统使用红黑树来索引数据，提高查询效率。
  4. 其他应用：如 Java 的 TreeMap 和 TreeSet、Python 的 SortedContainers 等。
红黑树与其他数据结构的比较

红黑树与其他平衡二叉搜索树（如 AVL 树、B 树等）相比，具有以下特点：

  1. 与 AVL 树相比：红黑树的平衡性要求不如 AVL 树严格，因此插入和删除操作的旋转次数更少，但查找操作的效率略低。
  2. 与 B 树相比：红黑树是二叉树，而 B 树是多叉树，更适合存储在磁盘等外部存储设备上。
  3. 与哈希表相比：红黑树可以保证元素的有序性，而哈希表不能，但哈希表的平均查找时间复杂度为 O (1)，比红黑树更快。
总结

红黑树作为一种重要的数据结构，凭借其良好的平衡性和高效的操作性能，在计算机科学领域得到了广泛应用。通过本文的介绍，读者应该对红黑树的原理、实现和应用有了全面的了解。掌握红黑树不仅有助于理解各种高级算法和数据结构，也能在实际编程中发挥重要作用。

希望本文对您理解 C++ 红黑树有所帮助！
 

附：恩师博客hnjzsyjyj-CSDN博客

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

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

相关文章

外星人笔记本装win11哪个版本好_外星人笔记本装win11专业版教程

外星人笔记本装win11哪个版本好_外星人笔记本装win11专业版教程

外星人笔记本安装win11哪个版本好&#xff1f;答&#xff1a;外星人笔记本还是建议安装win11专业版。Win分为多个版本&#xff0c;其中家庭版&#xff08;Home&#xff09;和专业版&#xff08;Pro&#xff09;是用户选择最多的两个版本。win11专业版在功能以及安全性方面有着明…
阅读更多...
自学嵌入式 day37 HTML

自学嵌入式 day37 HTML

HTML:超文本标记语言HyperText Markup Language一种用于创建网页的标准标记语言HTML 运行在浏览器上&#xff0c;由浏览器来解析。https://www.runoob.com/html/html-tutorial.html1.格式 <!DOCTYPE html> <html><head><meta charset"utf-8"&g…
阅读更多...
【车联网kafka】Kafka核心架构与实战经验（第一篇）

【车联网kafka】Kafka核心架构与实战经验（第一篇）

目录 一、我与kafka的缘分-初识Kafka 二、Kafka深入探讨-了解kafka ​编辑2.1 kafka 生产者框架 2.1.1 生产者在生活中的实例 2.1.2 kafka生产者流程及框架 1. 主线程处理阶段 2. Sender线程处理阶段 设计优势总结 2.2 kafka 生产者框架中的一些关键参数 2.3 kafka 生…
阅读更多...
Go 语言变量作用域

Go 语言变量作用域

Go 语言变量作用域 引言 在编程语言中&#xff0c;变量作用域是定义变量可以使用和不可使用的区域。在Go语言中&#xff0c;理解变量的作用域对于编写高效且易于维护的代码至关重要。本文将详细介绍Go语言中的变量作用域&#xff0c;包括其规则、类型以及实际应用。 一、变量作…
阅读更多...
单卡10分钟部署MiniCPM4-0.5B：轻量级大模型本地运行指南

单卡10分钟部署MiniCPM4-0.5B：轻量级大模型本地运行指南

一、介绍 MiniCPM 4 是一个极其高效的边缘侧大型模型&#xff0c;经过了模型架构、学习算法、训练数据和推理系统四个维度的高效优化&#xff0c;实现了极致的效率提升。 &#x1f3d7;️ 高效的模型架构&#xff1a; InfLLM v2 – 可训练的稀疏注意力机制&#xff1a;采用可…
阅读更多...
CSS变量与Houdini自定义属性：解锁样式编程新维度

CSS变量与Houdini自定义属性：解锁样式编程新维度

在前端开发中&#xff0c;CSS变量和Houdini自定义属性正在彻底改变我们编写和管理样式的方式。这些技术不仅提高了样式代码的可维护性&#xff0c;更为CSS带来了编程语言的强大能力。一、CSS变量&#xff1a;原生样式的革命 CSS变量&#xff08;CSS Custom Properties&#xff…
阅读更多...
Android中PID与UID的区别和联系(2)

Android中PID与UID的区别和联系(2)

一、核心概念对比特性PID (Process ID)UID (User ID)本质进程唯一标识符应用身份标识符分配时机进程启动时动态分配应用安装时静态分配生命周期进程结束时回收应用卸载时才回收变化性每次启动都可能不同长期保持不变作用范围单进程内唯一全设备范围唯一核心作用系统资源管理&am…
阅读更多...
TCPDump实战手册：协议/端口/IP过滤与组合分析指南

TCPDump实战手册：协议/端口/IP过滤与组合分析指南

目录 一、基础过滤速查表 1. 协议过滤&#xff08;单协议&#xff09; 2. 端口过滤 3. IP地址过滤 二、组合过滤实战示例 1. 协议端口组合 2. IP端口组合 3. 复杂逻辑组合 三、高级协议分析示例 1. HTTP请求分析 2. DNS问题排查 3. TCP连接问题分析 四、组合过滤场…
阅读更多...
【智能协同云图库】智能协同云图库第八弹：基于阿里云百炼大模型—实现 AI 扩图功能

【智能协同云图库】智能协同云图库第八弹：基于阿里云百炼大模型—实现 AI 扩图功能

AI 扩图功能 需求分析 随着 AI 的高速发展&#xff0c;AI 几乎可以应用到任何传统业务中&#xff0c;增强应用的功能&#xff0c;带给用户更好的体验。 对于图库网站来说&#xff0c;AI 也有非常多的应用空间&#xff0c;比如可以利用 AI 绘图大模型来编辑图片&#xff0c;实现…
阅读更多...
2025年Solar应急响应公益月赛-7月笔记ing

2025年Solar应急响应公益月赛-7月笔记ing

应急响应身为颜狗的我是真心觉得lovelymem的ui写得~~~~【任务1】应急大师题目描述&#xff1a;请提交隐藏用户的名称&#xff1f;print打印注册表&#xff0c;或者开启环境是就有【任务4】应急大师题目描述&#xff1a;请提交黑客创建隐藏用户的TargetSid&#xff08;目标账户安…
阅读更多...
C++/CLI vs 标准 C++ vs C# 语法对照手册

C++/CLI vs 标准 C++ vs C# 语法对照手册

&#x1f680; C/CLI vs 标准 C vs C# 语法对照手册&#x1f9e9; 核心类型系统对比 // 类型声明语法对比 标准 C C/CLI C# ─────────────────────────────────────────────────…
阅读更多...
仓库管理系统-2-后端之基于继承基类的方式实现增删改查

仓库管理系统-2-后端之基于继承基类的方式实现增删改查

文章目录 1 数据库表user 2 后端通用框架 2.1 User.java(实体类) 2.2 使用封装的方法(继承基类) 2.2.1 UserMapper.java(mapper接口) 2.2.2 UserService.java(service接口) 2.2.3 UserServiceImpl.java(service实现类) 2.2.4 UserController.java(控制器) 3 增删改查(封装的方法…
阅读更多...
【el-table滚动事件】el-table表格滚动时，获取可视窗口内的行数据

【el-table滚动事件】el-table表格滚动时，获取可视窗口内的行数据

一个简单的获取内容的办法 表格部分&#xff0c;主要是ref写一下<el-table :data"tableData" ref"tableRef"> </el-table>进入页面的时候绑定监听 mounted(){ // 绑定滚动事件this.$nextTick(() > {const table this.$refs.tableRef;const…
阅读更多...
OCR 赋能自动阅卷：让评分更高效精准

OCR 赋能自动阅卷：让评分更高效精准

考试阅卷中&#xff0c;OCR 技术正成为高效助手&#xff0c;尤其在客观题和标准化答题场景中表现亮眼。将考生答题卡扫描后&#xff0c;OCR 能快速识别填涂的选项、手写数字或特定符号&#xff0c;与标准答案比对后自动判分。相比人工阅卷&#xff0c;它能在短时间内完成成百上…
阅读更多...
在docker中安装frp实现内网穿透

在docker中安装frp实现内网穿透

服务端frps 1.首先在服务器端安装frps docker pull snowdreamtech/frps2.本地创建frps的配置文件frps.ini [common] bind_port 7000 # frp 服务端控制端口 token xxxxx # 客户端认证密钥3.启动frps docker run -d --name frps \ --network host \ --restartalwa…
阅读更多...
电脑开机后网络连接慢？

电脑开机后网络连接慢？

在数字化日益普及的今天&#xff0c;电脑已成为我们工作和生活中不可或缺的工具。但是&#xff0c;可能很多用户都遇到过电脑开机后网络连接慢的情况&#xff0c;这不仅影响了我们的工作效率&#xff0c;还极大降低了上网体验。怎么解决该问题呢&#xff1f;本文分享的这5个方法…
阅读更多...
一分钟部署一个导航网站

一分钟部署一个导航网站

先看效果1.部署教程 mkdir -p /home/ascendking/mysite cd /home/ascendking/mysite# 安装 WebStack-Hugo 主题git clone https://gitee.com/WangZhe168_admin/WebStack-Hugo.git themes/WebStack-Hugo# 将 exampleSite 目录下的文件复制到 hugo 站点根目录 cd /home/ascendki…
阅读更多...
Rust实现微积分与高等数学公式

Rust实现微积分与高等数学公式

基于Rust实现高等数学中微积分 以下是基于Rust实现高等数学中微积分相关公式的示例整理，涵盖微分、积分、级数等常见计算场景。内容分为基础公式和进阶应用两类，提供可直接运行的Rust代码片段（需依赖num或nalgebra等库）。 微分运算 导数的数值近似（前向差分） 适用于函…
阅读更多...
Android 键盘

Android 键盘

基础知识1. 物理键盘&#xff08;Physical Keyboard&#xff09;定义物理键盘指的是设备上真实存在的、可以按压的键盘。例如&#xff1a;早期的 Android 手机&#xff08;如黑莓、摩托罗拉 Milestone&#xff09;自带的 QWERTY 键盘外接的蓝牙/USB 键盘平板或 Chromebook 上的…
阅读更多...
SuperClaude Framework 使用指南

SuperClaude Framework 使用指南

SuperClaude Framework 使用指南SuperClaude Framework 是一个开源配置框架&#xff0c;将 Claude Code 从通用 AI 助手转变为专业的上下文感知开发伙伴。该框架通过模板驱动架构应用软件工程原理&#xff0c;为专业软件开发工作流程提供了强大的增强功能。目前该项目处于 v3.0…
阅读更多...
最新文章

Copyright @ 2022~2023