Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

03.01.md 删除修复情况2 #430

Open
ZacharyHuang opened this issue Aug 27, 2015 · 0 comments
Open

03.01.md 删除修复情况2 #430

ZacharyHuang opened this issue Aug 27, 2015 · 0 comments

Comments

@ZacharyHuang
Copy link

删除修复情况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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant