C++进阶6：红黑树原理
·
目录
一、红黑树的概念
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过在插入和删除操作中维护一系列颜色规则，确保树的高度始终保持在对数级别，从而保证了高效的查找、插入和删除性能。
1.1 红黑树的规则
一棵红黑树必须满足以下 4 条核心性质：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色。
- 如果一个节点是红色，则它的两个子节点都是黑色（即不能有两个连续的红色节点）。
- 从任一节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。注意这里的一条路径是从根节点一直走到NULL。
1.2 红黑树如何确保最长路径不超过最短路径的 2 倍？
- 最短路径：全为黑色节点的路径。
- 最长路径：红黑交替的路径。
- 根据性质 4，红色节点不能连续出现，因此最长路径的长度不会超过最短路径的 2 倍。这保证了红黑树的平衡性，其时间复杂度稳定在 O (log n)。
1.3 红黑树的效率
- 时间复杂度：查找、插入、删除操作的平均和最坏时间复杂度均为 O (log n)。
- 空间复杂度：O (n)，用于存储 n 个节点。
- 与 AVL 树相比，红黑树牺牲了部分平衡性，换取了更少的旋转操作，在频繁插入删除的场景下性能更优。
二、红黑树的实现
2.1 红黑树的结构
在 C++ 中，我们可以用结构体来定义红黑树的节点：
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:
private:
Node* _root = nullptr;
};2.2 红黑树的插入
2.2.1 红黑树插入一个值的大概过程
- 按照二叉搜索树的规则，将新节点插入到合适的位置，并将其颜色设为红色。(因为所有路径的黑色节点都必须保持一致，如果插入的节点是黑色会非常麻烦)
- 检查插入后是否违反了红黑树的性质。
- 如果违反了性质，则通过变色和旋转操作进行修复，直到所有性质都得到满足。
2.2.2 情况 1：变色
当新节点的父节点和叔叔节点都是红色时：
- 将父节点和叔叔节点变为黑色。
- 将祖父节点变为红色。
- 将祖父节点作为新的节点，继续向上检查。
cur作为新插入的节点这里只是一种概述情况，但这种逻辑是只要节点出现这种情况就如此处理，但我们需要注意如果我们变化的祖父节点是根节点，就违反了红黑树的逻辑，所以无论如何变化我们都要加上一句让根节点始终保持黑色。（可以有两个连续的根节点）
2.2.3 情况 2：单旋 + 变色
当新节点的父节点是红色，叔叔节点是黑色或者不存在。叔叔不存在，则c一定是新增结点，叔叔存在且为黑，则 c一定不是新增，c之前是黑色的，是在c的⼦树中插入，符合情况1，变色将c从黑色变成红色，更新上来的：
2.2.4 情况 2：双旋 + 变色
当新节点的父节点是红色，叔叔节点是黑色或者不存在。叔叔不存在，则c一定是新增结点，叔叔存在且为黑，则 c一定不是新增，c之前是黑色的，是在c的⼦树中插入，符合情况1，变色将c从黑色变成红色，更新上来的：
2.3 红黑树的插入代码实现
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;
// 父亲是红色，出现连续的红色节点，需要处理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
// g
// p u
Node* uncle = grandfather->_right;
//情况1
if (uncle && uncle->_col == RED)
{
// 变色
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else
{
//情况2
if (cur == parent->_left)
{
// g
// p u
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情况3
// g
// p u
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红，-》变色即可
//情况1
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 叔叔不存在，或者存在且为黑
{
// 情况二：叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
//情况2
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
//情况3
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* pParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
subL->_parent = pParent;
}
}
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 (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}2.4 红黑树的查找
红黑树的查找操作与普通二叉搜索树完全一致：
- 从根节点开始，若查找值小于当前节点，则向左子树查找；若大于，则向右子树查找。
- 直到找到目标值或到达叶子节点（NIL 节点）。
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;
}2.5 红黑树的验证
这里获取最长路径和最短路径，检查最长路径不超过最短路径的2倍是不可行的，因为就算满足这个条件，红黑树也可能颜色不满足规则，当前暂时没出问题，后续继续插入还是会出问题的。所以我们还是去检查4点规则，满足这4点规则，⼀定能保证最长路径不超过最短路径的2倍。
1. 规则1枚举颜色类型，天然实现保证了颜色不是黑色就是红色
2. 规则2直接检查根即可
3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检查父亲的颜色就方便多了
4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色节点数量)，前序遍历遇到黑色结点就++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点数量作为参考值，依次比较即可。
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);
}
private:
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 前序遍历走到空时，意味着一条路径走完了
//cout << blackNum << endl;
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);
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)