7.3.1.5 二叉排序树的查找效率
原书定位
印刷页P286起,对应PDF第298页。下文为目视整理的知识提要;完整内容见原书对照。
查找代价与树高有关,平衡时 ,退化时 。等概率成功 ASL 为各结点层数之和除以 ;同一关键字集合的 ASL 可以随树形变化。
数组折半查找在静态有序表上性能稳定,但插入删除需移动元素;BST 的动态更新可通过指针完成,仍须考虑是否保持平衡。

同组关键字构成的不同树形,原书P286。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P286起,对应PDF第298页。下文为目视整理的知识提要;完整内容见原书对照。
查找代价与树高有关,平衡时 ,退化时 。等概率成功 ASL 为各结点层数之和除以 ;同一关键字集合的 ASL 可以随树形变化。
数组折半查找在静态有序表上性能稳定,但插入删除需移动元素;BST 的动态更新可通过指针完成,仍须考虑是否保持平衡。

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

