知识卡片
删除真实节点避免陈旧引用
早期删双子节点的做法是复制后继的键和值到待删节点,再实际删除后继;若外部保存节点指针,就会留下指向已删除后继的陈旧引用。
本版改为搬迁后继节点,保证传入的 z 本身被删。
数据结构 API 的节点身份语义会决定删除算法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
it guarantees that a call to delete node z deletes node z and only node z.
参考来源
- 位置:《算法导论(第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 .