红黑树(red-black tree)是一棵二叉搜索树,每个结点多存一位颜色。它不追求 AVL 那种"左右高度差不超过 1"的精确平衡,而是用几条颜色约束把树高压住。这些约束读起来抽象,但每一条都能翻译成一句可检查的话。
五条性质与 NIL
课件列了 4 条规则,并说明《算法导论》等书另外补了一条叶子(NIL)为黑。合起来完整的表述是:
- 每个结点不是红色就是黑色;
- 根结点是黑色;
- 红结点的两个孩子必须是黑色,也就是任意一条路径上不会出现连续的红结点;
- 对任意结点,从它出发到所有空指针(NIL)的每条简单路径上,黑结点数量相同;
- NIL 本身算黑结点。
第 5 条的作用是给第 4 条的"所有路径"一个明确终点。课件说得很清楚:这里的叶子不是通常意义上的叶子结点,而是空结点,有些书叫它外部结点;真正实现时用 nullptr 充当 NIL,不必为它分配结点。

把这五条压缩成两句:红不能连,黑要均分。其余三条是为了让这两句能写下来、算清楚。
最长路径为什么不超过最短的两倍
设黑高 black height 为 bh,指从根到某个 NIL 的路径上的黑结点数量(含根,不含终点的 NIL)。由第 4 条,所有路径的黑结点数量相同。第 5 条只用来给"所有路径"一个明确终点,数黑高时把 NIL 略去,这样下面算结点数才对得上。
最短路径只能是全黑:每条路径固定有 bh 个黑结点,长度不可能低于 bh;一条不含红结点的路径正好达到 bh。
最长的路径只能一黑一红交替:由第 3 条,红结点不能相邻;又由第 4 条,每条路径的黑结点数固定。路径以黑结点开头(根是黑的),所以红结点的个数不可能超过黑结点的个数,最长就是 bh 个黑配 bh 个红,长度 2*bh。

任意路径的长度 x 落在 bh ≤ x ≤ 2*bh。理论上全黑最短路径和一黑一红最长路径不一定同时出现,但只要规则成立,界限就在那里。
结点数 N 与黑高之间的关系也能估出来:黑高为 bh 的树至少有 2^bh - 1 个结点(把它当成一棵满二叉树来数黑结点),于是 bh ≤ log₂(N+1),最长路径不超过 2 log₂(N+1)。增删查改最坏走最长路径,复杂度仍是 O(logN)。课件给的不等式 2^h - 1 ≤ N < 2^(2h) - 1 就是这个意思,只是把 h 当成了最短路径(黑高)来用。
新结点涂红,把难修的问题换成好修的
插入按二叉搜索树规则走位,挂上去之后只需要检查颜色。两种情况先定下来:
- 空树插入,新结点是唯一的结点,也是根,必须涂黑;
- 非空树插入,新结点一律涂红。
第二条的理由是:涂黑会让它所在的那条路径凭空多一个黑结点,第 4 条当场被破坏,而第 4 条极难修,只能靠旋转"借黑还黑";涂红不参与黑高计数,最坏只是和父亲凑成一对红,问题局限在 cur、parent、grand、uncle 四个结点里。这一次选择把违规从难修的第 4 条挪到了好修的第 3 条。
挂上之后如果父亲是黑的,什么都没违反,插入结束。父亲是红时才需要修。此时 p 红、c 红、g 必黑(g 若也红,说明更早一步就已经违规),三色固定,唯一的变数是叔叔 u。
叔叔 u | p、c 的位置 | 动作 | 变色 | 之后 |
|---|---|---|---|---|
| 存在且为红 | 任意 | 不旋转 | p、u 涂黑,g 涂红 | 把 g 当作新的 c 继续往上 |
| 不存在或为黑 | p 是 g 的左,c 是 p 的左(LL) | 以 g 右单旋 | p 黑,g 红 | 结束 |
| 不存在或为黑 | p 是 g 的右,c 是 p 的右(RR) | 以 g 左单旋 | p 黑,g 红 | 结束 |
| 不存在或为黑 | p 是 g 的左,c 是 p 的右(LR) | 先以 p 左旋,再以 g 右旋 | c 黑,g 红 | 结束 |
| 不存在或为黑 | p 是 g 的右,c 是 p 的左(RL) | 先以 p 右旋,再以 g 左旋 | c 黑,g 红 | 结束 |
叔叔为红时为什么敢只变色?以 g 为根的子树原来每条路径黑高都是 bh。p 那条路径因为 p 转黑多了一个黑,u 那条也一样;g 自己从黑转红,相当于两条路径上都扣掉一个。一加一减,两边回到 bh,连续红也没了,因为 p 已经变黑。g 变红后如果它的父亲也是红,就冒出一对新的连续红,所以要把 g 当作新的 c 往上抛。

叔叔不存在或为黑时,单纯变色不够:p 必须变黑才能消灭连续红,但 p 转黑会让这条路径黑高加 1,叔叔是黑的,没有第二个红结点一起变黑来对冲。账做不平,只能旋转。两种情况要先分清:叔叔不存在,c 一定是新插入的结点;叔叔存在且为黑,c 一定不是新结点,它原本是黑的,是在它子树里插入后触发变色被"上提"上来的。结论一样,动作按形状分。

