知识卡片
后继查找还需处理无右子树
节点x的中序后继是大于其键的最小键。若x有右子树,后继为右子树中最左的节点;但x没有右子树时,原答案给出的步骤就不完整。
后一种情况应向上找第一个使x位于其左子树中的祖先;没有这样的祖先,x已是最大键,就没有后继。没有父指针时,可在从根定位x时记录大于x的候选祖先,走左时更新该候选。
在普通BST中沿路径处理为O(h),高度受限时为O(log n)。若有隐藏节点,还需额外处理可见性,不能把未过滤的物理中序后继直接交作逻辑后继。这里补全原答案缺失边界,是概念推导,未提供或运行新函数。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
后继结点是指x之后的下一个最大结点。例如,在一棵二叉搜索树中包含键值24、39、41、55、87、92,于是41的后继是55。如何在二叉搜索树中找到某个结点的后继结点?该操作的时间复杂度是多少? 答:要在二叉搜索树中确定结点x的后继结点,首先要定位到x。然后,移动到x的右子结点,从这个结点开始不断通
参考来源
- 位置:《算法精解:C语言描述》第9章《问与答》(spine1306;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1273.html;u168-ch09-028)。
- 结论依据:168后继问答与键例全文实读,右子树方案只覆盖有右孩子;祖先条件由全子树键序直接推导,未假造本书包含完整代码。
- 原始内容:后继结点是指x之后的下一个最大结点。例如,在一棵二叉搜索树中包含键值24、39、41、55、87、92,于是41的后继是55。如何在二叉搜索树中找到某个结点的后继结点?该操作的时间复杂度是多少? 答:要在二叉搜索树中确定结点x的后继结点,首先要定位到x。然后,移动到x的右子结点,从这个结点开始不断通