Argue that after executing RB-DELETE-FIXUP, the root of the tree must be black.
我们来看4种情况吧.
- case1会被转化为case2,3,4.
- 如果case1转变成case2退出的时候，会设置color[x] = BLACK. 否则，会继续往上递归.
- case3会被转化成case4.
- case4会将x置为root,循环条件不成立，color[x] = BLACK
因此，root总是黑的.
Argue that if in RB-DELETE both x and p[y] are red, then property 4 is restored by the call RB-DELETE-FIXUP(T, x).
因为color[x] = RED,不会进入循环,第23行会直接设置color[x] = BLACK.
In Exercise 13.3-2, you found the red-black tree that results from successively inserting the keys 41, 38, 31, 12, 19, 8 into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order 8, 12, 19, 31, 38, 41.
Thanks uta for the picture.
In which lines of the code for RB-DELETE-FIXUP might we examine or modify the sentinel nil[T]?
如果y没有孩子，那么x为哨兵nil[T].
只有第2行会检测.
In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtree shown to each of the subtrees α, β, ..., ζ, and verify that each count remains the same after the transformation. When a node has a color attribute c or c′, use the notation count(c) or count(c′) symbolically in your count.
看着4个case慢慢数 ＝ ＝
Professors Skelton and Baron are concerned that at the start of case 1 of RB- DELETE-FIXUP, the node x:p might not be black. If the professors are correct, then lines 5–6 are wrong. Show that x:p must be black at the start of case 1, so that the professors have nothing to worry about.
如果p(x)是红色的，那么w不可能是红色的，第4行就不会成立.
Suppose that a node x is inserted into a red-black tree with RB-INSERT and then immediately deleted with RB-DELETE. Is the resulting red-black tree the same as the initial red-black tree? Justify your answer.
不一定. thanks uta for the picture.
Follow @louis1992 on github to help finish this task.