知识卡片
删除修复按兄弟颜色分流
删除修复以 x 为左孩子为例:
- 红兄弟先旋成黑兄弟;
- 黑兄弟且两孩子黑则把额外黑向上推;
- 近侧红、远侧黑先旋成远侧红;
- 远侧红再旋转着色终结。
右孩子情形镜像处理,不能把四种分支当成互斥的一次选择。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第13章 红黑树 · 查看原书依据
Only case 2 causes the loop to repeat. (a) Case 1 is transformed into case 2, 3, or 4 by exchanging the colors of nodes B and D and performing a left rotation. (b) In case 2, the extra black represented by the pointer x moves up the tree by coloring node D red and setting x to point to node B. If case 2 is entered through case 1, the while loop terminates because the new node x is red-and-black, and therefore the value c of its color attribute is RED. (c) Case 3 is transformed to case 4 by exchanging the colors of nodes C and D and performing a right rotation. (d) Case 4 removes the extra black represented by x by changing some colors and performing a left rotation (without violating the red-black properties), and then the loop terminates.