知识卡片

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

红叔叔使冲突向上传递

理解等级:中级

插入后若新节点和父节点均红且叔叔也红,可把父、叔染黑,祖父染红,保留黑高并把可能的新冲突上移到祖父。此分支不旋转,但可能沿祖先重复,最后仍须把根染黑。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第13章 红黑树 · 查看原书依据

      Case 1. z’s uncle y is red Figure 13.5 shows the situation for case 1 (lines 5–8), which occurs when both z.p and y are red. Because z’s grandparent z.p.p is black, its blackness can transfer down one level to both z.p and y, thereby fixing the problem of z and z.p both being red. Having had its blackness transferred down one level, z’s grandparent becomes red, thereby maintaining property 5.

    参考来源

    - 位置:《算法导论(第4版)》第 13 章13.3 节(`OEBPS/chapter013.xhtml`,文本字符 [20000, 25000);图 13.5、Art_P439)。 - 结论依据:RB-INSERT-FIXUP 的情况 1 要求父和叔都红;代码把父、叔染黑、祖父染红,再令 z 上移到祖父,保持黑高;循环末把根染黑。 - 原始内容:Case 1. z’s uncle y is red Figure 13.5 shows the situation for case 1 (lines 5–8), which occurs when both z.p and y are red. Because z ’s grandparent z.p.p is black, its blackness can transfer down one level to both z.p and y , thereby fixing the problem of z and z.p both being red. Having had its blackness transferred down one level, z ’s grandparent becomes red, thereby maintaining property 5.