【数据结构】查找结构（二叉排序树、ALV树、散列技术哈希表）

查找：就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

• 静态查找表：只作查找操作的查找表。
• 动态查找表：查找过程中，同时进行插入或删除元素的工作。

为了提高查找的效率，需要转么为查找操作是指数据结构，这种面向查找操作的数据结构成为查找结构。

一、顺序查找表（线性表，不要求元素有序）

1、for循环多次比较

2、while循环，减少比较次数（i<=n）

时间复杂度O(n)

缺点：n很大时朝赵效率极为地下

优点：算法简单，对静态查找表的记录灭有任何要求。

适合：小型数据的查找时适用。

二、有序查找表（要求元素有序）

1、折半查找（二分法查找）

前提：线性表中的记录柏旭是关键码有序（通常从小到大有序），线性表柏旭采用顺序存储。

基本思想：略

时间复杂度：O(logn)。完全二叉树的深度为[logn]+1，远远浩宇顺序查找的O(n)。

2、插值查找（对二分查找的改进：mid值进行改进）

插值：

• 在离散数据的基础上补插连续函数，使得这条连续曲线通过全部给定的离散数据点。
• 插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。插值：用来填充图像变换时像素之间的空隙。

• 适用：表长较大，关键字分布比较均匀的查找表。
• 不适用：分布极端不均匀的查找表。

3、斐波那契查找

二、线性索引查找

1、稠密索引

2、分块索引

3、倒排索引

三、二叉排序树

二叉排序树的前提是二叉树。

对二叉排序树进行中序遍历时，得到的就是一个有序的序列。

1、二叉排序树的查找（递归）

2、二叉排序树插入操作

通过与叶子结点进行比较，然后根据二叉排序树的规则进行插入

3、二叉排序树的删除

三种情况：

1）删除叶子结点--直接删除即可

2）仅有左或右子树的结点：删除结点后，讲它的左子树或右子树整体移动到删除结点的位置即可，可以理解为独子继承父业。

3）左右子树都有结点：---找删除结点的前驱或者后继结点来替换。

二叉排序树总结：

四、平衡二叉树（AVL树）

ALV的由来：

平衡因子BF：将二叉树的左子树深度减去右子树深度的值。

具体细节比较复杂，略。

五、多路查找树

1、2-3树

2、2-3-4树

3、B树

六、散列表查找（哈希树）

1、散列函数的构造方法

原则：

最常用方法：除留余数法

        

        如果没有冲突，散列查找是介绍的所有查找中效率最高的，因为时间复杂度为O(1)。但是没有冲突的散列只是一个理想，在实际的应用中冲突是不可避免的。

查找结构总结