数据结构考研第七章——查找（内含动态）

一、顺序查找（下标从1开始）

1. 算法思想：把待查关键字key存入表头（哨兵），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。
2. 数据结构

typedef struct{
	ElemType *elem;
	int TableLen;
}SSTable;
1
2
3
4

3. 代码实现

int Search_Seq(SSTable ST,KeyType key){
	ST.elem[0]=key
	for(i=ST.TableLen;ST.elem[i]!=key;--i);		//当不存在key，将查找到i=0，退出循环
	return i;
}
1
2
3
4
5

4. 具体实例（算法较为简单，此处省略动态，谢谢）
5. 性能分析

1. 空间复杂度：仅使用一个辅助变量，因而空间复杂度为O(1);
2. 平均查找长度：ASL = (n+1)/2
3. 使用范围：顺序表、链式表

二、有序表的顺序查找(下标从1开始)

1. 算法思想：若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。
2. 代码实现（很有趣的是，只需要在顺序查找中修改一个符号就行）

int Search_Seq(SSTable ST,KeyType key){
	ST.elem[0]=key
	for(i=ST.TableLen;ST.elem[i]>=key;--i);		//修改地方：ST.elem[i]>=key
	return i;
}
1
2
3
4
5

3. 算法分析

1. 平均查找长度：ASL=n/2+n/(n+1)
2. 空间复杂度：仅使用一个辅助变量，因而空间复杂度为O(1);
3. 使用范围：有序顺序表、有序链式表

三、折半查找（下标从0开始）

1. 算法思想：首先将给定值key与表中中间位置的元素比较，若相等则查找成功，返回该元素的存储位置；若不等则所需查找的元素只能在中间元素以外的前半部分或后半部分。
2. 代码实现

