第十章 搜索 静态搜索结构 动态搜索结构 散列 可扩充散列.

Presentation on theme: "第十章 搜索 静态搜索结构 动态搜索结构 散列 可扩充散列."— Presentation transcript:

1 第十章 搜索 静态搜索结构 动态搜索结构 散列 可扩充散列

2 查找 搜索 搜索结构 同一数据类型（纪录）的元素 构成的数据集合。 搜索 在数据集合中寻找满足条件的对 象（数据元素）。
查找 搜索 搜索结构 同一数据类型（纪录）的元素 构成的数据集合。 搜索 在数据集合中寻找满足条件的对 象（数据元素）。 关键字 数据元素中某个字段（数据项） 的值。 主关键字 唯一地表示一个纪录 。 次关键字 标识若干纪录

3 搜索成功 找到满足条件的数据对象 报告该对象在结构中的位置 给出整个纪录的信息 搜索失败 搜索不成功 静态搜索 搜索结构在搜索前后不发生变化 动态搜索 搜索的同时执行插入或删除 结构自行调整 提高效率 先排序，分类，编目，索引 优化结构

4 一、静态搜索结构 基于数组的数据表类 顺序表——线性表、数组、链表。 (1) 顺序搜索 从头至尾逐个比较 最快O(1) 最慢O(n)
(1) 顺序搜索 从头至尾逐个比较 最快O(1) 最慢O(n) 搜索成功的等概率平均时间复杂性 O((n+1)/2) (1+2+3+······+n) /n=(n+1)/2 搜索失败O(n+1) 搜索的等概率平均时间复杂性 O(3(n+1)/4) 搜索成功失败各半 ((1+2+······+n)+n(n+1)) /2n =3(n+1)/4

5 (2)有序表的搜索 折半搜索 对已排序的搜索结构先确定中点，比较待查关键字与中点关键字的大小，反复直到成功。
求n个数据折半查找的等概率成功搜索的平均时间复杂性 1 2 2 3 3 3 3 4 4 4 1+2*2+4*3+3*4= O(29/10)

6 S=1+2*2+4*3+8*4+······+2k-1*k = 1+2*2+3*4+4*8+······+k*2k-1 k
满二叉树n个数据的总查找次数： 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 S=1+2*2+4*3+8*4+······+2k-1*k = 1+2*2+3*4+4*8+······+k*2k-1 k s =∑j·2j 其中 n=2k-1 j=1

7 满二叉树n个数据的总查找次数： k s =∑j·2j-1 其中 n=2k-1 j=1
S=1+2·2+3·4+4*8+5*16+·····+k·2k-1 = ···+2k-1+ 2+2·4+3·8+4·16+····+(k-1)·2k-1 = ···+2k-1+ 2·(1+2·2+3·4+4*8+5*16+·····+(k-1)·2k-2) = ···+2k-1+2·(1+2+4+···+2k-2)+ 22·(1+2+4+···+2k-3)+·····+2k-2·(1+2)+2k-1 =2k-1+2·(2k-1-1)+22·(2k-2-1)+·····+2k-2·(22-1)+ 2k-1(2-1) =k·2k-(1+2+4+···+2k-1)=k·2k-(2k-1)=(k-1)·2k+1

8 满二叉树n个数据的总查找次数： k s =∑j·2j-1 其中 n=2k-1 j=1
令s=f(k), k=1,2,3,4,······ f(1)=1 f(2)=5 f(3)=17 f(4)=49 f(5)=129 ······· f(k)-1= 0, 22, 24, 3·24，27，······ = 0·21, 1·22, 2·23, 3·24，4·25····· 猜想 f(k)-1=(k-1)·2k

9 k f(k)= s =∑j·2j-1 其中 n=2k-1 j=1
f(k)-1=(k-1)2k 证明 1) f(1)-1=0 2) f(k+1)-1=f(k)+(k+1)·2k –1 = (k-1)2k+ (k+1)·2k =2·k·2k=k·2k+1 =(k+1-1)·2k+1 S=(k-1)2k+1

