C++算法
C++ 红黑树详解：原理、实现与性能对比
C++ 红黑树的概念、性质及实现原理。内容涵盖红黑树的定义、五大性质解读、路径平衡推导、插入算法（包括变色与四种旋转情况 LL/RR/LR/RL）、旋转操作的具体代码实现以及树的验证方法。同时提供了完整的可运行代码示例，并对比了红黑树与 AVL 树在性能上的差异，指出红黑树在频繁增删场景下的优势及其在 STL 容器中的应用价值。
C++ 红黑树的概念、性质及实现原理。内容涵盖红黑树的定义、五大性质解读、路径平衡推导、插入算法（包括变色与四种旋转情况 LL/RR/LR/RL）、旋转操作的具体代码实现以及树的验证方法。同时提供了完整的可运行代码示例，并对比了红黑树与 AVL 树在性能上的差异，指出红黑树在频繁增删场景下的优势及其在 STL 容器中的应用价值。
红黑树是一种自平衡二叉搜索树，由德国计算机科学家 Rudolf Bayer 在 1972 年发明。它通过为每个结点增加一个存储位来表示结点的颜色（红色或黑色），并对从根节点到任意叶子节点路径上的节点颜色进行约束，从而保持树的左右两边的相对平衡。
红黑树确保没有一条路径会比其他路径长出 2 倍，即 2 * 最短路径 >= 最长路径，因而它是一种近似平衡的二叉搜索树。它在很多编程语言的库和实际应用场景中都有广泛使用，例如 C++ 的 STL 库中的 map 和 set 底层实现，Java 的 TreeMap 等库的实现。
![图片：红黑树示例]
因此，红黑树的性质可以简记为：左根右，根叶黑，不红红，黑路同。
计算路径是从根节点到空结点 (NIL)。如果树路径的计算不包含空节点，可能会导致误判违反性质 4。
![图片：树路径计算]
bh (black height)。2*bh。enum Colour { Red, Black };
template<class K, class V>
struct RBTreeNode {
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
std::pair<K, V> _kv;
Colour _col;
RBTreeNode(const std::pair<K, V>& kv)
: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(Red) {}
};
template<class K, class V>
class RBTree {
public:
int _rotateCount = 0;
private:
typedef RBTreeNode<K, V> Node;
Node* _root = nullptr;
public:
bool insert(const std::pair<K, V>& kv);
// ... 其他接口
private:
void RotateL(Node* parent);
void RotateR(Node* parent);
// ... 辅助函数
};
当对一棵空的红黑树进行插入时，直接插入并把其颜色设置为黑色即可。
在非空情况下，插入节点的颜色必定是红色。如果父亲是黑色，不会违反红黑树的任何一条性质，插入结束。
此时需要调整以维持性质。
这里的旋转操作和 AVL 树的旋转操作一致，只需把 AVL 树中的更新平衡因子的步骤去掉。
void RotateL(Node* parent) {
if (parent == nullptr || parent->_right == nullptr) return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
parent->_right = curLeft;
if (curLeft) curLeft->_parent = parent;
if (parent == _root) {
_root = curNode;
curNode->_parent = nullptr;
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent;
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
parent->_parent = curNode;
curNode->_left = parent;
}
}
void RotateR(Node* parent) {
if (parent == nullptr || parent->_left == nullptr) return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
parent->_left = curRight;
if (curRight) curRight->_parent = parent;
if (parent == _root) {
_root = curNode;
curNode->_parent = nullptr;
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent;
if (parent == ppNode->_left) ppNode->_left = curNode;
else ppNode->_right = curNode;
curNode->_parent = ppNode;
curNode->_right = parent;
parent->_parent = curNode;
}
}
bool insert(const std::pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = Black;
return true;
}
Node* parent = nullptr;
Node* curNode = _root;
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else {
return false; // 不允许重复
}
}
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first)
parent->_left = curNode;
else
parent->_right = curNode;
curNode->_parent = parent;
// 控制近似平衡
while (parent && parent->_col == Red) {
Node* grandFather = parent->_parent;
if (parent == grandFather->_left) {
Node* uncle = grandFather->_right;
if (uncle && uncle->_col == Red) {
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
curNode = grandFather;
parent = curNode->_parent;
} else {
if (curNode == parent->_left) {
RotateR(grandFather);
parent->_col = Black;
grandFather->_col = Red;
} else {
RotateL(parent);
RotateR(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
} else {
Node* uncle = grandFather->_left;
if (uncle && uncle->_col == Red) {
parent->_col = uncle->_col = Black;
grandFather->_col = Red;
curNode = grandFather;
parent = curNode->_parent;
} else {
if (curNode == parent->_right) {
RotateL(grandFather);
parent->_col = Black;
grandFather->_col = Red;
} else {
RotateR(parent);
RotateL(grandFather);
curNode->_col = Black;
grandFather->_col = Red;
}
break;
}
}
}
_root->_col = Black;
return true;
}
int Height() { return _Height(_root); }
int _Height(Node* root = _root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool isBalance() { return _isBalance(_root); }
bool _isBalance(Node* root = _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);
}
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) {
std::cout << root->_kv.first << " 出现连续红色节点" << std::endl;
return false;
}
return CheckColour(root->_left, blacknum, benchmark) &&
CheckColour(root->_right, blacknum, benchmark);
}
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O(logN)。红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比 AVL 树更优。
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// #include "AVL_Tree.h"
using namespace std;
int main() {
const int N = 10000000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++) {
v.push_back(rand() + i * i + 2); // 插入随机数据
}
RBTree<int, int> rbt;
for (auto e : v) {
rbt.insert(make_pair(e, e));
}
cout << "红黑树是否平衡：" << rbt.isBalance() << endl;
cout << "红黑树的高度：" << rbt.Height() << endl;
cout << "红黑树的旋转次数：" << rbt._rotateCount << endl;
// AVLTree<int, int> avlt;
// for (auto e : v) {
// avlt.insert(make_pair(e, e));
// }
// cout << "AVL 树是否平衡：" << avlt.isBalance() << endl;
// cout << "AVL 树的高度：" << avlt.height() << endl;
// cout << "AVL 树的旋转次数：" << avlt._rotateCount << endl;
return 0;
}
红黑树作为一种'近似平衡'的二叉搜索树，通过颜色标记与旋转调整，在插入与删除操作频繁的场景下有效避免了 AVL 树的高频旋转问题。它在时间复杂度上与 AVL 树相同，都是 O(logN)，但实际应用中更具工程价值，因此成为了 STL map、set 等容器的底层数据结构。
本文自底向上实现了红黑树的插入、变色与旋转机制，并通过与 AVL 树的对比，揭示了红黑树在平衡效率与维护开销上的折中之美。
红黑树的核心思想：不追求完美平衡，而是保证最长路径不超过最短路径的 2 倍；通过简单的局部旋转与变色操作实现全局近似平衡；用颜色规则取代复杂的高度平衡因子，使得结构更简洁、效率更高。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online