05、查找

一、有序表查找

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

时间复杂度：O(log n)
适用：经常查询而不经常修改的数据集
计算公式：

mid = (low+hight)/2 = low+1/2(heigh-low)

步骤

1. 定义指针指向寻找范围的头，尾，中部
2. 让目标值与中间值比较
   1. 如果小于中间值则去左半段找
   2. 如果大于中间值则去右半段找
   3. 等于中间值是输出（临界条件）

      public class 二分法查找 {
      public static int binarySearch(int[] nums,int target){
        int low=0;  //查找范小的围的那头
        int heigh = nums.length-1; //查找范围大的那头
        int mid = 0; //此范围的中间值
        while(low<=heigh){
            mid = (low+heigh)/2;
            if (target < nums[mid]) {
                heigh = mid-1;//目标在左边部分
            }else if(target>nums[mid]){
                low = mid+1;//目标在右边部分
            }else {
                return mid;//等于key找到目标
            }
        }
        return 0;
      }
      }

      02、插值查找

时间复杂度：O(log n)
适用：关键字比较分布比较均匀的查找，平均性能比二分法查找好。
插值计算公式：(预估目标值的分布位置)

positon = low+ (key-a[low] )/(a[heigh]-a[low])*(heigh-low) = (key-a[low] )/(a[heigh]-a[low])

这是对二分法查找的改造。

03、斐波那契查找

二、线性索引查找

01、稠密索引

• 在线性索引中，将数据集中的每一个记录对应一个索引项。
• 对于稠密索引的索引项来说，索引项一定是按照关键码有序排列

02、分块索引

• 分块有序，把数据集的记录分成若干块，并且这些块需要满足块内无序、块间有序
• 每块对应一个索引项，索引项结构分为三个数据项：
  1. 最大关键码（每一块中的最大关键字）
  2. 记录个数
  3. 指向块首数据元素的指针

分块索引中查找

1. 查找关键字所在的块
2. 根据首指针找到相应的块，顺序查找关机按码。

03、倒排索引

索引项：

1. 次关键码
2. 记录号表：存储具有相同次关键字的所有记录的记录号。

   由于不是由记录来确定属性值，而是由属性值来确定记录的位置，所以称倒排索引

三、二叉排序树（二叉查找树）

特征：

1. 若它的左子树不空，则左子树上所有的结点的值均小于它的根结点的值。
2. 若它的右子树不空，则左子树上所有的结点的值均打于它的根结点的值。
3. 它的左右子树也分别为二叉排序树

   二叉排序树的目的不是为了排序，而是为了提高查找和插入删除关键字的速度。

01、查找步骤

1. 先判断当前二叉树是否到了叶子节点，若果是返回false
2. 将目标值与根节点比较，等于返回true
3. 将目标值与根节点小于，遍历左子树，重复上述操作
4. 将目标值与根节点大于，遍历右子树，重复上述操作
5. 找到后返回true到第三层、第二层、第一层、最终返回true。

02、插入操作

1. 先查找判断是否存在
2. 新建结点
3. 判断当前树是否为空
4. 判断值，小于插入为左孩子
5. 判断值，大于插入为右孩子

03、删除操作（复杂）

删除结点的三种情况

1. 叶子节点 ——>直接删除
2. 仅有左子树或者右子树的节点—->独子继承父业·
3. 左右子树都有的结点—->用这个树的中序遍历的前驱或者后继代替删除结点

四、平衡二叉树（AVL树）

定义：平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1

平衡因子BF：左子树的深度减去右子树的深度。取值 是-1 、 0、 1。

实现原理

实现代码

五、多路查找树（B树）

多路查找树(multi-way search tree)，其每一个节点的孩子数可以多于两个（包括两个），且每一个节点处可以存储多个元素。

保证所有叶子都在同一层次上

01、2-3树

2-3树是这样一棵多路查找树：其中每一个结点都具有两个孩子（我们称它为2节点），或三个孩子（我们称它为3结点）

• 一个2节点包含一个元素和两个孩子（或没有孩子）
• 一个3节点包含一小一大两个元素和三个孩子（或没有孩子）

插入实现

1. 对于空树插入一个2节点即可
2. 插入结点到一个2结点的叶子上，由本身只有一个元素，所以只需将其升级为3结点即可
3. 往3节点中插入一个元素。要将其拆分，且将树中两元素或插入元素的三者中选择其一向上一层移动。

   2-3树插入传播效应导致根节点的拆分，则树的高度就会增加

删除实现

1. 所删除的元素位于3结点的叶子结点上，直接删除。
2. 所删除的元素位于2结点的结点上
   1. 此结点的双亲是2结点的情况，且拥有一个3结点的右孩子。删除，左旋
   2. 此节点的双亲是2节点，它的右孩子也是2结点。需要整树变形。
   3. 此节点的双亲是3节点，拆分双亲结点，其中一个与孩子合并，成为3结点。
   4. 当前一棵树是满二叉树，删除后，会降低一层。
3. 所删除的元素位于非叶子结点的分支结点。通常是将树中序遍历后得到的此元素的前驱或者后继，考虑让它们来补位。

   02、2-3-4树

   是2-3的扩展
   补充一条：

• 一个4节点包含小中大三个元素和四个孩子（或没有孩子）

  03、B树（平衡多路查找树）

• 2-3树和2-3-4树都是B树的特例

• 结点最大的孩子数目称为B树的阶。因此2-3树是3阶B树，2-3-4树是4阶B树。

一个m阶的B树具有如下属性

1. 如果结点不是叶结点，则至少有两棵子树。
2. 每一个非根的分支结点都有k-1个元素和k个孩子，其中m/2<=k<=m。21每一个叶子结点n都有k-1个元素，其中m/2≤k≤m。
3. 所有叶子结点都位于同一层次。
4. 所有分支结点包含下列信息数据（n,A0,K1,A1,K2A2…,KnAn)，其中:Ki(i=1,2,…,n)为关键字，且Ki<Ki+1(i=1,2,…,n-1)；Ai(i=0,2,…,n)为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,…,n)，An所指子树中所有结点的关键字均大于Kn，n (m/2-1≤n≤m-1)为关键字的个数(或n+1为子树的个数)。

在2-3-4树最左侧节点加入，节点中元素的个数，就转为了B树

04、B+树

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

01、散列表查找的定义

通过某个函数

存储位置=f（关键字）

这种不需要比较就可以获得需要记录的存储位置，这就是一种新的存储技术——散列技术

• 散列技术是在记录的存储位置和他的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)
• f称为散列函数，又称为哈希函数
• 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash Table）

02、散列表的查找步骤

整个散列过程其实就是两步

1. 在存储时，不管什么记录，都要先用同一个散列函数计算出地址再存
2. 在查找记录时，同样通过散列函数计算记录的散列地址，按此散列地址访问该记录

• 所以说散列技术即是一种存储方法，又是一种查找方法
• 散列是面向查找的存储结构
• 散列技术最适合求解问题是查找与给定值相等的记录
• 冲突：两个关键字对应一个地址
  我们把key1和key2称为这个散列函数的同义词

  存在key1！=key2 有f(key1)=f(key2) 的情况

03、散列函数的构造方法

1、好的散列函数

1. 计算简单，散列函数的计算时间不应该超过其他查找技术与关键字比较的时间
2. 散列地址分布均匀，尽量让散列地址分布均匀在存储空间中，不聚在同一个位置发生冲突 | 方法 | 实现 | 适用范围 | | —- | —- | —- | | 直接定址法 | 取关键字的某个线性函数值为散列地址即f(key)=a*key+b(a,b 为常数) | 此方法虽简单但不常用 | | 数字分析法 | 使用关键字的一部分来计算散列存储位置的方法，eg 电话尾号（同一地区的前7为相同程度高） | 这是散列函数中常用的手段 | | 平方取中法 | eg 假设关键字为1234，他的平方就为1522756，再取中间的三位227，用作散列地址，如果中间的三位不是最中间的可以取靠左或者靠右的三位，不过确定左三位或者右三位后就只能用一种方法来用作散列地址 | 平方取中发适合不知道关键字的分布，而位数又不是很大的情况 | | 折叠法 | 将关键字从左到右分割成数位相等的几部分（最后一部分位数不够可以短些）。 eg 关键字为9876543210 分为4组987/654/321/0，将他们叠加求和987+654+32+1=1962，再取后三位得到散列地址962 | 折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。 | | 除留余数法 | 公式为f(key)=key mod p(P<=m),m为散列表的长度。通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。 | 此方法为最常用的的构造散列方法。 | | 随机数法 | 取关键字的随机函数值为他的散列地址，即f(key)=random(key)。针对字符可以使用各种编码，例如ASCII或者Unicode等表示。 | 当关键字的长度不等时，采用这个方法比较合适。 |

2、选择散列函数的方法考虑

1. 计算散列地址所需的时间
2. 关键字长度
3. 散列表的大小
4. 关键字的分布情况
5. 记录产找的频率

综合这些因素才能决策选择哪种散列函数合适

04、处理散列冲突的方法

1、开放定址法（线性探测法）

就是一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

公式：

fi=(f(key)+di)mod m(di=1,2,3,m-1)

堆积：不是同义词争夺同一个位置

2、二次探测法

公式：

fi=(f(key)+di)mod m(di=12,-12,22,-022,32,-32,…,q2,-q2(p<=2/ m)

3、随机探测法

公式

fi=(f(key)+di)mod m(di是一个随机数列）

位移量di采用随机函数计算得到

总之开放定址法只要散列式未满是，总是能够找到不发生冲突的地址，是我们常用的解决冲突的方法

4、再散列函数法

事先准备多个散列函数，当散列地址发生冲突时，就换一个散列函数计算，总有一个可以把冲突解决。

公式

fi(key)=RHi(i=1,2,….,k)

RHi就是不同的散列函数，我们可以把前面的除留余数，折叠，平方取中方法等全部用上。

5、链地址法

将所有的关键字为同义词的记录存储在一个单链表中，我们称这种表为同义子表，在散列表中只存储所有同义子表的表头。

提供了绝不会出现找不到地址的保障，但同时带来的查找时需要遍历单链表的性能损耗。

6、公共溢出区法

所有冲突的关键字建立了一个公共区域来存放

当有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

05、散列表的实现

散列表查找算法实现

//TODO

散列表查找性能分析

1. 散列函数是否均匀
   由于不同的散列函数对同一组随机关键字，产生的冲突的可能性相同，所有我们可以不考虑他对平均查找长度的影响。
2. 处理冲突的方法
   相同的关键字，形同的散列函数，但是处理冲突的方法不同，会使得平均查找长度不同。
   比如：线性探测处理冲突可能会产生堆积，显然没有二次探测法好。而链地址处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。
3. 散列表的装填因子
   装填因子α=装入表中的记录个数/散列表的长度，α越大，产生冲突的可能性就越大。
   空间换时间。