07. 查找

基础查找方法

评价方法

• 查找效率
  • 占用存储空间的多少
  • 算法本身复杂程度
• 平均查找长度 ASL

$$ASL=\sum _{i=1}^n{p}_i{c}_i$$

p_i 为查找表中第 i 个元素的概率，

$$\sum _{i=1}^n{p}_i=1$$

c_i 为找到表中第 i 个元素所需比较次数。

顺序查找

从表的一端开始，逐一开始查找。

折半查找

ASL：log_2(n)

适合表结点比较稳定、很少做插入或删除操作的顺序表。

分块查找

插值查找

类似于二分查找，不过不是取中间位置，而是取数据的中值，也要求数据有序。

适用于查找表数据量较大、数据分布比较均匀。

斐波拉契查找

······

二叉排序树(BST)

关键：

按中序遍历该树得到的序列是递增有序的

二叉排序树的查：

性能分析

• ASL 与二叉树的形态有关
• ASL = （n+1）/2[顺序表]~~~log_2(n)

二叉排序树的删除

• p 是叶子，直接删除。
• p 有一个孩子，将孩子与双亲相连，然后删除。
• p 有两个孩子，用中序遍历的前趋替代 p。

平衡二叉树(AVL)及其调整

对给定序列建立 BST，使左子树和右子树高度差的绝对值（平衡因子）不超过 1。

插入或删除结点后，可能使树失去平衡，需调平：

哈希表

。。。

见散列表实现查找