一、定义
红黑树是带有颜色约束的自平衡二叉搜索树，每个节点存储颜色（红色 / 黑色），通过着色、旋转、变色操作，保证树大致平衡，查找、插入、删除时间复杂度 \(O(\log n)\)，C++ STL 的map/set底层就是红黑树。（空树也算红黑树）
举例
二、性质
1. 性质
1.1 每个节点只能是红色或者黑色。
1.2 根节点一定是黑色。
1.3 所有空叶子结点都是黑色。
1.4 如果一个节点是红色，那么它的两个子节点必须都是黑色。即不能出现连续的红色节点。
1.5 对于任意一个节点，从该节点出发，到达它每一个空叶子的所有路径上，包含的黑色节点数目相同，这个数值称为该节点的黑高。
2. 结果
从根到 NIL 叶子，最长路径节点数 ≤ 2 × 最短路径节点数
即最长路径的长度不会超过最短路径的 2 倍
原因：
最短路径 : 路径上没有任何红色节点，全是黑色节点。 路径总节点数 =h(black)
最长路径 : 红黑交替排列：黑‑红‑黑‑红……，红色尽可能多。 因为不能连续红，每一个红节点后面必须搭配一个黑节点。
最多：每一个黑色后面跟一个红色。 最长路径节点数 =2*h(black)
三、结构
1. 枚举表示节点的颜色
2. 节点的结构
包含节点的值，左/右/父节点指针，节点颜色
3. 树的结构
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
......// 一些方法的实现
private:
Node* _root = nullptr;
};
四、重要接口
1. 对外
2. 内部
2.1 旋转相关
2.2 递归辅助相关
五、一些接口的模拟实现
1. 左单旋/右单旋
上一期我们已经实现过，不再赘述
2. 遍历
3. 检查
红黑树合法性检查首先判断空树合法、根节点必须为黑色，再以最左路径的黑色节点数作为基准黑高；通过递归遍历整棵树，全程禁止出现连续红色节点，同时统计每条路径的黑色节点数量，保证所有叶子路径的黑高完全一致，全部条件满足即为合法红黑树。
4. 插入（重点）
为空节点
不为空时
它的父亲是黑色时
直接插入一个红色的节点
它的父亲是红色时判断它叔叔的情况
叔叔在右时
叔叔可能是红色，黑色，或者不存在
叔叔在左时
思路同理不再赘述
完整代码如下
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root= new Node(kv);
_root->_col = BLACK;
return true;
}
//找插入的位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first == kv.first)
{
return false;
}
else if (kv.first < cur->_kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
parent = cur;
cur = cur->_right;
}
}
//插入红色的新增节点
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* grandparent = parent->_parent;
if (grandparent->_left==parent)
{
// 爷爷
//父亲 叔叔
Node* ancle = grandparent->_right;
if (ancle && ancle->_col == RED)
{
parent->_col = BLACK;
ancle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_left == cur)
{
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
else
{
// 爷爷
//叔叔 父亲
Node* ancle = grandparent->_left;
if (ancle && ancle->_col == RED)
{
parent->_col = BLACK;
ancle->_col = BLACK;
grandparent->_col = RED;
//继续向上处理
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
六、总结
1. 对比红黑树和AVL树
2. 优点
1. 时间复杂度稳定：查找、插入、删除均为 O(log n）。
2. 旋转次数少，执行效率高：属于弱平衡树，不要求严格平衡；插入最多 2 次旋转，删除最多 3 次旋转，大量操作只需要变色，不需要旋转。对比 AVL 树，增删频繁时性能更好。
3. 工程实用性强：C++ STL 的map / set / multimap / multiset底层就是红黑树，工业界广泛使用。
4. 最坏情况可控：树高保证最长路径 ≤ 2× 最短路径，不会退化成为链表，避免 BST 最坏O(n)的情况。
3. 缺点
1. 实现复杂。插入逻辑已经比较麻烦，删除逻辑尤为复杂，要处理大量变色、旋转分支，手写代码容易出错。
2. 弱平衡，树高比 AVL 更高。在以查找为主、插入删除很少的场景，AVL 树高度更低，查找速度理论上优于红黑树。
3. 每个节点需要额外存储颜色信息，每个节点多 1bit 颜色开销。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2502_94372528/article/details/163572382
