知识卡片
双子节点删除需搬迁后继
删除有两个孩子的节点 z 时,用其右子树最小节点 y 接替。
- 若 y 就是 z 的右孩子,保留 y 原右子树;
- 否则先以 y 的右孩子填补 y 原位置,再把 z 的左右子树接到 y。
后继没有左孩子是这些指针操作成立的关键。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
If y is not z’s right child (Figure 12.4(d)), then two nodes have to move.
参考来源
- 位置:《算法导论(第4版)》第 12 章 12.3 节(`OEBPS/chapter012.xhtml`,文本字符 [15000, 25000))。
- 结论依据:12.3 节 TREE-DELETE 第 5 行取 z 右子树最小值 y,故 y 无左孩子;若 y 是 z.right,直接移植并接左子树,否则先以 y.right 填补旧位置,再接 z 的左右子树。
- 原始内容:If y is not z ’s right child ( Figure 12.4(d) ), then two nodes have to move.