查找

1. 顺序：
   ASL(n) = (n+1)/2
2. 折半：
   当n大于50时 ASL ≈ ㏒₂(n+1) - 1
   n趋于无穷大时 ASL = ((n+1)㏒₂(n+1))/n - 1
3. 分块：
   长为 n 的表分成均等的 b 块，每块 s 个元素
   ①ASL = ㏒₂(n/s + 1) + s/2
   ②b = (n/s)向上取整
   ASL = (b+1)/2 + (s+1)/2
   如果索引表中采用折半查找，则ASL=(s+1)/2+㏒₂(b+1)-1

(一)查找的基本概念

1.问题: 在哪里找?
查找表
查找表是由同一类型的数据元素 (或记录) 构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构

2.问题: 什么是查找?
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或(记录)
关键字：用来标识一个数据元素 (或记录) 的某个数据项的值
     主关键字：可唯一地标识一个记录的关键字是主关键字；
     次关键字：反之，用以识别若干记录的关键字是次关键字。

3.问题: 查找成功否?
若查找表中存在这样一个记录，则称 “查找成功”
     查找结果给出整个记录的信息，或指示该记录在查找表中的位置
否则称 “查找不成功”
     查找结果给出“空记录”或“空指针”

4.问题: 查找目的是什么?
对查找表经常进行的操作作:

1. 查询某个 “特定的” 数据元素是否在查找表中
2. 检索某个 “特定的” 数据元素的各种属性
3. 在查找表中插入一个数据元素
4. 删除查找表中的某个数据元素

5.问题: 查找表怎么分类?
查找表可分为两类
静态查找表
仅作“查询”(检索)操作的查找表
动态查找表
作“插入”和“删除”操作的查找表
     有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;
     或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素，此类表为动态查找表。

6.问题: 如何评价查找算法?
查找算法的评价指标:
关键字的平均比较次数，也称平均查找长度ASL(Average Search Length)
ASL =∑pici(关键字比较次数的期望值)
n:记录的个数
pi:查找第i个记录的概率(通常认为pi =1/n)
ci: 找到第i个记录所需的比较次数

7.问题: 查找过程中我们要研究什么?
   查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。
   由于对查找表来说，在集合中查询或检索一个“特定的”数据元素时若无规律可循，只能对集合中的元素一一加以辨认直至找到为止。
   而这样的“查询”或“检索”是任何计算机应用系统中使用频度都很高的操作，因此设法提高查找表的查找效率，是本章讨论问题的出发点。
   为提高查找效率素一个办法就是在构造查找表时，在集合中的数据元之间人为地加上某种确定的约束关系。
研究查找表的各种组织方法及其查找过程的实施

(二)线性表的查找

(1)线性查找(顺序查找)

应用范围:
顺序表或线性链表表示的静态查找表
表内元素之间无序

数据元素类型定义

typedef struct {
	KeyType key; //关键字域
	...... //其他域
} ElemType;

顺序表结构类型定义

typedef struct{
	ElemType *R; //表基址//表长
	int length;
}SSTable; //Sequential Search Table
SSTable ST; //定义顺序表ST

*设置监视哨的顺序查找*

int Search Seq( SSTable ST , KeyType key ){
	ST.R[O].key =key;
	for( i=ST.length; ST.R[ i ].key!=key;--i);
	return i;
}

当ST.length 较大时，此改进能使进行一次查找所需的平均时间几乎减少一半

时间效率分析
比较次数与key位置有关：
查找第 i 个元素，需要比较 n - i + 1次
查找失败，需比较 n + 1 次
时间复杂度：O(n)
    ASL(n) = (1+2+…+n)/n = (n+1)/2
空间复杂度：一个辅助空间 —— O(1)

如何提高查找效率?
1、记录的查找概率不相等时如何提高查找效率?
查找表存储记录原则 一 按查找概率高低存储
1)查找概率越高，比较次数越少
2)查找概率越低，比较次数较多

2、记录的查找概率无法测定时如何提高查找效率?
方法 —— 按查找概率动态调整记录顺序
1)在每个记录中设一个访问频度域
2)始终保持记录按非递增有序的次序排列
3)每次查找后均将刚查到的记录直接移至表头

顺序查找的特点
优点: 算法简单，逻辑次序无要求，且不同存储结构均适用
缺点: ASL太长，时间效率太低。

(2)折半查找(二分/对分查找)

有序表表示静态查找表 -> 折半查找法(二分查找)
折半查找：每次将待测记录所在区间缩小一半

