9.6.2 哈希函数的构造方法
构造哈希函数的目标：
哈希地址尽可能均匀分布在表空间上——均 匀性好； 哈希地址计算尽量简单。
考虑因素：
函数的复杂度； 关键字长度与表长的关系； 关键字分布情况； 元素的查找频率。
一、直接地址法 取关键字或关键字的某个线性函数值为哈希地址 即： H(key) = key 或： H(key) = a* key + b 其中，a， b为常数。 例：1949年后出生的人口调查表，关键字是年份 年份 1949 1950 1951 … 人数 … … … …
9.4 二叉排序树
1．定义：
二叉排序树(二叉搜索树或二叉查找树) 或者是一棵空树；或者是具有如下特性的二叉树
(1) 若它的左子树不空，则左子树上所有结点的 值均小于根结点的值；
(2) 若它的右子树不空，则右子树上所有结点 的值均大于等于根结点的值； (3) 它的左、右子树也都分别是二叉排序树。
例如:
H(key)
通常设定一个一维数组空间存储记录集合，则 H(key)指示数组中的下标。
称这个一维数组为哈希(Hash)表或散列表。 称映射函数 H 为哈希函数。 H(key)为哈希地址
例：假定一个线性表为： A = (18，75，60，43，54，90，46) 假定选取的哈希函数为
hash3(key) = key % 13
H(key) = key + (-1948) 此法仅适合于： 地址集合的大小 = = 关键字集合的大小
二、数字分析法
假设关键字集合中的每个关键字都是由 s 位数 字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为 地址。 例如：有若干记录，关键字为 8 位十进制数， 假设哈希表的表长为100, 对关键字进行分析， 取随机性较好的两位十进制数作为哈希地址。
ASL = (1 + 2 * 2 + 3 * 3)/6 =14/6
例：关键字序列：(12, 24, 37, 45, 53, 90)。
其二叉排序树为：
12 24
ASL = (1 + 2 + 3 + 4 + 5 + 6)/6
= 21/6
二叉排序树的性能取决于树 的形态，而二叉树的形态取决于 插入结点的顺序。 构造一棵接近理想平衡树的 二叉排序树？
查找不成功：
查找61： H(61)= 61%13= 9
如果 key1 ≠ key2， 但
H(key1) = H(key2)
这种现象称为“冲突”，称 key1 和 key2 为同义词。 在实际应用中，应尽量选择均匀的哈希函 数来减少冲突。
冲突不能避免时，选定一个解决冲突的方 法。
发生冲突与下列三个因素有关：
30
20 35
某结点的前驱一 定在它的左子树 的最右下方
80
40 90 85
32
前驱结点 被删结点
88
以其前驱替代之，然后 再删除该前驱结点
5. 二叉排序树的查找分析
比较次数 = 被查结点所在的层次数。 二叉排序树的性能取决于树的形态，而二叉树的 形态取决于插入结点的顺序。
关键字序列：(45，24，53，12，37，90) 45 24 12 37 53 90
{13，24，37，90，53，28，98}
插入点 插入后结果
13 24
13 A 24 B 13 13 24
失衡原因
调整
RR型
24
B
37
37
13 A 37
90
13
24 37 90
24
24 A 90 B
53
13
-2 37
RL型
13 A 37
53
C 90 B
53 C
-2
24 A 53 37 C B 90
3. 二叉排序树的构造
特点：树结构在查找的过程中动态生成。
每次插入的结点只能成为新的叶子结点
例：关键字序列为 {45，24，53，12，14，90 }
45
24 53 90 14
中序遍历:12,14,24,45,53,90
12
(1) 插入算法： status ins_bstree(BiTree &bt，BiTree s){
30 20 10 25 35
50
80 40 66 85 90
23
不 是二叉排序树。
88
对二叉排序树进行中序遍历，得到一个有序序列
2. 二叉排序树的查找算法：
若二叉排序树为空，则查找不成功； 否则 1）若给定值等于根结点的关键字，则 查找成功；
2）若给定值小于根结点的关键字，则 继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则 继续在右子树上进行查找。
A BR AL BL
X
AL<A<BL<B<BR
1 0 B
A AR CR
X
C
LR型
BL
B CL
X
A -1
C BL CL
X -1 A
CR
X
AR
BL<B<CL<C< CR< A<AR
C
A AL CL
X
B 0
AL C CL CR
X X
RL型
B -1 CR
X
BR
BR
AL<A<CL<C< CR< B<BR
例：按下列关键字的次序生成一棵AVL树。
RL型
A 24 13
37 C 53 B 28 90
28
13
28
37
98
13
24 28
-2 53 A 90 B
RR型
24
37 90
13
98
28
53
98Βιβλιοθήκη 9.6 哈希表9.6.1 什么是哈希表
哈希表的基本思想: “一次”查找成功。
ASL的T(n)=O(1)。
映射函数 H
关 键 字 集 合 地 址 空 间
(1)装填因子(load factor): =
n (负载因子) m
m为hash表的长度，n为填入的记录数。
越大，冲突的可能性越大。 越小，冲突的可能性会减小，但空间的利用率变低。
为兼顾两者， 在 [0.6，0.9]范围内为宜。 (2) 与采用的散列函数有关。
(3) 与解决冲突的方法有关。
方法选择的好坏也将减少或增加发生冲突的可能性。
六、 随机数法
设定哈希函数为:
例如: 二叉排序树 50
30
20 40
80
90
35
32 查找关键字 = 50 , 35 , 90 , 95 ,
85
88
二叉链表类型定义：
typedef struct BiTNode{
KeyType key；
…… //其它成员
struct BiTNode *lchild； struct BiTNode *rchild； } BiTNode，*BiTree；
此方法仅适合于： 能预先估计出全体关键字的每一位上各 种数字出现的频度。
三、平方取中法
将k平方后的中间几位取为哈希地址。位数由表长决定
例1：时间 8:40:02。m=84002, (m)2=705633604.
例2：四位字母标识符的hash地址，地址空间为0~ 999
用两位数字01~ 26表示对应的26个字母， 如：AABB的内部代码：01010202 关键字 KEYA KEYB AKEY BKEY 内部代码 11052501 11052502 01110525 02110525 (内部代码)2 122157778355001 122157800460004 001233265775625 004454315775625 H(key) 778 800 265 315
二叉排序树的查找：
BiTree bstsrch(BiTree bt，KeyType k){
//二叉排序树的存储结构为二叉链表，函数返回结点的 //关键字为k的指针，若查找不成功，返回空指针
if (t==NULL）return NULL； else if（bt→key==k） return(bt) else if(bt→key < k ) return（bstsrch(bt→rchild，k)） else return（bstsrch(bt→lchild，k)）； }
0 30
0 53
0 63
是平衡树 问：平衡树是理想平衡树吗？ 不是平衡树
如何检测二叉树是否失去平衡？
当插入一个新结点时，重新计算从新插入的 结点到根结点的路径上所包含结点的平衡因 子（bf），如果某一结点的 bf 的绝对值超 过1，则二叉树失去平衡。
1 -1 3 1 3 -2 3 7 2 4 0 1
若根据哈希函数把元素存储到哈希表H[13]
中，则存储映象为：
0 1 2 3 4 5 6 7 8 9 10 11 12
H
54
43 18
46 60
75
90
0
1
2
3
4
5
6
7
8
9 10 11
12
H
54
43 18
46 60
75
90
哈希表的查找
同插入元素一样。如从表中查找关键字为60 的元素时，只要利用上面的函数计算出地址 H(60) = 60 % 13 = 8
4. 二叉排序树的删除算法
删除一个结点后，仍是二叉排序树。
可分三种情况讨论：
(1) 被删除的结点是叶子； (2) 被删除的结点只有左子树或者只有右子树； (3) 被删除的结点既有左子树，也有右子树。