published: true
date: 2022-1-22
tags: '算法与数据结构'

查找

本章对算法中的基本问题--查找做了一个简要介绍，包含了一些基本算法思想以及评价，后续文章详细介绍一些算法，欢迎关注本系列。

可以转载，但请声明源链接：文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)

基础查找方法

评价方法

• 查找效率

• 占用存储空间的多少
• 算法本身复杂程度

• 平均查找长度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。

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

哈希表

。。。

见散列表实现查找