C++ 红黑树实现与优化详解

深入讲解了 C++ 中红黑树的原理、实现与优化。首先介绍了红黑树的五大性质及其平衡机制，对比了其与 AVL 树的差异。接着详细阐述了红黑树的节点设计、插入操作中的变色与旋转逻辑（左旋、右旋、双旋），并提供了完整的 C++ 代码实现。最后通过测试验证了红黑树的平衡性，分析了其在数据库索引及 STL 容器中的应用场景。

PhpPioneer发布于 2026/3/29更新于 2026/4/187 浏览

文章配图

坎坷之路，终抵星空。

—— 哈珀·李《杀死一只反舌鸟》

1. 解密红黑树：平衡与效率的双重奏

探讨红黑树如何通过一组简单的规则保持平衡，并提供高效的查询和更新操作。

红黑树是一种特殊的二叉树，它遵循一套独特的规则：

每个节点要么是红色，要么是黑色。根节点必须是黑色的。如果一个节点是红色的，则它的两个子节点必须是黑色的。对于任意一个节点，从该节点到其所有后代叶子节点的简单路径上，必须包含相同数目的黑色节点。每个叶子节点都是黑色的。这里的叶子节点指的是为空的节点。

TIP：红黑树的规则并不要求红黑节点严格交替出现。黑色节点可以连续，但红色节点不能连续。这是规则的设定。

文章配图

通过这些规则，红黑树可以保持接近平衡的状态。虽然它不像 AVL 树那样可以维持严格的平衡状态，但是它可以保证搜索的效率。需要记住的是：红黑树每条路径（从根节点到空节点）上的黑色节点数量相同。

那么问题来了，红黑树如何确保最长路径不超过最短路径的 2 倍的？

由规则 4 可知，从根到 NULL 结点的每条路径都有相同数量的黑色结点，所以极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为 bh(black height)。由规则 2 和规则 3 可知，任意一条路径不会有连续的红色结点，所以极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为 2bh。综合红黑树的规则而言，理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。假设任意一条从根到 NULL 结点路径的长度为 x，那么 bh <= x <= 2bh。

这样红黑树保证了查找效率！！！

假设 N 是红黑树树中节点数量，h 为最短路径长度，那么等比数列求和有 2^(h) -1<=N<=2^(2h) -1 因此可以知道 h 近似为 log N，也就是意味着红黑树增删查改最坏也就是走最长路径 2*logN，那么时间复杂度还是 O(log N)

红黑树的表达相对 AVL 树要抽象一些，AVL 树通过高度差直观的控制了平衡。红黑树通过规则的颜色控制，间接的实现了近似平衡，他们效率都是同一档次，但是相对而言，插入相同数量的结点，红黑树的旋转次数是更少的，因为他对平衡的控制没那么严格。

文章配图

红黑树的应用场景十分广泛，其中之一是在很多高性能的 C++ STL 库中被广泛采用，比如 map 和 set。这是因为红黑树具有平衡性能较好的特性，能够保持树的高度较低，从而保证了在插入、删除和查找操作上的较高效率。除此之外，它还常用于实现范围查询和有序遍历等功能。后续将实现 map 与 set 的封装。

红黑树的平衡性质使其在数据库系统中也得到了广泛的应用，特别是在实现索引结构时。在数据库系统中，红黑树可以用于实现基于范围的查询，如在 B+ 树的实现中，通常使用红黑树来维护叶子节点的有序性。

2. 搭建红黑树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

红黑树的基本设计思想，构建红黑树所需的基本元素和数据结构。

红黑树的节点设计基于二叉搜索树的节点增加了一个表示颜色的变量，用来标识该节点的颜色，我们采用枚举表示颜色状态

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return 1; } Node* cur = _root; Node* parent = nullptr; // 查找逻辑 cur 到对应的位置去 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 0; } } cur = new Node(kv); cur->_col = RED; // 新插入非空节点为红色 // 连接 prev 与 cur if (parent->_kv.first > kv.first) parent->_left = cur; else parent->_right = cur; cur->_parent = parent; // 父亲是红色出现了连续红节点需要处理可能多次处理 while (parent && parent->_col == RED) // 可能为空 { Node* grandfather = parent->_parent; if (grandfather->_left == parent) { // g p u Node* uncle = grandfather->_right; // 叔叔不为空且红色 if (uncle && uncle->_col == RED) { // 父亲和叔叔变黑爷爷变红变色解决连续红色节点并且保证路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 往上更新 cur = grandfather; parent = cur->_parent; } else // 叔叔不存在或者叔叔存在为黑色 { if (parent->_left == cur) // 右单旋 + 变色 { // g p u c RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p c g u } else // 双旋处理 { // g p u c RotateLR(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c p g u } break; } } else { // g u p Node* uncle = grandfather->_left; // 叔叔不为空且红色 if (uncle && uncle->_col == RED) { // 父亲和叔叔变黑爷爷变红变色解决连续红色节点并且保证路径黑节点数量不变 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; // 往上更新 cur = grandfather; parent = cur->_parent; } else { if (parent->_right == cur) // 左单旋 + 变色 { // g u p c RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; // p g c u } else // 双旋处理 { // g u p c RotateRL(grandfather); cur->_col = BLACK; grandfather->_col = RED; // c g p u } break; } } } _root->_col = BLACK; return 1; }