查找过程
mid = (low + high) / 2
key < mid则: high = mid - 1
key > mid则 : low = mid + 1
key == mid ，找到
high < low，结束

折半查找算法: (非递归算法)
设表长为n，low、high和mid分别指向待查元素所在区间的上界下界和中点，key为给定的要查找的值
初始时，令low=1，high=n，mid=⌊(low+high)/2⌋
让k与mid指向的记录比较
    若key == R[mid].key 查找成功
    若key < R[mid].key，则 high = mid-1
    若key > R[mid].key，则 low = mid+1
重复上述操作，直至low > high时，查找失败

折半查找非递归

int Search_Bin ( SSTable ST, KeyType key ) {
	low = 1 ; 
	high = ST.length ;// 置区间初值
	while (low <= high) {
		mid = (low + high) / 2; 
		if (ST.R[mid].key == key) return mid ; // 找到待查元素
		else if (key < ST.R[mid].key) {//缩小查找区间
			high=mid-1;//继续在前半区间进行查找
		}else {
			low = mid + 1;// 继续在后半区间进行查找
		}
	}
	return 0 ;// 顺序表中不存在待查元素
}

递归算法

int Search_Bin ( SSTable ST, KeyType key ,int low,int height) {
	if(low > height) return 0;
	mid = (low + high) / 2; 
	// 找到待查元素
	if (ST.elem[mid].key == key){
		 return mid 
	}else if (key < ST.R[mid].key) {
		Search_Bin(ST,key,low,mid-1)
	}else {
		Search_Bin(ST,key,mid + 1,height)
	}
}

折半查找的性能分析 —— 判定树

查找成功：
比较次数 = 路径上的结点数 = 结点的层数 <= 树的深度(⌊㏒₂n⌋ + 1)
查找不成功：
比较次数 = 路径上的内部结点数 <= 树的深度(⌊㏒₂n⌋ + 1)

时间效率分析
成功时：
ASL ≈ ㏒₂(n+1) - 1 (n>50)
ASL = ((n+1)㏒₂(n+1))/n - 1

折半查找的特点
优点: 效率比顺序查找高
缺点:只适用于有序表，且限于顺序存储结构 (对线性链表无效)

(3)分块查找(索引查找)

牛津词典的索引
索引顺序表的查找

条件:

1. 将表分成几块，且表或者有序，或者分块有序
   若 i < j ,则第 j 块中所有记录的关键字均大于第i块中的最大关键字。
2. 建立索引表(每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序)

查找过程:
先确定待查记录所在块(顺序或折半查找)
再在块内查找(顺序查找)

查找效率
ASL = Lb + Lw
Lb:对索引表查找的ASL
Lw:对块内查找的ASL
①ASL = ㏒₂(n/s + 1) + s/2

长为 n 的表分成均等的 b 块，每块 s 个元素
②b = (n/s)向上取整
ASL = (b+1)/2 + (s+1)/2
如果索引表中采用折半查找，则ASL=(s+1)/2+㏒₂(b+1)-1

分块查找的优缺点
优点: 插入和删除比较容易，无需进行大量移动。
缺点:要增加一个索引表的存储空间并对初始索引表进行排序运算
适用情况: 如果线性表既要快速查找又经常动态变化，则可采用分块查找

查找方法比较

(三)树表的查找

如果用折半查找，当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录

改用动态查找表 —— 几种特殊的树
表结构在查找过程中动态生成

对于给定值key
若表中存在，则成功返回
否则，插入关键字等于key的记录

(1)二叉排序树BST

二叉排序树(BST)(Binary Sort Tree)：又称为二叉搜索树、二叉查找树