折线(LR/RL)不能直接对 g 单旋,因为 p 会被甩到一边,c 还挂在 p 的内侧,连续红没解决。先在里层把折线掰直,再在外层转一次。

写代码时三件事要记住:g 每轮重新取,不能缓存,因为走变色分支后 parent 和 cur 都换了;单旋、双旋之后直接 break,新根是黑的,往上不会再有连续红;while 结束后无条件把 _root 刷黑,兜住"根被涂红"这种情况。
插入与旋转的代码
结点比二叉搜索树多一位颜色和一个父指针:
#include <cassert>
#include <iostream>
#include <utility>
enum Colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
std::pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const std::pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)
{}
};课件的构造函数没有给 _col 赋初值,颜色是在 Insert 里 new 之后补一句 cur->_col = RED; 设的。因为每条创建路径都补了,程序不会出错;但把颜色写进初始化列表更稳,以后多一条创建路径也不会忘记。
下面几段是 template<class K, class V> class RBTree 的成员函数,Node 是结点的别名,_root 是根指针。旋转与 AVL 树完全一样,只是不用改平衡因子:
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;
}
}
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 (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}旋转不碰数据、不动颜色,只重排父子关系。它敢随便转,是因为旋转不改变中序遍历序列:以左旋为例,subRL 夹在 parent 和 subR 之间,转完正好挂回 parent 的右边,相对顺序没变。
bool Insert(const std::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* grand = parent->_parent;
if (parent == grand->_left)
{
Node* uncle = grand->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grand->_col = RED;
cur = grand;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grand);
parent->_col = BLACK;
grand->_col = RED;
}
else
{
RotateL(parent);
RotateR(grand);
cur->_col = BLACK;
grand->_col = RED;
}
break;
}
}
else
{
Node* uncle = grand->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grand->_col = RED;
cur = grand;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grand);
parent->_col = BLACK;
grand->_col = RED;
}
else
{
RotateR(parent);
RotateL(grand);
cur->_col = BLACK;
grand->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
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",编号重了。按动作分,插入修复实际只有三类:只变色、单旋加变色、双旋加变色,读的时候别以为同一件事讲了两遍。
一次插入最多做一次旋转(单旋算一次,双旋算一次),但变色可能发生多次。红黑树"旋转少"就体现在这里:旋转有硬上界,变色很便宜。
验证:规则能查,路径倍数不能查
自己实现的树对不对,不要去量最长路径和最短路径的比值。课件这点说得很准:即使比值不超过 2,颜色也可能不合法,今天没出问题,明天再插一个就炸。正确做法是逐条检查第 2、3、4 条:
- 第 2 条查根的颜色;
- 第 3 条前序遍历,遇到红结点查它的父亲——孩子有两个且不一定存在,查父亲更省事;
- 第 4 条前序遍历,用形参记下从根到当前结点的黑结点数量,走到空就得到一条路径的计数,再和参考值比较。
参考值可以取最左路径的黑结点数,因为第 4 条要求所有路径相等,拿哪条当标准都一样。

bool IsBalance() const
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
return false;
}
int refNum = 0;
const Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
private:
bool Check(const Node* root, int blackNum, int refNum) const
{
if (root == nullptr)
{
return blackNum == refNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
std::cout << root->_kv.first << " 连续红色结点\n";
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}blackNum 必须传值,不能传引用。左右两条分支共用一份计数的话,走完左边那份会被右边接着用,两条路径的数字混在一起,比较必然错。refNum 用最左路径的黑结点数,Check 从 0 开始累加,到空时刚好和它相等。
判断连续红时反过来查父亲,比查两个孩子省事。根结点没有父亲,所以 Check 在递归里要先保证当前结点是红的才有父亲——根是黑的,第一次调用不会踩空;更稳的写法是加一句 root->_parent &&。
和 AVL 的取舍,以及它在 STL 与内核里的位置
AVL 用平衡因子把左右高度差锁在 1 以内,树更矮,查找更快,但插入删除要维护更严格的账本,旋转更多。红黑树只承诺最长路径不超过最短路径的两倍,树可以稍高,查找略慢,换来插入最多两次旋转、删除最多三次。
两者都是 O(logN),效率在同一档,区别在成本放在哪:读多写少偏 AVL,读写混合偏红黑树。
std::map 和 std::set 的底层通常是红黑树(cppreference 的 std::map 页面写的是 "usually",标准没有强制实现方式)。Linux 内核的红黑树用来管虚拟内存区域、高精度定时器和 epoll 的文件描述符,理由一致:这些场景插入删除频繁,需要的是"改结构便宜且延迟稳定",而不是查找再快一点。
删除这部分课件明确说不讲,可以参考《算法导论》或《STL源码剖析》。难点方向可以先用一句话记住:删红结点几乎无代价,它不参与黑高计数;删黑结点必然让某条路径少一个黑,缺口只能找兄弟"借黑",或者靠旋转把缺口往上顶。组合比插入多得多,判断顺序还是那套——看兄弟颜色、看侄子颜色、决定单旋双旋、决定是否继续向上。
还没有评论 — 第一条由你来留。