5.二叉排序树的性能分析
二叉排序树查找的最差情况与顺序查找相同,ASL=(n+1)/2;最好情况与折半查找相同,ASL可以达到对数级log2n。
对于二叉排序树的插入和删除操作来说,只需修改某些结点的指针城,不需要大量移动其他记录,动态查找的效率很高。
8.3.2 平衡二叉树
略
8.3.3 B树和B+树
略
8.3.4伸展树
略
8.3.5红黑树
略
8.4 散列
散列方法是一种计算式查找方法，又叫“hash（哈希。杂凑）法”或“关键字地址计算”等。
它的基本思想是,首先在记录的关键字key和记录的存储位置p之间建立一个对应关系H,使得p=H(key),H称为“哈希函数”,p称为“散列地址”。当创建哈希表时,把关键字为key的记录 建存人地址为H(key)的地址单元中;以后当在找关键字为key的记录时,再利用哈希函数n: H(k)计算出该记录的散列地址p,从而达到直接存取记录的目的。因此,散列方法的核心就是由哈希函数决定关键字值与散列地址之间的对应关系,通过这种关系来组织存储并进行查找等操作。
由于哈希函数是一个压缩映像,因此在实际应用中很少存在不产生冲突的哈希函数,因而在采用散列方法进行查找时必须解决以下两个问题。
①如何构造恰当的哈希函数,使得结点分布均匀,尽量少产生冲突。
②一旦发生冲突,如何处理冲突。
8.4.1哈希函数的构造方法
本节将介组几种哈希函数的构造方法。在这些方法中,假设处理的关键字值为整型,这样就 可以建立一种关键字与整数之间的对应关系,从而把关键字的查找转换为对应的整数的查找。哈希函数的构造原则为简单和均匀,具体如下。
①哈希函数本身运算尽量简单,便于计算:
②哈希函数值必须在散列地址范围内,且分布均匀,地址冲突尽可能少。
下面介绍几种常用的哈希函数构造方法。
(1)除留余数法
该方法是最为简单常用的一种方法。假设表长为m,p为小于等于表长m的最大素数,则哈希函数为H(key)=key%p
对于p的选取问题,p应为不大于m的质数或者是不含20以下的质因子 。
（2）数字分析法
（3）平方取中法
（4）分段叠加法
（5）基数转换法
在实际应用中,还是应该根据实际情况选择采用恰当的散列方法,并用实际数据测试它的性能,以便做出正确判定。
一般应考虑以下因素。
①计算哈希函数所需的时间,
②关键字的长度
③散列表的大小
④关键字分布的情况
⑤记录查找的频率
8.4.2处理冲突的方法
尽管构造性能良好的哈希函数可以减少冲突,但实际上冲突是不可避免的。事实上,处理冲突的实际含义就是为产生冲突的地址寻找下一个散列地址。接下来介绍几种处理冲突的方法
1.开放定址法
开放定址法也被称为“再散列法”。其基本思想是,当关键字key的初始散列地址h0=H(key)出现冲突时,以h0为基础查找下一个地址h1,如果h1仍然冲突,再以h0为基础,产生另一个散列地址h2…直到找出一个不冲突的地址hi,将相应元素存入其中。这种方法有一个通用的再散列函数形式:
hi=(H(key)+di)%m i=1,2,…,n
其中,H(key)为哈希函数,h,=H(key),m为表长,di为增量序列。增量序列的取值方式不同,对应有不同的再散列方式,主要有以下三种。
(1)线性探测再散列
di=cxi 最简单的情况c=1
这种方法的特点是,冲突发生时,顺序查看表中下一个单元,直到找到一个空单元或查遍全表。值得注意的是,由于这里使用的是%运算,因而整个表成为一个首尾连接的循环表,在查找时类似于循环队列,表尾的后边是表头,表头的前边是表尾。
(2)二次探测再散列
di=12,-12,22,-22,…k2,-k2(k≤m/2)
这种方法的特点是,冲突发生时分别在表的右、左进行跳跃式探测,较为灵话,不易产生聚集，但缺点是不能探查到整个散列地址空间。
(3)随机探测再散列
di=伪随机数
这种方法需要建立一个随机数发生器,并给定一个随机数作为起始点。
2.链地址法
链地址法解决冲突的基本思想是,把所有具有地址冲突的关键字链在同一个单链表中: 若哈希表的长度为m,则可将哈希表定义为一个由m个头指针组成的指针数组。散列地址为i的记录均插入以指针数组第i个单元为头指针的单链表。
8.4.3哈希表查找
根据不同的处理冲突的方法,哈希表的查找操作也有所不同。这里以开放定址法处理冲突为例,介绍相关的操作。
数据类型描述如下。
#define HASHSIZE 11 typedef int otherdata; typedef struct{ int key; otherdata other; }Datatype; typedef struct{ Datatype data; int times;//比较次数 }Hashtable[HASHSIZE];
如果构造哈希函数采用除留余数法,即H(key)=key%m,则获得散列地址的算法描述如下。
[算法8-10]采用除留余数法构造哈希函数
4-哈希表查找.c
相关代码请看配套资源
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
如果采用线性探测再散列处理冲突,处理冲突的算法描述如下。
[算法8-11]采用线性探测再散列处理冲突
相关代码请看配套资源
4-哈希表查找.c
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
1.哈希表的查找
哈希表的查找过程与构建哈希表的过程类似。查找过程如下。
①根据待查找记录的关键字和建表时的哈希函数计算散列地址
②若该地址所对应的地址单元为空,则在找失败;若不为空,则将该单元中的关键字与待查记录的关键字进行比较,如果相等则查找成功,否则按建表时设定的处理冲突的方法找下一个地址。
③重复上述步骤②,直至某个单元为空,则查找失败或与待查记录的关键字相等,查找
成功
哈希表的查找算法如下。
[算法8-12]哈希表的查找
相关代码请看配套资源
4-哈希表查找.c
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
2.哈希表的插入
哈希表的插入步疆为,首先通过查找算法找到待插记染在表中的位置、若在表中找到待查记录,则不必插入;著没有找到,此时查找算法给出一个单元的散列地址,将待插记录插入该地址单元
哈希表的插入算法如下。
[算法8-13] 哈希表的插入
4-哈希表查找.c
相关代码请看配套资源
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
3.哈需表的创建
和前面讲过的内容相似,哈希克的创建算法是基于插入算法的。首先将表中各结点的关键字置空,使其地址为开放的,然后调用插入算法将给定的记录的关键字序列依次插入哈希表。
哈希表的创建算法如下
[算法8-14]哈希表的创建
相关代码请看配套资源
4-哈希表查找.c
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
4.哈希表的删除
基于开放定址法的哈希表不能实现真正的删除操作、只能给被删除结点设置删除标志,以 在删除后找不到比它晚插入且与它发生过冲突的记录。也就是说,如果执行真正的删除操作, 中断查找路径。如果必须对哈希表做真正的删除操作，则最好采用链地址法处理冲突的哈希表。
哈希表的删除算法如下
[算法8-15] 哈希表的删除
相关代码请看配套资源
4-哈希表查找.c
// 19,01,23,14,55,68,11,82,36 int main(){ Hashtable ht; Datatype L[9]={0}; int data[9]={19,1,23,14,55,68,11,82,36}; CreateData(L,data,9); // printData(L,9); Createht(ht,L,9); output(ht); return 0; }
代码运行结果如下
根据以上介绍的内容,产生冲突的问题是无法避免的,因而ASL=0还是理想中的情况,基于散列的方法仍然需要与关键字进行比较。因此,基于散列的查找方法的性能评价仍然需要用平均查找长度来衡量，影响关键字比较次数的因素有三个:哈希函数、处理冲突的方法以及哈希表的装填因子。
哈希表的装填因子:
α=哈希表中已存入的元素个数 / 哈希表的长度
它表示哈希表的装满程度。显然,α越小,冲突的可能性就越小,但存储空间的利用率就低；α越大,冲突的可能性就越大,但存储空间的利用率就越高。为了兼顾两者，一般选α在0.6 ~0.9的范围内
表8-2所示为几种不同外理冲突方法下的哈希表的ASL。
| 处理冲突的方法 | ASLsucc | ASLsucc |
| 线性探查法 | 1/2 （1+1/(1-α） | 1/2 [1+1/(1-α)2] |
| 二次线性探查法 | 1/α ln(1-α） | 1/(1-α) |
| 链地址法 | 1+α/2 | α+e-α |
从表8-2中可以看出,哈希表的平均查找长度与装填因子α相关,而与待散列记录的数目 n无关。因此,无论记录数目n有多大,关键还是通过调整装填因子α控制平均查找长度使其在合理范围之内。