定义：
二叉排序树或是空树，或是满足如下性质的二叉树：
(1)若其左子树非空，则左子树上所有结点的值均小于根结点的值
(2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值
(3)其左右子树本身又各是一棵二又排序树

二叉排序树的性质
中序遍历非空的二又排序树所得到的数据元素序列是一个按关键字排列的递增有序序列
(二叉排序树中序遍历：递增有序)

①二叉排序树-查找Find

若查找的关键字等于根结点，成功
否则
    若小于根结点，查其左子树
    若大于根结点，查其右子树
在左右子树上的操作类似

二叉排序树的存储结构

typedef struct {
	KeyType key;//关键字项
	InfoType otherinfo ;//其他数据域
} ElemType;

typedef struct BSTNode {
	ElemType data ;   //数据域
	struct BSTNode *Ichild*rchild; //左右孩子指针
}BSTNode，*BSTree;

BSTree T;  //定义二叉排序树T

查找算法

BSTree SearchBST(BSTree T,KeyType key) {
	if((!T)  key==T->data.key){
		 return T;
	}else if (key<T->data.key){
		return SearchBST(T->lchild,key); //在左子树中继续查找
	}else return SearchBST(T->rchild,key); //在右子树中继续查找

比较的关键字次数 = 此结点所在层次数 最多的比较次数 = 树的深度

二叉排序树的平均查找长度：
树的高度越高，平均查找长度ASL越大(ASL和树的形态有关)

最好：
    ASL = ㏒₂(n+1) - 1
    树的深度：⌊㏒₂n⌋ + 1 层
    与折半查找中的判定树向同
    O(㏒₂n)
最坏：
    ASL = (n+1)/2
    n 个结点 n 层,深度为 n
    查找效率与顺序查找相同
    O(n)

②二叉排序树-插入Insert

若二又排序树为空，则插入结点作为根结点插入到空树中
否则，继续在其左、右子树上查找
    树中已有，不再插入
    树中没有
        查找直至某个结点的左子树或右子树为空为止，则插入
        结点应为该结点的左孩子或右孩子
插入的元素一定在叶结点上

③二叉排序树-生成

从空树出发，经过一系列的查找、插入操作之后，可生成一颗二叉排序树。
一个无序序列可通过构造二叉排序树而变成一个有序序列构造树的过程就是对无序序列进行排序的过程
插入的结点均为叶子结点，故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。

关键字的输入顺序不同，建立的不同二叉排序树

④二叉排序树-删除Delete

   从二又排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变
   由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二又排序树中删去一个结点相当于删去有序序列中的一个结点。

1. 被删除的结点是叶子结点：直接删除
   双亲结点指向的值改为null
   
2. 被删除的结点只有左子树or只有右子树，
   用其左子树or右子树替换它(结点替换)，将其双亲结点指向被删除结点的左子树or右子树
   
3. 被删除的结点既有左子树，也有右子树
   ①以其中序前趋值替换之 (值替换) ，然后再删除该前趋结点
   前趋是左子树中最大的结点
   ②也可以用其后继替换之，然后再删除该后继结点
   后继是右子树中最小的结点
   

全部情况的例子：

(2)平衡二叉树AVL

问题:如何提高形态不均衡的二又排序树的查找效率?（树的查找效率取决于树的高度）
解决办法:做 “平衡化”处理，即尽量让二叉树的形状均衡!

平衡二叉树 (balanced binary tree) 又称 AVL树 (Adelson-Velskii and Landis)

一棵平衡二又树或者是空树，或者是具有下列性质的二叉排序树：

• 左子树与右子树的高度之差的绝对值小于等于1
• 左子树和右子树也是平衡二又排序树

    为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子 (BF)。
平衡因子 = 结点左子树的高度 - 结点右子树的高度
根据平衡二又树的定义，平衡二又树上所有结点的平衡因子只能是-1、0，或1。

失衡二叉排序树的分析与调整
如果在一棵AVL 树中插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡

平衡调整的四种类型

A: 失衡结点 不止一个失衡结点时，为最小失衡子树的根结点
B: A结点的孩子，C结点的双亲
C: 插入新结点的子树

调整原则：
①降低高度
②保持二叉排序树性质

LL：
B结点带左子树一起上升
A结点成为B的右孩子
原来B结点的右子树作为A的左子树
RR:
B结点带右子树一起上升
A结点成为B的左孩子
原来B结点的左子树作为A的右子树
LR:
C结点穿过A、B结点上升
B结点成为C的左孩子
A结点成为C的右孩子
原来C结点的左子树作为B的右子树
原来C结点的右子树作为A的左子树
RL:
C结点穿过A、B结点上升
B结点成为C的右孩子
A结点成为C的左孩子
原来C结点的左子树作为A的右子树
原来C结点的右子树作为B的左子树

(3)红黑树RBT

红黑树（R-B Tree，Red-Black Tree）它一种特殊的二叉查找树，同时具备以下特征

为了解决AVL树的问题，保证查找效率的同时，提升插入效率(插入效率比 AVL高，不用做复杂旋转[最多旋转两次])

从根到叶子的最长的路径不多于最短的可能路径的两倍长

1. 节点非红即黑
2. 根节点是黑色
3. 所有NUll节点称为叶子节点，且认为颜色为黑
4. 所有红色节点的子节点都为黑色
5. 从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点

(4)B-树

B-树是一种平衡的有序的多路查找树
磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。

一棵 m 阶的 B-树 ，或为空树,或为满足下列特性的 m 叉树:
(1)树中每个结点至多有 m 棵子树(即最多有 m 个分叉，最多有 m-1 个关键字[按照递增顺序排列]);
(2) 若根结点不是叶子结点(终端结点),则至少有两棵子树;
(3)除根之外的所有非终端结点至少有 ⌈m/2⌉ 棵子树;

保持绝对的平衡，所有的叶结点都出现在同一层次上，并且不带信息

n 存了几个关键字
Ki (i从 1 开始)是当前结点存的关键字
Ai (i从 0 开始)指向子树结点的指针

B-树具有平衡、有序、多路的特点。

(5)B+树

B+ 树是一种 B-树的变形树，更适合用于文件索引系统。
有着比B-树更高的查询性能

B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。

B+ 树和B-树的差异
一棵 m 阶的 B+ 树 和 m 阶的 B-树的差异在于：
（1）有n棵子树的结点中含有n个关键字；
（2）所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；
（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

B+树对比B树的优势总结：
单一节点存储更多的元素，使得查询的 IO 次数更少。
所有查询都要查找到叶子节点，查询性能稳定。
所有叶子节点形成有序链表，便于范围查询。

键树

(四)哈希表的查找

Hash：哈希
翻译为：散列、杂凑

基本思想：记录的存储位置与关键字之间存在对应关系
对应关系 —— hash函数
Loc(i) = H(keyi)

关键字的值是多少，其存储位置就是在哪儿
用关键字的值直接去对应一个存储位置
H(key) = k
优点:查找效率高 O(1)
缺点: 空间效率低!

(1)散列表的若干术语

散列方法(杂凑法)
    选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放
    查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功
散列函数(杂凑函数): 散列方法中使用的转换函数
散列表(杂凑表): 按上述思想构造的表
冲突:不同的关键码映射到同一个散列地址
    key1≠key2，但是H(key1)=H(key2)
同义词:具有相同函数值的多个关键字

(2)散列函数的构造方法

使用散列表要解决好两个问题：
①构造好的散列函数
②制定一个好的解决冲突的方案

构造散列函数考虑的因素
①执行速度(即计算散列函数所需时间)
②关键字的长度
③散列表的大小
④关键字的分布情况
⑤查找频率

根据元素集合的特性构造要求
①地址空间尽量小
②尽量均匀地存放，以避免冲突

方法
①直接定址法
②数字分析法
③平方取中法
④折叠法
⑤除留余数法
⑥随机数法

①直接定址法

Hash(key) = a.key + b (a、b为常数)
优点: 以关键码key的某个线性函数值为散列地址，不会产生冲突
缺点:要占用连续地址空间，空间效率低

②除留余数法

Hash(key)= key mod p (p是一个整数)
关键:如何选取合适的p?
技巧: 设表长为m，取 p ≤ m 且为质数

(3)处理冲突的方法

1. 开放定址法 (开地址法)
2. 链地址法(拉链法)
3. 再散列法(双散列函数法)
4. 建立一个公共溢出区

①开放定址法(开地址法)

基本思想:有冲突时就去寻找下一个空的散列地址，只要散列表足够天空的散列地址总能找到，并将数据元素存入。(非同义词可能会冲突)

例如: 除留余数法 Hi=(Hash(key)+di) mod m
di:为增量序列

确定增量序列 di 的常用方法：
①线性探测法： di 为 1，2，…m-1线性序列
    一旦冲突，就找下一个地址，直到找到空地址存入
②二次探测法： di为 1²，-1²，2²，-2²,…,q² 二次序列
③伪随机探测法： di 为伪随机数序列

②链地址法(拉链法)

基本思想: 相同散列地址的记录链成一单链表，m 个散列地址就设 m 个单链表，然后用一个数组将 m 个单链表的表头指针存储起来，形成一个动态的结构。

链地址法的优点
①非同义词不会冲突，无“聚集”现象
②链表上结点空间动态申请，更适合于表长不确定的情况

(4)散列表的查找

例题：

使用平均查找长度ASL来衡量查找算法，ASL取决于
散列函数
处理冲突的方法
散列表的装填因子α

装填因子α = 表中填入的记录数 / 哈希表的长度
α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

1. 散列表技术具有很好的平均性能，优于一些传统的技术
2. 链地址法优于开地址法
3. 除留余数法作散列函数优于其它类型函数

Donate