Chapter 13: Red-Black Trees

13.1 Properties of red-black trees

A red-black tree is a binary search tree that satisfies the following red-black properties:

  1. Every node is either red or black.
    给 BST 的结点添加颜色属性,用以维持平衡
  2. The root is black.
    这条性质可不可以删除呢?(Exercise 13.1-3)
    那将变成 relaxed red-black tree ,也是可以平衡的
    令根为黑色只是为了方便(比如后面的插入操作)
  3. Every leaf (NIL) is black.
    否则根据性质4,最下一层非空结点将不能为红色
  4. If a node is red, then both its children are black.
    保证了黑色结点在纵向上(每条垂直路径)至少占一半
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.
    简称,黑高一致,保证了黑色结点在横向上分布均匀
    又因为黑色结点在纵向上至少占一半,所以整棵树至少有一半结点在横向上大致平衡

Balance

Red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. (Exercise 13.1-5)
We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x).
由性质4易知 \(bh(x) \ge h(x)/2\)
由性质5易知 \(size(x) \ge 2^{bh(x)}-1\)
由引理易知 \(n \ge 2^{h/2\ -\ 1}-1\)
因此 \(h = O(lg\ n)\)

NULL

之前我们往往用 NULL 表示空结点,现在我们用一个特殊的结点 T.nil表示(为什么呢?其实仅仅是为了方便)
为了节省空间,整棵树的空节点合并为了一个:

Figure-13.1 (b)
红黑树示意图

现在整棵树的叶子都是那个结点,但是当我们一般说某个结点有多少个孩子时,是不包括 T.nil的(只计算internal nodes
因此可以这样说:如果某个结点只有一个孩子,那么它一定为黑色,它的孩子一定为红色(为什么呢?这是个挺常用的性质)


13.2 Rotations

由 Exercise 13.2-4 可知,仅仅利用旋转,就可以把 BST 调整成任何想要的形状(足够快,而且不破坏 BST 的性质)
因此大多数平衡树都有用旋转这个操作

Figure 13.2
旋转示意图


13.3 Insertion

首先按照 BST 的套路插入:

Fixup

我们令新插入的结点为红色(为什么呢?因为性质5一旦被破坏,是很难调整回来的)
那么现在有哪些性质可能被破坏了呢?

  • 如果 z 为根节点,则性质2被破坏(小问题)
  • 如果 z 的父亲为红色, 则性质4被破坏(主要矛盾)

接下来的工作便是修复(以此维持红黑树的平衡性):

CLRS中用了一大段循环不变量来证明程序的正确性:

The while loop above maintains the following three-part invariant at the start of each iteration of the loop:
a. Node z if red.
b. If z.p if the root, then z.p is the black.
c. If the tree violates any of the red-black properties, then it violates at most one of them, and the violation is of either property 2 or property 4. If the tree violates property 2, it is because z is the root and is red. If the tree violates property 4, it is because both z and z.p are red.

一言以蔽之,就是保证当通过 while 循环的 test 条件之后, zz.p 不为 T.root 且为红色
所以循环要解决的问题就只是双红,而且循环里的 z.p.p不为 T.nil

Figure 13.4
红黑树的插入

下面分别说说那三个case:

  1. z’s uncle y is red
    把锅(红色)甩给爷爷,进入下一重循环
    然后爷爷或者进入case 2/3,终止循环
    或者再次进入case 1,再次甩锅
    最坏情况下会一直甩到根节点,所以时间复杂度为O(lg n)
  2. z’s uncle y is black and z is a right child
    直接通过旋转转化成case 3
  3. z’s uncle y is black and z is a left child
    这里用了一种常用的操作:
    父亲把家产(黑色)传给儿子(原本为红色),自己就没钱了(变成红色),然后让儿子继承自己的位置(通过旋转),以此维持社会和谐(黑高一致)
    更一般地,可以写个子函数叫“换色旋转”,在下面的删除里也会用上

13.4 Deletion

首先是一个子函数(类似于第十二章里的 TRANSPLANT()

The procedure RB-T RANSPLANT differs from T RANSPLANT in two ways.
First, line 1 references the sentinel T.nil instead of NIL.
Second, the assignment to v.p in line 6 occurs unconditionally:
we can assign to v.p even if v points to the sentinel.
In fact, we shall exploit the ability to assign to v.p when v = T.nil.

这里提到了用 T.nil代替 NULL的好处,其实不止这一个(还有哪些?)
然后是删除

(一个小细节:第12、13行看似没用( x本来就是 y的孩子,为什么还要 x.p = y?),实则有用(为什么呢?因为 x有可能为 T.nil,那么 x.p就不一定是 y))
基本上和普通的 BST 的删除一样
关键是分析删除之后会怎样破坏性质
首先要对 xy有直观理解:

  • y是对于颜色来说被删除的点
    怎么理解这句话呢?
    在 case 1/2 里, y等于 z
    在 case 3 里, y等于 z的后继
    首先是 z被它的后继 y覆盖,但 y要继承 z的颜色,所以对于颜色来说, z并没有被删除
    然后是把 y从原来的位置删除掉,即转化成了 case 1/2(因为后继最多只有一个孩子)所以对于颜色来说,真正被删除的是 y
  • x是代替了 y的点( x有可能为 T.nil,但是无所谓(再次体现了 T.nil的优势))

现在再来分析可能会被破坏的性质:

  • 如果 y为根, x为红,则破坏性质2(小问题)
  • 如果 y-original-color为黑,则破坏性质5
  • 如果 xx.p都为红,则破坏性质4
    首先注意到,此时 y-original-color一定为黑,同时也破坏了性质5
    所以再用插入那里的套路处理双红是不妥当的
    然后注意到,只要让 x继承 y的黑色,就可以了
    所以这也是小问题

下面来分析 y-original-color为黑的情况(主要矛盾):
前面提到过,性质5是很难修复的,我们的原则是不破坏它,所以这里我们要强行不破坏它:
统一让 x继承 y的黑色,如果 x原本为红色,就会变成“红黑”,如果 x原本为黑色,就会变成“双黑”
于是强行变成了性质1被破坏

Fixup

然后我们的任务就是在保持黑高一致的前提下,修复性质1:

(The extra black on a node is reflected in x’s pointing to the node rather than in the color attribute)

Figure 13.7
红黑树的删除

The key idea is that in each case, the transformation applied preserves the number of black nodes (including x’s extra black) from (and including) the root of the subtree shown to each of the subtrees \(\alpha ,\beta ,\dots ,\zeta\).
下面分别说说那四个case:

  1. x’s sibling w is red
    通过上面提到换色旋转(B、D 之间)转化成 case 2/3/4
  2. x’s sibling w is black, and w’s right children is black, and w’s left children is black
    因为 w的两个孩子都是黑色,所以 w可以变成红色,所以可以甩锅给父亲(类似于插入的套路)
  3. x’s sibling w is black, and w’s right children is black, and w’s left children is red
    通过上面提到的换色旋转(C、D 之间)转化成 case 4
  4. x’s sibling w is black, and w’s right children is red
    首先是换色旋转(B、D 之间),然后把 E 染黑

Code

完整的代码稍后上传。。。

发表评论

电子邮件地址不会被公开。 必填项已用*标注