查找

基础查找方法

评价方法

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

$$ ASL = \sum_{i=1}^{n}p_ic_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。

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

哈希表

。。。

见散列表实现查找