知识卡片
子树移植不修复新子树内部
TRANSPLANT 把子树 u 在父节点处的入口替换为 v,并更新 v 的父指针;v 可以是 NIL。
它不设置 v 的左右孩子,因此调用者必须完成内部连接,特别是双子节点删除时,不能把一次移植当成整段删除算法。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
The procedure TRANSPLANT does not attempt to update v.left and v.right.
参考来源
- 位置:《算法导论(第4版)》第 12 章 12.3 节(`OEBPS/chapter012.xhtml`,文本字符 [20000, 25000))。
- 结论依据:12.3 节 TRANSPLANT 仅在 u 的父节点或根处换入口,v 非 NIL 时更新 v.p;原文明确不更新 v.left、v.right,由调用者负责内部连接。
- 原始内容:The procedure T RANSPLANT does not attempt to update v.left and v.right .