10 满二叉树n个数据的总查找次数： k s =∑j·2j-1 其中 n=2k-1 j=1
S= (k-1)·2k+1 由 n=2k-1 得 k=log2(n+1) S=(n+1)(log2(n+1)-1)+1 = (n+1)log2(n+1)-n 满二叉树n个数据的搜索成功平均概率时间复杂性 ((n+1)/n) log2(n+1)-1 当n>50时 近似于 log2(n+1)-1

11 n个元素的折半搜索 2k-1≤n<2k+1-1 搜索成功平均概率时间复杂性
介于 log2(2k)-1 和 log2(2k+1)-1 之间 即 k-1 和 k 之间 k=[log2(n+1)] n个元素的折半搜索成功平均概率时间复杂性 log2(n+1)-1/2

12 根据斐波那契序列的特点对有序表分割 斐波那契搜索 0.618法 斐波那契序列
······f(n)······ f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个，如果小，再比较第8个，···· 如果大 比较后几个数的第5个······ 每次都比较位于这个数列的黄金分割点0.618处

13 平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差
以下序列中查找元素10的过程 平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差

14 （3）静态树表的搜索 不等概率查找时折半查找不一定好， 以每点查找次数（概率）为这点的权wi 带权二叉树总路径长度 PH=∑wihi i
不同于霍夫曼树：每个结点都有权值，都 要查找。

15 PH=3·1+2·2+2·4+1·3 +5·3+4·3+3·3+1·4+5·4 A B C D E F G H I
=78 A B C D E F G H I 3 E 查找次数 不是静态最优二叉树 C 2 G 4 B D H F 3 1 5 4 A I 1 5 权值

16 次优查找树 Nearly Optimal Search
数据 al,al+1,······,ai-1,ai, ai+1,······,ah 权值 wl,wl+1,·····wi-1,wi,wi+1,·····,wh 令 h i-1 Δpi= ∑wj-∑wj j=i j=l 取最小值： Δpi=min{Δpj: l≤j≤h} 以ai为根， al+1,······,ai-1为左子树 ai+1,······,ah 为右子树 构造次优查找树

17 i 令swi= ∑wj , Δpi = swh-swi-swi-1 j=l
A B C D E F G H I wi s wi Δpi Δpi Δpi

18 A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 平均查找次数 O(HP/swh) 4 F
1*3+3*3+4*3+5*3+ 1*4+2*4=71<78 D 5 H 3 B E I G 1 5 次最优树 3 4 A C 1 2 平均查找次数 O(HP/swh)

19 索引顺序表 分块有序 后一子表中的关键字都大于前一子表中的关键字 索引表 最大关键字 起始地址 22 48 86 1 7 13 22 12
9 20 33 42 44 38 24 48 60 58 74 49 86 53 分块有序 后一子表中的关键字都大于前一子表中的关键字

20 索引顺序表的查找 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索 索引表 22 48 86 1 7 13
12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索

21 索引顺序表的查找成功的平均概率时间复杂性
索引表查找时间+子表查找时间 设索引表长为s，搜索表长为n,被平均分成s块， 每块长n/s, 索引表平均查找时间 (s+1)/2 子表平均查找时间 (n/s+1)/2 ½(s+1)+ ½(n/s+1)= ½(s+n/s)+1 当 s=√n 时 有最小值 √n +1

22 有序索引顺序表 当索引顺序表已经排序时，子块搜索可以用折半搜索。 平均查找时间： (s+1)/2 +log2(1+n/s)-1/2
= log2(1+n/s)+s/2 索引也用折半查找，平均查找时间 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1 当s= √n 时 log2(√n +1)-1

23 二、动态搜索表 特点 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树

24 二叉搜索树 （二叉排序树） 49 38 65 97 76 13 27 49 其左非空子树上所有结点的值都小于根结点的值
其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树 二叉搜索树的作用：排序，检索 49 65 38 97 13 49 27 76

25 二叉搜索树的插入过程 57 20 60 8 45 59 3 45 12 50 12 57 11 8 20 60 50 3 11 59

