第 8章 查找表
8.1 静态查找表
8.2 动态查找树表
8.3 哈希表学习提要
熟练掌握顺序表和有序表的查找方法。
熟练掌握二叉排序树的构造和查找方法。
掌握二叉平衡树的维护平衡方法。
理解 B-树的特点以及它们的建树过程。
熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
何谓查找表？
查找表是由同一类型的数据元素 (或记录 )构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
对查找表经常进行的 操作,
1)查询 某个,特定的,数据元素是否在查找表中；
2)检索 某个,特定的,数据元素的各种属性；
3)在查找表中 插入 一个数据元素；
4)从查找表中 删去 某个数据元素 。
仅作 查询 和 检索 操作的查找表。静态查找表在查询之后，还需要将“查询”结果为
,不在查找表中,的数据元素 插入到 查找表中；或者，从查找表中 删除 其“查询”
结果为,在查找表中,的数据元素。
动态查找表查找表分类是数据元素 (或记录 )中某个 数据项 的值，
用以 标识 (识别 )一个数据元素 (或记录 )。
关键字若此关键字识别 唯一的 一个记录,则称之谓,主关键字,,若此关键字能识别 若干 记录，则称之谓,次关键字,。
根据给定的某个值，在查找表中 确定一个其关键字等于给定值的数据元素或（记录）
查找若查找表中存在这样一个记录,则称 查找成功,查找结果,
给出整个记录的信息,或指示该记录在查找表中的位臵 ;
否则称 查找不成功,查找结果,给出 空记录 或 空指针 。
由于查找表中的数据元素之间不存在明显的组织规律，
因此 不便于查找 。为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，
用另外一种结构来表示查找表。
如何进行查找？ 查找的方法取决于查找表的结构。
查找表 (Search Table),是一种以集合为逻辑结构,
以查找为核心运算 的数据结构 。
静态查找表,只对查找表进行 查询 某个特定的数据元素或某个特定数据元素的各种属性的操作 。
如：查询成绩表中是否有某学生或该学生某门课程的成绩 。
动态查找表,对查找表进行插入或删除某个数据元素的操作 。 如：修改某个学生某门课程的成绩 。
衡量查找算法的标准：
(1)平均查找长度；
(2)算法所需要的存储量和算法的复杂性等 。
平均查找长度定义,为确定记录在表中的位臵，需和给定值进行比较的关键字的个数的期望值叫查找算法在查找成功时的 平均查找长度 。
n
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpASLn
i
n
i
ii
i
ii
1
1
1 =
=
=
=
物理意义,假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为 ASL。
显然,ASL值越小，时间效率越高。
构造一个含 n 个数据元素的静态查找表 ST。
Create(&ST,n);
操作结果：
基本操作销毁表 ST。
Destroy(&ST);
初始条件：
操作结果：
静态查找表 ST存在；
若 ST 中存在其关键字等于 kval 的数据元素，则函数值为该元素的值或在表中的位臵，否则为“空”。
Search(ST,kval);
初始条件：
操作结果：
静态查找表 ST存在,kval 为和查找表中元素的关键字类型相同的给定值；
按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次，一旦 Visit()失败，则操作失败。
Traverse(ST,Visit());
初始条件：
操作结果：
静态查找表 ST存在,Visit是对元素操作的应用函数；
一、顺序查找（ Linear search，又称线性查找 ）
顺序表的机内存储结构：
typedef struct {
ElemType *elem; //表基址,0号单元留空
int length; //表长
} SSTable;
顺序查找,用逐一比较的办法顺序查找关键字。
对 顺序结构 如何线性查找？
对 单链表结构 如何线性查找？
对 非线性树结构 如何顺序查找? 借助各种遍历操作！
8.1 静态查找表
typedef struct {
keyType key; // 关键字域
… … // 其它属性域
} ElemType ;
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
回顾顺序表的查找过程：
假设给定值 e = 64,
要求 ST.elem[i] = e,问,i =?
i i
66
i
以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找查找过程,从表的一端开始逐个进行记录的关键字和给定值的比较算法描述
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
比较次数 =5比较次数：
查找第 n个元素,1
查找第 n-1个元素,2
……….
查找第 1个元素,n
查找第 i个元素,n+1-i
查找失败,n+1
算法的实现技巧,把待查关键字 key存入表头或表尾（俗称,哨兵,），这样可以加快执行速度。
例,若将待查找的特定值 key存入 顺序表的 首部 (如 0号单元 ),则顺序查找的实现方案为,从后向前 逐个比较！
int Search_Seq( SSTable ST,KeyType key ) {
//在顺序表 ST中，查找关键字与 key相同的元素；若成功，返回其位臵信息，否则返回 0
ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当 n>1000时，查找时间将减少一半。
for( i=ST.length; ST.elem[ i ].key!=key; --i );
//不要用 for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++)
return i; //若到达 0号单元才结束循环，说明不成功，返回 0值
(i=0)。成功时则返回找到的那个元素的位臵 i。
}
int location( SqList L,ElemType& e,
Status (*compare)(ElemType,ElemType)) {
i = 1;
p = L.elem;
while ( i<=L.length &&
!(*compare)(*p++,e))) i++;
if ( i<= L.length) return i;
else return 0;
} //location
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
i
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
i
60
i
kval = 64
kval = 60
i
64
分析顺序查找的时间性能定义,查找算法的 平均查找长度 (Average Search Length)
为确定记录在查找表中的位臵，需和给定值 进行比较的关键字个数的期望值
=
=
n
i
iiCPA S L
1其中,n 为表长,P
i 为查找表中第 i个记录的概率，且
Ci为找到该记录时，曾 和给定值比较过的关键字的个数
1
1
=?
=
n
i
iP
顺序表查找的平均查找长度 为：
对 顺序表 而言,Ci = n-i+1
2
111
1
==?
=
n)i(n
nA S L
n
i
ss
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
nPi
1=在 等概率 查找的情况下，
若查找概率无法事先测定，则查找过程采取的改进办法是,在每次查找之后,将刚刚查找到的记录直接移至表尾的位臵上 。
在 不等概率查找 情况下,ASLss在 Pn≥Pn-1≥···≥P2≥P1 时 取极小值
—— 返回特殊标志，例如返回空记录或空指针。前例中设立了,哨兵,,
就是将关键字送入末地址 ST.elem[0].key使之结束并返回 i=0。
讨论① 查不到怎么办？
讨论③ 如何计算 ASL？
分析：
查找第 1个元素所需的比较次数为 1；
查找第 2个元素所需的比较次数为 2；
……
查找第 n个元素所需的比较次数为 n；
总计全部比较次数为,1＋ 2＋ … ＋ n = (1+n)n/2
未考虑查找不成功的情况：查找哨兵所需的比较次数为 n+1
这是查找成功的情况若求某一个元素的平均查找次数，还应当除以 n(等概率 ),
即,ASL＝ (1＋ n)/2,时间效率为 O(n)
优点,算法简单，且对顺序结构或链表结构均适用。
缺点,ASL 太长，时间效率太低。
讨论④ 顺序查找的特点：
讨论② 查找效率怎样计算？ 用平均查找长度 ASL衡量。
问题,顺序查找表的查找算法简单,但平均查找长度较大,特别不适用于 表长较大 的查找表。
二、有序查找表办法,若以 有序表 表示静态查找表，则查找过程可以基于 折半 进行,
查找过程,每次将待查记录所在区间缩小一半
适用条件,采用顺序存储结构的有序表
算法实现
– 设表长为 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时，查找失败
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 21
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
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
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 high
mid
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
lowhigh
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 1 0 1 1
ST.elem
ST.length
例如,key = 64 的查找过程如下
low high
mid
low
mid
high
mid
low 指示查找区间的下界 ;
high 指示查找区间的上界 ;
mid = (low+high)/2。
② 运算步骤,
(1) low =1,high =11,mid =6,待查范围是 [1,11]；
(2) 若 ST.elem[mid].key < key，说明 key?[ mid+1,high],
则令,low =mid+1;重算 mid＝?(low+high)/2?；,
(3) 若 ST.elem[mid].key > key，说明 key?[low,mid-1]，
则令,high =mid–1;重算 mid ；
(4)若 ST.elem[ mid ].key = key，说明查找成功，元素序号 =mid;
结束条件,(1) 查找成功,ST.elem[mid].key = key
(2) 查找不成功,high≤low（意即区间长度小于 0）
解,① 先设定 3个辅助标志,low,high,mid，
折半查找举例：
Low指向待查元素所在区间的下界 high指向待查元素所在区间的上界
mid指向待查元素所在区间的中间位臵已知如下 11个元素的 有序表,
（ 05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为 21
和 85的数据元素。
显然有,mid=?(low+high)/2?
int Search_Bin ( SSTable ST,KeyType kval ) {
low = 1; high = ST.length; // 臵区间初值
while (low <= high) {
mid = (low + high) / 2;
if （ kval == ST.elem[mid].key )
return mid; // 找到待查元素
else if ( kval < ST.elem[mid].key) )
high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin
全部比较总次数为 1× 20＋ 2× 21＋ 3× 22＋ 4× 23… ＋ m× 2m— 1
＝?
=
m
j
jj
1
12
讨论① 若关键字不在表中，怎样得知和停止？
—— 典型标志是：当查找范围的上界 ≤下界时停止查找 。
讨论② 二分查找的效率（ ASL）
1次比较就查找成功的元素有 1个 (20),即中间值；
2次比较就查找成功的元素有 2个 (21),即 1/4处（或 3/4）处；
3次比较就查找成功的元素有 4个 (22),即 1/8处（或 3/8）处 …
4次比较就查找成功的元素有 8个 (23),即 1/16处（或 3/16）处 …
……
则第 m次比较时查找成功的元素会有 (2m-1)个 ；
为方便起见，假设表中全部 n个元素＝ 2m-1个,此时就不讨论第 m
次比较后还有剩余元素的情况了。
推导过程性能分析以 11个数的查找为例：
5 13 19 21 37 56 64 75 80 88 92
1 2 3 4 5 6 7 8 9 10 11
找到第 6个数仅需比较 1次,
找到第 3和第 9个数需 2次,
找到第 1,4,7,10个数需 3次，
找到第 2,5,8和 11个数需 4次。
6
3 9
1 4 7 10
2 5 8 11
性能分析
查找成功时进行比较的次数最多不超过该树的深度。
具有 n个结点的判定树的深度为?log2n?。
折半查找法在查找成功时比较次数最多 为?log2n?+1次。
查找不成功的情况如下所示 (方框表示查找不成功的情况 )
6
3 9
1 4 7 10
2 5 8 11-1 3-4 6-7 9-10
1-2 3-4 4-5 5-6 7-8 8-9 10-11 11-
查找不成功时的最多比较次数也是?log2n?+1。
查找某个结点的过程就是从根结点到相应的结点的路径。查找过程用二叉树来表示查找某个结点所比较的次数等于该结点的层次数加 1。
先看一个具体的情况，假设,n=11
折半查找的平均查找长度
6
3 9
1 4
2 5
7
8
10
11
判定树
i 1 2 3 4 5 6 7 8 9 10 11
C i
12 23 3 3 34 4 4 4
假设 n=2h-1 并且查找概率相等则一般情况下，表长为 n的折半查找的判定树的深度和含有 n个结点的完全二叉树的深度相同。
1)1(lo g1211 2
1
1
1
=?
==
=
=
n
n
nj
n
C
n
A S L
h
j
j
n
i
ibs
1)1(l o g 2 nA S L bs在 n>50 时,可得近似结果优点,比较次数少，检索速度快,
缺点,字典按关键码排序,只适用于顺序存储结构,
三、分块查找（索引顺序查找）
这是一种顺序查找的另一种改进方法 。
1,先让数据 分块有序,即分成若干子表，要求每个子表中的数值 (用关键字更准确 )都比后一块中数值小 (但子表内部未必有序 )。
2,然后将各子表中的最大关键字构成一个 索引表,表中还要包含每个子表的起始地址 (即头指针 )。
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
第 3块例：
22 48 86
1 7 13
特点：块间有序，块内无序索引表最大关键字起始地址第 1块 第 2块索引顺序表在建立顺序表的同时，建立一个索引。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ……
17 08 21 19 14 31 33 22 25 40 52 61 78 46 ……
21 0 40 5 78 10 ……
例如：
索引顺序表 = 索引 + 顺序表顺序表索引分块查找分块查找
– 查找过程,将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找
– 适用条件,分块有序表
– 算法实现
用数组存放待查记录,每个数据元素至少含有关键字域
建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
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
查找步骤 分两步进行：
① 对索引表使用折半查找法（因为索引表是有序表）；
② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
查找效率,ASL=Lb+Lw
对索引表查找的 ASL 对块内查找的 ASL
)2 1( lo g2)1(lo g 22 nA S LnssnA S L bsbs
S为每块内部的记录个数,n/s即块的数目例如当 n=9,s=3时,ASLbs=3.5,而折半法为 3.1,顺序法为 5
typedef struct {
KeyType maxkey;
int stadr;
} indexItem; //索引项
typedef struct {
indexItem *elem;
int stadr;
} indexTable; //索引表索引顺序表的查找过程：
1）由索引确定记录所在区间；
2）在顺序表的某个区间内进行查找。
索引顺序查找 的过程也是一个,缩小区间” 的查找过程。
对比顺序表和有序表的查找性能顺序表 有序表表的特性 无序 有序存储结构 顺序 或 链式 顺序插删操作 易于进行 需移动元素
ASL的值 大 小
int Search_Idx ( SSTable ST,indexTable ID,KeyType kval )
{ low = 0; high = ID.length-1; found = FALSE;
if ( kval>ID.elem[high].key ) return 0;
while ( low <=high && !found ) {
mid = (low+high)/2;
if ( kval < ID.elem[mid].key ) high = mid - 1;
else if ( kval > ID.elem[mid].key ) low = mid +1;
else { found = TRUE; low = mid; }
}
s = ID.elem[low].stadr;
if ( low < ID.length-1 ) t = ID.elem[low +1].stadr-1; else t = ST.length;
if ( ST.elem[t].key== kval ) return t;
else {
ST.elem[0] = ST.elem[t]; // 暂存 ST.elem[t]
ST.elem[t].key = kval; // 设置监视哨
for ( k=s; ST.elem[k].key !=kval; k++ ) ;
ST.elem[t] = ST.elem[0]; // 恢复暂存值
if ( k != t ) return k; else return 0;
}
}
22
1 7 13
48 86
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引表最大关键字起始地址索引顺序法查找方法,分块查找,是顺序查找的一个改进方法。
在此查找法中，除顺序表外还有一个索引表。
整个表分成三个子表，对每个子表建立一个索引项，索引项包括两项内容：
关键字项 (其值为该子表内的最大关键字 )
指针项 (指示该子表的第一个记录在表中的位臵 )。
索引表按关键字有序,表或者有序或者分块有序。分块有序指的是后一个子表中所有记录的关键字均大于前一个子表中的最大关键字。
分块查找需分两步进行：
(1) 现确定待查记录所在的块 (子表 )
(2) 然后在块中顺序查找。
分块查找的平均查找长度为,ASL ＝ Lb + Lw
将长度为 n的表均匀地分成 b块,每块含有 s个记录,即 b=?n/s?;
假定表中每个记录的查找概率相等，则每块查找的概率为 1/b,
块中每个记录的查找概率为 1/s。
若用顺序查找确定所在块,则
ASL = Lb + Lw = (b+1)/2 + (s+1)/2 = n/(2s) + s/2 +1
2
)1(lo g 2 s
s
nA S L
bs
：用折半查找确定所在块索引顺序查找的平均查找长度 =
查找 索引 的平均查找长度 + 查找 顺序表 的平均查找长度注意：索引可以根据查找表的特点来构造。
综合上一节讨论的几种查找表的特性：
查找 插入 删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表
(n)
(1)
(n)
(1)
(nlogn)
(n)
(n)
(logn)
(n)
(logn)
(1)
(1)
(n)
(1)
(nlogn)
可得如下结论：
1) 从 查找 性能看,最好情况能达?(logn),此时要求表 有序 ；
2) 从 插入 和 删除 的性能看,最好情况能达?(1),此时要求存储结构是链表 。
ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找 折半查找 分块查找
8.2 动态查找树表一、二叉排序树（二叉查找树）
二、键树基本操作 P操作结果,构造一个空的动态查找表 DT。InitDSTable(&DT);
销毁动态查找表 DT。
DestroyDSTable(&DT);
初始条件：
操作结果：
动态查找表 DT存在；
若 DT中存在其关键字等于 kval的数据元素,则函数值为该元素的值或在表中的位臵,否则为“空”,
SearchDSTable(DT,kval);
初始条件：
操作结果：
动态查找表 DT 存在,kval为和关键字类型相同的给定值 ;
动态查找表 DT 存在,e 为待插入的数据元素；
InsertDSTable(&DT,e);
初始条件：
操作结果,若 DT中不存在关键字等于 e.key的元素,则插入 e 到 DT。
动态查找表 DT存在,kval为和关键字类型相同的给定值 ;
DeleteDSTable(&T,kval);
初始条件：
操作结果,若 DT中存在其关键字等于 kval的数据元素,则删除之。
动态查找表 DT存在,Visit是对结点操作的应用函数；
TraverseDSTable(DT,Visit());
初始条件：
操作结果,按某种次序对 DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。
二叉排序树 (Binary Sort Tree)或者是一棵空二叉树；或者具有下列性质的二叉树：
A,若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
B,若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
C,它的左右子树也分别为二叉排序树。
8.2.1 二叉排序树实际上，折半查找法的判定树就是一棵二叉排序树。
中序遍历可以得到一个关键字的有序序列 (怎么证明?)，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。 二叉排序树既有折半查找的特性，又采用了链表作存储结构。因此是动态查找表的适宜结构。
1、二叉排序树定义
50
30 80
20 90
10 85
40
3525
23 88
例如,
是二叉排序树。
66
不
struct BinTreeNode;
typedef struct BinTreeNode * pBinTreeNode;
struct BinTreeNode
{ KeyType key; /* 结点的关键码字段 */
DataType other; /* 结点的属性字段 */
PBinTreeNode llink,rlink;
/* 二叉树的左、右指针 */
};
typedef struct BinTreeNode * BinTree;
typedef BinTree *PBinTree;
二叉排序树的存储结构
K= { 18,73,10,05,68,99,27,41,51,32,25 }
18
10 73
9968
27
25 41
32 51
05
二叉排序树示例
45
24 53
12 90
如果待 查找的关键字序列输入顺序为,(24,53,45,45,12,24,90)
24
53
45
12
90
查找成功，
返回查找成功，
返回讨论 1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：
例,输入待查找的关键字序列 =（ 45,24,53,45,12,24,90）
则生成的二叉排序树形态不同：
查找成功，
返回查找成功，
返回
2．二叉排序树的查找算法
1）若给定值 等于 根结点的关键字,则查找成功；
2）若给定值 小于 根结点的关键字,则继续在左子树上进行查找；
3）若给定值 大于 根结点的关键字,则继续在右子树上进行查找。
否则若二叉排序树 为空,则查找不成功；
例如,二叉排序树 查找关键字 == 50,35,90,95
50
30 80
20 90
85
40
35
8832
L.key<T.key<R.key
while （ T非空）
{
if (T.key==key)
查到；
else if (T.key>key)
查左子树；
else 查右子树；
}
二叉排序树的检索算法
T
L R
查找步骤,若根结点的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,查其左子树。大于根结点的关键字值,查其右子树。在左右子树上的操作类似。
122
250
300110 200
99
105 230
216
BiTree SearchBST ( BiTree T,KeyType key )
{ if ( ( !T) || key==T->data,key ) return ( T ) ;
else if ( key<T->data,key ) return (SearchBST ( T->lchild,key ));
else return ( SearchBST ( T->rchild,key ));
}
typedef float keyType;
typedef int keyType;
typedef struct { keyType key; …… } ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode * lchild,*rchild;
} BiTNode; *BiTree;
if ( !T ) { p = f; return FALSE; }
else if ( kval == T->data.key ) { p = T; return TRUE; }
else if ( kval < T->data.key )
return SearchBST (T->lchild,kval,T,p );
else
return SearchBST (T->rchild,kval,T,p );
f T设 key = 48 f
Tf
T
22
p
f
T f
T
T
T
T
f
f
fp
30
20
10
40
3525
23
1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
比较的关键字次数＝ 此结点的层次数 ;
最多的比较次数＝ 树的深度（或高度），即?log2 n?+1
2) 一棵二叉排序树的平均查找长度为：
二叉排序树的查找分析其中：
ni 是每层结点个数；
Ci 是结点所在层次数；
m 为树深。
最坏情况,即插入的 n个元素从一开始就有序，
—— 变成单支树的形态！
此时树的深度为 n ; ASL= (n+1)/2
此时查找效率与顺序查找情况相同。
=
=
m
i
ii CnnA S L
1
1
最好情况,即：与折半查找中的判定树相同（形态比较均衡）
对有 n 个关键字的二叉排序树的平均查找长度,设每种树态出现概率相 同,查找每个关键字也是等概率的。则 ASL求解过程可推导。
树的深度为,?log 2n? +1 ；
ASL=log 2(n+1) –1 ；与折半查找相同。
结论：二叉排序树的 ASL≤2(1+1/n)*ln(n)
最坏情况,即插入的 n个元素从一开始就有序。（ 单支树）
此时树深为 n ; ASL= (n+1)/2 ; 与顺序查找情况相同。
最好情况,即：与折半查找中的判定树相同 （形态均衡）
此时树深为,?log 2n? +1 ；
ASL=log 2(n+1) –1 ；与折半查找情况相同。
一般情况,（与 log n 同阶）
问题：如何提高二叉排序树的查找效率？
尽量让二叉树的形状均衡
nnA S L ln)11(2
平衡二叉树
根据动态查找表的定义,插入 操作在 查找不成功 时才进行 ;
3．二叉排序树的插入算法
若二叉排序树为空树，则新插入的结点为 新的根结点 ；
否则，新插入的结点必为一个 新的叶子结点,其插入位臵由查找过程得到。
注,若 数据元素的 输入顺序不同，则得到的二叉排序树形态也不同！
—— 这种既查找又插入的过程称为 动态查找 。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。
二叉排序树的插入
– 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
– 示例：从空树出发，待插的关键字序列为 33,44,23,46,12,37
33
4423
4612 37
中序遍历二叉排序树可得到一个关键字的有序序列。
该例中，中序遍历结果为,12,23,33,37,44,46
若从空树出发，经过一系列插入操作后，可生成一棵二叉排序树。
18
7310
05 68 99
27
41
5132
25
二叉排序树的生成过程示例例如,K = { 18,73,10,05,68,99,27,41,51,32,25 }
当树中不存在关键字等于给定值的结点时，需要生成新结点并插入到二叉树中。而新插入的结点必定是一个叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
算法,if ( 二叉排序树中查不到该结点 )
{ 建立新结点；
if (原二叉排序树是空树 )
新结点作为根结点 ;
else if (新结点 <父结点 )
插入左子树；
else 插入右子树；
}
二叉排序树中插入结点的算法
BSTSEARCH(K,t) //K为待查关键字,t为根结点指针
p=t; //p为查找过程中进行扫描的指针
while(p!=NULL){
case {
K=data(p),{查找成功,return }
K<data(p),{q=p； p=L_child(p) } //继续向左搜索
K>data(p),{q=p； p=R_child(p) } //继续向右搜索
}
}
Get(s); data(s)=K; L_child(s)=NULL; R_child(s)=NULL;
//查找不成功，生成一个新结点 s，插入到二叉排序树中
case {
t=NULL,p=s; //若 t为空，则插入的结点 s作为根结点
K<data(q),L_child(q)=s;
K>data(q),R_child(q)=s;
}
return OK
}
bool SearchBST ( BiTree T,KeyType key,BiTree f,BiTree &p )
{ if ( ( !T) { p = f; return FALSE; }
else if ( key==T ->data,key) { p = T; return TRUE; }
else if ( key<T->data,Key ) return ( SearchBST(T->lchild,key,T,p));
else return ( SearchBST(T->rchild,key,T,p) );
} // SearchBST
122
250
300110
99
T
p
f = nullf,T 的父亲结点
p,指向最后一个结点,TRUE 找到； FALSE 叶子的父亲结点。
如：插入 280 的过程。
280
r ( r,val,BiTree f,Bi ree &f
{ p = T;
while( p） {
if ( kval==p->data,Key ) return TRUE;
else if ( kval<p->data,Key ) { f = p; p = p->lchild; }
else { f = p; p = p->rchild; }
}
return FALSE;
} // SearchBST
bool Inset BST ( BiTree &T,ElemType e )
{
f = NULL;
if ( ! SearchBST ( T,e.key,NULL,p,f ) ） return FALSE;
else {
s = new BitNode;
s->data = e; s->lchild = s->rchild = NULL;
if ( ! f ) T = s;
else if ( e.key < f->data.key ) { f->lchild = s; else f->rchild = s; }
return TRUE;
}
} // Insert BST
122
250
300110
99
T
f
280
f = null
（ 1）被删除的结点 是叶子 ；
（ 2）被删除的结点 只有左子树 或者 只有右子树 ；
（ 3）被删除的结点 既有左子树，也有右子树 。
4．二叉排序树的删除算法可分 三种情况 讨论：
和插入相反，删除在 查找成功 之后进行，并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性 。
50
30 80
20 90
85
40
35
8832
（ 1）被删除的结点是 叶子结点例如,被删关键字 = 2088
其双亲结点中相应指针域的值改为“空”
50
30 80
20 90
85
40
35
8832
（ 2）被删除的结点 只有左子树或者 只有右子树其双亲结点的相应指针域的值改为
“指向被删除结点的左子树或右子树”。
被删关键字 = 4080
50
30 80
20 90
85
40
35
8832
（ 3）被删除的结点 既有左子树，也有右子树
40
以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 50
二叉排序树的删除假设被删结点为 *p，其双亲结点为 *f，
– *p为叶子结点：删去 *p，并修改 *f 的孩子域。
– *p只有左子树 PL或只有右子树 PR：令 PL或 PR直接成为 *f 的子树
33
4423
4612 37
33
4423
4612
45
46
45
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空
33
4423
4612 37
40 50
48
35
38
46
50
48
33
23
12
37
4035
38
方法 1,PL 接替 *p成为 *f 的子树,PR成为 PL最右下结点
(中序遍历 PL所得序列的最后一个结点 )的右子树。
这种方法可能会导致二叉排序树高度的增长 ！
本例中高度,5?6
48
46
50
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空
33
4423
4612 37
40 50
48
35
38
33
23
12
方法 2,与方法 1对称,PR 接替 *p成为 *f 的子树,PL成为 PR最左下结点 (中序遍历 PR所得序列的最后一个结点 )
的左子树。
37
4035
38
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空方法 3,令 *p的中序遍历的 直接前驱 替代 *p，再从二叉排序树中删去它的直接前驱。
这种方法不会导致二叉排序树高度的增长！
本例中高度,5?5
删除时，如何不增长树的高度？ 33
4423
4612 37
40 50
48
35
38
40
38
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空方法 4,与方法 3对称,令 *p的中序遍历的 直接后继替代 *p，再从二叉排序树中删去它的直接后继。
33
4423
4612
50
48
37
4035
38
46
48
50
F
C
CL
S
SL
QL
P
PR
Q PR
F
C
CL
S
SL
QL
P
PR
Q
法 2:
F
C
CL
S
SL
QL
P
PR
Q
法 1:
例：请从下面的二叉排序树中删除结点 P。
S
SL
例,在 p的左子树中找出关键码最大的结点 r，将 r的右指针指向 p的右子女，用 p的左子女代替 p结点。
18
7310
05 68 99
27
41
5132
25 删除结点 73的过程
99
K= {18,73,10,05,68,99,27,41,51,32,25}
18
10 73
9968
27
25 41
32 51
05
二叉排序树的删除操作示例
68
bool DeleteBST( BiTree &T,KeyType kval )
{
if ( !T ) return FALSE;
else
{
if ( kval == T->data.key ) { Delete (T); return TRUE; }
else if ( kval < T->data.key )
return DeleteBST ( T->lchild,kval );
else
return DeleteBST ( T->rchild,kval );
}
}
void Delete ( BiTree &p ){
// 从 二叉排序树中删除结点 p，
// 并重接它的左子树或右子树
if ( !p->rchild ) { }
else if ( !p->lchild ) { }
else { }
} // Delete
其中 删除操作 过程如下所描述
… …
… …
… …
p
// 右子树为空树则只需重接它的左子树
q = p; p = p->lchild; delete(q);
pq q
//左子树为空树只需重接它的右子树
q = p; p = p->rchild; delete(q);
p pq
q
q = p; s = p->lchild;
while (s->rchild) { q = s; s = s->rchild; }
//左右子树均不空
p->data = s->data;
if ( q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild;
delete(s); pq
s
// s指向被删结点的前驱
bool DeleteBST ( BiTree &T,KeyType key )
{
if ( !T ) return FALSE;
else if ( key == T->data,key ) Delete ( T );
else if ( key < T->data,key ) DeleteBST ( T->lchild,key );
else DeleteBST ( T->rchild,key );
return TRUE;
}
注意：删除根结点而相应的二叉树没有另增的头结点的情况。
void Delete ( BiTree &p )
{ if ( ! p-> rchild ) { q = p; p = p->lchild ; free(q); }
else if ( ! p-> lchild ) { q = p; p = p->rchild ; free(q); }
else {
q = p; s = p-> lchild;
while ( s->rchild ) { q = s; s = s->rchild; }
p->data = s->data;
if ( q != p ) q->rchild = s->lchild; else q->lchild = s->lchild;
free(s);
}
}
5、查找性能的分析对于每一棵特定的二叉排序树,均可按照平均查找长度的定义来求它的 ASL 值,显然,由值相同的 n 个关键字,构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同,甚至可能差别很大。
由关键字序列 3,1,2,5,4构造而得的二叉排序树由关键字序列 1,2,3,4,5 构造而得的二叉排序树，例如：
2
1
3
4
53
5
4
1
2
ASL=(1+2+3+4+5)/5 = 3
ASL=(1+2+3+2+3)/5 = 2.2
二叉排序树的查找分析
– 与给定值比较的关键字个数不超过二叉排序树的深度
– 示例：从空树出发，待插的关键字序列为 33,44,23,46,12,37
33
4423
4612 37
二叉排序树的形态与关键字的插入次序直接相关！
如：将上例的关键字插入次序调整为,12,23,33,44,37,46
12
23
33
37
44
46
查找成功时,等概率下,ASL(b)=(1+2+3+4+5*2)/6=20/6
查找成功时,等概率下,ASL(a)=(1+2*2+3*3)/6=14/6
下面讨论平均情况,
不失一般性,假设长度为 n的序列中有 k个关键字 小于 第一个关键字,则必有 n-k-1个关键字 大于 第一个关键字,由它构造的二叉排序树的平均查找长度是 n和 k的函数
n-k-1k
P(n,k) ( 0? k? n-1 )
假设 n个关键字可能出现的 n!种排列的可能性相同，则含 n个关键字的二叉排序树的平均查找长度
==?
=
1
0
),(1)( n
k
knPnnPA S L
=?=
==
n
i i
n
i ii
CnCpknP
11
1),(
在 等概率查找 的情况下，
=?=
= R
i
L
ir o o t
n
i
i CCCnCnknP
11),(
1)1)1()(1()1)((11= knPknkPk
n)1()1()(11= knPknkPk
n
由此可类似于解差分方程，此递归方程有解,Cn
n
nnP= log12)(
=?
=
1
0
)1()1()(111)( n
k
knPknkPknnnP
=?
=
1
12
)(21 n
k
kPkn
8.2.2 键树
1,键树的结构特点
2.,双链树
3,Trie树
1、键树的结构特点
※ 关键字 中的各个符号 分布在从根结点到叶的路径上,叶结点内的符号为“结束”的标志符。因此,键树的深度和关键字集合的大小无关 ;
※ 键树 被约定为 是一棵有序树,即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘ $’小于任何其它符号。
H
A
D
$
S
$
V
E
$
E
$ R
$ E
$
I
G
H
$
S
$
例如,
表示关键字集合
{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS }
void setmatch(DLTree root,char line[],int count[])
{
// 统计以 root为根指针的键树中,各关键字在文本串 line中
// 重复出现的次数，
// 并将其累加到统计数组 count中去
i=0;
while (i<=LINESIZE)
{
if (!Search_DLTree(root,i,k)) i++;
// 查找不成功，从下一个字符起重新开始匹配
else i += k-1;
// 从匹配成功的子串的后一个字符开始进行下一单词的匹配
}
}
2.双链树
— 以二叉链表作存储结构实现的键树
typedef enum { LEAF,BRANCH }NodeKind;
// 两种结点,{叶子 和 分支 }
结点结构,
first symbol next
分支结点
infoptr symbol next
叶子结点指向孩子结点的指针指向兄弟结点的指针指向记录的指针
H?
A
D
$
HAD
E
$
R
$
$
E
S
$
G
H
$
I?
HE
HER
HERE
HIGH HIS
…
T
叶子结点分支结点含关键字的记录
#define MAXKEYLEN 16 //关键字的最大长度
typedef struct {
char ch[MAXKEYLEN]; // 关键字
int num; // 关键字长度
} KeysType; // 关键字类型
typedef struct DLTNode {
char symbol;
struct DLTNode *next; // 指向兄弟结点的指针
NodeKind kind;
union {
Record *infoptr; // 叶子结点内的记录指针
struct DLTNode *first; // 分支结点内的孩子链指针
}
} DLTNode,*DLTree; // 双链树的类型初始状态,p=T->first; i = 0;
若 ( p && p->symbol == K.ch[i] && i<K.num-1)
则继续和给定值的下一位进行比较
p=p->first; i++;
若 ( p && p->symbol != K.ch[i] )
则继续在键树的同一层上进行查找 p=p->next;
若 ( p && p->symbol==K.ch[i] && i==K.num-1)
则 查找成功，返回指向相应记录的指针 p->infoptr
若 ( p == NULL) 则表明查找不成功，返回“空指针” ;
在双链树中查找记录的过程假设,T 为指向双链树根结点的指针,K.ch[0..K.num-1] 为待查关键字 (给定值 )。
则查找过程中的基本操作为进行下列比较,
K.ch[i] =? p->symbol
其中,p 指向双链树中某个结点,0 ≤ i ≤ K.num-1
bool Search_DLTree( DLTree rt,int j,int &k )
{
k=0; found = FALSE;
p = rt->first; // p指向双链树中第一棵子树的树根
while ( p && !found) {
while( p && p->symbol<line[j+k]) p=p->next;
if (!p || p->symbol>line[j+k]) break; // 在键树的第 k+1层上匹配失败
else { // 继续匹配
p = p->first; k++;
if (p->kind == LEAF) { //找到一个单词
count[p->idx]++; found = TRUE;
}// if
}// else
}//while
return found;
} //Search_DLTree
bool Insert_DLTree( DLTree &root,KeysType K,int &n )
{ p = root->first; f = root; j = 0;
while ( p && j < K.num ) { //在键树中进行查找
pre = NULL;
while( p && p->symbol < K.ch[j] ) { pre = p; p = p->next; }
if ( p && p->symbol == K.ch[j] ) { f = p; p = p->first; j++; }
else { //没有找到和 K.ch[j]相同的结点，插入 K.ch[j]
s = new DLNode; s->kind = BRANCH; s->symbol = K.ch[j++];
if (pre) pre->next = s; else f->first = s;
s->next = p; p = s;
break;
} //else
}//while
if ( p && j == K.num )
if ( p->first->kind == LEAF ) return FALSE; // 键树中已存在 K
else { //键树中已存在相同前缀的单词,插入由剩余字符构成的单支树
while ( j <= K.num ) {
s = new DLNode;
s->next = p->first; p->first = s; p = s;
if ( j < K.num)
{ s->kind = BRANCH; s->symbol = K.ch[j++]; s->first = NULL; }
else { s->kind = LEAF; s->symbol = '$'; n++; s->idx = n; }
}//while
return TRUE;
}//else
}
3,Trie树
— 以多重链表作存储结构实现的键树结点结构,
分支结点 叶子结点指向记录的指针
0 1 2 3 4 5 … … 24 25 26
关键字指向下层结点的指针每个域对应一个“字母”
T
0 1(A) 3 4 5(E) 9(I) … … 26
8(H)
4(D) 19(S) 22(V) 0 18(R) 7(G) 19
0 5(E)
HAD HISHIGH
HEREHER
HEHAVEHAS
叶子结点分支结点指向记录的指针
typedef struct TrieNode {
NodeKind kind; // 结点类型
union {
struct { KeyType K; Record *infoptr } lf;
// 叶子结点 (关键字和指向记录的指针 )
struct { TrieNode *ptr[27]; int num } bh;
// 分支结点 (27个指向下一层结点的指针 )
}
} TrieNode,*TrieTree; // 键树类型结点结构的 C 语言描述在 Trie树中查找记录的过程假设,T 为指向 Trie 树根结点的指针，
K.ch[0..K.num-1] 为待查关键字 (给定值 )。
则查找过程中的基本操作为：
搜索和对应字母相应的指针,
若 p不空，且 p所指为分支结点，则 p=p->bh.Ptr[ord(K.Ch[i])];
( 其中,0≤i≤K.num-1 )
初始状态,p=T; i = 0;
若 ( p && p->kind == BRANCH && i<K.num)
则继续搜索下一层的结点
p=p->bh.ptr[ord(K.ch[i])]; i++;
其中,ord 为求字符在字母表中序号的函数若 ( p && p->kind==LEAF && p->lf.K==K)
则 查找成功,返回指向相应记录的指针 p->lf.infoptr
反之，即 ( !p || p->kind==LEAF && p->lf.K!=K )
则表明 查找不成功,返回空指针 ;
一,哈希表是什么？
二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希表的查找及分析
8.3 哈希表以上两节讨论的表示查找表的各种 结构 的共同 特点,
记录在表中的位臵和它的关键字之间不存在一个确定的关系 ;
一,哈希表是什么？
查找的过程 为 给定值 依次和关键字集合中各个 关键字 进行 比较 ;
查找的效率 取决于和给定值 进行比较 的关键字 个数 。
用这类方法表示的查找表,其平均查找长度都不为零不同的表示方法，其差别仅在于：
关键字和给定值进行比较的顺序不同。
对于频繁使用的查找表，希望 ASL = 0。
只有一个办法,预先知道所查关键字在表中的位置，即，要求：
记录在表中位置和其关键字之间存在一种确定的关系。
若 以下标为 000 ~ 999 的顺序表 表示之。
例如,为每年招收的 1000 名新生建立一张查找表,其关键字为学号,其值的范围为 xx000 ~ xx999 (前两位为年份 )。
则查找过程可以简单进行：取给定值 (学号 )的后三位,不需要经过比较便可直接从顺序表中找到待查关键字,
但是，对于 动态查找表 而言，
因此在一般情况下，需在关键字与记录在表中的存储位臵之间建立一个函数关系,以 f(key) 作为关键字为 key 的记录在表中的位臵,
通常 称 这个函数 f(key) 为哈希函数。
1) 表长不确定；
2) 在设计查找表时,只知道关键字所属范围,而知确切的关键字。
{ Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei }例如,对于如下关键字设 哈希函数 f(key) =?(Ord(第一个字母 ) -Ord('A')+1)/2? 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3
Chen ZhaoQian SunLi WuHan YeDei
问题,若添加关键字 Zhou,怎么办？ 能否找到另一个哈希函数？
1) 哈希 (Hash)函数是一个 映象,即,将关键字的集合映射到某个地址集合上,它的设臵很灵活，只要这个地址集合的大小不超出允许范围即可 ;
从这个例子可见，
2) 由于哈希函数是一个 压缩映象,因此，在一般情况下，很容易产生,冲突” 现象，即,key1? key2，而 f(key1) = f(key2)。
3) 很难 找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数，使冲突尽可能少地产生。
因此，在构造这种特殊的“查找表” 时，除了需要选择一个,好” (尽可能少产生冲 突 )的哈希函数之外 ;还需要找到 一种,处理冲突” 的方法 。
选取某个函数，依该函数按关键字计算元素的存储位臵，并按此存放； 查找时，由同一个函数 对给定值 k计算地址，将 k与地址单元中元素关键码进行比，
确定查找是否成功。
通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后,可能将不同的关键码映射到同一个哈希地址上,这种现象称为 冲突 。
若干术语哈希方法
(杂凑法 )
哈希函数
(杂凑函数 )
哈希表
(杂凑表 )
冲 突哈希方法中使用的转换函数称为 哈希函数 (杂凑函数 )
按上述思想构造的表称为 哈希表 (杂凑表 )
哈希表 ——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表
哈希查找 ——又叫散列查找，利用哈希函数进行查找的过程叫哈希查找例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族 …...
1 北京
2 上海
….
..
….
..
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数,H(Beijing)=2
H(Shanghai)=19
H(Shenyang)=19
哈希表,即散列存储结构。
散列法存储的基本思想,建立关键码字与其存储位臵的对应关系,
由关键码的值决定数据的存储地址。
优点,查找速度极快 (O(1)),查找效率与元素个数 n无关！
例 1,若将学生信息按如下方式存入计算机，如：
将 2001011810201的所有信息存入 V[01]单元；
将 2001011810202的所有信息存入 V[02]单元；
……
将 2001011810231的所有信息存入 V[31]单元。
欲查找学号为 2001011810216的信息，便可直接访问 V[16]！
哈希表的定义,
根据设定的 哈希函数 H(key)和所选中的 处理冲突的方法,将一组关键字 映象到 一个有限的、地址连续的地址集 (区间 )上，并以关键字在地址集中的 象 作为相应记录在表中的 存储位臵,如此构造所得的查找表称之为 哈希表 。
哈希查找
基本思想,在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，
一次存取就能得到所查元素的查找方法
定义
– 哈希函数 ——在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
哈希函数可写成,addr(ai)=H(ki)
– ai是表中的一个元素
– addr(ai)是 ai的存储地址
– ki是 ai的关键字关键字集合存储地址集合
hash
例,有数据元素序列 (14,23,39,9,25,11),若规定每个元素 k的存储地址 H(k)＝ k,请画出存储结构图 。 (注,H(k)＝ k称为散列函数 )
解,根据散列函数 H(k)＝ k,可知元素 14应当存入地址为 14的单元，元素 23应当存入地址为 23的单元,……,
对应散列存储表（哈希表）如下：
讨论,如何进行散列查找？
根据存储时用到的散列函数 H(k)表达式，迅即可查到结果！
例如，查找 key=9,则访问 H(9)=9号地址，若内容为 9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
地址 … 9 … 11 … 14 … 23 24 25 … 39 …
内容 14119 23 25 39
缺点：空间效率低！
有 6个元素的关键码分别为,(14,23,39,9,25,11） 。
选取关键码与元素位臵间的函数为 H(k) = k mod 7
通过哈希函数对 6个元素建立哈希表：
25
3923
9
14
冲突现象举例：
6个元素用 7个地址应该足够 !
H(14)=14%7=0 11 H(25)=25%7=4H(11)=11%7=4
有冲突！
0 1 2 3 4 5 6
所以,哈希方法必须解决以下两个问题：
1) 构造好的哈希函数
(a)所选函数尽可能简单，以便提高转换速度；
(b)所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。
2)制定一个好的解决冲突的方案查找时,如果从哈希函数计算出的地址中查不到关键码,则应当依据解决冲突的规则,有规律地查询其它相关单元 。
用哈希查找方法,冲突是不可能避免的,只能尽可能减少,
二,哈希函数的构造方法常用的哈希函数构造方法有：
1,直接定址法
2,除留余数法
3,乘余取整法
4,数字分析法
5,平方取中法
6,折叠法
7,随机数法要求一,n个数据原仅占用 n个地址，
虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
要求二,无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
Hash(key) = a·key + b (a,b为常数 )
优点,以关键码 key的某个线性函数值为哈希地址,不会产生冲突,
缺点,要占用连续地址空间，空间效率低。
例,关键码集合为 {100,300,500,700,800,900}，
选取哈希函数为 Hash(key)=key/100，
则存储结构 （ 哈希表 ） 如下：
0 1 2 3 4 5 6 7 8 9
900800700500300100
1、直接定址法
Hash(key)=key mod p (p是一个整数 )
特点,以关键码除以 p的余数作为哈希地址。
关键,如何选取合适的 p？
技巧,若设计的哈希表长为 m，则一般取 p≤m且为 质数
（也可以是不包含小于 20质因子的合数）。
2、除留余数法
Hash(key)=? B*( A*key mod 1 )? (A,B均为常数,且 0<A<1,B为整数 )
特点,以关键码 key乘以 A,取其小数部分,然后再放大 B倍并 取整,作为哈希地址 。
3、乘余取整法例,欲以学号最后两位作为地址，则哈希函数应为：
H(k)=100*(0.01*k % 1 )
其实也可以用法 2实现,H(k)=k % 100
4、数字分析法特点,某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。
3 4 7 0 5 2 4
3 4 9 1 4 8 7
3 4 8 2 6 9 6
3 4 8 5 2 7 0
3 4 8 6 3 0 5
3 4 9 8 0 5 8
3 4 7 9 6 7 1
3 4 7 3 9 1 9
例,有一组（例如 80个）关键码，其样式如下：
讨论：
① 第 1,2位均是,3和 4”,第 3位也只有,7,8,9”,因此,这几位不能用,余下四位分布较均匀,可作为哈希地址选用。
位号：①②③ ④⑤⑥⑦
② 若哈希地址取两位 (因元素仅 80个 ),则可取这四位中的任意两位组合成哈希地址,也可以取其中两位与其它两位叠加求和后,取低两位作哈希地址。
(A*key mod 1)
就是取 A*key 的小数部分特点,对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。
理由,因为中间几位与数据的每一位都相关。
例,2589的平方值为 6702921，可以取中间的 029为地址。
6、折叠法特点,将关键码自左到右分成位数相等的几部分 (最后一部分位数可以短些 ),然后将这几部分叠加求和,并按哈希表表长,
取后几位作为哈希地址 。
适用于,每一位上各符号出现概率大致相同的情况 。
法 1,移位法 ──将各部分的最后一位对齐相加 。
法 2,间界叠加法 ──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。
例,元素 42751896,用 法 1,427＋ 518＋ 96=1041
用 法 2,427 518 96—> 724+518+69 =1311
5、平方取中法
7、随机数法
Hash(key) = random ( key ) (random为伪随机函数 )
适用于,关键字长度不等的情况。造表和查找都很方便。
① 执行速度 (即计算哈希函数所需时间 )；
② 关键字的长度；
③ 哈希表的大小；
④ 关键字的分布情况；
⑤ 查找频率。
小结：构造哈希函数的原则：
实际造表时,采用何种 构造哈希函数的 方法 取决于建表的关键字集合的情况 (包括关键字的范围和形态 )，总 的原则是使产生冲突的可能性降到尽可能地小 。
三、处理冲突的方法处理冲突 的实际含义是：
为产生冲突的地址 寻找下一个 哈希地址常见的冲突处理方法有：
1.开放定址法（开地址法）
2.链地址法（拉链法）
3.再哈希法（双哈希函数法）
4.建立一个公共溢出区为产生冲突的地址 H(key) 求得一个 地址序列,
H0,H1,H2,…,Hs 1≤ s≤m-1
其中,H0 = H(key)
Hi = (H(key)+di) MOD m i=1,2,…,s
1,开放定址法对增量 di 有三种取法：
1) 线性探测再散列,di = c? i 最简单的情况 c=1
2) 平方探测再散列,di = 12,-12,22,-22,…,
3) 随机探测再散列,di 是一组伪随机数列或者 di=i× H2(key)
(又称双散列函数探测 )
即：产生的 Hi 均不相同，且所产生的
s(m-1)个 Hi 值能 覆盖 哈希表中所有地址。则要求：
注意,增量 di 应具有,完备性,
※ 随机探测时的 m 和 di 没有公因子。
※ 平方探测时的表长 m 必为形如 4j+3
的素数（如,7,11,19,23,… 等）；
例如,关键字集合
{ 19,01,23,14,55,68,11,82,36 }
设定 哈希函数 H(key) = key MOD 11 ( 表长 =11 )
0 1 2 3 4 5 6 7 8 9 1 0
0 1 2 3 4 5 6 7 8 9 1 0
1901 23 1455 68
1901 23 14 68
若采用 线性探测再散列 处理冲突若采用 二次探测再散列 处理冲突
11 82 36
55 118236
1 1 2 1 3 6 2 5 1
例 表长为 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
例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：
H(key)=key MOD 13,哈希表长为 m=16,设每个记录的查找概率相等
(1) 用线性探测再散列处理冲突，即 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
线性探测法的优点,只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；
线性探测法的缺点,可能使第 i个哈希地址的同义词存入第 i+1个哈希地址，这样本应存入第 i+1个哈希地址的元素变成了第 i+2个哈希地址的同义词,……,
因此，可能出现很多元素在相邻的哈希地址上,堆积,起来，大大降低了查找效率。
解决方案,可采用 二次探测法 或 伪随机探测法,以改善
,堆积,问题。
讨论
2、链地址法 (拉链法）
基本思想,将具有相同哈希地址的记录链成一个单链表,m个哈希地址就设 m个单链表,然后用一个数组将 m个单链表的表头指针存储起来，形成一个动态的结构。
设 { 47,7,29,11,16,92,22,8,
3,50,37,89 }的哈希函数为：
Hash(key)=key mod 11，
用 拉链法 处理冲突,则建表如右图所示 。
例,0
1
2
3
4
5
6
7
8
9
10
22 11
89
3 47
37 92
29 7
16
50
8
10
注,有冲突的元素可以插在表尾,
也可以插在表头
Hi=Rhi(key) i=1,2,…,k
Rhi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。
优点,不易产生聚集；
缺点,增加了计算时间。
4,建立一个公共溢出区思路,除设立哈希基本表外,另设立一个溢出向量表 。
所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。
3、再哈希法
– 方法,构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即,Hi=Rhi(key) i=1,2,……k
– 其中,Rhi—— 不同的哈希函数例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
0
1
2
3
4
5
6
7
8
9
10
11
12
ASL=(1*6+2*4+3+4)/12=1.75
将所有哈希地址相同的记录都链接在同一链表中。
链地址法
0
1
2
3
4
5
6
11
19 8268
55
14
36?01
23
ASL=(6× 1+2× 2+3)/9=13/9
例如,同前例的关键字，哈希函数为
H(key)=key MOD 7
查找过程和造表过程一致。假设采用开放定址处理冲突，则 查找过程 为,
四、哈希表上的操作算法对于 给定值 K,计算 哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功若 r[i].key = K 则查找成功否则 求下一地址 Hi,直至
r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
int hashsize[] = { 997,..,};
typedef struct {
ElemType *elem;
int count; // 当前数据元素个数
int sizeindex;
// hashsize[sizeindex]为当前容量
} HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
//--- 开放定址哈希表 的存储结构 ---
Status SearchHash (HashTable H,KeyType K,
int &p,int &c) {
// 在开放定址哈希表 H中查找关键码为 K的记录
} // SearchHash
p = Hash(K); // 求得哈希地址
while ( H.elem[p].key != NULLKEY &&
!EQ(K,H.elem[p].key)）
collision(p,++c); // 求得下一探查地址 p
if (EQ(K,H.elem[p].key)) return SUCCESS;
// 查找成功,返回待查数据元素位臵 p
else return UNSUCCESS; // 查找不成功
Status InsertHash (HashTable &H,Elemtype e){
} // InsertHash
c = 0;
if ( HashSearch ( H,e.key,p,c ) == SUCCESS )
return DUPLICATE;
// 表中已有与 e 有相同关键字的元素
else
H.elem[p] = e; ++H.count; return OK;
// 查找不成功时，返回 p为插入位臵
else RecreateHashTable(H); // 重建哈希表
if ( c < hashsize[H.sizeindex]/2 ) {
// 冲突次数 c 未达到上限，（阀值 c 可调）
}
1) 选用的 哈希函数 ;
2) 选用的 处理冲突的方法 ;
3) 哈希表饱和的程度,装载因子
α =n/m 值的 大小 （ n—记录数,m—表的长度）
决定哈希表查找的 ASL的因素,
哈希表查找的分析从查找过程得知，哈希表查找的平均查找长度 实际上并不等于零 。
一般情况下，可以认为选用的哈希函数是均匀的，
则在讨论 ASL时，可以不考虑它的因素。
因此,哈希表的 ASL是 处理冲突方法 和 装载因子的函数。
例如：前述例子线性探测处理冲突时,ASL =
双散列探测处理冲突时,ASL =
链地址法处理冲突时,ASL =
22/9
14/9
13/9
线性探测再散列链地址法随机探测再散列
)
1
11(
2
1
nlS
)1ln (1?
nrS
2
1ncS
可以证明,查找成功 时有下列结果：
从以上结果可见，哈希表的平均查找长度是?
的函数,而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子
,使得 平均查找长度限定在某个范围内 。
讨论
2）,冲突,是不是特别讨厌？
答,不一定！正因为有冲突，使得文件加密后无法破译
（不可逆，是单向散列函数，可用于数字签名）。
利用了哈希表性质,源文件稍稍改动，会导致哈希表变动很大。
随机探测法）
线性探测法拉链法）
()1l n (
1
)()
1
1
1(
2
1
(
2
1
A S L
A S L
A S L
1） 散列存储的查找效率到底是多少？
答,ASL与装填因子?有关！既不是严格的 O(1)，也不是
O(n)
应尽量选择一个合适的?，以降低 ASL
的长度
序表和有序表的查找方法及其平均查找长度的计算方法。
静态查找树的构造方法和查找方法及其和有序表的差别。
熟练掌握二叉排序树的构造和查找方法。
熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
小结
8.1 静态查找表
8.2 动态查找树表
8.3 哈希表学习提要
熟练掌握顺序表和有序表的查找方法。
熟练掌握二叉排序树的构造和查找方法。
掌握二叉平衡树的维护平衡方法。
理解 B-树的特点以及它们的建树过程。
熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
何谓查找表？
查找表是由同一类型的数据元素 (或记录 )构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。
对查找表经常进行的 操作,
1)查询 某个,特定的,数据元素是否在查找表中；
2)检索 某个,特定的,数据元素的各种属性；
3)在查找表中 插入 一个数据元素；
4)从查找表中 删去 某个数据元素 。
仅作 查询 和 检索 操作的查找表。静态查找表在查询之后，还需要将“查询”结果为
,不在查找表中,的数据元素 插入到 查找表中；或者，从查找表中 删除 其“查询”
结果为,在查找表中,的数据元素。
动态查找表查找表分类是数据元素 (或记录 )中某个 数据项 的值，
用以 标识 (识别 )一个数据元素 (或记录 )。
关键字若此关键字识别 唯一的 一个记录,则称之谓,主关键字,,若此关键字能识别 若干 记录，则称之谓,次关键字,。
根据给定的某个值，在查找表中 确定一个其关键字等于给定值的数据元素或（记录）
查找若查找表中存在这样一个记录,则称 查找成功,查找结果,
给出整个记录的信息,或指示该记录在查找表中的位臵 ;
否则称 查找不成功,查找结果,给出 空记录 或 空指针 。
由于查找表中的数据元素之间不存在明显的组织规律，
因此 不便于查找 。为了提高查找的效率,需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，
用另外一种结构来表示查找表。
如何进行查找？ 查找的方法取决于查找表的结构。
查找表 (Search Table),是一种以集合为逻辑结构,
以查找为核心运算 的数据结构 。
静态查找表,只对查找表进行 查询 某个特定的数据元素或某个特定数据元素的各种属性的操作 。
如：查询成绩表中是否有某学生或该学生某门课程的成绩 。
动态查找表,对查找表进行插入或删除某个数据元素的操作 。 如：修改某个学生某门课程的成绩 。
衡量查找算法的标准：
(1)平均查找长度；
(2)算法所需要的存储量和算法的复杂性等 。
平均查找长度定义,为确定记录在表中的位臵，需和给定值进行比较的关键字的个数的期望值叫查找算法在查找成功时的 平均查找长度 。
n
个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：
个记录的表，对含有
ic
pip
cpASLn
i
n
i
ii
i
ii
1
1
1 =
=
=
=
物理意义,假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为 ASL。
显然,ASL值越小，时间效率越高。
构造一个含 n 个数据元素的静态查找表 ST。
Create(&ST,n);
操作结果：
基本操作销毁表 ST。
Destroy(&ST);
初始条件：
操作结果：
静态查找表 ST存在；
若 ST 中存在其关键字等于 kval 的数据元素，则函数值为该元素的值或在表中的位臵，否则为“空”。
Search(ST,kval);
初始条件：
操作结果：
静态查找表 ST存在,kval 为和查找表中元素的关键字类型相同的给定值；
按某种次序对 ST的每个元素调用函数 Visit()一次且仅一次，一旦 Visit()失败，则操作失败。
Traverse(ST,Visit());
初始条件：
操作结果：
静态查找表 ST存在,Visit是对元素操作的应用函数；
一、顺序查找（ Linear search，又称线性查找 ）
顺序表的机内存储结构：
typedef struct {
ElemType *elem; //表基址,0号单元留空
int length; //表长
} SSTable;
顺序查找,用逐一比较的办法顺序查找关键字。
对 顺序结构 如何线性查找？
对 单链表结构 如何线性查找？
对 非线性树结构 如何顺序查找? 借助各种遍历操作！
8.1 静态查找表
typedef struct {
keyType key; // 关键字域
… … // 其它属性域
} ElemType ;
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
回顾顺序表的查找过程：
假设给定值 e = 64,
要求 ST.elem[i] = e,问,i =?
i i
66
i
以顺序表或线性链表表示静态查找表一、顺序查找表顺序查找查找过程,从表的一端开始逐个进行记录的关键字和给定值的比较算法描述
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
比较次数 =5比较次数：
查找第 n个元素,1
查找第 n-1个元素,2
……….
查找第 1个元素,n
查找第 i个元素,n+1-i
查找失败,n+1
算法的实现技巧,把待查关键字 key存入表头或表尾（俗称,哨兵,），这样可以加快执行速度。
例,若将待查找的特定值 key存入 顺序表的 首部 (如 0号单元 ),则顺序查找的实现方案为,从后向前 逐个比较！
int Search_Seq( SSTable ST,KeyType key ) {
//在顺序表 ST中，查找关键字与 key相同的元素；若成功，返回其位臵信息，否则返回 0
ST.elem[0].key =key; //设立哨兵，可免去查找过程中每一步都要检测是否查找完毕。当 n>1000时，查找时间将减少一半。
for( i=ST.length; ST.elem[ i ].key!=key; --i );
//不要用 for(i=n; i>0; - -i) 或 for(i=1; i<=n; i++)
return i; //若到达 0号单元才结束循环，说明不成功，返回 0值
(i=0)。成功时则返回找到的那个元素的位臵 i。
}
int location( SqList L,ElemType& e,
Status (*compare)(ElemType,ElemType)) {
i = 1;
p = L.elem;
while ( i<=L.length &&
!(*compare)(*p++,e))) i++;
if ( i<= L.length) return i;
else return 0;
} //location
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
i
21 37 88 19 92 05 64 56 80 75 13
0 1 2 3 4 5 6 7 8 9 10 1 1
S T,L engt h
ST.elem
i
60
i
kval = 64
kval = 60
i
64
分析顺序查找的时间性能定义,查找算法的 平均查找长度 (Average Search Length)
为确定记录在查找表中的位臵，需和给定值 进行比较的关键字个数的期望值
=
=
n
i
iiCPA S L
1其中,n 为表长,P
i 为查找表中第 i个记录的概率，且
Ci为找到该记录时，曾 和给定值比较过的关键字的个数
1
1
=?
=
n
i
iP
顺序表查找的平均查找长度 为：
对 顺序表 而言,Ci = n-i+1
2
111
1
==?
=
n)i(n
nA S L
n
i
ss
ASL = nP1 +(n-1)P2 + +2Pn-1+Pn
nPi
1=在 等概率 查找的情况下，
若查找概率无法事先测定，则查找过程采取的改进办法是,在每次查找之后,将刚刚查找到的记录直接移至表尾的位臵上 。
在 不等概率查找 情况下,ASLss在 Pn≥Pn-1≥···≥P2≥P1 时 取极小值
—— 返回特殊标志，例如返回空记录或空指针。前例中设立了,哨兵,,
就是将关键字送入末地址 ST.elem[0].key使之结束并返回 i=0。
讨论① 查不到怎么办？
讨论③ 如何计算 ASL？
分析：
查找第 1个元素所需的比较次数为 1；
查找第 2个元素所需的比较次数为 2；
……
查找第 n个元素所需的比较次数为 n；
总计全部比较次数为,1＋ 2＋ … ＋ n = (1+n)n/2
未考虑查找不成功的情况：查找哨兵所需的比较次数为 n+1
这是查找成功的情况若求某一个元素的平均查找次数，还应当除以 n(等概率 ),
即,ASL＝ (1＋ n)/2,时间效率为 O(n)
优点,算法简单，且对顺序结构或链表结构均适用。
缺点,ASL 太长，时间效率太低。
讨论④ 顺序查找的特点：
讨论② 查找效率怎样计算？ 用平均查找长度 ASL衡量。
问题,顺序查找表的查找算法简单,但平均查找长度较大,特别不适用于 表长较大 的查找表。
二、有序查找表办法,若以 有序表 表示静态查找表，则查找过程可以基于 折半 进行,
查找过程,每次将待查记录所在区间缩小一半
适用条件,采用顺序存储结构的有序表
算法实现
– 设表长为 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时，查找失败
low highmid
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
找 21
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
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
low highmid
找 70
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 high
mid
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
lowhigh
11852
10741
93
6判定树：
1 2 3 4 5 6 7 8 9 10 11
5 13 19 21 37 56 64 75 80 88 92
05 13 19 21 37 56 64 75 80 88 92
0 1 2 3 4 5 6 7 8 9 1 0 1 1
ST.elem
ST.length
例如,key = 64 的查找过程如下
low high
mid
low
mid
high
mid
low 指示查找区间的下界 ;
high 指示查找区间的上界 ;
mid = (low+high)/2。
② 运算步骤,
(1) low =1,high =11,mid =6,待查范围是 [1,11]；
(2) 若 ST.elem[mid].key < key，说明 key?[ mid+1,high],
则令,low =mid+1;重算 mid＝?(low+high)/2?；,
(3) 若 ST.elem[mid].key > key，说明 key?[low,mid-1]，
则令,high =mid–1;重算 mid ；
(4)若 ST.elem[ mid ].key = key，说明查找成功，元素序号 =mid;
结束条件,(1) 查找成功,ST.elem[mid].key = key
(2) 查找不成功,high≤low（意即区间长度小于 0）
解,① 先设定 3个辅助标志,low,high,mid，
折半查找举例：
Low指向待查元素所在区间的下界 high指向待查元素所在区间的上界
mid指向待查元素所在区间的中间位臵已知如下 11个元素的 有序表,
（ 05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为 21
和 85的数据元素。
显然有,mid=?(low+high)/2?
int Search_Bin ( SSTable ST,KeyType kval ) {
low = 1; high = ST.length; // 臵区间初值
while (low <= high) {
mid = (low + high) / 2;
if （ kval == ST.elem[mid].key )
return mid; // 找到待查元素
else if ( kval < ST.elem[mid].key) )
high = mid - 1; // 继续在前半区间进行查找
else low = mid + 1; // 继续在后半区间进行查找
}
return 0; // 顺序表中不存在待查元素
} // Search_Bin
全部比较总次数为 1× 20＋ 2× 21＋ 3× 22＋ 4× 23… ＋ m× 2m— 1
＝?
=
m
j
jj
1
12
讨论① 若关键字不在表中，怎样得知和停止？
—— 典型标志是：当查找范围的上界 ≤下界时停止查找 。
讨论② 二分查找的效率（ ASL）
1次比较就查找成功的元素有 1个 (20),即中间值；
2次比较就查找成功的元素有 2个 (21),即 1/4处（或 3/4）处；
3次比较就查找成功的元素有 4个 (22),即 1/8处（或 3/8）处 …
4次比较就查找成功的元素有 8个 (23),即 1/16处（或 3/16）处 …
……
则第 m次比较时查找成功的元素会有 (2m-1)个 ；
为方便起见，假设表中全部 n个元素＝ 2m-1个,此时就不讨论第 m
次比较后还有剩余元素的情况了。
推导过程性能分析以 11个数的查找为例：
5 13 19 21 37 56 64 75 80 88 92
1 2 3 4 5 6 7 8 9 10 11
找到第 6个数仅需比较 1次,
找到第 3和第 9个数需 2次,
找到第 1,4,7,10个数需 3次，
找到第 2,5,8和 11个数需 4次。
6
3 9
1 4 7 10
2 5 8 11
性能分析
查找成功时进行比较的次数最多不超过该树的深度。
具有 n个结点的判定树的深度为?log2n?。
折半查找法在查找成功时比较次数最多 为?log2n?+1次。
查找不成功的情况如下所示 (方框表示查找不成功的情况 )
6
3 9
1 4 7 10
2 5 8 11-1 3-4 6-7 9-10
1-2 3-4 4-5 5-6 7-8 8-9 10-11 11-
查找不成功时的最多比较次数也是?log2n?+1。
查找某个结点的过程就是从根结点到相应的结点的路径。查找过程用二叉树来表示查找某个结点所比较的次数等于该结点的层次数加 1。
先看一个具体的情况，假设,n=11
折半查找的平均查找长度
6
3 9
1 4
2 5
7
8
10
11
判定树
i 1 2 3 4 5 6 7 8 9 10 11
C i
12 23 3 3 34 4 4 4
假设 n=2h-1 并且查找概率相等则一般情况下，表长为 n的折半查找的判定树的深度和含有 n个结点的完全二叉树的深度相同。
1)1(lo g1211 2
1
1
1
=?
==
=
=
n
n
nj
n
C
n
A S L
h
j
j
n
i
ibs
1)1(l o g 2 nA S L bs在 n>50 时,可得近似结果优点,比较次数少，检索速度快,
缺点,字典按关键码排序,只适用于顺序存储结构,
三、分块查找（索引顺序查找）
这是一种顺序查找的另一种改进方法 。
1,先让数据 分块有序,即分成若干子表，要求每个子表中的数值 (用关键字更准确 )都比后一块中数值小 (但子表内部未必有序 )。
2,然后将各子表中的最大关键字构成一个 索引表,表中还要包含每个子表的起始地址 (即头指针 )。
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
第 3块例：
22 48 86
1 7 13
特点：块间有序，块内无序索引表最大关键字起始地址第 1块 第 2块索引顺序表在建立顺序表的同时，建立一个索引。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 ……
17 08 21 19 14 31 33 22 25 40 52 61 78 46 ……
21 0 40 5 78 10 ……
例如：
索引顺序表 = 索引 + 顺序表顺序表索引分块查找分块查找
– 查找过程,将表分成几块，块内无序，块间有序；
先确定待查记录所在块，再在块内查找
– 适用条件,分块有序表
– 算法实现
用数组存放待查记录,每个数据元素至少含有关键字域
建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针
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
查找步骤 分两步进行：
① 对索引表使用折半查找法（因为索引表是有序表）；
② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
查找效率,ASL=Lb+Lw
对索引表查找的 ASL 对块内查找的 ASL
)2 1( lo g2)1(lo g 22 nA S LnssnA S L bsbs
S为每块内部的记录个数,n/s即块的数目例如当 n=9,s=3时,ASLbs=3.5,而折半法为 3.1,顺序法为 5
typedef struct {
KeyType maxkey;
int stadr;
} indexItem; //索引项
typedef struct {
indexItem *elem;
int stadr;
} indexTable; //索引表索引顺序表的查找过程：
1）由索引确定记录所在区间；
2）在顺序表的某个区间内进行查找。
索引顺序查找 的过程也是一个,缩小区间” 的查找过程。
对比顺序表和有序表的查找性能顺序表 有序表表的特性 无序 有序存储结构 顺序 或 链式 顺序插删操作 易于进行 需移动元素
ASL的值 大 小
int Search_Idx ( SSTable ST,indexTable ID,KeyType kval )
{ low = 0; high = ID.length-1; found = FALSE;
if ( kval>ID.elem[high].key ) return 0;
while ( low <=high && !found ) {
mid = (low+high)/2;
if ( kval < ID.elem[mid].key ) high = mid - 1;
else if ( kval > ID.elem[mid].key ) low = mid +1;
else { found = TRUE; low = mid; }
}
s = ID.elem[low].stadr;
if ( low < ID.length-1 ) t = ID.elem[low +1].stadr-1; else t = ST.length;
if ( ST.elem[t].key== kval ) return t;
else {
ST.elem[0] = ST.elem[t]; // 暂存 ST.elem[t]
ST.elem[t].key = kval; // 设置监视哨
for ( k=s; ST.elem[k].key !=kval; k++ ) ;
ST.elem[t] = ST.elem[0]; // 恢复暂存值
if ( k != t ) return k; else return 0;
}
}
22
1 7 13
48 86
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53
索引表最大关键字起始地址索引顺序法查找方法,分块查找,是顺序查找的一个改进方法。
在此查找法中，除顺序表外还有一个索引表。
整个表分成三个子表，对每个子表建立一个索引项，索引项包括两项内容：
关键字项 (其值为该子表内的最大关键字 )
指针项 (指示该子表的第一个记录在表中的位臵 )。
索引表按关键字有序,表或者有序或者分块有序。分块有序指的是后一个子表中所有记录的关键字均大于前一个子表中的最大关键字。
分块查找需分两步进行：
(1) 现确定待查记录所在的块 (子表 )
(2) 然后在块中顺序查找。
分块查找的平均查找长度为,ASL ＝ Lb + Lw
将长度为 n的表均匀地分成 b块,每块含有 s个记录,即 b=?n/s?;
假定表中每个记录的查找概率相等，则每块查找的概率为 1/b,
块中每个记录的查找概率为 1/s。
若用顺序查找确定所在块,则
ASL = Lb + Lw = (b+1)/2 + (s+1)/2 = n/(2s) + s/2 +1
2
)1(lo g 2 s
s
nA S L
bs
：用折半查找确定所在块索引顺序查找的平均查找长度 =
查找 索引 的平均查找长度 + 查找 顺序表 的平均查找长度注意：索引可以根据查找表的特点来构造。
综合上一节讨论的几种查找表的特性：
查找 插入 删除无序顺序表无序线性链表有序顺序表有序线性链表静态查找树表
(n)
(1)
(n)
(1)
(nlogn)
(n)
(n)
(logn)
(n)
(logn)
(1)
(1)
(n)
(1)
(nlogn)
可得如下结论：
1) 从 查找 性能看,最好情况能达?(logn),此时要求表 有序 ；
2) 从 插入 和 删除 的性能看,最好情况能达?(1),此时要求存储结构是链表 。
ASL 最大 最小 两者之间表结构 有序表、无序表 有序表 分块有序表存储结构顺序存储结构线性链表顺序存储结构顺序存储结构线性链表查找方法比较顺序查找 折半查找 分块查找
8.2 动态查找树表一、二叉排序树（二叉查找树）
二、键树基本操作 P操作结果,构造一个空的动态查找表 DT。InitDSTable(&DT);
销毁动态查找表 DT。
DestroyDSTable(&DT);
初始条件：
操作结果：
动态查找表 DT存在；
若 DT中存在其关键字等于 kval的数据元素,则函数值为该元素的值或在表中的位臵,否则为“空”,
SearchDSTable(DT,kval);
初始条件：
操作结果：
动态查找表 DT 存在,kval为和关键字类型相同的给定值 ;
动态查找表 DT 存在,e 为待插入的数据元素；
InsertDSTable(&DT,e);
初始条件：
操作结果,若 DT中不存在关键字等于 e.key的元素,则插入 e 到 DT。
动态查找表 DT存在,kval为和关键字类型相同的给定值 ;
DeleteDSTable(&T,kval);
初始条件：
操作结果,若 DT中存在其关键字等于 kval的数据元素,则删除之。
动态查找表 DT存在,Visit是对结点操作的应用函数；
TraverseDSTable(DT,Visit());
初始条件：
操作结果,按某种次序对 DT的每个结点调用函数 Visit() 一次且至多一次。一旦 Visit() 失败，则操作失败。
二叉排序树 (Binary Sort Tree)或者是一棵空二叉树；或者具有下列性质的二叉树：
A,若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
B,若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
C,它的左右子树也分别为二叉排序树。
8.2.1 二叉排序树实际上，折半查找法的判定树就是一棵二叉排序树。
中序遍历可以得到一个关键字的有序序列 (怎么证明?)，一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列。 二叉排序树既有折半查找的特性，又采用了链表作存储结构。因此是动态查找表的适宜结构。
1、二叉排序树定义
50
30 80
20 90
10 85
40
3525
23 88
例如,
是二叉排序树。
66
不
struct BinTreeNode;
typedef struct BinTreeNode * pBinTreeNode;
struct BinTreeNode
{ KeyType key; /* 结点的关键码字段 */
DataType other; /* 结点的属性字段 */
PBinTreeNode llink,rlink;
/* 二叉树的左、右指针 */
};
typedef struct BinTreeNode * BinTree;
typedef BinTree *PBinTree;
二叉排序树的存储结构
K= { 18,73,10,05,68,99,27,41,51,32,25 }
18
10 73
9968
27
25 41
32 51
05
二叉排序树示例
45
24 53
12 90
如果待 查找的关键字序列输入顺序为,(24,53,45,45,12,24,90)
24
53
45
12
90
查找成功，
返回查找成功，
返回讨论 1：二叉排序树的插入和查找操作则生成二叉排序树的过程为：
例,输入待查找的关键字序列 =（ 45,24,53,45,12,24,90）
则生成的二叉排序树形态不同：
查找成功，
返回查找成功，
返回
2．二叉排序树的查找算法
1）若给定值 等于 根结点的关键字,则查找成功；
2）若给定值 小于 根结点的关键字,则继续在左子树上进行查找；
3）若给定值 大于 根结点的关键字,则继续在右子树上进行查找。
否则若二叉排序树 为空,则查找不成功；
例如,二叉排序树 查找关键字 == 50,35,90,95
50
30 80
20 90
85
40
35
8832
L.key<T.key<R.key
while （ T非空）
{
if (T.key==key)
查到；
else if (T.key>key)
查左子树；
else 查右子树；
}
二叉排序树的检索算法
T
L R
查找步骤,若根结点的关键字值等于查找的关键字,成功。否则,若小于根结点的关键字值,查其左子树。大于根结点的关键字值,查其右子树。在左右子树上的操作类似。
122
250
300110 200
99
105 230
216
BiTree SearchBST ( BiTree T,KeyType key )
{ if ( ( !T) || key==T->data,key ) return ( T ) ;
else if ( key<T->data,key ) return (SearchBST ( T->lchild,key ));
else return ( SearchBST ( T->rchild,key ));
}
typedef float keyType;
typedef int keyType;
typedef struct { keyType key; …… } ElemType;
typedef struct BiTNode {
ElemType data;
struct BiTNode * lchild,*rchild;
} BiTNode; *BiTree;
if ( !T ) { p = f; return FALSE; }
else if ( kval == T->data.key ) { p = T; return TRUE; }
else if ( kval < T->data.key )
return SearchBST (T->lchild,kval,T,p );
else
return SearchBST (T->rchild,kval,T,p );
f T设 key = 48 f
Tf
T
22
p
f
T f
T
T
T
T
f
f
fp
30
20
10
40
3525
23
1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。
比较的关键字次数＝ 此结点的层次数 ;
最多的比较次数＝ 树的深度（或高度），即?log2 n?+1
2) 一棵二叉排序树的平均查找长度为：
二叉排序树的查找分析其中：
ni 是每层结点个数；
Ci 是结点所在层次数；
m 为树深。
最坏情况,即插入的 n个元素从一开始就有序，
—— 变成单支树的形态！
此时树的深度为 n ; ASL= (n+1)/2
此时查找效率与顺序查找情况相同。
=
=
m
i
ii CnnA S L
1
1
最好情况,即：与折半查找中的判定树相同（形态比较均衡）
对有 n 个关键字的二叉排序树的平均查找长度,设每种树态出现概率相 同,查找每个关键字也是等概率的。则 ASL求解过程可推导。
树的深度为,?log 2n? +1 ；
ASL=log 2(n+1) –1 ；与折半查找相同。
结论：二叉排序树的 ASL≤2(1+1/n)*ln(n)
最坏情况,即插入的 n个元素从一开始就有序。（ 单支树）
此时树深为 n ; ASL= (n+1)/2 ; 与顺序查找情况相同。
最好情况,即：与折半查找中的判定树相同 （形态均衡）
此时树深为,?log 2n? +1 ；
ASL=log 2(n+1) –1 ；与折半查找情况相同。
一般情况,（与 log n 同阶）
问题：如何提高二叉排序树的查找效率？
尽量让二叉树的形状均衡
nnA S L ln)11(2
平衡二叉树
根据动态查找表的定义,插入 操作在 查找不成功 时才进行 ;
3．二叉排序树的插入算法
若二叉排序树为空树，则新插入的结点为 新的根结点 ；
否则，新插入的结点必为一个 新的叶子结点,其插入位臵由查找过程得到。
注,若 数据元素的 输入顺序不同，则得到的二叉排序树形态也不同！
—— 这种既查找又插入的过程称为 动态查找 。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。
二叉排序树的插入
– 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
– 示例：从空树出发，待插的关键字序列为 33,44,23,46,12,37
33
4423
4612 37
中序遍历二叉排序树可得到一个关键字的有序序列。
该例中，中序遍历结果为,12,23,33,37,44,46
若从空树出发，经过一系列插入操作后，可生成一棵二叉排序树。
18
7310
05 68 99
27
41
5132
25
二叉排序树的生成过程示例例如,K = { 18,73,10,05,68,99,27,41,51,32,25 }
当树中不存在关键字等于给定值的结点时，需要生成新结点并插入到二叉树中。而新插入的结点必定是一个叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
算法,if ( 二叉排序树中查不到该结点 )
{ 建立新结点；
if (原二叉排序树是空树 )
新结点作为根结点 ;
else if (新结点 <父结点 )
插入左子树；
else 插入右子树；
}
二叉排序树中插入结点的算法
BSTSEARCH(K,t) //K为待查关键字,t为根结点指针
p=t; //p为查找过程中进行扫描的指针
while(p!=NULL){
case {
K=data(p),{查找成功,return }
K<data(p),{q=p； p=L_child(p) } //继续向左搜索
K>data(p),{q=p； p=R_child(p) } //继续向右搜索
}
}
Get(s); data(s)=K; L_child(s)=NULL; R_child(s)=NULL;
//查找不成功，生成一个新结点 s，插入到二叉排序树中
case {
t=NULL,p=s; //若 t为空，则插入的结点 s作为根结点
K<data(q),L_child(q)=s;
K>data(q),R_child(q)=s;
}
return OK
}
bool SearchBST ( BiTree T,KeyType key,BiTree f,BiTree &p )
{ if ( ( !T) { p = f; return FALSE; }
else if ( key==T ->data,key) { p = T; return TRUE; }
else if ( key<T->data,Key ) return ( SearchBST(T->lchild,key,T,p));
else return ( SearchBST(T->rchild,key,T,p) );
} // SearchBST
122
250
300110
99
T
p
f = nullf,T 的父亲结点
p,指向最后一个结点,TRUE 找到； FALSE 叶子的父亲结点。
如：插入 280 的过程。
280
r ( r,val,BiTree f,Bi ree &f
{ p = T;
while( p） {
if ( kval==p->data,Key ) return TRUE;
else if ( kval<p->data,Key ) { f = p; p = p->lchild; }
else { f = p; p = p->rchild; }
}
return FALSE;
} // SearchBST
bool Inset BST ( BiTree &T,ElemType e )
{
f = NULL;
if ( ! SearchBST ( T,e.key,NULL,p,f ) ） return FALSE;
else {
s = new BitNode;
s->data = e; s->lchild = s->rchild = NULL;
if ( ! f ) T = s;
else if ( e.key < f->data.key ) { f->lchild = s; else f->rchild = s; }
return TRUE;
}
} // Insert BST
122
250
300110
99
T
f
280
f = null
（ 1）被删除的结点 是叶子 ；
（ 2）被删除的结点 只有左子树 或者 只有右子树 ；
（ 3）被删除的结点 既有左子树，也有右子树 。
4．二叉排序树的删除算法可分 三种情况 讨论：
和插入相反，删除在 查找成功 之后进行，并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性 。
50
30 80
20 90
85
40
35
8832
（ 1）被删除的结点是 叶子结点例如,被删关键字 = 2088
其双亲结点中相应指针域的值改为“空”
50
30 80
20 90
85
40
35
8832
（ 2）被删除的结点 只有左子树或者 只有右子树其双亲结点的相应指针域的值改为
“指向被删除结点的左子树或右子树”。
被删关键字 = 4080
50
30 80
20 90
85
40
35
8832
（ 3）被删除的结点 既有左子树，也有右子树
40
以其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 50
二叉排序树的删除假设被删结点为 *p，其双亲结点为 *f，
– *p为叶子结点：删去 *p，并修改 *f 的孩子域。
– *p只有左子树 PL或只有右子树 PR：令 PL或 PR直接成为 *f 的子树
33
4423
4612 37
33
4423
4612
45
46
45
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空
33
4423
4612 37
40 50
48
35
38
46
50
48
33
23
12
37
4035
38
方法 1,PL 接替 *p成为 *f 的子树,PR成为 PL最右下结点
(中序遍历 PL所得序列的最后一个结点 )的右子树。
这种方法可能会导致二叉排序树高度的增长 ！
本例中高度,5?6
48
46
50
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空
33
4423
4612 37
40 50
48
35
38
33
23
12
方法 2,与方法 1对称,PR 接替 *p成为 *f 的子树,PL成为 PR最左下结点 (中序遍历 PR所得序列的最后一个结点 )
的左子树。
37
4035
38
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空方法 3,令 *p的中序遍历的 直接前驱 替代 *p，再从二叉排序树中删去它的直接前驱。
这种方法不会导致二叉排序树高度的增长！
本例中高度,5?5
删除时，如何不增长树的高度？ 33
4423
4612 37
40 50
48
35
38
40
38
二叉排序树的删除
– *p的左子树 PL和右子树 PR均不为空方法 4,与方法 3对称,令 *p的中序遍历的 直接后继替代 *p，再从二叉排序树中删去它的直接后继。
33
4423
4612
50
48
37
4035
38
46
48
50
F
C
CL
S
SL
QL
P
PR
Q PR
F
C
CL
S
SL
QL
P
PR
Q
法 2:
F
C
CL
S
SL
QL
P
PR
Q
法 1:
例：请从下面的二叉排序树中删除结点 P。
S
SL
例,在 p的左子树中找出关键码最大的结点 r，将 r的右指针指向 p的右子女，用 p的左子女代替 p结点。
18
7310
05 68 99
27
41
5132
25 删除结点 73的过程
99
K= {18,73,10,05,68,99,27,41,51,32,25}
18
10 73
9968
27
25 41
32 51
05
二叉排序树的删除操作示例
68
bool DeleteBST( BiTree &T,KeyType kval )
{
if ( !T ) return FALSE;
else
{
if ( kval == T->data.key ) { Delete (T); return TRUE; }
else if ( kval < T->data.key )
return DeleteBST ( T->lchild,kval );
else
return DeleteBST ( T->rchild,kval );
}
}
void Delete ( BiTree &p ){
// 从 二叉排序树中删除结点 p，
// 并重接它的左子树或右子树
if ( !p->rchild ) { }
else if ( !p->lchild ) { }
else { }
} // Delete
其中 删除操作 过程如下所描述
… …
… …
… …
p
// 右子树为空树则只需重接它的左子树
q = p; p = p->lchild; delete(q);
pq q
//左子树为空树只需重接它的右子树
q = p; p = p->rchild; delete(q);
p pq
q
q = p; s = p->lchild;
while (s->rchild) { q = s; s = s->rchild; }
//左右子树均不空
p->data = s->data;
if ( q != p ) q->rchild = s->lchild;
else q->lchild = s->lchild;
delete(s); pq
s
// s指向被删结点的前驱
bool DeleteBST ( BiTree &T,KeyType key )
{
if ( !T ) return FALSE;
else if ( key == T->data,key ) Delete ( T );
else if ( key < T->data,key ) DeleteBST ( T->lchild,key );
else DeleteBST ( T->rchild,key );
return TRUE;
}
注意：删除根结点而相应的二叉树没有另增的头结点的情况。
void Delete ( BiTree &p )
{ if ( ! p-> rchild ) { q = p; p = p->lchild ; free(q); }
else if ( ! p-> lchild ) { q = p; p = p->rchild ; free(q); }
else {
q = p; s = p-> lchild;
while ( s->rchild ) { q = s; s = s->rchild; }
p->data = s->data;
if ( q != p ) q->rchild = s->lchild; else q->lchild = s->lchild;
free(s);
}
}
5、查找性能的分析对于每一棵特定的二叉排序树,均可按照平均查找长度的定义来求它的 ASL 值,显然,由值相同的 n 个关键字,构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同,甚至可能差别很大。
由关键字序列 3,1,2,5,4构造而得的二叉排序树由关键字序列 1,2,3,4,5 构造而得的二叉排序树，例如：
2
1
3
4
53
5
4
1
2
ASL=(1+2+3+4+5)/5 = 3
ASL=(1+2+3+2+3)/5 = 2.2
二叉排序树的查找分析
– 与给定值比较的关键字个数不超过二叉排序树的深度
– 示例：从空树出发，待插的关键字序列为 33,44,23,46,12,37
33
4423
4612 37
二叉排序树的形态与关键字的插入次序直接相关！
如：将上例的关键字插入次序调整为,12,23,33,44,37,46
12
23
33
37
44
46
查找成功时,等概率下,ASL(b)=(1+2+3+4+5*2)/6=20/6
查找成功时,等概率下,ASL(a)=(1+2*2+3*3)/6=14/6
下面讨论平均情况,
不失一般性,假设长度为 n的序列中有 k个关键字 小于 第一个关键字,则必有 n-k-1个关键字 大于 第一个关键字,由它构造的二叉排序树的平均查找长度是 n和 k的函数
n-k-1k
P(n,k) ( 0? k? n-1 )
假设 n个关键字可能出现的 n!种排列的可能性相同，则含 n个关键字的二叉排序树的平均查找长度
==?
=
1
0
),(1)( n
k
knPnnPA S L
=?=
==
n
i i
n
i ii
CnCpknP
11
1),(
在 等概率查找 的情况下，
=?=
= R
i
L
ir o o t
n
i
i CCCnCnknP
11),(
1)1)1()(1()1)((11= knPknkPk
n)1()1()(11= knPknkPk
n
由此可类似于解差分方程，此递归方程有解,Cn
n
nnP= log12)(
=?
=
1
0
)1()1()(111)( n
k
knPknkPknnnP
=?
=
1
12
)(21 n
k
kPkn
8.2.2 键树
1,键树的结构特点
2.,双链树
3,Trie树
1、键树的结构特点
※ 关键字 中的各个符号 分布在从根结点到叶的路径上,叶结点内的符号为“结束”的标志符。因此,键树的深度和关键字集合的大小无关 ;
※ 键树 被约定为 是一棵有序树,即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘ $’小于任何其它符号。
H
A
D
$
S
$
V
E
$
E
$ R
$ E
$
I
G
H
$
S
$
例如,
表示关键字集合
{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS }
void setmatch(DLTree root,char line[],int count[])
{
// 统计以 root为根指针的键树中,各关键字在文本串 line中
// 重复出现的次数，
// 并将其累加到统计数组 count中去
i=0;
while (i<=LINESIZE)
{
if (!Search_DLTree(root,i,k)) i++;
// 查找不成功，从下一个字符起重新开始匹配
else i += k-1;
// 从匹配成功的子串的后一个字符开始进行下一单词的匹配
}
}
2.双链树
— 以二叉链表作存储结构实现的键树
typedef enum { LEAF,BRANCH }NodeKind;
// 两种结点,{叶子 和 分支 }
结点结构,
first symbol next
分支结点
infoptr symbol next
叶子结点指向孩子结点的指针指向兄弟结点的指针指向记录的指针
H?
A
D
$
HAD
E
$
R
$
$
E
S
$
G
H
$
I?
HE
HER
HERE
HIGH HIS
…
T
叶子结点分支结点含关键字的记录
#define MAXKEYLEN 16 //关键字的最大长度
typedef struct {
char ch[MAXKEYLEN]; // 关键字
int num; // 关键字长度
} KeysType; // 关键字类型
typedef struct DLTNode {
char symbol;
struct DLTNode *next; // 指向兄弟结点的指针
NodeKind kind;
union {
Record *infoptr; // 叶子结点内的记录指针
struct DLTNode *first; // 分支结点内的孩子链指针
}
} DLTNode,*DLTree; // 双链树的类型初始状态,p=T->first; i = 0;
若 ( p && p->symbol == K.ch[i] && i<K.num-1)
则继续和给定值的下一位进行比较
p=p->first; i++;
若 ( p && p->symbol != K.ch[i] )
则继续在键树的同一层上进行查找 p=p->next;
若 ( p && p->symbol==K.ch[i] && i==K.num-1)
则 查找成功，返回指向相应记录的指针 p->infoptr
若 ( p == NULL) 则表明查找不成功，返回“空指针” ;
在双链树中查找记录的过程假设,T 为指向双链树根结点的指针,K.ch[0..K.num-1] 为待查关键字 (给定值 )。
则查找过程中的基本操作为进行下列比较,
K.ch[i] =? p->symbol
其中,p 指向双链树中某个结点,0 ≤ i ≤ K.num-1
bool Search_DLTree( DLTree rt,int j,int &k )
{
k=0; found = FALSE;
p = rt->first; // p指向双链树中第一棵子树的树根
while ( p && !found) {
while( p && p->symbol<line[j+k]) p=p->next;
if (!p || p->symbol>line[j+k]) break; // 在键树的第 k+1层上匹配失败
else { // 继续匹配
p = p->first; k++;
if (p->kind == LEAF) { //找到一个单词
count[p->idx]++; found = TRUE;
}// if
}// else
}//while
return found;
} //Search_DLTree
bool Insert_DLTree( DLTree &root,KeysType K,int &n )
{ p = root->first; f = root; j = 0;
while ( p && j < K.num ) { //在键树中进行查找
pre = NULL;
while( p && p->symbol < K.ch[j] ) { pre = p; p = p->next; }
if ( p && p->symbol == K.ch[j] ) { f = p; p = p->first; j++; }
else { //没有找到和 K.ch[j]相同的结点，插入 K.ch[j]
s = new DLNode; s->kind = BRANCH; s->symbol = K.ch[j++];
if (pre) pre->next = s; else f->first = s;
s->next = p; p = s;
break;
} //else
}//while
if ( p && j == K.num )
if ( p->first->kind == LEAF ) return FALSE; // 键树中已存在 K
else { //键树中已存在相同前缀的单词,插入由剩余字符构成的单支树
while ( j <= K.num ) {
s = new DLNode;
s->next = p->first; p->first = s; p = s;
if ( j < K.num)
{ s->kind = BRANCH; s->symbol = K.ch[j++]; s->first = NULL; }
else { s->kind = LEAF; s->symbol = '$'; n++; s->idx = n; }
}//while
return TRUE;
}//else
}
3,Trie树
— 以多重链表作存储结构实现的键树结点结构,
分支结点 叶子结点指向记录的指针
0 1 2 3 4 5 … … 24 25 26
关键字指向下层结点的指针每个域对应一个“字母”
T
0 1(A) 3 4 5(E) 9(I) … … 26
8(H)
4(D) 19(S) 22(V) 0 18(R) 7(G) 19
0 5(E)
HAD HISHIGH
HEREHER
HEHAVEHAS
叶子结点分支结点指向记录的指针
typedef struct TrieNode {
NodeKind kind; // 结点类型
union {
struct { KeyType K; Record *infoptr } lf;
// 叶子结点 (关键字和指向记录的指针 )
struct { TrieNode *ptr[27]; int num } bh;
// 分支结点 (27个指向下一层结点的指针 )
}
} TrieNode,*TrieTree; // 键树类型结点结构的 C 语言描述在 Trie树中查找记录的过程假设,T 为指向 Trie 树根结点的指针，
K.ch[0..K.num-1] 为待查关键字 (给定值 )。
则查找过程中的基本操作为：
搜索和对应字母相应的指针,
若 p不空，且 p所指为分支结点，则 p=p->bh.Ptr[ord(K.Ch[i])];
( 其中,0≤i≤K.num-1 )
初始状态,p=T; i = 0;
若 ( p && p->kind == BRANCH && i<K.num)
则继续搜索下一层的结点
p=p->bh.ptr[ord(K.ch[i])]; i++;
其中,ord 为求字符在字母表中序号的函数若 ( p && p->kind==LEAF && p->lf.K==K)
则 查找成功,返回指向相应记录的指针 p->lf.infoptr
反之，即 ( !p || p->kind==LEAF && p->lf.K!=K )
则表明 查找不成功,返回空指针 ;
一,哈希表是什么？
二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找五、哈希表的查找及分析
8.3 哈希表以上两节讨论的表示查找表的各种 结构 的共同 特点,
记录在表中的位臵和它的关键字之间不存在一个确定的关系 ;
一,哈希表是什么？
查找的过程 为 给定值 依次和关键字集合中各个 关键字 进行 比较 ;
查找的效率 取决于和给定值 进行比较 的关键字 个数 。
用这类方法表示的查找表,其平均查找长度都不为零不同的表示方法，其差别仅在于：
关键字和给定值进行比较的顺序不同。
对于频繁使用的查找表，希望 ASL = 0。
只有一个办法,预先知道所查关键字在表中的位置，即，要求：
记录在表中位置和其关键字之间存在一种确定的关系。
若 以下标为 000 ~ 999 的顺序表 表示之。
例如,为每年招收的 1000 名新生建立一张查找表,其关键字为学号,其值的范围为 xx000 ~ xx999 (前两位为年份 )。
则查找过程可以简单进行：取给定值 (学号 )的后三位,不需要经过比较便可直接从顺序表中找到待查关键字,
但是，对于 动态查找表 而言，
因此在一般情况下，需在关键字与记录在表中的存储位臵之间建立一个函数关系,以 f(key) 作为关键字为 key 的记录在表中的位臵,
通常 称 这个函数 f(key) 为哈希函数。
1) 表长不确定；
2) 在设计查找表时,只知道关键字所属范围,而知确切的关键字。
{ Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei }例如,对于如下关键字设 哈希函数 f(key) =?(Ord(第一个字母 ) -Ord('A')+1)/2? 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3
Chen ZhaoQian SunLi WuHan YeDei
问题,若添加关键字 Zhou,怎么办？ 能否找到另一个哈希函数？
1) 哈希 (Hash)函数是一个 映象,即,将关键字的集合映射到某个地址集合上,它的设臵很灵活，只要这个地址集合的大小不超出允许范围即可 ;
从这个例子可见，
2) 由于哈希函数是一个 压缩映象,因此，在一般情况下，很容易产生,冲突” 现象，即,key1? key2，而 f(key1) = f(key2)。
3) 很难 找到一个不产生冲突的哈希函数。一般情况下,只能选择恰当的哈希函数，使冲突尽可能少地产生。
因此，在构造这种特殊的“查找表” 时，除了需要选择一个,好” (尽可能少产生冲 突 )的哈希函数之外 ;还需要找到 一种,处理冲突” 的方法 。
选取某个函数，依该函数按关键字计算元素的存储位臵，并按此存放； 查找时，由同一个函数 对给定值 k计算地址，将 k与地址单元中元素关键码进行比，
确定查找是否成功。
通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后,可能将不同的关键码映射到同一个哈希地址上,这种现象称为 冲突 。
若干术语哈希方法
(杂凑法 )
哈希函数
(杂凑函数 )
哈希表
(杂凑表 )
冲 突哈希方法中使用的转换函数称为 哈希函数 (杂凑函数 )
按上述思想构造的表称为 哈希表 (杂凑表 )
哈希表 ——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表
哈希查找 ——又叫散列查找，利用哈希函数进行查找的过程叫哈希查找例 30个地区的各民族人口统计表编号 地区别 总人口 汉族 回族 …...
1 北京
2 上海
….
..
….
..
以编号作关键字，
构造 哈希函数,H(key)=key
H(1)=1
H(2)=2
以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数,H(Beijing)=2
H(Shanghai)=19
H(Shenyang)=19
哈希表,即散列存储结构。
散列法存储的基本思想,建立关键码字与其存储位臵的对应关系,
由关键码的值决定数据的存储地址。
优点,查找速度极快 (O(1)),查找效率与元素个数 n无关！
例 1,若将学生信息按如下方式存入计算机，如：
将 2001011810201的所有信息存入 V[01]单元；
将 2001011810202的所有信息存入 V[02]单元；
……
将 2001011810231的所有信息存入 V[31]单元。
欲查找学号为 2001011810216的信息，便可直接访问 V[16]！
哈希表的定义,
根据设定的 哈希函数 H(key)和所选中的 处理冲突的方法,将一组关键字 映象到 一个有限的、地址连续的地址集 (区间 )上，并以关键字在地址集中的 象 作为相应记录在表中的 存储位臵,如此构造所得的查找表称之为 哈希表 。
哈希查找
基本思想,在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，
一次存取就能得到所查元素的查找方法
定义
– 哈希函数 ——在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
哈希函数可写成,addr(ai)=H(ki)
– ai是表中的一个元素
– addr(ai)是 ai的存储地址
– ki是 ai的关键字关键字集合存储地址集合
hash
例,有数据元素序列 (14,23,39,9,25,11),若规定每个元素 k的存储地址 H(k)＝ k,请画出存储结构图 。 (注,H(k)＝ k称为散列函数 )
解,根据散列函数 H(k)＝ k,可知元素 14应当存入地址为 14的单元，元素 23应当存入地址为 23的单元,……,
对应散列存储表（哈希表）如下：
讨论,如何进行散列查找？
根据存储时用到的散列函数 H(k)表达式，迅即可查到结果！
例如，查找 key=9,则访问 H(9)=9号地址，若内容为 9则成功；
若查不到，应当设法返回一个特殊值，例如空指针或空记录。
地址 … 9 … 11 … 14 … 23 24 25 … 39 …
内容 14119 23 25 39
缺点：空间效率低！
有 6个元素的关键码分别为,(14,23,39,9,25,11） 。
选取关键码与元素位臵间的函数为 H(k) = k mod 7
通过哈希函数对 6个元素建立哈希表：
25
3923
9
14
冲突现象举例：
6个元素用 7个地址应该足够 !
H(14)=14%7=0 11 H(25)=25%7=4H(11)=11%7=4
有冲突！
0 1 2 3 4 5 6
所以,哈希方法必须解决以下两个问题：
1) 构造好的哈希函数
(a)所选函数尽可能简单，以便提高转换速度；
(b)所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。
2)制定一个好的解决冲突的方案查找时,如果从哈希函数计算出的地址中查不到关键码,则应当依据解决冲突的规则,有规律地查询其它相关单元 。
用哈希查找方法,冲突是不可能避免的,只能尽可能减少,
二,哈希函数的构造方法常用的哈希函数构造方法有：
1,直接定址法
2,除留余数法
3,乘余取整法
4,数字分析法
5,平方取中法
6,折叠法
7,随机数法要求一,n个数据原仅占用 n个地址，
虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
要求二,无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
Hash(key) = a·key + b (a,b为常数 )
优点,以关键码 key的某个线性函数值为哈希地址,不会产生冲突,
缺点,要占用连续地址空间，空间效率低。
例,关键码集合为 {100,300,500,700,800,900}，
选取哈希函数为 Hash(key)=key/100，
则存储结构 （ 哈希表 ） 如下：
0 1 2 3 4 5 6 7 8 9
900800700500300100
1、直接定址法
Hash(key)=key mod p (p是一个整数 )
特点,以关键码除以 p的余数作为哈希地址。
关键,如何选取合适的 p？
技巧,若设计的哈希表长为 m，则一般取 p≤m且为 质数
（也可以是不包含小于 20质因子的合数）。
2、除留余数法
Hash(key)=? B*( A*key mod 1 )? (A,B均为常数,且 0<A<1,B为整数 )
特点,以关键码 key乘以 A,取其小数部分,然后再放大 B倍并 取整,作为哈希地址 。
3、乘余取整法例,欲以学号最后两位作为地址，则哈希函数应为：
H(k)=100*(0.01*k % 1 )
其实也可以用法 2实现,H(k)=k % 100
4、数字分析法特点,某关键字的某几位组合成哈希地址。所选的位应当是：各种符号在该位上出现的频率大致相同。
3 4 7 0 5 2 4
3 4 9 1 4 8 7
3 4 8 2 6 9 6
3 4 8 5 2 7 0
3 4 8 6 3 0 5
3 4 9 8 0 5 8
3 4 7 9 6 7 1
3 4 7 3 9 1 9
例,有一组（例如 80个）关键码，其样式如下：
讨论：
① 第 1,2位均是,3和 4”,第 3位也只有,7,8,9”,因此,这几位不能用,余下四位分布较均匀,可作为哈希地址选用。
位号：①②③ ④⑤⑥⑦
② 若哈希地址取两位 (因元素仅 80个 ),则可取这四位中的任意两位组合成哈希地址,也可以取其中两位与其它两位叠加求和后,取低两位作哈希地址。
(A*key mod 1)
就是取 A*key 的小数部分特点,对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。
理由,因为中间几位与数据的每一位都相关。
例,2589的平方值为 6702921，可以取中间的 029为地址。
6、折叠法特点,将关键码自左到右分成位数相等的几部分 (最后一部分位数可以短些 ),然后将这几部分叠加求和,并按哈希表表长,
取后几位作为哈希地址 。
适用于,每一位上各符号出现概率大致相同的情况 。
法 1,移位法 ──将各部分的最后一位对齐相加 。
法 2,间界叠加法 ──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。
例,元素 42751896,用 法 1,427＋ 518＋ 96=1041
用 法 2,427 518 96—> 724+518+69 =1311
5、平方取中法
7、随机数法
Hash(key) = random ( key ) (random为伪随机函数 )
适用于,关键字长度不等的情况。造表和查找都很方便。
① 执行速度 (即计算哈希函数所需时间 )；
② 关键字的长度；
③ 哈希表的大小；
④ 关键字的分布情况；
⑤ 查找频率。
小结：构造哈希函数的原则：
实际造表时,采用何种 构造哈希函数的 方法 取决于建表的关键字集合的情况 (包括关键字的范围和形态 )，总 的原则是使产生冲突的可能性降到尽可能地小 。
三、处理冲突的方法处理冲突 的实际含义是：
为产生冲突的地址 寻找下一个 哈希地址常见的冲突处理方法有：
1.开放定址法（开地址法）
2.链地址法（拉链法）
3.再哈希法（双哈希函数法）
4.建立一个公共溢出区为产生冲突的地址 H(key) 求得一个 地址序列,
H0,H1,H2,…,Hs 1≤ s≤m-1
其中,H0 = H(key)
Hi = (H(key)+di) MOD m i=1,2,…,s
1,开放定址法对增量 di 有三种取法：
1) 线性探测再散列,di = c? i 最简单的情况 c=1
2) 平方探测再散列,di = 12,-12,22,-22,…,
3) 随机探测再散列,di 是一组伪随机数列或者 di=i× H2(key)
(又称双散列函数探测 )
即：产生的 Hi 均不相同，且所产生的
s(m-1)个 Hi 值能 覆盖 哈希表中所有地址。则要求：
注意,增量 di 应具有,完备性,
※ 随机探测时的 m 和 di 没有公因子。
※ 平方探测时的表长 m 必为形如 4j+3
的素数（如,7,11,19,23,… 等）；
例如,关键字集合
{ 19,01,23,14,55,68,11,82,36 }
设定 哈希函数 H(key) = key MOD 11 ( 表长 =11 )
0 1 2 3 4 5 6 7 8 9 1 0
0 1 2 3 4 5 6 7 8 9 1 0
1901 23 1455 68
1901 23 14 68
若采用 线性探测再散列 处理冲突若采用 二次探测再散列 处理冲突
11 82 36
55 118236
1 1 2 1 3 6 2 5 1
例 表长为 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
例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79),哈希函数为：
H(key)=key MOD 13,哈希表长为 m=16,设每个记录的查找概率相等
(1) 用线性探测再散列处理冲突，即 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
线性探测法的优点,只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；
线性探测法的缺点,可能使第 i个哈希地址的同义词存入第 i+1个哈希地址，这样本应存入第 i+1个哈希地址的元素变成了第 i+2个哈希地址的同义词,……,
因此，可能出现很多元素在相邻的哈希地址上,堆积,起来，大大降低了查找效率。
解决方案,可采用 二次探测法 或 伪随机探测法,以改善
,堆积,问题。
讨论
2、链地址法 (拉链法）
基本思想,将具有相同哈希地址的记录链成一个单链表,m个哈希地址就设 m个单链表,然后用一个数组将 m个单链表的表头指针存储起来，形成一个动态的结构。
设 { 47,7,29,11,16,92,22,8,
3,50,37,89 }的哈希函数为：
Hash(key)=key mod 11，
用 拉链法 处理冲突,则建表如右图所示 。
例,0
1
2
3
4
5
6
7
8
9
10
22 11
89
3 47
37 92
29 7
16
50
8
10
注,有冲突的元素可以插在表尾,
也可以插在表头
Hi=Rhi(key) i=1,2,…,k
Rhi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。
优点,不易产生聚集；
缺点,增加了计算时间。
4,建立一个公共溢出区思路,除设立哈希基本表外,另设立一个溢出向量表 。
所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。
3、再哈希法
– 方法,构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即,Hi=Rhi(key) i=1,2,……k
– 其中,Rhi—— 不同的哈希函数例 已知一组关键字 (19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为,H(key)=key MOD 13,
用链地址法处理冲突
14
^
1 27 79
68 55
19 84
20
23 10
11
^
^
^
^
^
^
^
^
^
^
^
^
0
1
2
3
4
5
6
7
8
9
10
11
12
ASL=(1*6+2*4+3+4)/12=1.75
将所有哈希地址相同的记录都链接在同一链表中。
链地址法
0
1
2
3
4
5
6
11
19 8268
55
14
36?01
23
ASL=(6× 1+2× 2+3)/9=13/9
例如,同前例的关键字，哈希函数为
H(key)=key MOD 7
查找过程和造表过程一致。假设采用开放定址处理冲突，则 查找过程 为,
四、哈希表上的操作算法对于 给定值 K,计算 哈希地址 i = H(K)
若 r[i] = NULL 则查找不成功若 r[i].key = K 则查找成功否则 求下一地址 Hi,直至
r[Hi] = NULL (查找不成功 )
或 r[Hi].key = K (查找成功 ) 为止。
int hashsize[] = { 997,..,};
typedef struct {
ElemType *elem;
int count; // 当前数据元素个数
int sizeindex;
// hashsize[sizeindex]为当前容量
} HashTable;
#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1
//--- 开放定址哈希表 的存储结构 ---
Status SearchHash (HashTable H,KeyType K,
int &p,int &c) {
// 在开放定址哈希表 H中查找关键码为 K的记录
} // SearchHash
p = Hash(K); // 求得哈希地址
while ( H.elem[p].key != NULLKEY &&
!EQ(K,H.elem[p].key)）
collision(p,++c); // 求得下一探查地址 p
if (EQ(K,H.elem[p].key)) return SUCCESS;
// 查找成功,返回待查数据元素位臵 p
else return UNSUCCESS; // 查找不成功
Status InsertHash (HashTable &H,Elemtype e){
} // InsertHash
c = 0;
if ( HashSearch ( H,e.key,p,c ) == SUCCESS )
return DUPLICATE;
// 表中已有与 e 有相同关键字的元素
else
H.elem[p] = e; ++H.count; return OK;
// 查找不成功时，返回 p为插入位臵
else RecreateHashTable(H); // 重建哈希表
if ( c < hashsize[H.sizeindex]/2 ) {
// 冲突次数 c 未达到上限，（阀值 c 可调）
}
1) 选用的 哈希函数 ;
2) 选用的 处理冲突的方法 ;
3) 哈希表饱和的程度,装载因子
α =n/m 值的 大小 （ n—记录数,m—表的长度）
决定哈希表查找的 ASL的因素,
哈希表查找的分析从查找过程得知，哈希表查找的平均查找长度 实际上并不等于零 。
一般情况下，可以认为选用的哈希函数是均匀的，
则在讨论 ASL时，可以不考虑它的因素。
因此,哈希表的 ASL是 处理冲突方法 和 装载因子的函数。
例如：前述例子线性探测处理冲突时,ASL =
双散列探测处理冲突时,ASL =
链地址法处理冲突时,ASL =
22/9
14/9
13/9
线性探测再散列链地址法随机探测再散列
)
1
11(
2
1
nlS
)1ln (1?
nrS
2
1ncS
可以证明,查找成功 时有下列结果：
从以上结果可见，哈希表的平均查找长度是?
的函数,而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子
,使得 平均查找长度限定在某个范围内 。
讨论
2）,冲突,是不是特别讨厌？
答,不一定！正因为有冲突，使得文件加密后无法破译
（不可逆，是单向散列函数，可用于数字签名）。
利用了哈希表性质,源文件稍稍改动，会导致哈希表变动很大。
随机探测法）
线性探测法拉链法）
()1l n (
1
)()
1
1
1(
2
1
(
2
1
A S L
A S L
A S L
1） 散列存储的查找效率到底是多少？
答,ASL与装填因子?有关！既不是严格的 O(1)，也不是
O(n)
应尽量选择一个合适的?，以降低 ASL
的长度
序表和有序表的查找方法及其平均查找长度的计算方法。
静态查找树的构造方法和查找方法及其和有序表的差别。
熟练掌握二叉排序树的构造和查找方法。
熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
小结
