知识卡片
删除搜索树要保持次序
删除叶子可去掉对应链接,只有一个孩子时可由孩子接替;有两个孩子时,选右子树最小值或左子树最大值替换当前键,再删除那个替代节点。
替代值位于合法次序边界,才能继续满足左右全子树范围。删除根要更新根入口,缺失目标应保持原树;替换值不等于原节点对象身份保留了原业务实体,外部节点引用也要按接口合同理解。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
需要使用一个节点替换该节点。由于要保持二叉搜索树 “左子树 根节点 右子树”的性质,因此这个节点可以是右子树的最小节点或左子树的最大节点 。 假设我们选择右子树的最小节点(中序遍历的下一个节点),则删除操作流程如图7‑2
参考来源
- 位置:《Hello 算法--Go版本》第07章《树》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/4.html;spine 3,归一字符[5546,5656))
- 结论依据:实际三种度情况及中序后继代码,区分值覆盖和对象身份。
- 原始内容:需要使用一个节点替换该节点。由于要保持二叉搜索树 “左子树 根节点 右子树”的性质,因此这个节点可以是右子树的最小节点或左子树的最大节点 。 假设我们选择右子树的最小节点(中序遍历的下一个节点),则删除操作流程如图7‑2