26 平衡二叉树AVL树 ——加快查找排序的速度
定义： 左右两子树深度之差不超过1， 左子树和右子树都是平衡二叉树。 45 45 平衡 不平衡 57 12 12 60 8 20 8 20 50 3 11 3 11 59

27 同一个数组的二叉排序树和二叉平衡树 49 20 49 30 65 13 49 30 10 49 60 65 13 20 80 27 40 13 40 80 27 10 97 13 60 50 49 70 50 97 70 49

28 AVL树的结点 增加一个平衡因子 balance=height(right subtree)-height(left subtree)
data balanceFactor right balance=height(right subtree)-height(left subtree) balance=1或-1

29 平衡因子 1 49 1 65 38 13

30 左重加左——右转 结点p左重，还要加一个左结点 不平衡 右转： 将p作lc的右子结点 p lc lc p 49 65 38 49 13 65
10 p 10 38

31 左重加左——右转 结点p左重，还要加一个左结点 不平衡 右转：将p作lc的右子结点, 将lc的右子树接成p的左子树 p lc lc p 38
13 lc 13 40 p 38 10 20 10 40 4 20 4

32 右重加右——左转 结点p右重，还要加一个右结点 不平衡 左转：将p作rc的左子结点, 将rc的左子树接成p的右子树 p rc rc p 38
40 rc 13 40 p 45 38 45 39 4 13 39 4

33 左重加左的右——双旋 左转再右转 结点p左重 lc的右子树加一个结点 不平衡 先以lc np为轴左转 再以p, np为轴右转 p np p
左重加左的右——双旋 左转再右转 结点p左重 lc的右子树加一个结点 不平衡 先以lc np为轴左转 再以p, np为轴右转 p np p 38 38 20 p lc np lc 40 20 13 40 38 13 lc np 20 13 26 10 40 26 10 26 10

34 右重加右的左——双旋 右转再左转 结点p右重 rc的左子树加一个结点 不平衡 先以rc np为轴右转 再以p, np为轴左转 p np p
右重加右的左——双旋 右转再左转 结点p右重 rc的左子树加一个结点 不平衡 先以rc np为轴右转 再以p, np为轴左转 p np p 38 38 46 rc np np p 46 13 13 55 55 38 rc np 41 46 55 67 67 13 41 41 67

35 AVL树的生成 20 30 80 40 10 60 50 70 左转 左重加左的右 左转再右转 49 30 49 65 13 20 49
49 30 49 65 13 20 49 30 13 65 49 27 80 20 27 80 10 40 左转 13 60 13 65 49 30 49 27 80 左重加左的右 左转再右转 20

36 13 30 49 65 左转 49 27 80 20 60 13 49 30 65 10 49 27 80 20 40 13 右转 10 40 13 49 13 30 65 60 49 20 60 左重加左的右 左转再右转 10 80 27 40 13

37 13 65 49 30 49 20 60 10 80 27 40 13 65 30 13 49 50 70 13 13 49 20 60 10 27 80 40 13

38 AVL树的高度 设AVL树高度为h, 这棵树至少多少结点？
设至少有nh个结点 n0=0, n1=1 , n2=2, nh+1=nh+nh-1+1, nh+1+1=nh+1+nh-1+1, 令 fh= nh+1, 则 f0=1, f1=2 , fh+1=fh+fh-1 nh = fh-1 nh=(51/2)*((1+ 51/2)/2)h+3 -1

39 n个结点的AVL树的高度h至多是多少？ n=(51/2)*((1+ 51/2)/2)h+3 -1
log2 (n+1)-log251/2= (h+3 )(log2 ((1+ 51/2)/2)) log2 ((1+ 51/2)/2)≈0.694 h+3= (log2 (n+1)-log251/2)/0.694 h<(3/2) log2 (n+1)-1

40 练习 一. 画出以下输入所对应AVL树： 1）R,O,T,A,R,Y,C,L,U,B 2）60，25，7，99，15，3，10 38，59，62，34 二. 分别给出这两棵树的前序，中序， 后序遍历输出 三、高度为5的AVL树至少几个节点。 15个节点的AVL树至多多高？