int Search_Bin(SSTable ST,KeyType key){
	int low=0,high=ST.TableLen-1,mid;
	while(low<high){
		mid=(low+high)/2;
		if(ST.elem[mid]==key) return mid;
		else if(ST.elem[mid]<key) low=mid+1;
		else high=mid-1;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10

3. 具体实例
   
4. 算法分析

1. 平均查找长度：ASL=$lo{g}_2$（n+1）
2. 空间复杂度：O(1)
3. 使用范围：有序顺序表、有序链表

四、分块查找

1. 算法思想

1. 块内无序，块之间有序。即第一个块中的最大关键字小于第二个块中的所有记录的关键字，以此类推。
2. 再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址。
3. 查找过程：首先在索引表中确定待查记录所在的块，可以顺序查找也可以折半查找。然后在块内顺序查找。

2. 具体实例
   
3. 算法分析

1. 平均查找长度：ASL=ASL折半查找+ASL顺序查找=$lo{g}_2$(b+1) +（s+1）/2，其中b为块数，s为块内记录个数

五、二叉排序树BST（通过中序遍历可以得到递增有序序列）

1. 基本概念：左子树小于根，右子树大于根，通过中序遍历可以得到递增有序序列。
2. 查找

【算法思想】

1. 若key=结点，返回结点地址；
2. 若key<结点，查找左子树；
3. 若key>结点，查找右子树；

【代码实现】

BSTree SearchBST(BSTree T,KeyType key){
	while(T!=NULL&&key!=T->data){
		if(key<T->data) T=T->lchild;
		else T=T->rchild;
	}
	return T;
}
1
2
3
4
5
6
7

【具体实例】

【算法分析】

1. 当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；
   当有序表是动态查找表时，宜用二叉排序树作为逻辑结构；

3. 插入

【算法思想】

1. 若原二叉排序树为空，则直接插入结点；
2. 若原二叉树不为空，
   *******若关键字k小于根结点值，则插入左子树，
   *******若关键字k大于根结点值，则插入到右子树。
3. 插入的结点一定是一个新添加的叶结点

【代码实现】

int BST_Insert(BiTree &T,KeyType k){
	if(T==NULL){				//这是最终要实现的，下面的都是查找适合的位置
		T=(BiTree*)malloc(sizeof(BSTNode));
		T->data=k;
		T->lchild=NULL;
		T->rchild=NULL;
		return 1;
	}
	else if(k=T->data) return 0;		//二叉排序树存在相同元素，则插入失败
	else if(k>T->data) return BST_Insert(T->lchild,k);
	else return BST_Insert(T->rchild,k);
}
1
2
3
4
5
6
7
8
9
10
11
12

【具体实例】

4. 二叉排序树的构造

【算法思想】

对每个元素调用一次插入

【代码实现】

void Creat_BST(BiTree &T,KeyType str[],int n){
	T=NULL;
	int i=0;
	while(i<n){
		BST_Insert(T,str[i]);
		i++;
	}
}
1
2
3
4
5
6
7
8

【具体实例】：与上述插入过程完成一样。

5. 二叉排序树的删除

【算法思想】：将因删除结点而断开的二叉链表重新链接起来，防止重新链接后树的高度增加

1. 删除叶节点，只需将其双亲结点指向它的指针清零，再释放它即可。
2. 被删除结点只有左子树，可以拿它的左子树结点顶替它的位置，再释放它。
3. 被删除结点只有右子树，可以拿它的右子树结点顶替它的位置，再释放它。
4. 被删除结点有左右子树，可以拿它的右子树中寻找中序下的第一个结点顶替它的位置，再来处理这个结点的删除问题。

【具体实例】

六、平衡二叉树AVL（通过中序遍历可以得到递增有序序列）

1. 基本概念

1. 平衡因子：该结点左子树与右子树的高度差

2. 平衡旋转 （动图展示）

1. 重点是在三个元素中找到中位数作为根结点
【LL平衡旋转】
【RR平衡旋转】
【LR平衡旋转】
【RL平衡旋转】

3. 平衡二叉树的删除

1. 与二叉树的删除相同，删除后要平衡旋转

4. 平衡二叉树的查找

1. 与二叉树的查找相同
2. 平均查找长度：ASL=O(log2n)

算法分析

1. 高度：二叉平衡树高度保持在O($lo{g}_2$n)

七、红黑树（后面补上）

八、B树（通过“中序遍历”可以得到递增有序序列）

1. 基本概念

1. B树：B树与AVL树的差别就是B树属于多叉树，又名平衡多路查找树，即一个结点的查找路径不止左右两个，而是有多个。数据库索引技术里大量使用B树和B+树的数据结构，一个结点存储多个值。
2. B树的阶数：M阶表示一个B树的结点最多有多少个查找路径。M=2是二叉树，M=3是三叉树。

2. 特点

1. 每个结点的值都是按递增次序排序存放的，并遵循左小右大原则
2. B树的所有叶子结点都位于同一层并且不带信息。实际上这些结点是不存在的，指向这些结点的指针为空。
3. 根节点的子节点个数为[2，M]
4. 除根节点以外的非叶子结点的子节点个数为[Math.ceil(M/2)，M]。
5. 每个非叶子结点的元素的个数=子节点个数-1，为[Math.ceil(M/2)-1，M-1]

3. 高度
   
4. 数据库的应用

在数据库查询中，以树存储数据。树有多少层，就意味着要读多少次磁盘IO。
所以树的高度越矮，就意味着查询数据时，需要读IO的次数就越少。（众所周知，读IO是一件费事的操作）
当数据量大的时候，用AVL树存的话，就算AVL是平衡树，但是也扛不住数据量大，数据量大，AVL树的树高肯定很高，那么读取数据的IO次数也会多。那么有没有办法能压缩AVL树的树高呢？这时候B树就出来了。B树的一个结点可以装多个值，读取时，是把整个结点读到内存，然后在内存中，对结点的值进行处理，在内存中处理速度肯定比磁盘快。所以只要树的高度低，IO少，就能够提升查询效率，这是B树的好处之一。

5. B树的查找

【算法思想】

B树的查找基本分为两个基本操作：①在B树中找到结点；②在结点内找到关键字。由于B树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标后，先将结点信息读入内存，然后再结点内采用顺序查找法或折半查找法

6. B树的插入

1. 定位：利用上述B树的查找法，找到插入该关键字的子底层中的某个非叶结点。（在B树查找key中，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。注意：插入位置一定是最底层中的某个非叶结点。）
2. 插入：插入后结点个数小于m则直接插入，否则需要分裂。
3. 分裂：插入key后的原结点，从中间位置math.ceil(m/2)将其中的关键字分为两部分，左部分关键字放在原结点中，右部分关键字放在新结点中，中间位置math.ceil(m/2)插入父节点。若此时导致父结点关键字个数超过了上限也要这样分裂。最后根节点也超上限了，那就高度+1

【具体实例】：6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

7. B树的删除
【被删除关键字k不在终端结点】（一层一层的代替，把问题向下推，最后推成被删除关键字k在终端结点的问题）

可以用k的前驱或后继来替代k，这个前驱或后继“是通过中序遍历”得到的元素

【被删除关键字k在终端结点】（这个才是复杂的）

1. 直接删除关键字k：在终端结点删除关键字k后符合B树定义，则直接删除关键字k
2. 兄弟够借：如果删除结点中关键后，关键字个数
3. 兄弟不够借：如果删除结点中关键后，关键字个数

【具体实例】B树动态实验地址

九、 B+树（只考基本概念）

基本概念

【数量关系】

1. 根结点子树个数为[2，M]，关键字个数为[2，M]
2. 非根结点子树个数为[Math.ceil(M/2)，M]，关键字个数为[Math.ceil(M/2)，M]
3. 结点子树个数和关键字个数相等

【B+树结构】

1. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针
2. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来。
3. 通常在B+树中有两个头指针：一个指向根结点，一个指向关键字最小的叶结点

【B+树与B树的区别】

1. B+树中，具有n个关键字的结点只含有n棵子树；
   B树中，具有n个关键字的结点含有n+1棵子树；
2. B+树中，每个结点关键字个数范围为[Math.ceil(M/2)，M]；
   B树中，每个结点关键字个数范围为[Math.ceil(M/2)-1，M-1]
3. 在B+树中，叶结点包含信息，所有非也结点仅起索引作用
4. 在B+树中，叶节点包含了所有关键字

查找操作

1. 方法一：从最小关键字开始的顺序查找；(因为是链表形式，所以只能顺序查找)
2. 方法二：从根结点开始的多路查找；

十、散列表

1. 基本概念

1. 散列表：根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系。在理想情况下，对散列表进行查找的时间复杂度为O(1)。
2. 散列函数：就是上述提到的映射关系
3. 冲突处理：把两个或多个关键字映射到同一地址上

2. 散列函数

【直接定址法】 H(key)=a*key+b

1. 冲突：不冲突
2. 适用：适合关键字的分布基本连续情况
3. 问题：如果关键字不连续，那就产生很多空位

【除留余数法】 H(key)=key%p

1. 冲突：关键是选好P，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性

【数字分析法】 抽取关键字中分布较为均匀的若干位作为散列地址

1. 适用：适用在已知关键字集合中，如果更换了关键字集合，则需要重新构造新的散列函数

【平方取中法】 关键字的平法值中间几位作为散列地址

1. 特点：散列地址较为均匀

3. 处理冲突的方法

【开放地址法】 即发生冲突时就寻找下一个空的哈希地址，只要地址足够大，总能找到

1. 线性探测法：Hi=（Hash(key)+$d_i$）mod m，其中di=0，1，2，3…
2. 平方探测法：Hi=（Hash(key)+$d_i$）mod m，其中di=0，$1^2$，-$1^2$，$2^2$，-$2^2$…
3. 双散列法 ： Hi=（Hash(key)+i*$d_i$）mod m，其中di=$Has{h}_2$(key)
4. 伪随机序列法：Hi=（Hash(key)+$d_i$）mod m，其中di=伪随机序列法

【链接法】 把所有的同义词存储在一个线性链表中，这个线性链表可以由其散列地址唯一标识。

4. 散列查找

【查找算法】

1. 检测表中地址为Addr的位置上是否有记录，若无记录，返回查找失败；
   若有记录，比较Addr对应元素与关键字，如相等则返回查找成功的标记；
   否则执行步骤2
2. 用给定的冲突处理方法计算下一个散列地址，并把Addr置为此地址，转入步骤1

【算法分析】

1. 以平均查找长度作为衡量散列表的查找效率的度量
2. 决定查找效率的三个因素：散列函数、处理冲突方法、装填因子=(表中记录数n) / (散列表长度m)