【C++】 深入理解红黑树：实现与原理全解

RBTree · e4a5c71 · 加油少年/CCCCC – Gitee.com

  一、红黑树是什么？解决了什么问题？

1. 二叉搜索树（BST）

二叉搜索树满足：

• 左子树所有节点 < 根节点
• 右子树所有节点 > 根节点
• 左右子树也是二叉搜索树

致命缺陷：数据有序插入时，BST 会退化成链表，查找 / 插入 / 删除复杂度从 O(logn) 暴跌到 O(n)。

2. 平衡二叉树

        为了解决退化问题，诞生了平衡二叉树：左右子树高度差不超过 1。

        但AVL 树（严格平衡）旋转次数过多，插入删除性能差。

3. 红黑树：非严格平衡的最优解

        红黑树是近似平衡的二叉搜索树，通过颜色规则 + 旋转保证：

        从根到叶子的最长路径不超过最短路径的 2 倍

思考⼀下，红⿊树如何确保最⻓路径不超过最短路径的2倍的？

        • 从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(black height)。

        • 任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh。

        • 综合红⿊树的规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2*bh。

时间复杂度稳定 O(logn)，插入 / 删除旋转远少于 AVL 树，工程实用性拉满。

  二、红黑树的 5 大核心性质  

这是红黑树的底层基石，所有操作都围绕维护这 5 条性质展开：

关键术语：NIL 节点红黑树不使用nullptr，而是用统一的黑色空节点 NIL，简化边界判断。

  三、红黑树的代码实现  

1. 红黑树节点设计

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) // ✅ 新插入节点默认为红色
{}
};

2.  红黑树整体结构

template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
private:
Node* _root = nullptr;
};

3. 插入逻辑（核心）

1️⃣ 普通 BST 插入

if (_root == nullptr) {
_root = new Node(kv);
_root->_col = BLACK;//根结点是⿊⾊的
return true;
}

2️⃣ 找到插入位置

Node* parent = nullptr;
Node* cur = _root;
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 false; // 去重
}
}

3️⃣ 插入新节点（红色）

cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

插入后的调整（重点 ⭐）

情况

叔叔颜色

处理方式

✅ 情况1：叔叔为红（变色）

if (uncle && uncle->_col == RED)//情况1：变⾊ c为红，p为红，g为⿊，u存在且为红
{
// g
// p u
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}

✅ 情况2：单旋 + 变色

左左 → 右旋

if (cur == parent->_left) // 情况2：单旋+变⾊ c为红，p为红，g为⿊，u不存在或者u存在且为⿊
{
// g
// p u
//c
// 右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}

右右 → 左旋

if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}

✅ 情况3：双旋 + 变色

// g
// p u
// c
// 左右单旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;

// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;

  四、红黑树合法性验证  

1️⃣ 检查黑色节点数量

bool IsBalance()
{
if (_root == nullptr)
return true;

if (_root->_col == RED)
return false;

// 黑色节点数量参考值
Node* leftMost = _root;
int blackRef = 0;
while (leftMost)
{
if (leftMost->_col == BLACK)
++blackRef;

leftMost = leftMost->_left;
}

return Check(_root, 0, blackRef);
}

2️⃣ 递归验证

bool Check(Node* cur, int blackNum, const int blackNumRef)//递归处理，比较每条路径的黑色节点数量
{
if (cur == nullptr)
{
if (blackNum != blackNumRef)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}

return true;
}
//错误情况，出现连续红色节点
if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "->" << "连续的红色节点" << endl;
return false;
}

if (cur->_col == BLACK)
++blackNum;

return Check(cur->_left, blackNum, blackNumRef)
&& Check(cur->_right, blackNum, blackNumRef);
}

  五、详细代码  

#pragma once
// 枚举值表示颜色
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)
{}
};

template<class K,class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
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 (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
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;
//确定完插入位置
//⾮空树插⼊后，新增结点必须红⾊结点，如果⽗亲结点是红⾊的，则违反规则3
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// 叔叔存在且为红->变色
if (uncle && uncle->_col == RED)//情况1：变⾊ c为红，p为红，g为⿊，u存在且为红
{
// g
// p u
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}

else
{
if (cur == parent->_left) // 情况2：单旋+变⾊ c为红，p为红，g为⿊，u不存在或者u存在且为⿊
{
// g
// p u
//c
// 右单旋
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else //情况3：双旋+变⾊ c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，
{
// g
// p u
// c
// 左右单旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // grandfather->_right == parent
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变色即可
if (uncle && uncle->_col == RED)//情况1：变⾊ c为红，p为红，g为⿊，u存在且为红
{
parent->_col = BLACK;
uncle ->_col = BLACK;
grandfather->_col = RED;

// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else// 情况2：单旋+变⾊ c为红，p为红，g为⿊，u不存在或者u存在且为⿊
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色

if (cur == parent->_right)
{
// g
// u p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} //情况3：双旋+变⾊ c为红，p为红，g为⿊，u不存在或者u存在且为⿊，u不存在，
else
{// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == nullptr)
return true;

if (_root->_col == RED)
return false;

// 黑色节点数量参考值
Node* leftMost = _root;
int blackRef = 0;
while (leftMost)
{
if (leftMost->_col == BLACK)
++blackRef;

leftMost = leftMost->_left;
}

return Check(_root, 0, blackRef);
}

int Height()
{
return _Height(_root);
}

int Size()
{
return _Size(_root);
}

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;
}
private:
int _Size(Node* root)
{
return root == nullptr ? 0 : _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;
}

bool Check(Node* cur, int blackNum, const int blackNumRef)//递归处理，比较每条路径的黑色节点数量
{
if (cur == nullptr)
{
if (blackNum != blackNumRef)
{
cout << "黑色节点的数量不相等" << endl;
return false;
}

return true;
}
//错误情况，出现连续红色节点
if (cur->_col == RED && cur->_parent && cur->_parent->_col == RED)
{
cout << cur->_kv.first << "->" << "连续的红色节点" << endl;
return false;
}

if (cur->_col == BLACK)
++blackNum;

return Check(cur->_left, blackNum, blackNumRef)
&& Check(cur->_right, blackNum, blackNumRef);
}

void _InOrder(Node* root)
{
if (root == nullptr)
return;

_InOrder(root->_left);
cout << root->_kv.first << " ";
//cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}

void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
subLR->_parent = parent;

Node* parentParent = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}

subL->_parent = parentParent;
}
}

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;

Node* parentParent = parent->_parent;

subR->_left = parent;
parent->_parent = subR;

if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}

subR->_parent = parentParent;
}
}
private:
Node* _root = nullptr;
};