,数据结构,
第九章
数据结构
tjm
第九章 查找
9.1 静态查找表
9.1.1 顺序表的查找
9.1.2 有序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树
9.2.2 B-树和 B+树
9.3 哈希表
9.3.1 什么是哈希表
9.3.2 哈希函数的构造方法
9.3.3 处理冲突的方法
9.3.4 哈希表的查找及其分析
数据结构
tjm
查找表：由同一类型的数据元素构成的集合。
对查找表的常用操作：
查询某特定元素是否在表中存在
查询某特定元素的各种属性
在查找表中插入一个数据元素
在查找表中删除一个数据元素
查找：也叫检索，是根据给定的某个值，在表中确
定一个关键字等于给定值的数据元素。
关键字：可以标识一个数据元素的某个数据项。
主关键字：可以唯一地识别一个数据元素的关键字。
静态查找表：只进行查询某元素在表中与否或检索
某元素的各种属性操作的表。
动态查找表：查找时同时进行插入表中无的元素或
删除表中有的某元素的表。
数据结构
tjm
静态查找表的 ADT参见 P216
查找过程：从表的一端开始逐个进行记录的关键字
和给定值的比较。
作为静态查找表存储结构的顺序表的类型定义参见
P216
顺序表的查找算法参见 P216
9.1 静态查找表
数据结构
tjm
i
例, 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
监视哨 i i i i比较次数：
查找第 n个元素,1
……….
查找第 i个元素,n-i +1
查找失败, n+1
顺序查找方法的平均查找长度 ASL:
?
?
? n
i
ii cpA S Ln
1
个记录的表，对含有
2
1
2
)1(1
)1(
1
1
11
?
?
?
??????
?
??
??
nnn
n
in
n
cpA S L
n
p
n
i
n
i
ii
i
则
概率相等设表中每个元素的查找
比较次数
=5
数据结构
tjm
9.1.2 有序表的查找
折半查找,每次将待查记录所在区间缩小一半。
适用条件：采用顺序存储结构的有序表。
算法实现：设表长为 n,low,high和 mid分别
指向待查元素所在区间的上界、下界和中点,k为
给定值。
初始时，令 low=1,high=n，
mid=?(low+high)/2?。
让 k与 mid指向的记录比较：
若 k=r[mid].key,查找成功。
若 k<r[mid].key,则 high=mid-1。
若 k>r[mid].key,则 low=mid+1。
重复上述操作，直至 low>high时，查找失败。
算法参见 P220
数据结构
tjm
例：找 21
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
数据结构
tjm
例：找 70
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
数据结构
tjm
判定树
为了分析二分查找的性能，可以用二叉树来描述二分
查找过程：树中每个结点表示表中一个元素，结点中
的值为该元素在表中的位臵。把当前查找区间的中点
作为根结点，左子区间和右子区间分别作为根的左子
树和右子树，左子区间和右子区间再按此方法类推，
由此得到的二叉树称为 二分查找的判定树 。
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21：比较次数 = 3，在树上
找 85：比较次数 = 3，不在树上
数据结构
tjm
索引顺序表查找 ——分块查找
查找过程：将表分成几块，块内无序，块间有
序；先确定待查记录所在块，再在块内查找。
适用条件：分块有序表。
算法实现：
用数组存放待查记录。
建立索引表，每个索引表结点含有最大关键字
域和指向本块第一个结点的指针。
数据结构
tjm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表例：查 38
找到
数据结构
tjm
ASL 最大 最小 两者之间
表结构 有序表、无序表 有序表 分块有序表
存储结构 顺序存储结构
线性链表
顺序存储结构 顺序存储结构
线性链表
查找方法比较
顺序查找 折半查找 分块查找
数据结构
tjm
9.2 动态查找表
特点：表结构本身在查找中动态生成。
一、二叉排序树和平衡二叉树
1、二叉排序树（或二叉查找树）
（ 1）二叉排序树定义
二叉排序树（ Binary Sort Tree）或者是一棵
空树；或者是具有下列性质的二叉树：
1)若左子树不空，则左子树上所有结点的值均
小于根结点的值；若右子树不空，则右子树上所有
结点的值均大于等于根结点的值。
2)左右子树也都是二叉排序树。
数据结构
tjm
（ 2）二叉排序树查找过程：
二叉排序树的查找思想：若二叉排树为空，则查
找失败，否则，先拿根结点值与待查值进行比较，
若相等，则查找成功，若根结点值大于待查值，
则进入左子树重复此步骤，否则，进入右子树重
复此步骤，若在查找过程中遇到二叉排序树的叶
子结点时，还没有找到待找结点，则查找不成功。
5842 9870
90
63
45
55
836710
二叉排序数示例
数据结构
tjm
（ 3）二叉排序树插入操作和构造
例,{10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 1210
183
8 122
10
183
8 122
7
10
183
8 122
7
3
二叉排序树生成：从空树出发，经过一系列的
查找、插入操作之后，可生成一棵二叉排序树。
特点：中序遍历可得一有序序列。
数据结构
tjm
（ 4）二叉排序树上的删除
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点：
只需修改 p双亲 f的 左（或右）孩子 指针为空。
p只有左子树或右子树：
p只有左子树，用 p的左孩子代替 p
数据结构
tjm
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
S
Q
PR
P
p只有右子树，用 p的右孩子代替 p
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
S
P
PR
Q
数据结构
tjm
F
P
C PR
CL Q
QL S
SL
中序遍历：
CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历：
CL C ……Q L Q SL S PR F
p左、右子树均非空：
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p
数据结构
tjm
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
若 C无右子树，用 C取代 p
数据结构
tjm
例,80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
数据结构
tjm
2、平衡二叉树 (AVL树 )
（ 1）定义：平衡二叉树 (balanced binary
tree)或者是一棵空树，或者是具有下列性质的二
叉排序树：它的左子树和右子树都是平衡二叉树，
且左子树和右子树高度之差的绝对值不超过 1。
平衡因子,该结点的左子树的深度减去它的右子树
的深度。
平衡二叉树的平衡因子只取 -1,0,1。
数据结构
tjm
91 0
0
0
065
50
47
41 85
30 60
72
78
42
-3
3
0
-2
0 2
1
b.平衡二叉树示例
41 85
30 60
72
78
42
-1
1
1
0
0 1 0
a.非平衡二叉树示例
数据结构
tjm
非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，插入某个结点后，
可能会变成非平衡二叉树，这时，就可以对该二叉树
进行平衡处理，使其变成一棵平衡二叉树。处理的原
则应该是处理与插入点最近的、而平衡因子又比 1大
或比 -1小的结点。下面将分四种情况讨论平衡处理。
（ 1） LL型的处理 (左左型 )
在 A的左孩子 B上插入一个左孩子结点 C，使 A的平衡因
子由 1变成了 2，成为不平衡的二叉排序树。这时的平衡
处理为：将 A顺时针旋转，成为 B的右子树，而原来 B的
右子树则变成 A的左子树，待插入结点 C作为 B的左子树。
A
B
C A
B
C
平衡处理
数据结构
tjm
（ 2） LR型的处理 (左右型 )
在 A的左孩子 B上插入一个右孩子 C，使的 A的平衡因子
由 1变成了 2，成为不平衡的二叉排序树。这时的平衡
处理为：将 C变到 B与 A 之间，使之成为 LL型，然后按
第 (1)种情形 LL型处理。
A
B
C A
C
B
平衡处理旋转
A
C
B
数据结构
tjm
（ 3） RR型的处理 (右右型 )
在 A的右孩子 B上插入一个右孩子 C，使 A的平衡因
子由 -1变成 -2，成为不平衡的二叉排序树。这时的平
衡处理为：将 A逆时针旋转，成为 B的左子树，而原
来 B的左子树则变成 A的右子树，待插入结点 C成为 B
的右子树。
C
B
A
平衡处理
A
C
B
数据结构
tjm
（ 4） RL型的处理 (右左型 )
在 A的右孩子 B上插入一个左孩子 C，使 A的平衡因子
由 -1变成 -2，成为不平衡的二叉排序树。这时的平
衡处理为：将 C变到 A与 B之间，使之成为 RR型，然后
按第 (3) 种情形 RR型处理。
A
B
C B
C
A
平衡处理旋转
A
C
B
数据结构
tjm
例：给定一个关键字序列 4,5,7,2,1,3,6，试
生成一棵平衡二叉树。
分析：平衡二叉树实际上也是一棵二叉排序树，故
可以按建立二叉排序树的思想建立，在建立的过程
中，若遇到不平衡，则进行相应平衡处理，最后就
可以建成一棵平衡二叉树。
插入 4 插入 5 插入 7
RR 型
4 0
4
5 0
- 1
7
4
5
- 2
- 1
0 0
0
4
5
7 0
数据结构
tjm
LL 型
插入 2
插入 1
4
2
5
7
1
1
0 0
0 0
4
2
5
7
1
0
0
1
2
2
4
2
5
7
0
0 1
1
- 1
5
2
1
4
3
7
2
0
1
0
0
5 2
1
4
3 7
- 1
0
0
0 0 0
LR 型
插入 3
数据结构
tjm
5 2
1
4
3 7
- 2
- 1
0
1 0 0
6 0
RL 型 0 6 2
1
4
3 7
0
0
0 0 0 5 0
插入 6
平衡二叉树的查找及性能分析
平衡二叉树本身就是一棵二叉排序树，故它的查找与二
叉排序树完全相同。但它的查找 性能优于二叉排序树，
不像二叉排序树一样，会出现最坏的时间复杂度 O(n)，
它的时间复杂度与二叉排序树的最好时间复杂度相同，
都为 O(log2n)。
数据结构
tjm
1.B-树
B-树是一种平衡的多路查找树。
定义：一棵 m阶的 B-树，或者为空树，或为满足
下列特性的 m叉树：
⑴树中每个结点至多有 m棵子树；
⑵若根结点不是叶子结点，则至少有两棵子树；
⑶除根结点之外的所有非终端结点至少有 ?m/2?
棵子树；
二,B-树
数据结构
tjm
⑷ 所有的非终端结点中包含以下信息数据,（ n，
A0,K1,A1,K2,…,Kn,An）
⑸所有的叶子结点都出现在同一层次上，并且不带信
息（可以看作是外部结点或查找失败的结点，实际上
这些结点不存在，指向这些结点的指针为空）。
数据结构
tjm
2 3 7 2 20 25 3 79 84 934 35 41 51 53 2 66 68 2 71 76
2 12 30 2 69 78
1 54t
F F F F F F F F F F F F F F F F F F F F F
a
b c
d e g hf i
一棵 5阶的 B-树
例如：
数据结构
tjm
B-树的操作
要查找关键字为 k的记录, 首先从根结点开始,
若相等则找所对应的记录, 否则沿 P所指结点的
子树继续查找, 其中：
A0 k<K1
P = An k>Kn
Ai Ki<k<Ki+1
若直到叶子结点还未找到, 则查找失败 。
1）查找：
数据结构
tjm
设要插入关键字为 k的记录，指向 k所在记录的指
针为 p。
首先找到 k应插入的叶子结点，将 p插入。
然后，判断被插入结点是否满足 m叉 B-树的定义，
即插入后结点的分支数是否大于 m（结点的关键
字数是否大于 m-1)，若不大于，则插入结束；否
则，要把该结点分裂成两个。方法是：
申请一个新结点，将插入后的结点按照关键字的
值大小分成左、中、右三部分，中间只含一项，
左边的留在原结点，右边的移入新结点，中间的
构成新的插入项，插入到它们的双亲结点中，若
双亲结点在插入后也要分裂，则类似处理。
2）插入：
数据结构
tjm
45
24
3 12 37 50
53 90
61 70 95
插入 30
3730
插入 85
8561 85
7053 90
70
数据结构
tjm
9.3 哈希表
9.3.1 什么是哈希表
基本思想：在记录的存储地址和它的关键字之间
建立一个确定的对应关系；这样，不经过比较，
直接就能得到所查元素的查找方法。
在记录的关键字与记录的存储地址之间建立的一
种对应关系叫哈希函数。
哈希表：应用哈希函数，由记录的关键字确定记
录在表中的地址，并将记录放入此地址，这样构
成的表叫哈希表。
哈希查找：又叫散列查找，利用哈希函数进行查
找的过程。
数据结构
tjm
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区名作关键字，取
地区名称第一个拼音字
母的序号作哈希函数：
H(Beijing)=2
H(Shanghai)=19
例：各民族人口统计表
编号 地区名 总人口 汉族 回族 …...
1 北京
2 上海…..,…...
数据结构
tjm
哈希函数只是一种映象，所以哈希函数的设定很灵活，
只要使任何关键字的哈希函数值都落在表长允许的范
围之内即可。
散列表的理想情形：
每一个关键字对应一个唯一的地址。
但是实际有可能出现这样的情形：两个不同的关键字
有可能对应同一个存储地址，这样，将导致后放的关
键字无法存贮，即 key1?key2,但
H(key1)=H(key2)，这种现象叫 冲突 。具有相同
函数值的两个关键字，叫该哈希函数的同义词。冲突
不可避免，只能尽量减少；因此冲突发生后，应该有
处理冲突的方法。
数据结构
tjm
9.3.2 哈希函数的构造方法
数字分析法
构造：对关键字进行分析，取关键字的若干位或其
组合作哈希地址。
适用于关键字位数比哈希地址位数大，且可能出现
的关键字事先知道的情况。
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，
即 H(key)=key 或 H(key)=a·key+b。
特点：
直接定址法所得地址集合与关键字集合大小相等，不
会发生冲突。
实际中能用这种哈希函数的情况很少。
数据结构
tjm
例：有 80个记录，关键字为 8位十进制数，哈希地址为 2
位十进制数。
8 1 3 4 6 5 3 2
8 1 3 7 2 2 4 2
8 1 3 8 7 4 2 2
8 1 3 0 1 3 6 7
8 1 3 2 2 8 1 7
8 1 3 3 8 9 6 7
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
????????
分析,?只取 8
?只取 1
?只取 3,4
?只取 2,7,5
????数字分布近乎随机
故取 ????任意两位或两位与另
两位的叠加作哈希地址。
数据结构
tjm
平方取中法
构造：取关键字平方后中间几位作哈希地址。
适于不知道全部关键字情况。
折叠法
构造：将关键字分割成位数相同的几部分，然后
取这几部分的叠加和（舍去进位）做哈希地址。
种类：
移位叠加：将分割后的几部分低位对齐相加。
间界叠加：从一端沿分割界来回折迭，然后对齐
相加。
适于关键字位数很多，且每一位上数字分布大致
均匀情况。
数据结构
tjm
例：关键字为, 0442205864，哈希地址位数为 4。
5 8 6 4
4 2 2 00 4
1 0 0 8 8
H(key)=0088
5 8 6 4
0 2 2 40 4
6 0 9 2
H(key)=6092
移位叠加：
间界叠加：
数据结构
tjm
除留余数法
构造：取关键字被某个不大于哈希表表长 m的数 p除后
所得余数作哈希地址，即 H(key)=key MOD p,p?m。
特点：
简单、常用，可与上述几种方法结合使用。
p的选取很重要； p选的不好，容易产生同义词。
随机数法
构造：取关键字的随机函数值作哈希地址，即
H(key)=random(key)。
适于关键字长度不等的情况。
数据结构
tjm
9.3.3 处理冲突的方法
开放定址法
方法：当冲突发生时，形成一个探查序列；沿此序列逐个
地址探查，直到找到一个空位置（开放的地址），将发生
冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，
i=1,2,……k(k ?m-1)。
其中,H(key)— 哈希函数
m— 哈希表表长
di— 增量序列
分类：
线性探测再散列,di=1,2,3,……m -1
二次探测再散列,di=12,-12,22,-22,32,…… ± k2(k?m/2)
伪随机探测再散列,di=伪随机数序列
数据结构
tjm
例：表长为 11的哈希表中已填有关键字为 17,60,29
的记录,H(key)=key MOD 11,现有第 4个记录，其关
键字为 38，按三种处理冲突的方法，将它填入表中 。
0 1 2 3 4 5 6 7 8 9 10
60 17 29
(1) H(38)=38 MOD 11=5 冲突
H1=(5+1) MOD 11=6 冲突
H2=(5+2) MOD 11=7 冲突
H3=(5+3) MOD 11=8 不冲突
38
(2) H(38)=38 MOD 11=5 冲突
H1=(5+12) MOD 11=6 冲突
H2=(5-12) MOD 11=4 不冲突
38
(3) H(38)=38 MOD 11=5 冲突
设伪随机数序列为 9,…,则：
H1=(5+9) MOD 11=3 不冲突
38
数据结构
tjm
再哈希法
方法：构造若干个哈希函数，当发生冲突时，计算
下一个哈希地址，即,Hi=Rhi(key) i=1,2,……k 。
其中,Rhi—— 不同的哈希函数
链地址法
方法：将所有关键字为同义词的记录存储在一个单
链表中，并用一维数组存放头指针。
数据结构
tjm
例：已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突,
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
数据结构
tjm
哈希查找过程：
给定 k值
计算 H(k)
此地址为空
关键字 ==k
查找失败
查找成功
按处理冲突
方法计算 Hi
Y
N
Y
N
9.3.4 哈希表的查找及其分析
数据结构
tjm
例：已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，
哈希函数为,H(key)=key MOD 13,哈希表长为 m=16，
设每个记录的查找概率相等。
哈希查找分析
哈希查找过程仍是一个给定值与关键字进行比较的过
程。
评价哈希查找效率仍要用 ASL。与哈希函数处理冲突
的方法。
数据结构
tjm
用线性探测再散列处理冲突
即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
数据结构
tjm
用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
ASL=(1*6+2*4+3+4)/12=1.75
第九章
数据结构
tjm
第九章 查找
9.1 静态查找表
9.1.1 顺序表的查找
9.1.2 有序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树
9.2.2 B-树和 B+树
9.3 哈希表
9.3.1 什么是哈希表
9.3.2 哈希函数的构造方法
9.3.3 处理冲突的方法
9.3.4 哈希表的查找及其分析
数据结构
tjm
查找表：由同一类型的数据元素构成的集合。
对查找表的常用操作：
查询某特定元素是否在表中存在
查询某特定元素的各种属性
在查找表中插入一个数据元素
在查找表中删除一个数据元素
查找：也叫检索，是根据给定的某个值，在表中确
定一个关键字等于给定值的数据元素。
关键字：可以标识一个数据元素的某个数据项。
主关键字：可以唯一地识别一个数据元素的关键字。
静态查找表：只进行查询某元素在表中与否或检索
某元素的各种属性操作的表。
动态查找表：查找时同时进行插入表中无的元素或
删除表中有的某元素的表。
数据结构
tjm
静态查找表的 ADT参见 P216
查找过程：从表的一端开始逐个进行记录的关键字
和给定值的比较。
作为静态查找表存储结构的顺序表的类型定义参见
P216
顺序表的查找算法参见 P216
9.1 静态查找表
数据结构
tjm
i
例, 0 1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 64
64
监视哨 i i i i比较次数：
查找第 n个元素,1
……….
查找第 i个元素,n-i +1
查找失败, n+1
顺序查找方法的平均查找长度 ASL:
?
?
? n
i
ii cpA S Ln
1
个记录的表，对含有
2
1
2
)1(1
)1(
1
1
11
?
?
?
??????
?
??
??
nnn
n
in
n
cpA S L
n
p
n
i
n
i
ii
i
则
概率相等设表中每个元素的查找
比较次数
=5
数据结构
tjm
9.1.2 有序表的查找
折半查找,每次将待查记录所在区间缩小一半。
适用条件：采用顺序存储结构的有序表。
算法实现：设表长为 n,low,high和 mid分别
指向待查元素所在区间的上界、下界和中点,k为
给定值。
初始时，令 low=1,high=n，
mid=?(low+high)/2?。
让 k与 mid指向的记录比较：
若 k=r[mid].key,查找成功。
若 k<r[mid].key,则 high=mid-1。
若 k>r[mid].key,则 low=mid+1。
重复上述操作，直至 low>high时，查找失败。
算法参见 P220
数据结构
tjm
例：找 21
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
数据结构
tjm
例：找 70
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
lowhigh
数据结构
tjm
判定树
为了分析二分查找的性能，可以用二叉树来描述二分
查找过程：树中每个结点表示表中一个元素，结点中
的值为该元素在表中的位臵。把当前查找区间的中点
作为根结点，左子区间和右子区间分别作为根的左子
树和右子树，左子区间和右子区间再按此方法类推，
由此得到的二叉树称为 二分查找的判定树 。
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92
找 21：比较次数 = 3，在树上
找 85：比较次数 = 3，不在树上
数据结构
tjm
索引顺序表查找 ——分块查找
查找过程：将表分成几块，块内无序，块间有
序；先确定待查记录所在块，再在块内查找。
适用条件：分块有序表。
算法实现：
用数组存放待查记录。
建立索引表，每个索引表结点含有最大关键字
域和指向本块第一个结点的指针。
数据结构
tjm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
22 48 86
1 7 13
索引表例：查 38
找到
数据结构
tjm
ASL 最大 最小 两者之间
表结构 有序表、无序表 有序表 分块有序表
存储结构 顺序存储结构
线性链表
顺序存储结构 顺序存储结构
线性链表
查找方法比较
顺序查找 折半查找 分块查找
数据结构
tjm
9.2 动态查找表
特点：表结构本身在查找中动态生成。
一、二叉排序树和平衡二叉树
1、二叉排序树（或二叉查找树）
（ 1）二叉排序树定义
二叉排序树（ Binary Sort Tree）或者是一棵
空树；或者是具有下列性质的二叉树：
1)若左子树不空，则左子树上所有结点的值均
小于根结点的值；若右子树不空，则右子树上所有
结点的值均大于等于根结点的值。
2)左右子树也都是二叉排序树。
数据结构
tjm
（ 2）二叉排序树查找过程：
二叉排序树的查找思想：若二叉排树为空，则查
找失败，否则，先拿根结点值与待查值进行比较，
若相等，则查找成功，若根结点值大于待查值，
则进入左子树重复此步骤，否则，进入右子树重
复此步骤，若在查找过程中遇到二叉排序树的叶
子结点时，还没有找到待找结点，则查找不成功。
5842 9870
90
63
45
55
836710
二叉排序数示例
数据结构
tjm
（ 3）二叉排序树插入操作和构造
例,{10,18,3,8,12,2,7,3}
10 10
18
10
183
10
183
8
10
183
8 1210
183
8 122
10
183
8 122
7
10
183
8 122
7
3
二叉排序树生成：从空树出发，经过一系列的
查找、插入操作之后，可生成一棵二叉排序树。
特点：中序遍历可得一有序序列。
数据结构
tjm
（ 4）二叉排序树上的删除
S
P
PL
Q
中序遍历,PL P S Q
S
PL Q
中序遍历,PL S Q
S
Q
PL
P
中序遍历,Q S PL P
S
Q PL
中序遍历,Q S PL
要删除二叉排序树中的 p结点，分三种情况：
p为叶子结点：
只需修改 p双亲 f的 左（或右）孩子 指针为空。
p只有左子树或右子树：
p只有左子树，用 p的左孩子代替 p
数据结构
tjm
中序遍历,Q S P PR
S
Q PR
中序遍历,Q S PR
S
Q
PR
P
p只有右子树，用 p的右孩子代替 p
中序遍历,P PR S Q
S
PR Q
中序遍历,PR S Q
S
P
PR
Q
数据结构
tjm
F
P
C PR
CL Q
QL S
SL
中序遍历：
CL C ……Q L Q SL S P PR F
F
S
C PR
CL Q
QL SL
中序遍历：
CL C ……Q L Q SL S PR F
p左、右子树均非空：
沿 p左子树的根 C的右子树分支找到 S,S的右子树为空，
将 S的左子树成为 S的双亲 Q的右子树，用 S取代 p
数据结构
tjm
F
P
C PR
CL
中序遍历,CL C P PR F
F
C
PRCL
中序遍历,CL C PR F
若 C无右子树，用 C取代 p
数据结构
tjm
例,80
50 120
60 110 150
55 70
53
删除 50
80
60 120
110 15055 70
53
删除 60
80
55 120
110 15053 70
10
4 25
8 13
5
4
删除 10
8
4 25
5 13
4
删除 5
8
4 25
4 13
数据结构
tjm
2、平衡二叉树 (AVL树 )
（ 1）定义：平衡二叉树 (balanced binary
tree)或者是一棵空树，或者是具有下列性质的二
叉排序树：它的左子树和右子树都是平衡二叉树，
且左子树和右子树高度之差的绝对值不超过 1。
平衡因子,该结点的左子树的深度减去它的右子树
的深度。
平衡二叉树的平衡因子只取 -1,0,1。
数据结构
tjm
91 0
0
0
065
50
47
41 85
30 60
72
78
42
-3
3
0
-2
0 2
1
b.平衡二叉树示例
41 85
30 60
72
78
42
-1
1
1
0
0 1 0
a.非平衡二叉树示例
数据结构
tjm
非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，插入某个结点后，
可能会变成非平衡二叉树，这时，就可以对该二叉树
进行平衡处理，使其变成一棵平衡二叉树。处理的原
则应该是处理与插入点最近的、而平衡因子又比 1大
或比 -1小的结点。下面将分四种情况讨论平衡处理。
（ 1） LL型的处理 (左左型 )
在 A的左孩子 B上插入一个左孩子结点 C，使 A的平衡因
子由 1变成了 2，成为不平衡的二叉排序树。这时的平衡
处理为：将 A顺时针旋转，成为 B的右子树，而原来 B的
右子树则变成 A的左子树，待插入结点 C作为 B的左子树。
A
B
C A
B
C
平衡处理
数据结构
tjm
（ 2） LR型的处理 (左右型 )
在 A的左孩子 B上插入一个右孩子 C，使的 A的平衡因子
由 1变成了 2，成为不平衡的二叉排序树。这时的平衡
处理为：将 C变到 B与 A 之间，使之成为 LL型，然后按
第 (1)种情形 LL型处理。
A
B
C A
C
B
平衡处理旋转
A
C
B
数据结构
tjm
（ 3） RR型的处理 (右右型 )
在 A的右孩子 B上插入一个右孩子 C，使 A的平衡因
子由 -1变成 -2，成为不平衡的二叉排序树。这时的平
衡处理为：将 A逆时针旋转，成为 B的左子树，而原
来 B的左子树则变成 A的右子树，待插入结点 C成为 B
的右子树。
C
B
A
平衡处理
A
C
B
数据结构
tjm
（ 4） RL型的处理 (右左型 )
在 A的右孩子 B上插入一个左孩子 C，使 A的平衡因子
由 -1变成 -2，成为不平衡的二叉排序树。这时的平
衡处理为：将 C变到 A与 B之间，使之成为 RR型，然后
按第 (3) 种情形 RR型处理。
A
B
C B
C
A
平衡处理旋转
A
C
B
数据结构
tjm
例：给定一个关键字序列 4,5,7,2,1,3,6，试
生成一棵平衡二叉树。
分析：平衡二叉树实际上也是一棵二叉排序树，故
可以按建立二叉排序树的思想建立，在建立的过程
中，若遇到不平衡，则进行相应平衡处理，最后就
可以建成一棵平衡二叉树。
插入 4 插入 5 插入 7
RR 型
4 0
4
5 0
- 1
7
4
5
- 2
- 1
0 0
0
4
5
7 0
数据结构
tjm
LL 型
插入 2
插入 1
4
2
5
7
1
1
0 0
0 0
4
2
5
7
1
0
0
1
2
2
4
2
5
7
0
0 1
1
- 1
5
2
1
4
3
7
2
0
1
0
0
5 2
1
4
3 7
- 1
0
0
0 0 0
LR 型
插入 3
数据结构
tjm
5 2
1
4
3 7
- 2
- 1
0
1 0 0
6 0
RL 型 0 6 2
1
4
3 7
0
0
0 0 0 5 0
插入 6
平衡二叉树的查找及性能分析
平衡二叉树本身就是一棵二叉排序树，故它的查找与二
叉排序树完全相同。但它的查找 性能优于二叉排序树，
不像二叉排序树一样，会出现最坏的时间复杂度 O(n)，
它的时间复杂度与二叉排序树的最好时间复杂度相同，
都为 O(log2n)。
数据结构
tjm
1.B-树
B-树是一种平衡的多路查找树。
定义：一棵 m阶的 B-树，或者为空树，或为满足
下列特性的 m叉树：
⑴树中每个结点至多有 m棵子树；
⑵若根结点不是叶子结点，则至少有两棵子树；
⑶除根结点之外的所有非终端结点至少有 ?m/2?
棵子树；
二,B-树
数据结构
tjm
⑷ 所有的非终端结点中包含以下信息数据,（ n，
A0,K1,A1,K2,…,Kn,An）
⑸所有的叶子结点都出现在同一层次上，并且不带信
息（可以看作是外部结点或查找失败的结点，实际上
这些结点不存在，指向这些结点的指针为空）。
数据结构
tjm
2 3 7 2 20 25 3 79 84 934 35 41 51 53 2 66 68 2 71 76
2 12 30 2 69 78
1 54t
F F F F F F F F F F F F F F F F F F F F F
a
b c
d e g hf i
一棵 5阶的 B-树
例如：
数据结构
tjm
B-树的操作
要查找关键字为 k的记录, 首先从根结点开始,
若相等则找所对应的记录, 否则沿 P所指结点的
子树继续查找, 其中：
A0 k<K1
P = An k>Kn
Ai Ki<k<Ki+1
若直到叶子结点还未找到, 则查找失败 。
1）查找：
数据结构
tjm
设要插入关键字为 k的记录，指向 k所在记录的指
针为 p。
首先找到 k应插入的叶子结点，将 p插入。
然后，判断被插入结点是否满足 m叉 B-树的定义，
即插入后结点的分支数是否大于 m（结点的关键
字数是否大于 m-1)，若不大于，则插入结束；否
则，要把该结点分裂成两个。方法是：
申请一个新结点，将插入后的结点按照关键字的
值大小分成左、中、右三部分，中间只含一项，
左边的留在原结点，右边的移入新结点，中间的
构成新的插入项，插入到它们的双亲结点中，若
双亲结点在插入后也要分裂，则类似处理。
2）插入：
数据结构
tjm
45
24
3 12 37 50
53 90
61 70 95
插入 30
3730
插入 85
8561 85
7053 90
70
数据结构
tjm
9.3 哈希表
9.3.1 什么是哈希表
基本思想：在记录的存储地址和它的关键字之间
建立一个确定的对应关系；这样，不经过比较，
直接就能得到所查元素的查找方法。
在记录的关键字与记录的存储地址之间建立的一
种对应关系叫哈希函数。
哈希表：应用哈希函数，由记录的关键字确定记
录在表中的地址，并将记录放入此地址，这样构
成的表叫哈希表。
哈希查找：又叫散列查找，利用哈希函数进行查
找的过程。
数据结构
tjm
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区名作关键字，取
地区名称第一个拼音字
母的序号作哈希函数：
H(Beijing)=2
H(Shanghai)=19
例：各民族人口统计表
编号 地区名 总人口 汉族 回族 …...
1 北京
2 上海…..,…...
数据结构
tjm
哈希函数只是一种映象，所以哈希函数的设定很灵活，
只要使任何关键字的哈希函数值都落在表长允许的范
围之内即可。
散列表的理想情形：
每一个关键字对应一个唯一的地址。
但是实际有可能出现这样的情形：两个不同的关键字
有可能对应同一个存储地址，这样，将导致后放的关
键字无法存贮，即 key1?key2,但
H(key1)=H(key2)，这种现象叫 冲突 。具有相同
函数值的两个关键字，叫该哈希函数的同义词。冲突
不可避免，只能尽量减少；因此冲突发生后，应该有
处理冲突的方法。
数据结构
tjm
9.3.2 哈希函数的构造方法
数字分析法
构造：对关键字进行分析，取关键字的若干位或其
组合作哈希地址。
适用于关键字位数比哈希地址位数大，且可能出现
的关键字事先知道的情况。
直接定址法
构造：取关键字或关键字的某个线性函数作哈希地址，
即 H(key)=key 或 H(key)=a·key+b。
特点：
直接定址法所得地址集合与关键字集合大小相等，不
会发生冲突。
实际中能用这种哈希函数的情况很少。
数据结构
tjm
例：有 80个记录，关键字为 8位十进制数，哈希地址为 2
位十进制数。
8 1 3 4 6 5 3 2
8 1 3 7 2 2 4 2
8 1 3 8 7 4 2 2
8 1 3 0 1 3 6 7
8 1 3 2 2 8 1 7
8 1 3 3 8 9 6 7
8 1 3 6 8 5 3 7
8 1 4 1 9 3 5 5
…..
…..
????????
分析,?只取 8
?只取 1
?只取 3,4
?只取 2,7,5
????数字分布近乎随机
故取 ????任意两位或两位与另
两位的叠加作哈希地址。
数据结构
tjm
平方取中法
构造：取关键字平方后中间几位作哈希地址。
适于不知道全部关键字情况。
折叠法
构造：将关键字分割成位数相同的几部分，然后
取这几部分的叠加和（舍去进位）做哈希地址。
种类：
移位叠加：将分割后的几部分低位对齐相加。
间界叠加：从一端沿分割界来回折迭，然后对齐
相加。
适于关键字位数很多，且每一位上数字分布大致
均匀情况。
数据结构
tjm
例：关键字为, 0442205864，哈希地址位数为 4。
5 8 6 4
4 2 2 00 4
1 0 0 8 8
H(key)=0088
5 8 6 4
0 2 2 40 4
6 0 9 2
H(key)=6092
移位叠加：
间界叠加：
数据结构
tjm
除留余数法
构造：取关键字被某个不大于哈希表表长 m的数 p除后
所得余数作哈希地址，即 H(key)=key MOD p,p?m。
特点：
简单、常用，可与上述几种方法结合使用。
p的选取很重要； p选的不好，容易产生同义词。
随机数法
构造：取关键字的随机函数值作哈希地址，即
H(key)=random(key)。
适于关键字长度不等的情况。
数据结构
tjm
9.3.3 处理冲突的方法
开放定址法
方法：当冲突发生时，形成一个探查序列；沿此序列逐个
地址探查，直到找到一个空位置（开放的地址），将发生
冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，
i=1,2,……k(k ?m-1)。
其中,H(key)— 哈希函数
m— 哈希表表长
di— 增量序列
分类：
线性探测再散列,di=1,2,3,……m -1
二次探测再散列,di=12,-12,22,-22,32,…… ± k2(k?m/2)
伪随机探测再散列,di=伪随机数序列
数据结构
tjm
例：表长为 11的哈希表中已填有关键字为 17,60,29
的记录,H(key)=key MOD 11,现有第 4个记录，其关
键字为 38，按三种处理冲突的方法，将它填入表中 。
0 1 2 3 4 5 6 7 8 9 10
60 17 29
(1) H(38)=38 MOD 11=5 冲突
H1=(5+1) MOD 11=6 冲突
H2=(5+2) MOD 11=7 冲突
H3=(5+3) MOD 11=8 不冲突
38
(2) H(38)=38 MOD 11=5 冲突
H1=(5+12) MOD 11=6 冲突
H2=(5-12) MOD 11=4 不冲突
38
(3) H(38)=38 MOD 11=5 冲突
设伪随机数序列为 9,…,则：
H1=(5+9) MOD 11=3 不冲突
38
数据结构
tjm
再哈希法
方法：构造若干个哈希函数，当发生冲突时，计算
下一个哈希地址，即,Hi=Rhi(key) i=1,2,……k 。
其中,Rhi—— 不同的哈希函数
链地址法
方法：将所有关键字为同义词的记录存储在一个单
链表中，并用一维数组存放头指针。
数据结构
tjm
例：已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突,
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
数据结构
tjm
哈希查找过程：
给定 k值
计算 H(k)
此地址为空
关键字 ==k
查找失败
查找成功
按处理冲突
方法计算 Hi
Y
N
Y
N
9.3.4 哈希表的查找及其分析
数据结构
tjm
例：已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)，
哈希函数为,H(key)=key MOD 13,哈希表长为 m=16，
设每个记录的查找概率相等。
哈希查找分析
哈希查找过程仍是一个给定值与关键字进行比较的过
程。
评价哈希查找效率仍要用 ASL。与哈希函数处理冲突
的方法。
数据结构
tjm
用线性探测再散列处理冲突
即 Hi=(H(key)+di) MOD m
H(55)=3 冲突,H1=(3+1)MOD16=4
冲突,H2=(3+2)MOD16=5
H(79)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
冲突,H4=(1+4)MOD16=5
冲突,H5=(1+5)MOD16=6
冲突,H6=(1+6)MOD16=7
冲突,H7=(1+7)MOD16=8
冲突,H8=(1+8)MOD16=9
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ASL=(1*6+2+3*3+4+9)/12=2.5
14 1 68 27 55 19 20 84 79 23 11 10
H(19)=6
H(14)=1
H(23)=10
H(1)=1 冲突,H1=(1+1) MOD16=2
H(68)=3
H(20)=7
H(84)=6 冲突,H1=(6+1)MOD16=7
冲突,H2=(6+2)MOD16=8
H(27)=1 冲突,H1=(1+1)MOD16=2
冲突,H2=(1+2)MOD16=3
冲突,H3=(1+3)MOD16=4
H(11)=11
H(10)=10 冲突,H1=(10+1)MOD16=11
冲突,H2=(10+2)MOD16=12
数据结构
tjm
用链地址法处理冲突
0
1
2
3
4
5
6
7
8
9
10
11
12
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
ASL=(1*6+2*4+3+4)/12=1.75
