红黑树是一种自平衡二叉搜索树，通过颜色约束确保路径长度不超过两倍，时间复杂度为 O(logN)。核心规则包括根节点黑色、红节点子节点必黑、任意路径黑节点数相同。实现涉及节点结构定义、插入时的变色与旋转调整（单旋或双旋）、查找及平衡验证。代码基于 C++ 模板实现，包含左右旋函数及插入逻辑中的四种情况处理，确保树结构满足红黑性质。
前面我们已经理解并实现了 AVL 树，不难发现：AVL 树对其自身结构有非常严格的要求，即任意节点的左右子树高度差不能超过 1。因此，又有人提出了红黑树这样的数据结构，但 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
思考：红黑树如何确保最长路径不超过最短路径的 2 倍的？
答：从根结点开始的一条路径上只有 n 个黑色结点，由红黑树规则，两条路径上黑色结点数相同，且红色结点不连续，则当另一条路径上黑色结点与红色结点相间分布时，有最长长度为 2n，这就保证了最长路径始终不超过最短路径的两倍。
假设 N 是红黑树中结点数量，h 最短路径的长度，那么 2^h − 1 <= N < 2^(2∗h) − 1，由此推出 h ≈ logN。这意味着红黑树增删查改最坏也就是走最长路径 2 ∗ logN，那么时间复杂度还是 O(logN)。
说明：我们以实现一个键值对（key_value）类型的红黑树，且数据不支持冗余。
对于结点，我们需要一个 pair 来存储键值对；left 指针指向左孩子结点；right 指针指向右孩子结点；color 变量存储结点颜色；后面插入结点时，如果需要调整平衡，则要频繁地访问父亲结点，所以还需要一个 parent 指针指向父亲结点（与 AVL 树相同）。
由于结点颜色只有黑或者红，而 enum（枚举类型）可以用于定义固定集合常量，所以可以将结点颜色存储在一个枚举类型中。
节点结构：
template<class K, class V> class RBTree {
typedef RBTreeNode<K, V> Node;
public:
// ...
private:
Node* _root = nullptr; // 根结点
};
当为空树时，插入节点作为根结点且颜色为黑；不为空时，插入结点就要满足红黑树的规则。如果插入黑色结点，则会打破规则四（对于任意一个结点，从该结点到其所有 NULL 结点的简单路径上，均包含相同数量的黑色结点），所以，新插入的结点颜色一定为红色。
而对于新插入节点的父亲结点（parent）和父亲结点的父亲节点（grandfather）颜色，进一步分析，若 parent 为黑，则直接插入；若 parent 为红，则 grandfather 一定黑，插入新节点（红），违反规则，需要处理。此时，就需要根据父亲结点的兄弟结点的状态来进一步分情况讨论：
说明：下图中假设我们把新增结点标识为 c (cur)，c 的父亲标识为 p (parent)，p 的父亲标识为 g (grandfather)，p 的兄弟标识为 u (uncle)。
当新插入结点的 parent 为红，即出现连续的红色结点，需要处理，大概分为下面两种情况：
情况一又根据 u 结点是左孩子还是右孩子分为两种情况，但是，对于这两种情况处理方式相同，即将 g 变为红，u 和 p 变为黑。但是，需要注意一点：g 变为红色后，也有可能 g 的父亲结点为红色，所以需要继续向上处理，即 c 指向 g，p 和 g 同时更新，直到所有结点满足红黑树规则。
此时 u 结点对于红黑树调整没有影响，但是需要考虑 p 和 c 结点的位置。
对于旋转调整平衡我们在前面的 AVL 树中已经做了详细地介绍。
bool Insert(const pair<K, V>& kv) {
// -----------------处理空树-----------------------------
if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
// -------------非空，找新结点应该插入的位置---------------
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
} else if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
} else {
return false;
}
}
// -------------找到后开始插入----------------------
cur = new Node(kv);
cur->_col = RED; // -------------------新插入的节点一定为红，否则会改变黑节点的数
if (kv.first < parent->_kv.first) {
parent->_left = cur;
} else {
parent->_right = cur;
}
// -------------------链接父亲节点---------------------
cur->_parent = parent;
// -------------------当出现连续的红色结点，开始调整------------------------
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
// -------------处理所有 p 为左孩子的情况---------------------------
if (parent == grandfather->_left) {
// g // p u
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 (cur == parent->_left) {
// g // p u // c
RotateR(grandfather); // ---------右旋
// -----------变色--------------------
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g // p u // c
RotateL(parent); // --------------左旋
RotateR(grandfather); // ---------右旋
// -----------变色--------------------
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
} else // ---------------------------处理所有 p 为右孩子的情况
{
// g // u p
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 (cur == parent->_right) {
// g // u p // c
RotateL(grandfather); // --------------左旋
// -----------变色--------------------
parent->_col = BLACK;
grandfather->_col = RED;
} else {
// g // u p // c
RotateR(parent); // ---------右旋
RotateL(grandfather); // --------------左旋
// -----------变色--------------------
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK; // ----------------------统一将修改根结点颜色
return true;
}
相比于 AVL 树，旋转代码只需要去掉修改平衡因子的代码即可。
void RotateL(Node* parent) {
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
Node* pParent = parent->_parent;
// --------------连接 parent 与 SubRL----------------
parent->_right = SubRL;
if (SubRL) SubRL->_parent = parent;
// --------------连接 parent 与 SubR----------------
SubR->_left = parent;
parent->_parent = SubR;
// -----------------------连接 SubR 与 pParent
if (pParent == nullptr) // -------------------判断 parent 是否为根结点
{
_root = SubR;
SubR->_parent = nullptr;
} else {
if (parent == pParent->_left) {
pParent->_left = SubR;
} else {
pParent->_right = SubR;
}
SubR->_parent = pParent;
}
}
void RotateR(Node* parent) {
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
Node* pParent = parent->_parent;
// ----------------------连接 SubLR 与 parent-----------------------
parent->_left = SubLR;
if (SubLR) SubLR->_parent = parent;
// ----------------------连接 SubL 与 parent-----------------------
SubL->_right = parent;
parent->_parent = SubL;
// -----------------------连接 SubL 与 pParent
if (parent == _root) // -------------------判断 parent 是否为根结点
{
_root = SubL;
SubL->_parent = nullptr;
} else {
if (pParent->_left == parent) {
pParent->_left = SubL;
} else {
pParent->_right = SubL;
}
SubL->_parent = pParent;
}
}
遍历红黑树即可。
Node* Find(const K& key) {
Node* cur = _root;
while (cur) {
if (cur->_kv.first < key) {
cur = cur->_right;
} else if (cur->_kv.first > key) {
cur = cur->_left;
} else // --------------------找到了
{
return cur;
}
}
return nullptr;
}
bool IsBalanceTree() {
if (_root == nullptr) //--------------空树也是红黑树
{
return true;
}
if (_root->_col == RED) // -------------根结点为红色
{
return false;
}
int hb = CountBlackNode(); // --------------获取基准值
return _IsbalanceTree(_root, 0, hb); // ------------调用子函数
}
// ---------------按左边或者最右边一条路径来统计黑色节点的数量，作为标准----------------------
int CountBlackNode() {
Node* cur = _root;
int count = 0;
while (cur) {
if (cur->_col == BLACK) {
count++;
}
cur = cur->_left;
}
return count;
}
// 将每一条路径上的黑色节点数作为一个参数，将上面得到的黑色节点数（基准）作为参数用来和 blacknum 做对比
bool _IsbalanceTree(Node* root, int balackNum, int hb) {
if (root == nullptr) {
// ------------------前序遍历走到空时，意味着一条路径走完了---------------------
if (balackNum != hb) {
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) {
balackNum++;
}
return _IsbalanceTree(root->_left, balackNum, hb) && _IsbalanceTree(root->_right, balackNum, hb);
}