泰晓科技 -- 聚焦嵌入式 Linux - 追本溯源,见微知著!
网站地址:http://tinylab.org
微信公众号关注我们新浪微博


扫一扫

关注 @泰晓科技
原创服务 | 实验云台 | 共享书籍 | 直播回放
请稍侯

红黑树 IN Linux (二)

Chen Jie 创作于 2016/09/15

By Chen Jie of TinyLab.org 2016-09-15 21:25:25

前言:

前文回顾了红黑树的 5 个属性,及 Linux 实现的红黑树所具备的额外俩属性:

  1. lockless lookup
  2. augment

lockless lookup 以部分准确性换取无需持锁查找。lookup 是指从根节点开始,一路向下,最终找到(或找不到)树中的一个位置(插言:这是个 “指位器 (iterator)” 的概念)。这要求 父节点指向子节点的指针 无需持锁访问;且更新过程中,不存在一刻指针成环。

augment 是附加在节点上的额外数据成员,并在树的增删操作中,同步更新此额外数据成员。 augment 可视作本节点、及子孙节点的“摘要”,比如在前文 unmapped_area() 例子中,augment(实际的数据成员叫做 rb_subtree_gap)记为 节点名下最大空隙的尺寸。于是,在分配 vma(遍寻 目标空隙)的过程中,能有效跳过 名下空隙均太小 的节点。

红黑树:删除一个节点

我们从一个函数调用栈入手:

// http://lxr.free-electrons.com/source/lib/rbtree.c?v=4.7#L424
void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *rebalance;
	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
	if (rebalance)
		____rb_erase_color(rebalance, root, dummy_rotate);
}

__rb_erase_augmented

此函数处理的情形,可分为两大类:

  • 被移除的节点 N,最多只有一个子节点
  • 被移除的节点 N,左右子节点都在

按照严格的定义,在 Linux 红黑树中叶子节点是 NULL。为方便期间,此处将 没有子节点(或说子节点都是 NULL)的节点称为“叶子节点”;只有一个子节点的(或说某个子节点是 NULL)的节点称为“半叶节点”。于是,第一大情形,实际上是删除 “(半)叶节点”:

image

上图中,我们用 虚线圆 圈起被移除的节点 N。由于大前提假定 N 最多有一个子节点,若 N 有子节点,子节点必然为红色,此时 N 为黑色。这是由红黑树的属性 5,结合属性 4 所推结论。图中 没有着色的点,代表其颜色不确定,可能红,也可能黑。

图中左、右俩情形:N 被移除后,其唯一子节点继承了 N(继承内容:N 在红黑树中位置、以及 N 的颜色)。由于涉及路径上黑色节点数目未变,故红黑树保持平衡。无需做 rebalance。

图中中间情形:N 被直接移除。若 N 为红色,则涉及路径上黑色节点数目未变,红黑树平衡。反之若 N 为黑色,则失衡,需要 rebalance。此时最靠近叶的失衡节点 P,用 橙色墨迹 圈出。P 将传入 ____rb_erase_color 中,进行 rebalance。

再来看第二大情形,又可细分成俩情形 —— Case2 和 Case3:

image

这是一个寻找 “N 的后继者” 的过程。红黑树是一个排序结构,“N 的后继者” 是指顺序上紧跟 N 的节点。即它右子节点名下,“最小”的节点。这个最小节点,有可能是右子节点本身(当右子节点没有左子时)即 Case2 所示情形;也可能是右子节点下,最靠左的节点,即 Case3 所示情形:

image

我们找到 “N 的后继者” 后,让它继承 N(继承内容:N 在红黑树中位置、以及 N 的颜色)。那么这个过程结束以后,需要 rebalance 吗?

—— 若 “N 的后继者” 还有子节点(如 Case2 和 Case3 的图例中的 Rr 和 B),让子节点 继承 “N 的后继者”(继承内容:位置、颜色),则保持涉及路径上黑色节点数不变,无需 rebalance。反之,则需从最靠近叶的失衡节点 R(Case2) 和 P’(Case3) 开始 rebalance

____rb_erase_color

图例:如何达到平衡?

image

