知识卡片

问题卡 · 5654.d.1.e.4.aa · 生成模型:未记录

后继查找还需处理无右子树

理解等级:中级

节点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的右子结点,从这个结点开始不断通