搜索树依靠键值次序寻找数据,但次序本身允许整棵树退化成长链。AVL 树直接限制相邻子树的高度;红黑树则为每个节点增加一个颜色位,约束路径上黑节点的分布。左右子树的普通高度未必相同。不过,每条路径的黑节点数相同,而且红节点不能连续出现。这两个条件合起来,就能防止某条路径无限制地变长。
颜色不属于集合所存储的数据:改变颜色不会改变键值。它的作用,是提供一个可以在更新附近修复的不变量。本节先证明高度界,再逐步推导插入修复,说明为什么一次插入可能沿途重新着色多个祖先,却最多只需两次旋转。删除需要另一套修复论证,不在本节范围内。
把空子链接也纳入定义
假设键值互不相同,并具有一致的全序。每个节点左子树的键都比它小,右子树的键都比它大。插入已存在的键不改变集合。普通搜索只按这些大小关系选择方向,不需要查看颜色。
定义 15.2.1
(内部节点、外部 NIL 叶与黑高度)
每个存储键值的节点都是内部节点,颜色为红或黑。每条空子链接在数学上通向一个黑色的外部叶 NIL。程序可以共用一个哨兵对象,但数学树中每条空链接仍代表一个独立的外部叶位置。
红黑搜索树须同时满足以下条件:
- 所有外部
NIL叶都是黑色。 - 非空树的根是黑色。
- 每个红色内部节点的子节点都是黑色。
- 对每个内部节点,从它向下到各外部叶的路径,在离开该节点之后所遇到的黑节点数相同,并计入末端的
NIL。
这个共同数目称为节点的黑高度 。约定 。因此,内部叶本身无论红黑,黑高度都是 1。对内部节点 及其任一子节点 ,
指示函数在子节点为黑色时等于 1,包括 NIL;子节点为红色时等于 0。它补计的是 没有计入的子节点本身。
两个内部子节点的黑高度可以不同:黑色子节点还要计入自己的颜色,红色子节点则不用。必须相等的是沿两条子链接向下的黑节点总贡献。黑节点数相等,也不表示两边存储的键数相等。
插入修复期间,我们暂时允许根是红色,或有一个红节点的父节点也是红色。这些是中间状态,并非完成后的合法形式。搜索次序及路径黑节点数相等的条件,则会一直保留。
为什么颜色能限制搜索深度
以 表示某子树的内部节点数;外部叶不计入。设 为根到外部叶的路径中,最多的边数;空树另设 。成功搜索最多访问 个内部节点。失败搜索最多比较 个键,然后抵达外部叶。
定理 15.2.2
(红黑树的高度界)
一棵存储 个键的合法红黑树满足
所以最坏情况下的搜索比较次数为 。
证明
(把黑层数与边数分开计算)
先对子树大小作归纳,证明 。在 NIL 处,两边都是零。若 是内部节点,两个子节点的黑高度都至少是 。由归纳假设,
现在考虑非空树的一条最长根至 NIL 路径。不计根后,路径上有 个节点位置,最后一个是黑色 NIL。每个红节点后面必有黑节点;由于红节点不能连续,不同红节点所配对的下一个黑节点也不同。因此至少有 个位置是黑色。它们的数目正是 ,故 。
再结合 ,就得到所需高度界。空树的情况另外直接成立。
这是最坏情况的上界,不是说每次搜索都要比较同样多次。红黑树的形状限制可以比 AVL 树宽松,但仍然排除了线性高度的长链。
新节点先用红色,保住黑节点数
先按普通搜索树的比较规则找插入位置。如果键不存在,就把相应外部叶换成新的红色节点 ,并让它有两个黑色 NIL 子节点。原来经过这条链接的路径计入一个黑色外部叶;新路径计入一个红节点,再计入一个黑色外部叶,所以黑节点数不变。
若 的父节点是黑色,各项条件已经成立,唯一例外是 自己可能就是根。最后把根涂黑即可。若父节点 是红色,就出现红红相邻。插入前根是黑色,而修复循环只在父节点为红色时继续,所以此时父节点一定有内部祖父节点 。在下面的不变量下, 必为黑色。
父节点的兄弟称为叔节点 。不存在的叔节点就是黑色 NIL,判断情况时不能略去它。先分析 在 左边的情况;另一边只需把左右完全对调。
常见错误
(不存在的叔节点是黑色)
在 10B(5R,-) 中,把 7 插入 5 之下,叔节点是 10 的空右孩子指针。它是黑色 NIL,须先左旋 5,再把 7 染黑、10 染红,并右旋 10。
证明透视
修复循环只保留一个移动中的缺陷
每次迭代开始时, 是红色。搜索次序和各路径黑节点数相等的条件都成立。唯一可能的红红相邻,是 与父节点之间;根也暂时允许是红色。其他红节点的子节点都是黑色。
若循环执行,父节点就是红色,因此 不是根。祖父存在而且是黑色:否则父与祖父之间还会有另一条红红边。下面每种修复都会保留这些性质、把唯一可能的缺陷向上移,或把它完全消除。这比“小图看起来平衡”是一个更具体的正确性保证。
叔节点是红色:把缺陷移到上面
若 是红色,把 和 改成黑色,把 改成红色,然后令 继续。原来经过这个子树的每条路径,计入黑色 和一个红色子节点;现在则计入红色 和一个黑色子节点。总黑贡献不变。
因为 和 原来是红色,它们的子节点原来都应为黑色,只有涉及 的那条红红边是允许的暂时例外。当 改成黑色,这条边就不再违规。新改红的 有黑色子节点,它唯一可能的冲突是与自己的父节点相邻,刚好成为下一轮所处理的缺陷。如果 是根,循环停止,最后把根涂黑即可。
所以,把这个子树的根 改红是必要步骤。若只把两个子节点改黑,却让 保持黑色,整个子树的黑贡献会增加一。当 不是全树的根时,祖先另一边的路径就可能不再与它相等。
叔节点是黑色:先把三角形变成直线
若叔节点为黑色,而 是左父节点的右子节点,两条红链接构成内侧三角形。先在 左旋,不改颜色。红色子节点升为红色父节点,原来的红色父节点成为它的左子节点,三角形就转成外侧直线。被旋转的两个节点都是红色,所以各路径的黑贡献不变。
现在考虑直线:红色 在黑色 的左边,而红色 在 的左边。把 改黑、 改红,再在 右旋。新子树根是 :
g(B) p(B)
/ \ / \
p(R) U becomes z(R) g(R)
/ \ / \ / \
z(R) C A B C U
/ \
A B
代表整个子树,不一定只有一个叶。它们的根都是黑色,也可能是 NIL。
证明透视
分别检查次序、颜色与黑节点数
旋转前后的中序次序都是 。旋转把 从 的右边移到 的左边,原有大小关系正好保证这个位置合法。没有键被丢失或重复。
为了检查黑节点数,从每个图示附挂子树的根开始,数到最后的外部叶,并且计入该附挂根本身。这些数目相同: 内的等式使 与 相同;红色 的等式又使它们与 相同;黑色 的等式再使它们与 相同。设共同数目为 。
修复前,整个图示子树的每条路径都计入黑色 ,再加上 。修复后,则计入黑色 ,再加上 。新改红的 和新的子树根 本身也满足路径等黑数。两个红节点 与 的子节点都是黑色。
最后,原子树根 是黑色,取代它的 也是黑色。祖先所见的黑贡献不变,也不会多出红红相邻。修复已经完成。三角形情况先做一次红红节点间的旋转后,就适用这个直线论证。
父节点在右侧时,用完全对称的操作:左内侧三角形先在父节点右旋,再在祖父左旋完成直线修复。大小关系及左右方向对调后,证明不变。
精确跟踪移动中的节点与父链接
以下伪代码以 RED、BLACK 表示颜色常量。root.parent 是黑色哨兵。每个内部节点有 left、right、parent 及 color 字段。NIL 永远是黑色,不会被重新着色。rotate_left(x) 与 rotate_right(x) 会在需要时更新全树根、受影响的父链接及被移动的中间子树。旋转本身不改颜色,但会保留搜索次序。
insert(key):
search for key from root
if key exists: return false
attach a new RED node z at the missing child link
set z.left = NIL and z.right = NIL
while z.parent.color == RED:
if z.parent == z.parent.parent.left:
u = z.parent.parent.right
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.right:
z = z.parent
rotate_left(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_right(z.parent.parent)
else:
u = z.parent.parent.left
if u.color == RED:
z.parent.color = BLACK
u.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.left:
z = z.parent
rotate_right(z)
z.parent.color = BLACK
z.parent.parent.color = RED
rotate_left(z.parent.parent)
root.color = BLACK
return true
三角形情况中,必须在旋转之前令 z = z.parent。旋转之后,原父节点成为较低的红节点;随后的 z.parent 才会指向中间键,也就是直线修复中应涂黑的节点。如果一直沿用已缓存而没有更新的父或祖父指针,就可能涂错节点或在错误位置旋转。
每次红叔节点修复都把 向上移两层。黑叔节点修复最多使用两次旋转,并消除缺陷;其后 的父节点是黑色,循环条件不再成立。因此循环必定终止。最后如有需要,把根改黑,会使全树每条路径都多计同一个黑节点,保持所有等式,并消除根的暂时例外。
寻找插入位置及向上修复的总时间是 。一次成功插入最多做两次旋转,但可能在 个祖先重新着色。两者是不同的操作计数,不能由旋转次数是常数就断言整次插入是常数时间。
定理 15.2.3
(插入保持红黑树不变量)
按上述过程在有效的红黑树中插入新键,必在有限步内结束,至多做两次旋转,并得到一棵有效的红黑树,其键为原有的键加上新键。所需时间为 。
证明
(把各种情形合成一次归纳)
第一次迭代之前,新的红节点不改变任何黑计数,唯一可能的红红边连接 与其父节点。每次迭代都由上文证明过的红叔节点或黑叔节点情形保持这项不变量,而循环至多做两次旋转就结束。结束时只可能剩下红色的根,把它染黑,使每条路径多一个黑节点。循环只走过新节点至多 个祖先。
先重新着色,再遇到三角形
例题 15.2.4
(在空树依次插入 10、5、15、1、2)
用 键颜色(左,右) 记录树,- 表示黑色外部叶;只有一个内部叶时,简写它的键与颜色。B 表示黑色,R 表示红色。
| 插入键 | 修复 | 完整结果 |
|---|---|---|
| 10 | 新根改黑 | 10B |
| 5 | 父节点 10 为黑色 | 10B(5R,-) |
| 15 | 父节点 10 为黑色 | 10B(5R,15R) |
| 1 | 父节点 5 与叔节点 15 都是红色:两者改黑,再恢复根的黑色 | 10B(5B(1R,-),15B) |
| 2 | 父节点 1 为红色,叔节点为 NIL,2 是内侧子节点:先在 1 左旋,再重新着色并在 5 右旋 | 10B(2B(1R,5R),15B) |
最后一次插入的局部次序是 。第一次旋转使 2 升到 1 上面;第二次再使它升到 5 上面。这次修复不改动以 15 为根的右子树。
最后从根 10 出发、不计根本身,每条路径都有两个黑节点位置。例如经过 2 和 1 的路径计入黑色 2 及外部 NIL;经过 15 的路径则计入黑色 15 及外部 NIL。根的黑高度因此是 2,但最长根至 NIL 路径有三条边。相等黑高度并不强迫普通路径长度相等。
例题 15.2.5
(按递增顺序插入 1、2、3、4)
依次插入 1、2 得 1B(-,2R)。插入 3 时,父节点 2 为红色,叔节点是 1 的空左指针,即黑色 NIL;3 是外侧孩子,所以把 2 染黑、1 染红并左旋 1,得 2B(1R,3R)。插入 4 时,父节点 3 与叔节点 1 都是红色:两者染黑、2 染红,再把根 2 染回黑色,得 2B(1B,3B(-,4R))。第四次插入时,重新着色传到根,整棵树的黑高度由 1 升至 2。
例题 15.2.6
(先重新着色,再在较高处旋转)
从有效的树 20B(10R(5B(2R,7R),15B),30B) 出发,把 1 插入为 2 的左孩子。父节点 2 与叔节点 7 都是红色:把它们染黑、5 染红,以 继续。它的父节点 10 为红色、叔节点 30 为黑色,而 5、10、20 排成左侧直线:把 10 染黑、20 染红并右旋 20。结果是 10B(5R(2B(1R,-),7B),20R(15B,30B))。
反例模式
新键一律涂黑,仍不能省去修复
先有一个黑键 10 及其两个外部叶。把 5 当作黑色左子节点插入。离开 10 后,左路径计入黑色 5 和黑色 NIL,右路径却只计入黑色 NIL:两边是 2 与 1。
虽然没有红红相邻,黑节点数相等的不变量已经被破坏。插入时先选红色,是为了保住黑节点数,再修复可能出现的局部红红冲突。
清楚界定这个实现的保证
这是一个有序集合的插入算法。它不保留插入次序,不会自动提供按任意排名的常数时间访问,也不表示存储数组或节点分配次序已经排序。中序遍历才提供键的排序次序。如果用作映射,更新已存在键的值不必改变形状或颜色。
若另外存储子树大小来支持排名查询,旋转时也要更新这些大小。若加入删除,移走黑节点可能改变路径黑数,不能直接使用上面的插入循环修复。NIL 是外部叶标记,不是供键比较访问的一般键。共用哨兵可以节省空间,却不改变数学树中的外部叶位置数。
练习与解答
快速检查
(1. 根 8 是黑色,左子节点 4 是红色并有黑色 NIL 子节点,右子节点是 NIL。这是红黑树吗?n、H 和根的黑高度各是多少?)
解答
是。经过 4 的各路径及直接向右的路径,离开 8 后都只计入一个黑节点:末端的 NIL。树中没有红红相邻。此时 、、。左子树有一个键,右子树没有键;相等黑数不等于相等子树大小。
快速检查
(2. 黑色根 10 有红色左叶 5。插入 7,指出叔节点、两次旋转及最后的颜色。为什么只在 10 右旋一次不够?)
解答
新节点 7 是红色,父节点 5 是红色,叔节点是黑色 NIL。这是左右三角形。先在 5 左旋,把 7 改黑、10 改红,再在 10 右旋。结果是黑根 7,左右子节点分别为红叶 5、10。
只在 10 右旋,会使 5 升到 10 上面,而 7 变成 10 的左子节点。即使只把新根改黑,仍有红色 10 接着红色子节点 7。因此须先把内侧红节点转成外侧直线。这里检查的是指定的旋转与着色修复;单靠旋转保留次序,从来不能保证颜色条件成立。
快速检查
(3. 合法树的根 20 为黑色,子节点 10、30 都是黑色;10 有红叶 5、15。插入 1。说明只把 5、15 改黑、却让 10 保持黑色为什么失败,再写出正确结果。)
解答
插入后,红色 1 在红色 5 下面,叔节点 15 也是红色。若把 5、15 改黑而让 10 保持黑色,离开 20 后经 10、5 的路径会计入 10、5、NIL 共三个黑位置;经 30 的右路径却只计入 30 和 NIL 共两个。
正确修复还须把 10 改红。它的父节点 20 是黑色,所以循环停止。结果是 20B(10R(5B(1R,-),15B),30B)。每条根路径的黑数都是 2;红节点 10 和 1 的子节点都是黑色。这次不用旋转。
快速检查
(4. 为什么最多两次旋转不能推出常数时间插入?这个旋转界适用于删除吗?)
解答
插入前的搜索可能走一条对数长度的根至叶路径,红叔节点修复也可能沿这条路径多次重新着色。常数界只是在数旋转:重新着色可以重复,但第一次黑叔节点修复会在一或两次旋转后结束。总插入时间仍是 。本证明不对删除作任何结论;移走黑节点需要另一套不变量及修复分析。