上图中,P 为最靠近叶的失衡点(橙色墨迹 圈出);N 为 P 右子节点,其所在支路,比其兄弟节点 S(蓝色墨迹 圈出)所在支路,要/少一个黑色节点/。

图中从 Case1 到 Case2,在 P 上进行右旋操作:S 继承了 P 的颜色和位置,P 被设置成了红色。这就是函数 __rb_rotate_set_parents(P /* old */, S /* new */, root, RB_RED) 所做的工作。

然后交换 P 和 Sr 的颜色,P 的左右支变平衡。

上图中,密密排了许多节点,我们用右边的 N,抵消掉左边相应节点(A、B、C、D),从而让图示更加清爽:

image

综上,我们看到树的旋转操作、置颜色之后,可达到平衡。

____rb_erase_color 骨架

// http://lxr.free-electrons.com/source/lib/rbtree.c?v=4.7#L223
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
	...)
{
	struct rb_node *node = NULL, *sibling, *tmp1, *tmp2;
	 
	while (true) {
		sibling = parent->rb_right;
		if (node != sibling) {  /* node == parent->rb_left */
			...
		} else {   /* node == parent->rb_right */
			...
		}
	}
}

观察 __rb_erase_augmented 输出结果可知,若出现了失衡点(parent),则失衡点有且仅有一个子节点。该子节点即为 sibling(而 node 为 NULL)。

依据 sibling 在右(node == parent->rb_left),还是在左(node == parent->rb_right)分成两大块处理。两块的处理流程是对称的。

下面以 sibling 在左为例,阐述代码中的 Case1 - Case4。

Case1 和 Case2

一个隐含的条件为:/sibling 一支/ 比 /node 一支/ 多一个黑色节点。

  • Case1:sibling (蓝色墨迹 圈出)为红色。
  • Case2:sibling (蓝色墨迹 圈出)为黑色,且两子节点均为黑色(或不存在,即 NULL - 严格意义上的叶节点。按照红黑树属性 3 定义,叶节点都是黑色)。

image

Case1 在 P 上进行了树的右旋操作,变化到了 Case2。

Case2 中对 parent(橙色墨迹 圈出)置黑色,sibiling(蓝色墨迹 圈出)置红色:

  • 由于 Case2 中 sibling 置色前为黑色,故置红色使路径损失 1 个黑色节点,由此 parent 回复平衡。
  • 但 grandparent 呢(即图中 G)?若 parent 置色前为红色,置色使路径增加 1 个黑色节点,刚好平衡。反之,G 成为最靠近叶的失衡节点,开始下一轮循环。
  • 由 Case1 变化来的 Case2,parent 总是红色的,故能在本轮循环中达到平衡。

落在 Case1 和 Case2 的情形,要么本轮循环中达到平衡,要么进入下一轮循环。

Case3 和 Case4

一个隐含的条件为:/sibling 一支/ 比 /node 一支/ 多一个黑色节点。

  • Case3:sibling(蓝色墨迹 圈出)为黑色;其左子节点为黑色(或不存在); 其右子节点为红色。
  • Case4:sibling(蓝色墨迹 圈出)为黑色;其左子节点为红色。
    • 注:由 Case3 变化而来的 “Case4”,并不符合上述描述 —— 特别是图例中,最靠近叶的失衡点为 Sr 而不是 P —— 这是个变化中的短暂特例,此处先忽略它。

image

Case3 在 S 上进行了树的左旋操作,变化到了 Case4。

Case4 在 P 上进行了树的右旋操作:

  • sibling 继承了 P(继承内容:位置和颜色)
  • 右旋后,sibling 的左右子均置为黑色

落在 Case3 和 Case4 的情形,都能在本轮循环中达到平衡。

小结

本篇是「红黑树 IN Linux (一)」的续篇,前篇关注了 Linux 中红黑树的基础信息,本篇开始关注红黑树算法及其实现。我们从 删除和增加 节点操作入手,来一窥究竟。

限于篇幅,本文仅探讨了 删除 操作,对应 Linux 源代码中 __rb_erase_augmented____rb_erase_color 俩函数。

“删操作” 是相对较复杂的操作,下一篇我们将些许轻松地体验下 “增操作”。


Read Related:

Read Latest: