查找的基础知识

o 基础概念

列表:由同- -类型的数据元素(或记录)构成的集合，可利用任意数据结构实现。
关键字:数据元素的某个数据项的值,用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯-标识列表中的一一个数据元素,则称其为主关键字，否则为次关键字。当数据元素仅有一个数据项时,数据元素的值就是关键字。
查找:根据给定的关键字值,在特定的列表中确定-一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素,则称查找是成功的,否则称查找是失败的，此时应返回空地址及失败信息,并可根据要求插人这个不存在的数据元素。
对于表的查找，一般有两种情况,一种是静态查找,指在查找过程中只是对数据元素进行查找;另一种是动态查找,指在实施查找的同时,插人找不到的元素,或从查找表中删除已查到的某个元素,即允许表中元素变化。
查找算法中涉及的三类参量:
1. 查找对象K(找什么)
2. 查找范围L(在哪找)
3. K在L中的位置(查找结果)。
- 其中1，2为输人参量,3为输出参量,在函数中，输人参量必不可少,输出参量也可用函数返回值表示。
平均查找长度:为确定数据元素在列表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度。对于长度为n的列表,查找成功时的平均查找长度为（P：访查找某元素的概率；C：查找到该元素时已经比较的次数） $\Sigma P_{i}*C_{i}$

o 查找的基本方法

比较查找法
- 基于线性表
  - 顺序查找法
  - 折半查找法
  - 分块查找法
- 基于树
计算查找法
- 也称哈希查找法

o 知识点

基于线性表

顺序查找法：
- 常常设置监视哨 r[0] 存放要查找的关键字，从表的另一端开始查找，可以起到防止越界的作用
- ASL = $\dfrac{n+1}{2}$
折半查找法（二分查找）
- 条件：
  1. 顺序存储结构
  2. 关键字有序排列
- 用平均查找长度(ASL)分析折半查找算法的性能。半查找过程可用二叉判定树的描述,判定树中每- -结点对应表中一个记录，但结点值不是记录的关键字,而是记录在表中的位置序号。根结点对应当前区间的中间记录,左子树对应前一子表,右子树对应后一子表。显然,找到有序表中任一记录的过程,对应判定树中从根结点到与该记录相应的结点的路径,而所做比较的次数恰为该结点在判定树上的层次数。因此,折半查找成功时,关键字比较次数最多不超过判定树的深度。查找成功时平均查找长度为： $ASL_{bs} = \dfrac{n+1}{n}log_{2}(n+1) - 1$ $\approx log_{2}(n+1)-1$
分块查找：
- 准备步骤：
  1. 首先将列表分成若千个块(子表)。一般情况下，块的长度均匀,最后一块可以不满。每块中元素任意排列,即块内无序,但块与块之间有序。
  2. 构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置,以及每块中的最大关键字(或最小关键字)。索引表按关键字有序排列。
- 过程：
  1. 将待查关键字k与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。
  2. 进一步用顺序查找法,在相应块内查找关键字为k的元素。
- 分块查找的平均查找长度由两部分构成,即查找索引表时的平均查找长度为 $L_{B}$ ,以及在相应块内进行顺序查找的平均查找长度 $L_{W}$ $ASL_{bs} = L_{B} + L_{W}$ 假设表长为n，分为b块，每块含s个元素，查找每个元素的概率相等，则 $ASL_{bs} = log_{2}(b+1) -1+\dfrac{s+1}{2}$ $\approx log_{2}(\dfrac{n}{s} + 1) + \dfrac{s}{2}$

基于树

二叉排序树
- 概念：
  - 二叉排序树又称为二叉查找树,它是一种特殊的二叉树。其定义为:二叉树排序树或者是一棵空树,或者是具有如下性质的二叉树：
    1. 若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
    2. 若它的右子树非空,则右子树上所有结点的值均大于(或大于等于)根结点的值;
    3. 它的左右子树也分别为二叉排序树.
- 创建二叉排序树的时间复杂度： $O(nlog_{2}n)$
- 二叉排序树平均查找长度： $O(log_{2}n)$
- 删除二叉排序树：
  - 删除操作首先查找要删除的结点,看是否在二叉排序树中,若不在则不做任何操作;否则,假设要删除的结点为p,结点p的双亲结点为f,并假设结点p是结点f的左孩子(右孩子的情况类似)。下面分三种情况讨论。
  1. 若p为叶结点,则可直接将其删:f->lchild=NULL;free§。
  2. 若ρ结点只有左子树,或只有右子树,则可将p的左子树或右子树,直接改为其双亲结点f的左子树。即:f->lchild = p->lchild(或f->lchild =p->rchild) ;free§。
  3. 若p既有左子树,又有右子树,如图8.8 (a)所示。此时有以下两种处理方法：
    - 方法1:首先找到p结点在中序序列中的直接前驱s结点，然后将p的左子树改为f的左子树,而将p的右子树改为s的右子树:f->lchild = p->lchild;s->rchild= p->rchild;free§
    - 方法2:首先找到p结点在中序序列中的直接前驱s结点,然后用s结点的值替代p结点的值,再将s结点删除,原s结点的左子树改为s的双亲结点q的右子树:p->data= s->data;q->rchild = s->lchild;free(s)
平衡二叉排序树：
- 概念：
  - 平衡二叉排序树又称AVL树。一棵平衡二叉排序树或者是空树,或者是具有下列性质的二叉排序树:
    1. 左子树与右子树的高度之差的绝对值小于等于1
    2. 左子树和右子树也是平衡二叉排序树。
- 引人平衡二叉排序树的目的,是为了提高查找效率,其平均查找长度为 $O(log_{2}n)$
- 结点的平衡因子( Balance Factor)定义为:结点的左子树深度与右子树深度之差。显然,对一棵平衡二叉排序树而言,其所有结点的平衡因子只能是-1、0或1. 当在一个平衡二叉排序树上插入一个结点时,有可能导致失衡,即出现绝对值大于1的平衡因子,如2.-2。
- 失衡的调整：通常，只有新插入节点的祖先节点平衡因子会受影响。这里假设最低层失衡节点为A，A_L, A_R, A_LR, A_RL分别为A的左子树，右子树，左子树的右子树，右子树的左子树, bf为平衡因子,FA为A的父指针.(教材P282-286)
  - LL型:A_L插入新节点后失衡。记B=A_L
    - 特征：A->bf = 2, B->bf = 1
```
A->lchild = B->lchild;
B->lchild = A;
A->bf = B->bf = 0;
if (FA==NULL) t=B;
else if(A == FA->lchild) FA->lchild= B;
else FA->rchild= B;
```
  - LR型:A_LR插入新节点后失衡。记B=A_L, C=A_LR
    - 特征：A->bf = 2, B->bf = -1
```
B->rchild = C->lchild ;
A->lchild = C->rchild;
C->lchild = B;
C->rchild = A;
if (S->key<C->key){/在C下插入S
    A->bf=-1; 
    B->bf=0; 
    C->bf=0;
  }
else if (S->key>C->key){//在Cp下插入S
  A->bf=0; 
  B->bf=1; 
  C->bf=0;
}
else if(S->key==C->key){//C本身就是插入的新结点S
  A->bf=0; 
  B->bf=0;
}
if (FA==NULL) t = C;
else if(A == FA->lchild) FA->lchild = C;
else FA->rchild = C;
```
  - RR型:A_RR插入新节点后失衡。记B = A_R
    - 特征：A->bf = -2, B->bf = -1
```
A->rchild = B->lchild;
B->lchild = A;
A->bf = 0;
B->bf = 0;
if (FA == NULL) t = B;
else if(A == FA->lchild)  FA->lchild = B;
else FA->rchild = B;
```
  - RL型:A_RL插入新节点后失衡。记B = A_R, C = A_RL
    - 特征：A->bf = -2, B->bf = 1
```
B->lchild = C->rchild ;
A->rchild = C->lchild;
C->lchild = A;
C->rchild = B ;
if(S->key < C->key){//在C下插入S
  A->bf=0; 
  B->bf=-1; 
  C->bf=0;
}
else if(S->key > C->key){//在C下插入S
  A->bf=1; 
  B->bf=0; 
  C->bf=0;
}
else(S->key==C->key){//C本身就是插入的新结点S
  A->bf=0; 
  B->bf=0;
}
if(FA == NULL) t=C;
else if(A == FA->lchild) FA->lchild = C;
else FA->rchild = C;
```

计算式查找法

即哈希查找法。基本思想:首先在元素的关键字h和元素的存储位置p之间建立一个对应关系H,使得p=H(k),H称为哈希函数。创建哈希表时,把关键字为h的元素直接存人地址为H(k)的单元;以后当查找关键字为hi的元素时,再利用哈希函数计算出该元素的存储位置p=H(k),从而达到按关键字直接存取元素的目的
构造哈希函数：教材P300-302
- 原则：函数便于计算；计算得到地址分布均匀，冲突少
- 常用方法：
  1. 数字分析法
  2. 平方取中法
  3. 分段叠加法
    - 折叠法
    - 移位法
  4. 除留余数法
  5. 伪随机数法
解决冲突：教材P302-304
- 开放定址法（再散列法）
  - $h_{i} = (H(key) + d_{i}) % m , i = 1,2,...,n$
    亦即 $h_{i} = (h_{0} + d_{i}) % m , i = 1,2,...,n$
  - 增量序列d的取法：
    - 线性探测再散列: $d_{i} = 1,2,3...,m-1$
    - 二次探测再散列: $d_{i} = 1^2,-1^2,2^2,-2^2,...k^2,-k^2(k\leq\dfrac{m}{2})$
    - 伪随机探测再散列
- 再哈希法：同时构造多个哈希函数，一个不行换下一个
- 链地址法：构成同义词链的单链表，将表头存储再哈希表的
- 建立公共溢出区：将哈希表分为基本表和溢出表
装填因子 $\alpha = \dfrac{哈希表中元素个数}{哈希表长度}$

显然， $\alpha$ 越小，发生冲突的可能越小，

平均查找长度

方法	线性探测再散列	伪随机探测、二次探测、哈希法	链址法
成功时的ASL	$\dfrac{1}{2}(1+\dfrac{1}{1-\alpha})$	$-\dfrac{1}{\alpha}ln(1-\alpha)$	$1+\dfrac{\alpha}{2}$
失败时的ASL	$\dfrac{1}{2}(1+\dfrac{1}{(1-\alpha)^2})$	$\dfrac{1}{1-\alpha}$	$\alpha+e^{-\alpha}$

哈希表的平均查找长度ASL是装填因子 $\alpha$ 的函数，和待散列元素数目n无关

装填因子通常取0.7-0.8