知识卡片

普通读书笔记卡 · 1292.f.1.a.5.e.2.a

删除修复按兄弟颜色分流

理解等级:高级

删除修复以 x 为左孩子为例:

  • 红兄弟先旋成黑兄弟;
  • 黑兄弟且两孩子黑则把额外黑向上推;
  • 近侧红、远侧黑先旋成远侧红;
  • 远侧红再旋转着色终结。

右孩子情形镜像处理,不能把四种分支当成互斥的一次选择。

这张卡片看不懂?

已有反馈 · 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.

    参考来源

    - 位置:《算法导论(第4版)》第 13 章13.4 节(`OEBPS/chapter013.xhtml`,文本字符 [40000, 45000);图 13.7、Art_P445)。 - 结论依据:13.4 节情况 1 用换色与左旋化为其他情况;情况 2 将额外黑上推并可能重复;情况 3 先右旋化为情况 4,情况 4 左旋着色后终止;右孩子情形镜像。 - 原始内容: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.