julycoding/The-Art-Of-Programming-By-July-2nd

03.01.md 删除修复情况2

ZacharyHuang opened this issue · 0 comments

删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色。

解法:_把当前结点和兄弟结点中抽取一重黑色追加到父结点上_,把父结点当成新的当前结点,重新进入算法。(此变换后性质5不变),即调用RB-INSERT-FIXUP(T, z) 的第9-10行代码操作,如下:

//调用RB-DELETE-FIXUP(T, x) 的9-11行代码
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
_11 x p[x] ▹ Case 2_

  1. 解法中 "把当前结点和兄弟结点中抽取一重黑色追加到父结点上" 恕本人愚钝,无法理解。从代码来看,是否是

解法:_把兄弟节点染成红色,并把当前结点额外的一层黑色移至父结点上_,把父结点当成新的当前结点,...

  1. 代码第11行遗漏符号 ←

11 x _←_ p[x] ▹ Case 2