C++ 红黑树是一种自平衡二叉搜索树，通过颜色约束保证最长路径不超过最短路径的两倍。文章详细阐述了红黑树的五条基本规则，分析了其时间复杂度 O(logN)。重点讲解了插入操作中的三种调整情况：变色、单旋加变色、双旋加变色，并提供了完整的 C++ 类实现代码及验证方法。删除操作较为复杂，通常涉及更多旋转与变色逻辑。
红黑树是一种二叉搜索树，每个节点增加一个存储位代表该节点的颜色。节点的颜色可以是红色或黑色。通过对任何一条根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。
红黑树是被多条规则束缚的二叉搜索树，通过这些规则，可以保证红黑树没有一条路径会比其他路径长出两倍，并且保持其相对平衡。
《算法导论》补充了一个知识点：每个叶子节点（NULL）都是黑色的。这里所指的叶子节点不是传统意义上的叶子节点，而是我们所说的空节点，有些书籍上也把 NULL 叫做外部节点。NULL 是为了方便准确地标志所有路径。
由规则 4 可以知道，每条路径上有着数量相同的黑色节点。在极端场景下，一条路上全都是黑色节点，最短路径其实就是一条路上全是黑色节点，我们将最短路径的长度记作 bh。
结合规则 2 和规则 3，一条路上不会出现连续的红色节点，所以最长路径应该是一红一黑交织组成，因此最长路径的长度是 2bh。
根据红黑树的规则，一般情况下的红黑树的路径是由数量不等的红黑节点组成的。假设红黑树一条路径的长度为 h，所以 bh <= h <= 2bh，即红黑树的最长路径不会是最短路径的两倍。
假设红黑树的节点个数为 N，最短路径的长度为 h，所以可知：2^h - 1 <= N < 2^(2*h) - 1，由此可以推出 h 大约等于 logN，也就是红黑树查找的效率最差也是 2 * logN，时间复杂度终归还是 O(log(N))。
红黑树的表达相对 AVL 树要更抽象一些，AVL 树可以根据高度更加直观地看出树的平衡，而红黑树则是需要根据四条规则的颜色进行约束，间接地实现了近似平衡。他们的效率都是同一档次的，但是相对而言，插入相同数量的节点，红黑树的旋转次数变得更少了，因为它对平衡的把控并不是那么严格。
在书写平衡树的代码之前，通常需要先完善它的结构。红黑树是一个典型的三叉链，节点需要包含父节点以及左右孩子节点。由于红黑树是通过颜色进行平衡的，还需要设置好一个枚举来确定节点的颜色，默认颜色为红色。红黑树通过 Key 和 Value 存放数据，Key 作为标记，Value 为核心数据。
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
红黑树的查找和二叉搜索树的查找是一样的，代码类似，效率都是 log(N)。
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first > key) {
cur = cur->_left;
} else if (cur->_kv.first < key) {
cur = cur->_right;
} else {
return cur;
}
}
return nullptr;
}
红黑树的插入比较复杂，涉及旋转和变色操作来维持规则。假设新增的节点叫 c(cur)，父亲为 p(parent)，祖父为 g(grandfather)，叔叔为 u(uncle)。
插入一个值是按照二叉搜索树的规则进行的。如果是空树插入，插入的必然是黑色节点；如果是非空树插入，插入的节点一定是红色节点，因为第四条规则约束着，如果插入的是黑色节点，会破坏黑色节点数量平衡。如果父节点是红色的，违反了第三条规则。此时 c 是红色，p 也是红色，g 必然是黑色的。关键变化取决于 u 的变化，分为四种情况讨论。
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK; // 根节点一定是黑色的
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} 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;
// 开始进行变色处理
// ... 后续调整逻辑
}
如果 c 是红的，p 为红，g 为黑，u 存在并且是红色的，需要进行变色处理，即将 p 和 u 都变为黑色，g 变红。再把 g 当做新的 c，继续往上更新。如果 g 是整棵树的根，最后需要将 g 变为黑色。
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
} else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
}
}
}
_root->_col = BLACK;
如果 c 是红色，p 是红色，g 为黑，u 不存在或者 u 是黑色的时候，不能单纯依靠变色修正。如果 p 是 g 的左子树，c 是 p 的左子树，以 g 为旋转点进行一次右单旋，然后让 g 变为红色，p 变为黑色。反之亦然。
if (uncle == nullptr || uncle->_col == BLACK) {
if (parent->_left == cur) {
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
} else {
if (parent->_right == cur) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
}
如果 p 是 g 的左，c 是 p 的右，需要通过双旋进行调整。先以 p 为旋转点进行一次左旋，再以 g 进行一次右旋，之后让 c 变为黑色，g 变为红色。
// 左右双旋转
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
guardfather->_col = RED;
验证红黑树需要检验四条规则：
bool Check(Node* root, int blackNum, const int refNum) {
if (root == nullptr) {
if (refNum != blackNum) {
cout << "存在黑色结点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK) {
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
bool IsBalance() {
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
int refNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) {
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
红黑树的删除比插入更为复杂，涉及更多的旋转与变色逻辑，此处不再赘述。
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<ctime>
using namespace std;
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED) {}
};
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
private:
void RotateR(Node* parent) {
Node* subl = parent->_left;
Node* sublR = subl->_right;
parent->_left = sublR;
if (sublR) {
sublR->_parent = parent;
}
Node* ppnode = parent->_parent;
subl->_right = parent;
parent->_parent = subl;
if (ppnode == nullptr) {
_root = subl;
subl->_parent = ppnode;
} else {
if (subl->_kv.first > ppnode->_kv.first) {
ppnode->_right = subl;
} else {
ppnode->_left = subl;
}
subl->_parent = ppnode;
}
}
void RotateL(Node* parent) {
Node* subL = parent->_right;
Node* subLL = subL->_left;
Node* ppnode = parent->_parent;
parent->_right = subLL;
if (subLL) {
subLL->_parent = parent;
}
subL->_left = parent;
parent->_parent = subL;
if (ppnode == nullptr) {
_root = subL;
subL->_parent = nullptr;
} else {
if (subL->_kv.first > ppnode->_kv.first) {
ppnode->_right = subL;
} else {
ppnode->_left = subL;
}
subL->_parent = ppnode;
}
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
public:
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} else if (cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} 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;
if (grandfather->_left == parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
} else {
if (parent->_left == cur) {
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else {
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
grandfather->_col = RED;
parent->_col = BLACK;
uncle->_col = BLACK;
cur = grandfather;
parent = cur->_parent;
} else {
if (parent->_right == cur) {
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} else {
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first > key) {
cur = cur->_left;
} else if (cur->_kv.first < key) {
cur = cur->_right;
} else {
return cur;
}
}
return nullptr;
}
void InOrder() {
_InOrder(_root);
}
bool Check(Node* root, int blackNum, const int refNum) {
if (root == nullptr) {
if (refNum != blackNum) {
cout << "存在黑色结点的数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED) {
cout << root->_kv.first << "存在连续的红色结点" << endl;
return false;
}
if (root->_col == BLACK) {
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
}
bool IsBalance() {
if (_root == nullptr) return true;
if (_root->_col == RED) return false;
int refNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) {
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
int Height() {
return _Height(_root);
}
int Size() {
return _Size(_root);
}
protected:
int _Size(Node* root) {
if (root == nullptr) return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
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;
};
本文详细介绍了 C++ 红黑树的设计原理、基本规则、插入操作的三种调整情况及验证方法，并提供了完整的类实现代码。红黑树作为一种高效的自平衡二叉搜索树，广泛应用于标准库中。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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