第九章 查找
?9.1 静态查找表
? 9.1.1 顺序表的查找
? 9.1.2 有序表的查找
?9.2 动态查找表
? 9.2.1 二叉排序树和二叉平衡树
?9.3 哈希 (Hashing )表 (散列表 )
?
第九章 查找
?查找表 (search table):
? 同一类型数据元素构成的集合。
?查找操作,
? (1)查询某个, 特定的, 数据元素是否在查找表
中 ;
? (2)检索某个, 特定的, 数据元素的各种属性 ;
? (3)在查找表中插入一个数据元素 ;
? (4)从查找表中删除某个数据元素,
?静态查找表,对查找表只作 (1),(2)操作；
?动态查找表：可以对查找表作 (1)-(4)操作。
有关查找的“词”的含义
?关键字 (KEY):
? 数据元素 (或记录 )的某个数据项的值,用
以标识一个数据元素 (或记录 ).
? 可以唯一标识一个记录的关键字称为 主
关键字 (Primary Key); 否则称为 次关键字
(Secondary Key).
? 查找 (Searching)
? 根据给定的值,在查找表中确定一个关键
字等于给定值的记录或数据元素,
9.1 静态查找表
?可以用顺序表，也可以用线性链表来表示静
态查找表。
? 顺序表的查找
? typedef struct{ //静态查找表的顺序存储结构
? ElemType *elem;
? int length;
? }SSTable;
elem
length
key 0
1
2
...
length-1
length
顺序查找（ Sequential Search）
? int Search_Seq(SSTable ST,KeyType key){
? ST.elem[0].key = key; //, 哨兵”
? for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
? return i;
? }
? 性能分析,设 Pi为查找表中第 i个记录的概率 (取 Pi=1/n)；
? Ci为找到第 i个记录所需的查找次数。则
? n
? ASL = ? Pi Ci = nP1+(n-1)P2+...+2Pn-1+Pn
? i=1
? = [n+(n-1) +...+2+1]*1/n = (n+1)/2
? 若查找成功与不成功的概率相同，即 Pi=1/2n，
? ASL = nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2 = (n+1)*3/4
有序表的查找,
折半查找（ Binary Search）
? 确定待查记录的区间，逐步缩小范围直到找到或找不到该记
录为止。
? 例子,数据元素有序表如下,查找关键字 key=21的数据元素。
? 21(05,13,19,21,37,56,64,75,80,88,92）
? 下标, 0 1 2 3 4 5 6 7 8 9 10 11
? 05,13,19,21,37,56,64,75,80,88,92
? ?low ?mid ?high
? mid = [(low+high)/2]; key=ST.elem[mid].key查找成功 ;
? 当 key<ST.elem[mid].key时,下一个 待查区间为 [low,mid-1]
? 05,13,19,21,37,56,64,75,80,88,92
? ?low ?mid ?high
? 当 key>ST.elem[mid].key时下一个 待查区间为 [mid+1,high]
折半查找的性能分析
查找上例中所有元素的判定二叉树为
6
3
1 4 7
9
5
10
2 118
判定树
判定树上每个结点需要的
查找次数刚好为该结点所
在的层数,
查找成功时查找次数不会
超过判定树的深度
n个结点的判定树的深度
为 [log2n]+1.
折半查找的算法复杂度为
[log2n]+1
9.2 动态查找表
9.2.1 二叉排序树
?什么是二叉排序树 (Binary Sort Tree)?
?二叉排序树是空树,或者是具有以下性质的二叉树,
?(1)若左子树非空,则左子树上所有结点的值均小于
? 它的根结点的值 ;
?(2)若右子树非空,则右子树上所有结点的值均大于
? 它的根结点的值 ;
?(3)它的左、右子树也分别为 二叉排序树。
二叉排序树举例
45
12
3 37
53
78
100
24
90
61
二叉排序树
查找过程：
从根结点出发，结点
的值与 key进行比较：
（ 1）相等时查找成功；
（ 2） key较大时，沿右
子树继续查找（无右子
树表明查找失败）；
（ 3） key较小时，沿左
子树继续查找（无左子
树表明查找失败）。
其中序遍历序列,
3,12,24,37,45,53,61,78,90,100
二叉排序树的生成 (插入结点 )
?二叉排序树的生成 (连续进行插入操作 )
?例如,对 {45,24,53,45,12,24,90}
?关键字序列的 二叉排序树 生成 过程如下,
45
24
12
53
45
24
12
53
90
45
24 53
45
24
45
二叉排序树结点的删除
(保持二叉排序树的特性及次序 )
?设被删除的结点为 *p,其父结点为 *f,并不失一般性
假设 *p为 *f的左孩子,则
?(1)若 *p为叶结点,即 PL和 PR均为空,直接删除不会影
响树结构 ;
?(2)若 *p只有 PL或只有 PR.只要令 PL或 PR直接成为其
双亲结点 *f的左孩子即可,这样也不会影响树结构 ;
?(3)若 *p有 PL也有 PR.为保持中序遍历二叉树的序列
不变,可以有两种处理方法,其一是令 PL为 *f的左子
树,PR为 *s的右子树 (*s为中序遍历 PL的最后一个结
点 );其二是令 *p的直接前驱 (或直接后继 )*s替代 *p,
然后删除直接前驱 (或直接后继 )*s.若 *s有左孩子
则左孩子取代 *s的位置,这样虽然影响了树结构,但
不会影响中序遍历二叉树时的结点次序,
在二叉排序树中删除结点 *p
F
P
C PR
SL
CL Q
SQ
L
F
S
C P
R
SL
CL
Q
QL
F
C
PL
CL S
QL
二叉排序树的查找分析
?n个结点的 二叉排序树的平均查找长度和树的形态
有关 {45,24,53,45,12,37,93}
?最坏情况是二叉排序树蜕变单支树,{12,24,37,45,
53,93}
45
24
12
53
9337
45
24
12
53
93
37
ASL = O(log2n) ASL = O(n/2)
二叉排序树举例 (题目 )
?已知如下所示长度为 12的表
? (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
?(1)试按表中元素的顺序依次插入一棵初始为
空的二叉排序树,画出插入插入完成之后的二
叉排序树,并求其在等概率的情况下查找成功
的平均查找长度 ASL;
?(2)若对表中元素先进行排序构成有序表,求
其在等概率的情况下对此有序表进行折半查
找时查找成功的平均查找长度 ;
二叉排序树举例 (解答 1)
? (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
Jan
Feb
Apr
Mar
June May
Dec Oct
Sep
二叉排序树
JulyAug
Nov
其在等概率 (1/12)的情况下
查找成功的平均查找长度,
ASL=(1+2*2+3*3+4*3+5*2+6*1)/12
= 42/12 = 3.5
July
Dec
Apr
May
June OctFeb
Nov Dec
判定树
JanAug Aug
二叉排序树举例 (解答 2)
? (Apr,Aug,Dec,Fab,Jan,July,June,Mar,May,Nov,Oct,Sep)
其在等概率 (1/12)的情况下
查找成功的平均查找长度,
ASL=(1+2*2+3*4+4*5)/12
= 37/12 = 3.1
9.2.2 平衡二叉树
?什么是平衡二叉树 (Balanced Binary Tree)?
?平衡二叉树是空树,或者是具有以下性质的二叉树,
? 它的左子树和右子树也都是 平衡二叉树并且
? 左子树和右子树的深度之差的绝对值不超过 1
?结点的平衡因子 BF(Balance Factor)是
? 左子树的深度减去右子树的深度,它只可能是 -1,0,1
?平衡二叉树 (也称 AVL树 )的深度为 O(log N)(其中 N
为结点个数 )
?它的平均查找长度也是 O(log N)
平衡二叉树及平衡因子举例
-1
1
0 0
-1
1
0
平衡的二叉树
1
1
0
0
不平衡的二叉树
-1
0
0 0
-2
1
0
2
-1
0 1
0
0
不平衡二叉树及平衡因子举例
二叉排序树转成平衡树示例
设关键字序列为 (13,24,37,90,53)
0
13
-1
13
0
24
0
37
0
13
-2
13
-1
24
0
24
0
37
0
53
0
13 0
13
0
37
0
90
0
53
-1
24
1
90
-2
37
-2
24
(a) (b) (c)
(d) (e)
(f) (g) (h)
24
13 37
53
90
二叉排序树转成平衡树
失去平衡后进行调整的四种情况
?(1)单向右旋平衡处理
? 当在左子树上插入左结点,使平衡因子由 1增至 2时
?(2)单向左旋平衡处理 (上例从图 (d)到图 (e))
? 当在右子树上插入右结点,使平衡因子由 -1增至 -2时
?(3)双向旋转 (先左后右 )平衡处理
? 当在左子树上插入右结点,使平衡因子由 1增至 2时
?(4)双向旋转 (先右后左 )平衡处理
? 当在右子树上插入左结点,使平衡因子由 -1增至 -2时
? (例如上例从图 (f)右旋到图 (g)再左旋到图 (h))
实验与习题
?理论习题 9.3,9.10,9.11
?实验算法题, 9.25
?9.1 静态查找表
? 9.1.1 顺序表的查找
? 9.1.2 有序表的查找
?9.2 动态查找表
? 9.2.1 二叉排序树和二叉平衡树
?9.3 哈希 (Hashing )表 (散列表 )
?
第九章 查找
?查找表 (search table):
? 同一类型数据元素构成的集合。
?查找操作,
? (1)查询某个, 特定的, 数据元素是否在查找表
中 ;
? (2)检索某个, 特定的, 数据元素的各种属性 ;
? (3)在查找表中插入一个数据元素 ;
? (4)从查找表中删除某个数据元素,
?静态查找表,对查找表只作 (1),(2)操作；
?动态查找表：可以对查找表作 (1)-(4)操作。
有关查找的“词”的含义
?关键字 (KEY):
? 数据元素 (或记录 )的某个数据项的值,用
以标识一个数据元素 (或记录 ).
? 可以唯一标识一个记录的关键字称为 主
关键字 (Primary Key); 否则称为 次关键字
(Secondary Key).
? 查找 (Searching)
? 根据给定的值,在查找表中确定一个关键
字等于给定值的记录或数据元素,
9.1 静态查找表
?可以用顺序表，也可以用线性链表来表示静
态查找表。
? 顺序表的查找
? typedef struct{ //静态查找表的顺序存储结构
? ElemType *elem;
? int length;
? }SSTable;
elem
length
key 0
1
2
...
length-1
length
顺序查找（ Sequential Search）
? int Search_Seq(SSTable ST,KeyType key){
? ST.elem[0].key = key; //, 哨兵”
? for(i=ST.length; !EQ(ST.elem[i].key,key); --i);
? return i;
? }
? 性能分析,设 Pi为查找表中第 i个记录的概率 (取 Pi=1/n)；
? Ci为找到第 i个记录所需的查找次数。则
? n
? ASL = ? Pi Ci = nP1+(n-1)P2+...+2Pn-1+Pn
? i=1
? = [n+(n-1) +...+2+1]*1/n = (n+1)/2
? 若查找成功与不成功的概率相同，即 Pi=1/2n，
? ASL = nP1+(n-1)P2+...+2Pn-1+Pn+(n+1)/2 = (n+1)*3/4
有序表的查找,
折半查找（ Binary Search）
? 确定待查记录的区间，逐步缩小范围直到找到或找不到该记
录为止。
? 例子,数据元素有序表如下,查找关键字 key=21的数据元素。
? 21(05,13,19,21,37,56,64,75,80,88,92）
? 下标, 0 1 2 3 4 5 6 7 8 9 10 11
? 05,13,19,21,37,56,64,75,80,88,92
? ?low ?mid ?high
? mid = [(low+high)/2]; key=ST.elem[mid].key查找成功 ;
? 当 key<ST.elem[mid].key时,下一个 待查区间为 [low,mid-1]
? 05,13,19,21,37,56,64,75,80,88,92
? ?low ?mid ?high
? 当 key>ST.elem[mid].key时下一个 待查区间为 [mid+1,high]
折半查找的性能分析
查找上例中所有元素的判定二叉树为
6
3
1 4 7
9
5
10
2 118
判定树
判定树上每个结点需要的
查找次数刚好为该结点所
在的层数,
查找成功时查找次数不会
超过判定树的深度
n个结点的判定树的深度
为 [log2n]+1.
折半查找的算法复杂度为
[log2n]+1
9.2 动态查找表
9.2.1 二叉排序树
?什么是二叉排序树 (Binary Sort Tree)?
?二叉排序树是空树,或者是具有以下性质的二叉树,
?(1)若左子树非空,则左子树上所有结点的值均小于
? 它的根结点的值 ;
?(2)若右子树非空,则右子树上所有结点的值均大于
? 它的根结点的值 ;
?(3)它的左、右子树也分别为 二叉排序树。
二叉排序树举例
45
12
3 37
53
78
100
24
90
61
二叉排序树
查找过程：
从根结点出发，结点
的值与 key进行比较：
（ 1）相等时查找成功；
（ 2） key较大时，沿右
子树继续查找（无右子
树表明查找失败）；
（ 3） key较小时，沿左
子树继续查找（无左子
树表明查找失败）。
其中序遍历序列,
3,12,24,37,45,53,61,78,90,100
二叉排序树的生成 (插入结点 )
?二叉排序树的生成 (连续进行插入操作 )
?例如,对 {45,24,53,45,12,24,90}
?关键字序列的 二叉排序树 生成 过程如下,
45
24
12
53
45
24
12
53
90
45
24 53
45
24
45
二叉排序树结点的删除
(保持二叉排序树的特性及次序 )
?设被删除的结点为 *p,其父结点为 *f,并不失一般性
假设 *p为 *f的左孩子,则
?(1)若 *p为叶结点,即 PL和 PR均为空,直接删除不会影
响树结构 ;
?(2)若 *p只有 PL或只有 PR.只要令 PL或 PR直接成为其
双亲结点 *f的左孩子即可,这样也不会影响树结构 ;
?(3)若 *p有 PL也有 PR.为保持中序遍历二叉树的序列
不变,可以有两种处理方法,其一是令 PL为 *f的左子
树,PR为 *s的右子树 (*s为中序遍历 PL的最后一个结
点 );其二是令 *p的直接前驱 (或直接后继 )*s替代 *p,
然后删除直接前驱 (或直接后继 )*s.若 *s有左孩子
则左孩子取代 *s的位置,这样虽然影响了树结构,但
不会影响中序遍历二叉树时的结点次序,
在二叉排序树中删除结点 *p
F
P
C PR
SL
CL Q
SQ
L
F
S
C P
R
SL
CL
Q
QL
F
C
PL
CL S
QL
二叉排序树的查找分析
?n个结点的 二叉排序树的平均查找长度和树的形态
有关 {45,24,53,45,12,37,93}
?最坏情况是二叉排序树蜕变单支树,{12,24,37,45,
53,93}
45
24
12
53
9337
45
24
12
53
93
37
ASL = O(log2n) ASL = O(n/2)
二叉排序树举例 (题目 )
?已知如下所示长度为 12的表
? (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
?(1)试按表中元素的顺序依次插入一棵初始为
空的二叉排序树,画出插入插入完成之后的二
叉排序树,并求其在等概率的情况下查找成功
的平均查找长度 ASL;
?(2)若对表中元素先进行排序构成有序表,求
其在等概率的情况下对此有序表进行折半查
找时查找成功的平均查找长度 ;
二叉排序树举例 (解答 1)
? (Jan,Fab,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)
Jan
Feb
Apr
Mar
June May
Dec Oct
Sep
二叉排序树
JulyAug
Nov
其在等概率 (1/12)的情况下
查找成功的平均查找长度,
ASL=(1+2*2+3*3+4*3+5*2+6*1)/12
= 42/12 = 3.5
July
Dec
Apr
May
June OctFeb
Nov Dec
判定树
JanAug Aug
二叉排序树举例 (解答 2)
? (Apr,Aug,Dec,Fab,Jan,July,June,Mar,May,Nov,Oct,Sep)
其在等概率 (1/12)的情况下
查找成功的平均查找长度,
ASL=(1+2*2+3*4+4*5)/12
= 37/12 = 3.1
9.2.2 平衡二叉树
?什么是平衡二叉树 (Balanced Binary Tree)?
?平衡二叉树是空树,或者是具有以下性质的二叉树,
? 它的左子树和右子树也都是 平衡二叉树并且
? 左子树和右子树的深度之差的绝对值不超过 1
?结点的平衡因子 BF(Balance Factor)是
? 左子树的深度减去右子树的深度,它只可能是 -1,0,1
?平衡二叉树 (也称 AVL树 )的深度为 O(log N)(其中 N
为结点个数 )
?它的平均查找长度也是 O(log N)
平衡二叉树及平衡因子举例
-1
1
0 0
-1
1
0
平衡的二叉树
1
1
0
0
不平衡的二叉树
-1
0
0 0
-2
1
0
2
-1
0 1
0
0
不平衡二叉树及平衡因子举例
二叉排序树转成平衡树示例
设关键字序列为 (13,24,37,90,53)
0
13
-1
13
0
24
0
37
0
13
-2
13
-1
24
0
24
0
37
0
53
0
13 0
13
0
37
0
90
0
53
-1
24
1
90
-2
37
-2
24
(a) (b) (c)
(d) (e)
(f) (g) (h)
24
13 37
53
90
二叉排序树转成平衡树
失去平衡后进行调整的四种情况
?(1)单向右旋平衡处理
? 当在左子树上插入左结点,使平衡因子由 1增至 2时
?(2)单向左旋平衡处理 (上例从图 (d)到图 (e))
? 当在右子树上插入右结点,使平衡因子由 -1增至 -2时
?(3)双向旋转 (先左后右 )平衡处理
? 当在左子树上插入右结点,使平衡因子由 1增至 2时
?(4)双向旋转 (先右后左 )平衡处理
? 当在右子树上插入左结点,使平衡因子由 -1增至 -2时
? (例如上例从图 (f)右旋到图 (g)再左旋到图 (h))
实验与习题
?理论习题 9.3,9.10,9.11
?实验算法题, 9.25
