知识卡片
查找只沿一条比较路径
查找目标键时,每个节点比较后只进入可能含该键的一侧;相等即停,走到 NIL 则不存在。访问节点形成从根向下的一条路径,因此成本是 O(h),与中序遍历的全树扫描不同。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
The nodes encountered during the recursion form a simple path downward from the root of the tree
参考来源
- 位置:《算法导论(第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