41 二叉搜索树的查找分析 平均等概率查找时间 (1+2+2+3+3+3)/6=14/6 (1+2+3+4+5+6)/6=7/2 8 8 3 45
57 12 60 8 20 45 20 ( )/6=7/2 12 11 8 3

42 随机二叉搜索树等概率平均查找时间 P(n)≤2(1+1/n)lnn O(log2n) 最坏 O(n/2)

43 平衡二叉搜索AVL树的查找分析 求含有n个关键字的AVL树的最大深度？ 设深度h的AVL树的最小结点数为Nh
N0=0, N1=1, N2=2 Nh= Nh-1+ Nh-2+1 Nh+1= Nh-1+1+ Nh-2+1 令 F(h)= Nh+1， 则 F(h)=F(h-1)+F(h-2) Nh Nh-1 Nh-2

44 深度h的AVL树的最小结点数Nh F(h)= Nh+1， F(h)=F(h-1)+F(h-2) F(h)是斐波那契数列
F(1)=1 F(2)=2 F(3)=3 F(4)=5 F(5)=8 ······· N1=0, N2=1, N3=2, N4=4, N5=7, N6=12,····

45 平衡二叉搜索AVL树的查找分析 设 n个结点的AVL树的最大深度为h， 则 Nh=n F(h)=n+1 可以得到h. h就是最大查找次数
等概率平均查找成功时间复杂性O(log2n)

46 B-树 平衡的多路搜索树 B-树的定义 空树 或 m叉树 每个结点至多有m棵子树， 如根结点不是叶，至少有两棵子树，
除根之外，所有非终端结点至少有┌m/2 ┐棵子树 ,本节中记为[m/2], m=3时 称为2-3树 所有的非终端结点含有信息 (n,A0,K1,A1,K2,······,Kn,An) [m/2]-1个关键字 5) 所有叶结点都在同一层次 ，叫做失败结点。

47 所有的非终端结点含有信息 n A0 K1 A1 K2 ······ Kn An n : 有n+1棵子树， K1≤K2≤······≤Kn 关键字有序序列, 指针Ai-1指向子树中结点的关键字小于Ki,

48 1 35 1 18 2 43 78 1 11 1 27 1 39 3 47 53 1 99 F F F F F F F F F F F

49 B-树的搜索过程 检索结点53 每增加一个关键字增加一个结点 最底层空结点有n+1个 1 · 35 1 · 18 2 · 43 78 F F
11 1 27 1 39 3 47 53 1 99 F F F F F F F F F F F 每增加一个关键字增加一个结点 最底层空结点有n+1个

50 B-树的查找分析 n个关键字，m阶B-树的最大深度h, 深度h的m阶B-树的最少结点数=n, 设第i层最少结点数Ni N1=1, N2=2, N3=2 [m/2] N4= 2 [m/2]2, N5= 2[m/2]3 ······ Nh= 2[m/2]h-2 Nh+1= 2[m/2]h-1 底层叶结点都是空结点 n+1≥Nh+1

51 h·[m/2] ≤ (log[m/2]((n+1)/2)+1)·[m/2] O(log2n)
Nh+1= 2[m/2]h-1≤ n+1 h-1 ≤ log[m/2]((n+1)/2) h ≤ log[m/2]((n+1)/2)+1 n个结点的B-树的最大查找次数 为 h·[m/2] ≤ (log[m/2]((n+1)/2)+1)·[m/2] O(log2n)

52 B-树的插入 先从底层以大小增加一个关键字 1. 结点中的关键字不超过m时完成。 2.结点中的关键字等于m时： 将该结点分成左右两个结点
中间一个关键字上升至双亲结点 重复2.直至根

53 增加一个关键字60 插入底层 1 · 35 1 · 18 2 · 43 78 F F F F F F F F F F F 1 · 11 1
27 1 39 3 47 53 1 99 F F F F F F F F F F F 插入底层

