知识卡片

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

删除真实节点避免陈旧引用

理解等级:高级

早期删双子节点的做法是复制后继的键和值到待删节点,再实际删除后继;若外部保存节点指针,就会留下指向已删除后继的陈旧引用。

本版改为搬迁后继节点,保证传入的 z 本身被删。

数据结构 API 的节点身份语义会决定删除算法。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 12 章章末注释(`OEBPS/chapter012.xhtml`,文本字符 [30000, 32758))。 - 结论依据:章注对比旧版复制后继键并实际删除后继的做法:外部节点指针可能变陈旧;本版 TREE-DELETE 搬迁后继,保证删除传入的 z 且只删除 z。 - 原始内容:it guarantees that a call to delete node z deletes node z and only node z .