静态搜索结构动态搜索结构散列可扩充散列-资料.ppt

文档介绍：静态搜索结构动态搜索结构散列可扩充散列-资料
查找 搜索
搜索结构 同一数据类型（纪录）的元素
构成的数据集合。
搜索 在数据集合中寻找满足条件的对
, 3·24，4·25·····
猜想 f(k)-1=(k-1)·2k
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
E
C
A
G
B
D
H
F
I
5
4
5
1
1
2
3
4
3
A B C D E F G H I
1 1 2 5 3 4 4 3 5
PH=3·1+2·2+2·4+1·3
+5·3+4·3+3·3+1·4+5·4
=78
不是静态最优二叉树
查找次数
权值
次优查找树 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+1 j=l
取最小值：
Δpi=min{Δpj: l≤j≤h}
以ai为根， al+1,······,ai-1为左子树
ai+1,······,ah 为右子树
构造次优查找树
i令swi= ∑wj , Δpi = swh-swi-swi-1 j=l
A B C D E F G H I
wi 1 1 2 5 3 4 4 3 5
s wi 1 2 4 9 12 16 20 23 28
Δpi 27 25 22 15 7 0 8 15 23
Δpi 11 9 3 1 9 8 1 7
Δpi 3 1 2
A B C D E F G H I wi 1 1 2 5 3 4 4 3 5
F
D
A
H
B
E
I
G
C
3
4
2
1
1
5
5
3
4
HP=4*1+5*2+3*2+
1*3+3*3+4*3+5*3+
1*4+2*4=71<78
次最优树
平均查找次数 O(HP/swh)
索引顺序表
分块有序
后一子表中的关键字都大于前一子表中的关键字
22
48
86
1
7
13
22
12
13
8
9
20
33
42
44
38
24
48
60
58
74
49
86
53
最大关键字
起始地址
索引表
索引顺序表的查找
查找 关键字key=38
1. 先检索索引表 确定子表位置
2. 再在子表中搜索
22
48
86
1
7
13
22
12
13
8
9
20
33
42
44
38
24
48
60
58
74
49
86
53
索引表
索引顺序表的查找成功的平均概率时间复杂性
索引表查找时间+子表查找时间
设索引表长为s，搜索表长为n,被平均分成s块，
每块长n/s,
索引表平均查找时间 (s+1)/2
子表平均查找时间 (n/s+1)/2
½(s+1)+ ½(n/s+1)= ½(s+n/s)+1
当 s=√n 时 有最小值 √