知识卡片

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

双子节点删除需搬迁后继

理解等级:高级

删除有两个孩子的节点 z 时,用其右子树最小节点 y 接替。

  • 若 y 就是 z 的右孩子,保留 y 原右子树;
  • 否则先以 y 的右孩子填补 y 原位置,再把 z 的左右子树接到 y。

后继没有左孩子是这些指针操作成立的关键。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.