知识卡片
极值沿同一方向查找
子树的最小键位于不断向左走到的末节点,最大键对称地向右找。
起点须是非空子树根;若重复键存在,返回的是一个极值节点,不保证唯一节点。
搜索范围是一条路径,耗时 O(h)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第12章 二叉搜索树 · 查看原书依据
To find an element in a binary search tree whose key is a minimum, just follow left child pointers from the root until you encounter a NIL
参考来源
- 位置:《算法导论(第4版)》第 12 章 12.2 节(`OEBPS/chapter012.xhtml`,文本字符 [5000, 15000))。
- 结论依据:12.2 节 TREE-MINIMUM 从非 NIL 的子树根持续沿 left 至 NIL 前一节点,TREE-MAXIMUM 对称沿 right;原文限定起点非空并给出 O(h) 路径成本。
- 原始内容:To find an element in a binary search tree whose key is a minimum, just follow left child pointers from the root until you encounter a NIL