红黑树的概念
红黑树是一种自平衡二叉搜索树,在每个节点上附加一个颜色位(红色或黑色)。通过对路径上节点颜色的约束,它确保没有一条路径的长度会超过其他路径的两倍,从而维持树的近似平衡。
核心规则
- 节点要么是红色,要么是黑色。
- 根节点必须是黑色。
- 红色节点的两个子节点都必须是黑色(即不会出现连续的红色节点)。
- 从任一节点到其所有后代叶子节点(NIL)的简单路径上,黑色节点的数量相同。
在《算法导论》的叙述里,通常还补充'每个叶子节点(NIL)都是黑色的'。这里的叶子节点指空指针(外部结点),实际编码时用 nullptr 表示,知道这个约定就够了。
为什么最长路径不超过最短路径的 2 倍?
根据规则 4,从根到 NIL 的所有路径含有同样多的黑色节点。极端情况下,最短路径全部由黑色节点组成,设其长度为 bh(黑高)。
规则 2 和 3 禁止出现连续红色节点,所以最长的路径只能是一黑一红交替出现,长度最多约为 2 * bh。
这样一来,任意路径长度 h 都满足 bh <= h <= 2 * bh,树的高度始终被压制在对数级别。
效率分析
设 N 为节点总数,h 为最短路径长度:
2^h - 1 <= N <= 2^(2*h) - 1
由此推出 h ≈ logN。红黑树的增删查操作在最坏情况下需要走过最长路径 2*logN,时间复杂度仍是 O(logN)。
与 AVL 树相比,红黑树的平衡条件更'模糊'。AVL 树用高度差直接约束,很直观;红黑树则靠颜色间接达成近似平衡,两者的效率在同一个量级。红黑树在插入时旋转次数更少,因为它对平衡的控制没那么严格,更适应插入频率高的场景。
红黑树的实现
结构定义
为了支持修复平衡时的向上回溯,节点中必须包含指向父节点的指针。下面是基于键值对的模板定义:
// 枚举值表示颜色
enum Colour {
RED,
BLACK
};
// 红黑树节点模板
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent; // 调整平衡需要 parent 指针
Colour _col;
RBTreeNode(const pair<K, V>& kv)
:_kv(kv), _left(nullptr), _right(nullptr), _parent() {}
};
< , >
{
RBTreeNode<K, V> Node;
:
:
Node* _root = ;
};


