7.3.1.5 二叉排序树的查找效率

教材导航 · 第7章

原书定位

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

查找代价与树高有关,平衡时 O(log⁡n)O(\log n),退化时 O(n)O(n)。等概率成功 ASL 为各结点层数之和除以 nn;同一关键字集合的 ASL 可以随树形变化。

数组折半查找在静态有序表上性能稳定,但插入删除需移动元素;BST 的动态更新可通过指针完成,仍须考虑是否保持平衡。

同组关键字构成的不同树形

同组关键字构成的不同树形,原书P286。

对应练习

7.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P286,PDF第298页

原书对照,原书P287,PDF第299页