知识卡片

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

删除须保存原颜色

理解等级:高级

红黑树删除沿普通 BST 的移植结构处理,但需记录真正被移除或搬迁节点 y 的原颜色。原来是黑色才可能破坏黑高并触发修复;仅查看输入节点 z 的颜色会在双子节点分支判断错误。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 13 章13.4 节(`OEBPS/chapter013.xhtml`,文本字符 [30000, 35000))。 - 结论依据:RB-DELETE 在选择实际移除/搬迁节点 y 后立即保存 y-original-color;若其原色黑,移除或搬迁可能破坏红黑性质,才调用 RB-DELETE-FIXUP。 - 原始内容:the variable y-original-color stores y ’s color before any changes occur.