第10 章 查找
查找的基本概念
静态查找
动态查找
本章主要知识点：
–查找的基本概念和衡量查找算法效率的标准
–静态查找表，主要包括顺序查找方法和索引顺序方法
–动态查找表，主要包括二叉排序树和B_树
查找的基本概念
查找:查询关键字是否在(数据元素集合）表中的过程。也
称作检索。
主关键字:能够惟一区分各个不同数据元素的关键字
次关键字:通常不能惟一区分各个不同数据元素的关键字
查找成功:在数据元素集合中找到了要查找的数据元素
查找不成功:在数据元素集合中没有找到要查找的数据元素
静态查找:只查找，不改变数据元素集合内的数据元素
动态查找:既查找，又改变（增减）集合内的数据元素
平均查找长度:查找过程所需进行的关键字比较次数的平均值,
是衡量查找算法效率的最主要标准,其数学定义为：
静态查找表
静态查找表主要有三种结构：
无序序列
有序序列
索引结构
在无序序列中查
找
基本思想是：从顺序表的一端开始，用给定数据元素的关
键字逐个和顺序表中各数据元素的关键字比较，若在顺序表
中查找到要查找的数据元素，则查找成功，函数返回该数据
元素在顺序表中的位置；否则查找失败，函数返回-1 。
查找函数设计如下：
public static int seqSearch(int a[], int item) {
//在数组a中顺序查找数据元素item 是否存在，
//查找成功时返回该元素的下标序号；失败时返回-1
int n= ;
int i = 0;
while(i < n && a[i] != item) i++;
if(a[i] == item) return i;
else return -1;
}
算法分析
查找成功时的平均查找长度ASL 成功为：
查找失败时的平均查找长度ASL 失败为
时间效率为 O (n )
在有序序列中查找
有序序列的查找算法主要有顺序查找和折半查找两种方法。
一、顺序查找
有序顺序表上的顺序查找算法和无序序列中的查找算法方
法类同
public static int orderSeqSearch(int [] a, int elem ){
int n = ;
int i = 0;
while(i < n && a[i] < elem ) i ++;
if(a[i] == elem ) return i;
else return -1;
}
二、二分查找（又称折半查找）
算法的基本思想：先给数据排序（例如按升序排好），形成
有序表，然后再将key 与正中元素相比，若key 小，则缩小
至前半部内查找；再取其中值比较，每次缩小1/2 的范围，
直到查找成功或失败为止。反之，如果key 大，则缩小至后
半部内查找。
public static int biSeach(int [] a, int elem ){
int n = ;
int low = 0, high = n - 1, mid;
while(low <= high){
mid = (low + high)/2;
if(a[mid] == elem ) return mid;
else if(a[mid] < elem ) low = mid + 1;
else high = mid - 1;
}
return -1;
}
算法分析
查找成功时的平均查找长度ASL 成功为：
查找失败时的平均查找长度ASL 失败为
索引
当要查找的数据元素个数非常大时，采用给查找的数
据元素序列建立索引表的办法提高查找速度。把要在其
上建立索引表的数据元素序列称作主表。主表中存放着
数据元素的全部信息，索引表中只存放主表中要查找数
据元素的主关键字和索引信息。
8
14
6
9
10
22
34
18
19
31
40
38
54
66
46
71
78
68
80
85
14 00
34 51
66 102
85 153
key link下标
索引表
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
key 其它域位置
主表
索引表结构
图
索引表中的数据元素由
两个域构成，key 域为被
索引的若干个数据元素中
关键字的最大值，link域
为被索引的若干个数据元
素中第一个数据元素的位
置编号。
块内无序，块间升
序
完全索引表:和主表项完全相同，但只包含索引关键字和该
数据元素在主表中位置信息的索引表
二级索引表:当主表中的数据元素个数非常庞大时，按照建
立索引表的同样方法对索引表再建立的索引表。二级以上
的索引结构称作多级索引结构
等长索引表:索引表中的每个索引项对应主表中的数据元素
个数相等;反之称为不等长索引表。不等长索引表中的索引
长度可随着动态插入和动态删除过程改变,因此不仅适用于
静态查找问题，而且也适用于动态查找问题。
相关术语
假设索引表的长度为m ，主表中每个子表的长度为s，
并假设在索引表上和在主表上均采用顺序查找算法，则
索引顺序表上查找算法的平均查找长度为：
算法分析
动态查找表
动态查找表主要有二叉树结构和树结构两种类型。二叉
树结构有二叉排序树、平衡二叉树等。树结构有B- 树、B +
树等。
二二叉叉排排序序树树
一一、、基基本本概概念念
二叉排序树或是一棵空树；或者是具有如下性质的非空二叉树：
（1）左子树的所有结点均小于根的值；
（2）右子树的所有结点均大于根的值；
（3）它的左右子树也分别为二叉排序树。
381
12 410
9 40 394 540
35 190
146
476 760
445 600 800
下图所示就是一棵二叉排序树
二二、、二二叉叉排排序序树树的的结结点点类类
三三、、二二叉叉排排序序树树类类
设计见教材
设计见教材
四、二叉排序树查找算法
二叉排序树上的查找过程，就是遍历二叉排序树并在遍
历过程中寻找要查找的数据元素是否存在。循环结构的查
找算法设计如下：
public BiTreeNode find(int item){
if(root != null){
BiTreeNode temp = root;
while(temp != null){
if( () == item) return temp;
if( () < item)temp =
();
else temp = ();
}
}
return null;
}
五、插入算法
插入操作要求首先查找数据元素是否在二叉排序树中
存在，若存在则返回；若不存在，插入查找失败时结点的
左指针或右指针上。 插入算法设计如下:
public void insert(BiTreeNode ptr, int item) {
if(item< ()){
if(() == null){
BiTreeNode temp = new BiTreeNode (item); //生
成新结点
(ptr ); //把ptr结点设为temp 结点
的父结点
(temp ): //把temp 结点设为ptr结点的
左孩子结点
} else insert((),item); //在左子树递归
} else if(item> ()){
if(() == null){
BiTreeNode temp = new BiTreeNode (item); //生
成新结点
(ptr ); //把ptr结点设为temp 结点
的父结点
(temp ): //把temp 结点设为ptr结点
的左孩子结点
} else insert((),item); //在右子树递归
}
}
下图是调用上述插入函数依次插入数据元素
4,5,7,2,1,9,8,11,3的过程。
4
11
52
7
9
1 3
8
4
11
52
7
9
1
8
4
52
7
9
1
8
4
52
7
9
1
4
52
71
4
52
7
4
5
7
4
5
4
(d)(c)(b)
(a)
(g)(f)(e)
(i)(h)
六、删除算法
删除操作要求首先查找数据元素是否在二叉排序树中存在
，若不存在则结束；存在的情况及相应的删除方法有如下四
种：
(1)要删除结点无孩子结点，直接删除该结点。
(2)要删除结点只有左孩子结点，删除该结点且使被删除结
点的双亲结点指向被删除结点的左孩子结点。
(3)要删除结点只有右孩子结点，删除该结点且使被删除结
点的双亲结点指向被删除结点的右孩子结点。
(4)要删除结点有左右孩子结点，分如下三步完成：首先寻
找数据元素的关键字值大于要删除结点数据元素关键字的最
小值，即寻找要删除结点右子树的最左结点；然后把右子树
的最左结点的数据元素值拷贝到要删除的结点上；最后删除
右子树的最左结点。
删除过程分别如图所示
18
14 24
5 16 20 38
7
10
30
35
18
14 24
5 16 20 38
7 30
35
18
14 24
5 16 20 38
7
10
30
35
18
14 24
5 16 20 30
7
10
35
ptr
ptr
(a)无孩子结点
(b)有左孩子结点
18
14 24
5 16 20 38
7
10
30
35
18
14 24
7 16 20 38
10 30
35
18
14 24
5 16 20 38
7
10
30
35
18
14 38
5 16 30
7
10
20 35
ptr
ptr
(c)有右孩子结点
(d)有左右孩子结点
算法设计如下:
public void delete(BiTreeNode ptr, int item) {
if(ptr != null){
if(item < ()) delete((), item);//在左
子树递归
else if(item > ptrgetData ()) delete( (), item);
//在右子树递归
else if(() != null && () != null){
//要删除结点找到，且其左右子树均存在的情况
BiTreeNode min;
min = (); //取当前结点的右孩子结点
while( () != null)
min = (); //min 取到最左孩子结点
( ()); //把min 的数据值赋给ptr
结点
delete( (), ()); //在ptr的右子树中
递归删除min 结点
}
else {
if(() == null && () != null){
//待删除结点找到，且其只有右子树的情况
//让ptr双亲的右孩子指向ptr的右孩子结点
().setRightChild( ());
//让ptr右孩子的双亲指向ptr的双亲结点
().setParent(());
}else if(() != null && () ==
null){
//待删除结点找到，且其只有左子树的情况
//让ptr双亲的左孩子指向ptr的左孩子结点
().setRLeftChild(());
//让ptr左孩子的双亲指向ptr的双亲结点
().setParent(());
} else{//待删除结点找到，且为叶结点的情况
BitreeNode p= ();
if(() == ptr) //若待删除结点是双亲的左
孩子
(null); //把双亲的左孩子置空
else //若待删除结点是双亲的右孩子
(null ); //把双亲的右孩子置空
}
}
}
}
七、二叉排序树的性能分析
一棵二叉排序树的平均查找长度为：
其中：
n i 是每层结点个数；
C i 是结点所在层次数；
m 为树深。
当二叉排序树是一棵单分支退化树时，查找成功的平均查找
长度和有序顺序表的平均查找长度相同，即为：
若每个数据元素的查找概率相等，则二叉排序树查找成功的
平均查找长度为：
3
4
5
6
7
8
10
6
4 8
3 5 7 10
(a)
(b)
（a）满二叉排序树时，k =
log 2(7+1)=3 ，所以查找成功的平均
查找长度为：
（b）左分支退化二叉排序树时，k
= n=7 ，所以查找成功的平均查找
长度为：
在最坏情况下，二叉排序树的平均查找长度为O (n )。在一
般情况下，二叉排序树的平均查找长度为O (log 2n )。
B_树
B_树是一种平衡多叉排序树。平衡是指所有叶结点都在同
一层上，从而可避免出现像二叉排序树那样的分支退化现象
。因此B_树的动态查找效率更高。
B_树中所有结点的孩子结点的最大值称为B_树的阶，一棵
m 阶的B_树或者是一棵空树，或者是满足下列要求的m 叉
树：
(1)树中每个结点至多有m 个孩子结点。
(2)除根结点外，其他结点至少有� m/2 � 个孩子结点（符
号“� � ”表示上取整）。
(3)若根结点不是叶结点，则根结点至少有两个孩子结点；
(4)每个结点的结构为：n P 0 K 1 P 1 K 2 P 2 … K n P n
(5)所有叶结点都在同一层上。
1 50
20 41 1 722
1 443 23 30 351 15 1 60 3 77 80 88∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧
root
一棵4阶B_树
1. 查找算法
在B_树上查找数据元素x的方法为：将 与根结点的K i
逐个进行比较：
（1）若= K i则查找成功。
（2）若key< K 1则沿着指针P 0所指的子树继续查找。
（3）若K i<key< K i+1 则沿着指针P i所指的子树继续查找。
（4）若key> K n则沿着指针P n所指的子树继续查找。
2. 插入算法
插入过程分两步完成：
（1）利用查找算法找出该关键字的插入结点（B_树的插
入结点一定是叶结点）。
（2）判断该结点是否还有空位置，即判断该结点是否满
足n<m-1 ，若该结点满足n<m-1 ，说明该结点还有空位
置，直接把关键字插入到该结点的合适位置上；若该
结点有n=m-1 ，说明该结点已没有空位置，要插入就要分
裂该结点。（结点分裂方法见课本P268 ）
100
20 60 120 180
5 10 25 40 80 110 116 132 189 200
a
b
c
100
20 60 120 180
5 10 25 40 80 90 110 116 132 189 200
a
b
c
(a)初始状态
(b)插入90 后的状态
在3阶B_树上进行插入操作如下图示
：
100
20 60 120 180
5 10 25 40 80 90 110 116 132 189 195 200
a
b
c
(c) 插入195 后结点分裂前的状态
100 180
20 60
5 10 25 40 80 90
a
120 195
'b ''b
110 116 132 189 200
(d)插入结点195 后结点分裂的过程
'c ''c
100
20 60 120 180 195
5 10 25 40 80 90 110 116 132
a
b
189 200
'c ''c
3.删除
删除分两步完成：
（1）利用查找算法找出该关键字所在的结点。
（2）在结点上删除关键字分两种情况：
一种是在叶结点上删除关键字，共有以下三种情况：
（a）假如要删除关键字结点的关键字个数n大于m/2+1 ，
说明删去该关键字后该结点仍满足B_树的定义，则可直接删
去该关键字。其过程如下图(b)所示
100
20 60 120 180
5 10 25 40 80 110 116 132 189 200
100
20 60 120 180
5 10 25 40 80 116 132 189 200
(a)初始状态
(b)删去110 后的状态
（b）假如要删除关键字结点的关键字个数n等于m/2+1 ，
说明删去该关键字后该结点将不满足B_树的定义，此时若
该结点的左（或右）兄弟结点中关键字个数n大于m/2+1
，则把该结点的左（或右）兄弟结点中最大（或最小）的
关键字上移到双亲结点中，同时把双亲结点中大于（或小
于）上移关键字的关键字下移到要删除关键字的结点中，
这样删去关键字后该结点以及它的左（或右）兄弟结点都
仍旧满足B_树的定义。其过程如图(c)所示
100
20 40 120 180
5 10 25 60 116 132 189 200
(c)删去40 后的状态
100
20 40 180
5 10 25 60 120 132 189 200
(d)删去116 后的状态
（c）假如要删除关键字结点的关键字个数n等于m/2+1
并且该结点的左和右兄弟结点（如果存在的话）中关键字
个数n均等于m/2+1 ，这时需把要删除关键字的结点与其
左（或右）兄弟结点以及双亲结点中分割二者的关键字合
并成一个结点。其过程如图(d)所示
另一种是在非叶结点上删除关键字。在非叶结点上删除关键
字时，假设要删除关键字K i（1≤i≤n），在删去该关键字后
，以该结点P i所指子树中的最小关键字K min 来代替被删关键
字K i所在的位置（P i所指子树中的最小关键字K min 一定是在
叶结点上），然后再以指针P i所指结点为根结点查找并删除
K min (在非叶结点上删除问题就转化成了叶结点上的删除问题
)。其过程如图(e)所示
100
20 40 189
5 10 25 60 120 132 200
(e)删去189 后的状态