54 增加一个关键字60 将53上移结点分裂 1 · 35 1 · 18 2 · 43 78 F F F F F F F 1 · 39 3 ·
47 53 60 1 99 F F F F F F F 将53上移结点分裂

55 增加一个关键字60 再将53上移结点分裂 1 · 35 1 · 18 2 · 43 53 78 F F F F F F F F 1 · 39
47 1 60 1 99 F F F F F F F F 再将53上移结点分裂

56 增加一个关键字60 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F 1 · 39 1 · 47 1
99 F F F F F F F F

57 B-树的删除 找到要删除的关键字所在结点，删除。 若这个结点是最下层结点，并且其中关键字数不少于[m/2]-1删除完成。
若删除的是非终端结点中的关键字Ki，以指针Ai 所指子树的最小关键字Y代替Ki,删除Y. 重复直至叶结点 若这个结点是最下层结点，但是其中关键字数不少于[m/2]-1，删除完成。

58 若该结点的左右兄弟结点的关键字数都等于[m/2]-1，则将其与一个兄弟结点合并，从双亲结点下移一个关键字被删除关键字的位置。
重复2。

59 删除一个关键字53 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F F 1 · 39 1 · 47
60 65 1 99 F F F F F F F F F

60 删除一个关键字53 关键字78上移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F F F 1 · 39 1
47 1 60 65 1 99 F F F F F F F F F 关键字78上移

61 删除一个关键字53 关键字99上移 1 · 35 78 1 · 18 2 · 43 1 99 F F F F F F F F F 1 ·
39 1 47 1 60 65 1 F F F F F F F F F 关键字99上移

62 删除一个关键字53 关键字65上移，99下移， 1 · 35 78 1 · 18 2 · 43 1 65 F F F F F F F F 1
39 1 47 1 60 1 99 F F F F F F F F 关键字65上移，99下移，

63 删除一个关键字53 关键字65继续上移，与78交换，删除完成 1 · 35 65 1 · 18 2 · 43 1 78 F F F F F
39 1 47 1 60 1 99 F F F F F F F F 关键字65继续上移，与78交换，删除完成

64 删除一个关键字53 关键字78上移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F F 1 · 39 1 ·
47 1 60 1 99 F F F F F F F F 关键字78上移

65 删除一个关键字53 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F 1 · 39 1 · 47 1
60 1 99 F F F F F F F F

66 删除一个关键字53 关键字99上移 1 · 35 78 1 · 18 2 · 43 1 99 F F F F F F F F 1 · 39
47 1 60 1 F F F F F F F F 关键字99上移

67 删除一个关键字53 两个结点合并，关键字99下移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F 1 ·
39 1 47 1 60 99 F F F F F F F 两个结点合并，关键字99下移

68 删除一个关键字53 两个结点合并，关键字78下移 1 · 35 1 · 18 2 · 43 78 F F F F F F F 1 · 39
47 1 60 99 F F F F F F F 两个结点合并，关键字78下移

69 删除一个关键字53 关键字78继续下移，与60交换 1 · 35 1 · 18 2 · 43 60 F F F F F F F 1 · 39
47 1 78 99 F F F F F F F 关键字78继续下移，与60交换

70 B+树 B-树的变形 根结点(非叶时)至少有两个结点 除根外，非叶结点至少有[m/2]棵子树 最多有m棵子树,非叶结点都是索引，
含有子树中的最大或最少关键字 含有n个关键字的非叶结点有n棵子树 所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针

71 B+树 根 59 97 15 44 59 72 97 叶 10 15 21 37 44 51 59 63 72 85 91 97 两种查找：从根开始，从叶起始

72 B+树查找成功的时间复杂性 设第i层最少结点数Ni N1=[m/2], N2=2[m/2], N3=2 [m/2]2 ······
Nh= 2[m/2]h-1 n≥Nh n ≥ 2[m/2]h-1 h-1=log[m/2](n/2) h=log[m/2](n/2)+1 h·[m/2]=(log[m/2](n/2)+1)·[m/2] O(log2n)

73 B+树的插入和删除 与B-树类似

