7.3.1.1 二叉排序树的查找

教材导航 · 第7章

原书定位

印刷页P284起,对应PDF第296页。下文为目视整理的知识提要;完整内容见原书对照。

从根开始,目标小则向左、大则向右,相等成功,遇空指针失败。查找路径对每个经过的祖先都建立范围约束,后续关键字必须落在这些约束的交集中。

一次查找为 O(h)O(h);非递归实现只需 O(1)O(1) 辅助空间,递归实现需要 O(h)O(h) 调用栈。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P284,PDF第296页