知识卡片

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

查找只沿一条比较路径

理解等级:中级

查找目标键时,每个节点比较后只进入可能含该键的一侧;相等即停,走到 NIL 则不存在。访问节点形成从根向下的一条路径,因此成本是 O(h),与中序遍历的全树扫描不同。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 12 章 12.2 节(`OEBPS/chapter012.xhtml`,文本字符 [5000, 10000))。 - 结论依据:12.2 节 TREE-SEARCH 按 k 与 x.key 的比较只进入左或右一侧;原文指出访问节点组成一条自根向下的简单路径,因而为 O(h)。 - 原始内容:The nodes encountered during the recursion form a simple path downward from the root of the tree