74 键树__ 数字查找树 Trie树 (Digital Search Tree)
度≥2的树， 每个结点只包含组成关键字的部分符号。 为查找方便，约定简述为有序树，同层兄弟有序排列。

75 键树的例 16个关键字 CAI,CAO,LI,LAN,CHA,CHANG,WEN,
CHAO,YUN,YANG,LONG,WANG,ZHAO, LIU,WU,CHEN

76 以首字符分组： {CAI,CAO, CHA,CHANG, CHAO,CHEN} {LI,LAN, LONG, LIU}
{WEN,WANG,WU} {YANG,YUN} {ZHAO}

77 继续以第二,第三····字符分组 直到每组一个关键字 {{{CAI},{CAO}}, {{CHA},{CHANG}, {CHAO}},
{CHEN}} {{LAN} , {LIU}, {LONG}} {{WANG}, {WEN},{WU}} {{YANG},{YUN}}

78 以集合,子集,元素的层次组成树 C L W Y Z A H A U H A I O A E U I O A E N $ U N N N $
G G $ N $ O $ $ $ A O N $ $ $ $ $ G $ $ $ $

79 键树的孩子兄弟表示———双链树 C L W Y Z A H A U H A I O A E U I O A E N $ U N N N $
G G $ N $ O $ $ $ A O N $ $ $ $ $ G $ $ $ $

80 键树的查找成功时间复杂性 键树的结点的最大度d由基决定: 关键字是英文单词： d=27 数字： d=11
设键树的深度为h 假设关键字的位数都相等 则查找一个字的平均长度 h(1+d)/2

81 三、哈希表 Hashing table___散列
一种搜索结构 不经过任何比较，一次存取就能得到所查的纪录： 每个记录和存储位置之间建立一个一一对应关系 f , 对每个关键字K, f(K)就是K的存储位置 称f为哈希函数。

82 哈希函数的例 int HF(int key)//直接定址法 a,b是选定的常数 { return a*key+b;}
1993 1994 1996 1999 2001

83 留余数法 int HF(int key)//模一个素数得到的余数 { return key%11; }
23 35 48 60 107 18 9 43

84 数字分析法 以第三位定位 2001 1939 1949 1969 1999

85 int HF(char *key)//首末字母法，首末字母之和模101
{ int len=strlen(key), hashf=0; if(len<=1)hashf=key[0]; else hashf=key[0]+key[len-1]; return hashf%101; } Beijing Shanghai Tianjin Chongqing Beijing ChongQing Shanghai Tianjin

86 int HF(char *key)//全字母法，所有字母的和模101
{ int hashf=0; while(*key)hashf+=*key++; return hashf%101; } int HF(int key)//平方取中法 { key*=key; //key平方 key>>=11; //右移11位，去掉末尾11位 return key%1024;//去掉前面11位

87 处理冲突的方法 冲突collision: 不同的关键字得到同一个地址 1.开放定址法——线性探查法
23 35 48 60 17 29 38 40

88 开放定址法 23 35 48 60 17 29 38 40 查找成功平均查找次数 ( )/8=12/8=3/2

89 哈希表的装填因子α α=———————— 表中填入的纪录数 哈希表的长度 开放定址法的查找成功的平均查找次数 (1+1/(1-α))/2
查找不成功的平均查找次数 (1+1/(1-α)2)/2

90 开放定址法的缺点 容易引起“二次聚集” 发生冲突的点引起再一次冲突的可能性增加 使冲突点聚集 可以用再哈希法改进 即定义一个哈希函数序列
发生冲突的关键字用下一个哈希函数确定位置 避免聚集

91 链地址法 1 2 3 4 5 6 7 8 9 10 11 12 ∧ 01 14 27 79 ∧ 55 68 ∧ 19 84 ∧ 20 ∧ 10 23 ∧ 11 ∧

92 查找成功的平均查找次数 （ ）/12 =21/12 α=12/12=1 1+1/2=1.5

93 链地址法 查找成功的平均查找次数 1+α/2 查找不成功的平均查找次数 α+e-α