第九章 查找

1、顺序表查找

1）顺序查找

①无监视哨查找

每次都要判断 i 是否越界。

②有监视哨查找

基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高了查找速度。


顺序查找的优缺点：

2）折半查找

使用条件：
线性表中的记录必须按关键码有序；
必须采用顺序存储。
基本思想：
在有序表中，取中间记录作为比较对象，
①若给定值与中间记录的关键码相等，则查找成功；
②若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；
③若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。
不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

①非递归实现

②递归实现

折半查找的性能分析：

3）分块查找

适用于对关键字分块有序的查找表进行查找操作。
关键字分块有序指的是：按关键字大小分成若干子表（或称为块），且前一块中的最大关键字小于后一块中的最小关键字，但是各个块内部的关键字不一定有序。

分块查找需要对子表建立索引表，查找表的每一个子表有索引表中的索引项确定。
索引项包括：关键字字段（存放对应子表中最大关键值）和指针字段（存放子表对应的起始序号）。

索引表通常有序，可以用折半查找

分块查找的效率介于顺序查找和折半查找之间。

2、树表的查找

1）二叉排序树

也称为二叉查找树。
特点：（树不为空树的情况下）
（1）若它的左子树不空，则左子树上所有节点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
（3）它的左右子树也都是二叉排序树。
二叉排序树的定义采用的是递归方法。

①插入

代码表示：

②构造

③查找

递归查找


总结

④删除

二叉排序树上删除某个结点后，仍然保持二叉排序树的特性。
分以下三种情况讨论：
（1）被删除的结点是叶子结点；
（2）被删除的结点只有左子树或者只有右子树；
（3）被删除的结点既有左子树，也有右子树。



删除算法描述（递归实现）：

2）平衡二叉树

平衡因子只能为：1，0，-1

①构造

基本思想：

**类型：**LL型，RR型，LR型，RL型

LL型调整方法：
进行一次向右的顺时针旋转；
RR型调整方法：
进行一次向左的逆时针旋转；
LR型调整方法：
进行两次旋转，首先具有不平衡因子的结点A（A的右孩子结点为B，B的左孩子为C）不动，做一次向左的逆旋转，将支撑点由B调整到C；然后进行一次向右的顺旋转，将支撑点由结点A调整到C处。

RL型调整方法：
进行两次旋转，首先具有不平衡因子的结点A（A的右孩子结点为B，B的左孩子为C）不动，做一次向右的顺旋转，将支撑点由B调整到C；然后进行一次向左的逆旋转，将支撑点由结点A调整到C处。

3）B树

B即balanced，平衡的意思。所以B树是平衡二叉树的延伸。
B树属于动态的多级索引，是一种平衡的多路查找树，它在文件系统很有用。
定义：一棵m阶的B树，或者为空树，或者为满足以下性质的m叉树：

<1>性质

①树中的叶子结点说明

②树中关键字的要求

③树中子树的要求

<2>查找

<3>插入

<4>删除

４）B＋树

3、Hash查找

1)散列技术的关键问题

①散列函数的设计

②冲突处理

(1)开放定址法

① 线性探测法
②二次探测法
③双hash函数探测法

(2)链地址法