第八章 查找表
★ 基本概念
★ 静态查找表
★ 动态查找表
★ Hash法
North China Electric Power University
查找表,是一种以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构。
关键字,用来标识数据元素的数据项，简称键。
★ 基本概念主关键字,可以唯一标识一个数据元素的关键字。
次关键字,可以标识若干数据元素的关键字。
查找,根据某个给定的 K值，在查找表中寻找一个键值等于 K的元素，若找到这样的元素，
则称查找成功，此时的运算结果为该数据元素在查找表中的位置，否则称查找不成功，运算结果为一特殊标志。
North China Electric Power University
North China Electric Power University
查找表静态查找表动态查找表
1.建表,Create(st)
2.查找,Search(st,k)
3.读表元,Get(st,pos)
2.查找,Search(st,k)
3.读表元,Get(st,pos)
1.初始化,Initiate(st)
4.插入,Insert(st,k)
5.删除,Delete(st,k)
North China Electric Power University
★ 静态查找表
1)顺序表上的查找,以顺序表作为存储结构，然后在这个存储结构上实现静态查找表的基本运算。
顺序表类型定义如下：
Const maxsize=静态查找表的表长 ;
Type Rec=Record
key:KeyType;
…
End;
sqTable=Array[0..maxsize] of Rec; n:Integer;
顺序查找过程,假定该查找表有 n个记录，首先将要查找的那个关键字赋给实际上并不存在的第 n+1个记录的关键字域，然后从头开始一个一个的向下查找，用 i来计数,查到就送出来看 i是第几个，若 i<=n，则查找成功，若 i=n+1
则查找失败。
North China Electric Power University
Procedure SqSearch(r:sqTable;k:KeyType);
Begin
r[n+1].key:=k;
i:=1;
while (r[i].key< >k) Do
i:=i+1;
if i<=n then Write(‘Succ i=’,i)
else Write(‘Unsucc’);
End;
平均查找长度,为确定某元素在表中某位置所进行的比较次数的期望值。
在长度为 n的表中找某一元素，查找成功的平均查找长度,
ASL=∑P iCi
North China Electric Power University
Pi,为查找表中第 i个元素的概率
Ci,为查到表中第 i个元素时已经进行的比较次数在顺序查找时,Ci取决于所查元素在表中的位置，
Ci =i,设每个元素的查找概率相等，即 Pi=1/n,则,
ASL=∑P iCi=(n+1)/2
查找不成功的查找长度为 n+1。
顺序查找表的优点,算法简单且适应面广，对表的结构无任何要求，无论元素是否按关键字有序都可应用。
顺序查找表的缺点,平均查找长度比较大，特别是当 n
较大时，查找效率较低。
North China Electric Power University
2)折半查找 (有序表上进行查找 )：
基本思想,设三个指针 low,high和 mid分别指示待查有序表的表头，表尾和中间元素，在开始查找时，三个指针的初值分别为,low:=1;high:=n;mid:=(low+high)
div 2 。折半查找是从表的中间元素开始，用待查元素的关键字 k和 r[mid].key比较，此时有三种情况 (假设该查找表按关键字的非递减次序排列 ),
1) 若 r[mid].key=k，则查找成功；
2) 若 r[mid].key>k，则 k必在较低标号的那一半表中，
令 high:=mid-1
3) 若 r[mid].key<k，则 k必在较高标号的那一半表中，
令 low:=mid+1
再取中间项进行比较，直到查找成功或 low>high(查找失败 )为止。
North China Electric Power University
例：给出表元素关键字为,{05,13,19,21,37,56,64,75,80,88,92}
1.查找关键字 k=21 的情况
(1) low:=1;high:=11;mid:=(1+11) div 2=6
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key>k，所以向左找，令 high:=mid-1=5
(2) low:=1;high:=5;mid:=(1+5) div 2=3
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key<k，所以向右找，令 low:=mid+1=4
(3) low:=4;high:=5;mid:=(4+5) div 2=4
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key=k，查找成功，所查元素在表中的序号为 mid 的值
North China Electric Power University
(1) low:=1;high:=11;mid:=(1+11) div 2=6
因为 r[mid].key<k，所以向右找，令 low:=mid+1=7
(2) low:=7;high:=11;mid:=(7+11) div 2=9
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key<k，所以向右找，令 low:=mid+1=10
(3) low:=10;high:=11;mid:=(10+11) div 2=10
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key>k，所以向左找,high:=mid-1=9
2.查找关键字 k=85 的情况
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 low>high，所以查找失败
North China Electric Power University
Procedure BinSearch(r:sqTable;k:KeyType);
Begin
low:=1;
high:=n;
while low<=high Do
[ mid:=(low+high) div 2;
Case
k>r[mid].key,low:=mid+1;
k=r[mid].key,[Write(mid);Return;]
k<r[mid].key,high:=mid-1;
EndCase;
]
Write(‘Unsucc’);
End;
North China Electric Power University
Procedure BinSearch(r:sqTable;k:KeyType,l,h:Integer);
Begin
low:=l;
high:=h;
if high<low then [Write(‘Unsucc’);Return;]
mid:=(low+high) div 2;
Case
k>r[mid].key,[low:=mid+1;BinSearch(r,k,low,high);
k=r[mid].key,[Write(mid);Return;]
k<r[mid].key,[high:=mid-1;BinSearch(r,k,low,high);
EndCase;
End;
递归算法描述如下：
算法的性能分析：
North China Electric Power University
以上面的 11个元素的查找表为例，找到第 6个元素仅需比较 1次；
找到第 3个和第 9个元素需比较 2次；找到第 1,4,7和 10个元素需比较
3次；找到第 2,5,8和 11个元素需比较 4次。上面的查找过程可以用下图所示的一棵二叉树来表示。
6
3 9
1 4 7 10
112 5 8
树中每一个结点表示表中的一个数据元素，结点中的值为该元素在表中的位置折半查找的平均查找长度为 log2(n+1)-1
找不到元素的过程：正好是从根节点一直走到某个叶子节点的路径，因此所用的比较次数最多等于树的深度。由此看来，无论元素找到或找不到,查找某一元素的比较次数最多等于树的深度,即 log2n 。
那么引出一个问题，折半查找的平均查找长度是多少?
我们用深度为 h的满二叉树描述折半查找来进行分析。
满二叉树的特点是：
层次为 1的结点有 1个 ;
层次为 2的结点有 2个 ;
…,
层次为 h的结点为 2h-1 个 。
若是完全二叉树则节点数 n=2h -1
那么表的长度一定为 n=2h-1,我们假定表中每个元素的查找概率相等,(Pi=1/n),则平均查找长度为,
ASLnS=∑CiPi=1/n∑j*2 j-1i=1n j=1n =(n+1/n)*log2(n+1)-1
North China Electric Power University
North China Electric Power University
3)分块查找,这种查找方法是表里的元素均匀的分成若干块，块与块之间是有序的，块中的元素是无序的，这种查找方法又称为索引顺序查找。
在分块查找中对每一块建立一个索引项，其中包括两项内容：关键字项 (其值为最大关键字或最小关键字 )和指针项 (指示该块的第 1个记录在表中的位置 )。索引表按关键字有序，表分块有序。
分块有序：指第二块中所有记录的关键字均大于 (或小于 )
第一块中最大 (或最小 )关键字，第三块中的所有关键字均大于 (或小于 )第二块中的最大 (或最小 )关键字 …,以此类推。
例,有一个表,各元素的关键字为,
｛ 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}
把它平均分成三块，按上升的次序排列，如下图所示：
North China Electric Power University
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
1
2
3
4
5
6
7
8
9
10
11
12
13
1415
第一块第二块第三块
1
6
11
22
44
74
关键字表小大指针表,应该指向各块的第一个关键字。
分成三块每块 5个关键字分块查找的方法,
1)由于索引表按关键字有序，则确定 k在哪一块的查找可以用顺序查找，也可用折半查找。
North China Electric Power University
2)块中的记录是任意排列的，则在块中只能用顺序查找。
分块查找的平均查找长度应该是前两者之和：
即,ASLbs=Lb+Lw
Lb:为查找所在块的平均查找长度。
用顺序查找方法,确定所在的块,则 Lb=1/b∑jj=1
b
用顺序查找方法,查找的元素所在位置,则 Lw=1/s∑ ii=1s
已知表的长度为 n,分成 b小块,每块有 s个元素,那么 b=n/s.若表中各元素的查找概率相等,那么每块的查找概率为 1/b,块中每个元素的查找概率为 1/s.
Lw:为块中查找元素的平均查找长度。
North China Electric Power University
ASLbs=1/b∑j+1/s∑i =(b+1)/2+(s+1)/2
=1/2(n/s+s+2)=1/2(n/s+s)+1j=1
b
i=1
s
可以证明,当 s= 时，平均查找长度最小 = +1
由上式可以看出，分块查找的平均查找长度不仅和表的长度 n有关，而且和每一块中的元素个数 s有关。
n n
用折半查找确定所在的块，则分块查找的平均查找长度为 ASLbs =log2(b+1)-1+(s+1)/2
=log2(n/s+1)+(s-1)/2
分块查找的算法描述如下：
Function Search_idx(st:sqTable,Id:IndexTable;k:KeyType):Integer;
{st为查找表,Id为索引表,k为待查关键字 }
Begin
low:=1;high:=Id.Length;found:=false;
while (low<=high) and (found=false) Do
[ mid=(low+high) div 2;
if(k<Id.Elem[mid].Key) then high:=mid-1
else if (k>Id.Elem[mid].key) then low:=mid+1
else [ found:=true;low:=mid;] ]
s:=Id.Elem[low].stadr;
{经索引表查找后，下一步的查找范围定位在第 low块 }
if (high<Id.Length) then t:=Id.Elem[low+1].stadr-1 else t:=st.length;
if(st.Elem[t].key=k) then Return(t)
else [ st.Elem[0]:=st.Elem[t+1];st.Elem[t+1].key:=k;i:=s;
while (st.Elem[i].Key< >k) Do i:=i+1;
st.Elem[t+1]:=st.Elem[0];
if i< >t+1 then Return(i) else Return(0); ] End;
North China Electric Power University
三种查找方法的比较,
就 平均查找长度 而言，折半查找最小，分块查找次之，顺序查找最大。
就 表的结构 而言，顺序查找对有序表和无序表均可应用，折半查找仅适用有序表，而分块查找要求表中数据是分块有序的，即需要把表分成若干块，块与块之间的记录按关键字有序。
就 表的存储结构 而言，顺序查找和分块查找对两种存储结构 --向量和链表均适用，而折半查找只适用于以向量做存储结构的的表，这就要求表中的元素基本不变，否则，当进行插入和删除运算时为保持表的有序性，便要移动元素，这在一定程度上降低折半查找的效率。
★ 动态查找表二叉排序树,或者是一棵空树，或者是具有下列性质的二叉树,1)若它的左子树不空，则它的左子树上所有结点的值均小于根结点的值； 2)若它的右子树不为空，则它的右子树上所有结点的值均大于或等于它的根结点的值； 3)它的左、右子树均为二叉排序树。
North China Electric Power University
二叉排序树的构造方法：
设 R={R1,R2,…,Rn}为一数列,按下面的原则建立二叉树：
1)令 R1为二叉树的根；
2)若 R2<R1，则令 R2为 R1的左子树的根结点，否则令 R2为
R1的右子树的根结点；
3)对 R3,R4,… Rn重复上述步骤 2)；
North China Electric Power University
例：给定 R={10,18,3,8,12,2,7,3}按上面的原则构造二叉排序树如下：
R2R1 R310
R1为根节点 R3<R1
R2
R2比 R1大
R4
R4<R1 左边
R4>R3 右边
R5
R5>R1 右边
R5<R2 左边
R6
R6<R1 左边
R6<R3 左边
R7
10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
R8
R7<R1 左边
R7>R3 右边
R&<R4 左边
R8<R1 左边
R8>R3 右边
R8<R4 左边
R8<R7 左边
North China Electric Power University
算法描述如下：
Procedure sortree(m,r,p);{建立一个含有 m 个结点 r[i](1≤i≤m) 的二叉排序树,p为指向二叉树根结点的指针 }
Procedure bsinsert(s,t);{将 s所指结点插入到根结点指针为 t的树中 }
Begin
if t=Nil then t:=s
else if s↑.data<t↑.data
then bsinsert(s,t↑.lchild) else bsinsert(s,t↑.rchild);
End;
Begin
new (q); q↑.data:=r[1];q↑.lchild:=Nil;q↑.Rchild:=Nil;
p:=q;
For i:=2 to m Do
[ new(q); q↑.data:=r[i]; q↑.lchild:=Nil;
q↑.rchild:=Nil; bsinsert(q,p);]
End;
North China Electric Power University
二叉排序树的查找已知要找的那个记录的关键字 k,从根结点的关键字开始比较，有下列三种情况：
1)若两者相等,则说明查找成功,根结点的记录为所找记录
2)若 k小于根结点的关键字，则继续查找左子树
3)若 k大于根结点的关键字，则继续查找右子树若二叉树为空，则查找失败。
Procedure SortSrch(t:Bitptr;k:KeyType);
Begin
if t=Nil then Write(‘Unsucc’)
else if k=t↑.key then [Write(‘Succ’);call outdata;]
else if k<t↑.key
then SortSrch(t↑.lchild,k)
else SortSrch(t↑.rchild,k);
End;
North China Electric Power University
非递归算法如下：
Procedure SortSrch(i,t:Bitptr;k:KeyType);{在二叉排序树 t中查找 k,每个结点有三个字段 lchild,Key,rchild,若 k不在 t中，则返回 B=1，否则，送回 i,结果 i↑.key=k}
Begin
i:=t; B:=1;{当 B=0时查找成功，否则失败 }
while(i< >Nil) and (B=1) Do
Case
k<t↑.key,i:=i↑.lchild;
k=t↑.key,[B:=0;Write(‘Succ’);]
k>t↑.key,i:=i↑.rchild;
EndCase;
End;
North China Electric Power University
二叉排序树在查找过程中的插入、删除
1)二叉排序树的插入,给定关键字 x,如果 x在二叉排序树中，送出指向 x所在结点的指针，否则将 x插入到二叉排序树的合适位置上。
Procedure Bst(t,j:Bitptr;x:Keytype);
Begin
j:=t; B,=1; p:=Nil;
while (j< >Nil) and (B=1) Do
Case x<j↑.key,[ p:=j;j:=j↑.lchild;]
x=j↑.key,[ B:=0;Write(‘Succ’);]
x>j↑.key,[ p:=j;j:=j↑.rchild;]
EndCase;
if B=1 then [new(j); j↑.key:=x; j↑.lchild:=Nil; j↑.rchild:=Nil;
Case t=Nil,t:=j;
x<p↑.key,p↑.lchild:=j;
x>p↑.key,p↑.rchild:=j; EndCase;]
End;
North China Electric Power University
2)二叉排序树的删除,在二叉排序中删除某个结点，删除此结点后仍保持二叉排序树的性质。
下面这棵二叉排序树，我们要删除结点 2：
2是根结点，它有左、右子树，要删除 2,就要找一个新的根结点，从哪儿找呢?从左子树，在左子树中找一个值最大的结点，此结点仅次于根节点，比右子树的所有结点都小，让这个结点做为根结点。
4
2 6
1 3 12
4
1 6
3 12
p
q,j
s
North China Electric Power University
在算法中用了 4个指针：
j:指向被删除结点 ; s:指向新选择的根结点 ;
p:指向被删除结点的双亲 ;q:指向新选择的根结点的双亲 ;
下面分四种情况进行讨论：
① 被删结点是叶子结点即 j↑.lchild=Nil;j↑.rchild=Nil
s=Nil 为选择的合适结点由于删去叶子结点不影响二叉排序树的结构和性质，
所以只需修改其双亲结点的指针即可。若被删结点是 p
的左子树，则 s →p↑.lchild;若被删结点是 p的右子树，
则 s →p↑.rchild
North China Electric Power University
North China Electric Power University
② 被删结点不是叶子,j无左，仅有右子树，则
s=j↑.rchild,s做 p的左 (或右 )子树。
4
1
3
6
12
4
3 6
12
③ 被删结点不是叶子,j有左，无右子树，则
s=j↑.lchild,s 做 p的左 (或右 )子树
p
j
s
4
1
3
6
12
4
3 6
12
p
j
s
North China Electric Power University
④ j既有左，又有右。则沿 j的左子树的右子树方向找，
一直找到按中序遍历 j的直接前趋结点。此结点作为新选的根结点 s,然后做相应的指针修改。
20
10 30
6 15
3 9 13 18
8
p
j
q
s
20
9 30
6 15
3 8 13 18
在上图中,s↑.rchild=Nil;s↑.lchild< >Nil
修改四个指针,1)s↑.rchild:=j↑.rchild;
2)q↑.rchild:=s↑.lchild;
3)s↑.lchild:=j↑.lchild;
4)p↑.lchild:=s;
North China Electric Power University
20
10 30
6 15
3 9 13 18
p
j
q
s
20
9 30
6 15
3 13 18
在上图中,s↑.rchild=s↑.lchild=Nil,仍做前面的四个操作
20
9 30
6 15
3 13 18
p
j,q
s
20
6 30
3 15
13 18
上图中,s↑.rchild=Nil,且 q=j,修改两个指针：
1)s↑.rchild:=j↑.rchild; 2)p↑.lchild:=s;
North China Electric Power University
下面给出在二叉排序树 T中查找结点 j,使 j↑.key=x,如果 x在 T中，则删除 x结点，否则,送出 B=1，说明此树中无被删结点的算法：
Procedure det(t,j,p:Bitptr;x:KeyType);
{j指向被删结点,p指向其双亲，假设树不空 }
Begin
j:=t;B:=1;p:=Nil;
while (j< >Nil) and (B=1) Do
Case
x<j↑.key:[ p:=j;j:=j↑.lchild;]
x=j↑,key,B:=0;
x>j↑.key:[ p:=j;j:=j↑.rchild;]
EndCase;
North China Electric Power University
If B=0
then [ if j↑.lchild=Nil{被删结点无左子树 }
then s:=j↑.rchild
Else if j↑.rchild=nil then s:=j↑.lchild
else [ q:=j;s:=q↑.lchild;
while s↑.rchild< >Nil Do
[ q:=s;s:=s↑.rchild];s↑.rchild:=j↑.rchild;
if q< >j
then [ q↑.rchild:=s↑.lchild;
s↑.lchild:=j↑.lchild;]
]
if p=Nil then t:=s else
[ if j=p↑.lchild then p↑.lchild:=s
else p↑.rchild:=s; ] ]
End;
平衡二叉树 (balanced binary tree)
平衡二叉树,或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。
平衡因子,二叉树中任一结点的左子树的深度与它的右子树的深度之差称为平衡因子。
例,2-1=1
0-0=01-0=1
0-0=0
平衡二叉树
2-3=-1A
B C
D F
G
1-1=0
0-0=0
0-2=-2
1-0=1
0-0=0
0-0=0
非平衡二叉树
A
B C
D
E
North China Electric Power University
二叉排序树的平衡化假设表中的关键字序列为 (13,24,37,90,53)
① 空树和一个结点 的二叉树显然是平衡二叉树,
② 插入 24后仍平衡
13
13
24
-1
0
③ 插入 后结点 的平衡因子为 0-2=-2，不平衡把 从 的右下侧左转到 的右上侧原来 的左为 的右,
新的 的左为
13
24
370
-1
-2
RR型即逆时针旋转
37 13
13
24
37
24 13
13
24 13
24 13
North China Electric Power University
④ 插入 90,53后,又失去平衡,可经过下列步骤转化为平衡二叉树
13
24
37
90
53
2_
0 2_
1
0
13
24
37
90
53
第一次旋转 (顺时针 )以 为轴心,把 从 的右上,转到的右下,的右是,的右为,原 的右变成新 的左。
RL型的第一次旋转 (顺时针 )
13
24
53
9037
RL型的第二次旋转 (逆时针 )
以 为轴心,把 从 的左上转到 的左下,使得 的左是 ;右是,原 的左变成了 的右。
53 90 53 53
37 53 53 90 53 90
53 37 53 53 53
37 90 53 37
North China Electric Power University
一般情况下，假设由于二叉排序树上插入结点而失去平衡的最小子树的根结点指针为 a（即 a是离插入结点最近,且平衡因子绝对值超过 1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况,
⒈ RR型平衡旋转,
b
a br
a1 b1
RRa
ba1
b1 br
-2
-1
hh-1
h-1
插入节点把结点 b从 a的右下侧逆时针 (左转 )转到 a的右上侧，
原 b的左成为 a的右，新 b的左为 a
North China Electric Power University
0
h
h-1
0
h-1
2.LL型平衡旋转,
LL
2
1
h h-1
h-1
a
b ar
brb1
ab1
br ar
0
0
把结点 b从左下侧顺转 (右转 )转到 a的左上侧,原 b的右成为 a的左,新 b的右为 a。
3.RL型平衡旋转,-2
1
h-11
h-1 a1
c
c1 cr
br
h-1 h-2
RL(顺时针 )
c1
a1
cr br
b
a
b
a
c
b
North China Electric Power University
h
h-1
h-1
h-2
h-1
h-1
-1
-1
-2
以 c为轴心，把 b从 c的右上侧顺时针（右转 )到 c的右下侧，从而 a的右是 c,c的右是 b，原 c的右变成 b的左。
以 c为轴心，把 a从 c的左上方，转到 c的左下方，使得 c的左是 a，右是 b，原 c的左子树变成 a的右。
RL(逆时针 )
c1a1 cr br
4.LR型平衡旋转,
c
a b
以 c为轴心把 b从 c的左上侧，逆时针（左转）到 c的左下侧，从而 a的左是 c,c的左是 b，原 c的左变成新 b的右。
North China Electric Power University
c1
a1
cr br
a
c
bh-1
h-2
h-1
h-1
-1
-1
-2
h-1
h-2
h-1
-10
0
LR(逆时针 )
c1
ar
cr
bl
2
-1
1
h-1
h-1 h-2
ar
c1 cr
b1h-1
LR(顺时针 )
c1 arcrbl
再以 c为轴心，把 a从 c的左上方转到 c的右下方，使得
c的右是 a，左是 b，原 c的右子树变成 a的左。
a
b
c
a
c
b
c
b a
North China Electric Power University
h-1 h-1
h-2
h-1
0
2
2
a
c1
ar
cr
bl
c
b
h-1 h-1
h-2
h-1
0
2
2
h-1
0
h-2
h-1
-1
0
North China Electric Power University
B-树
B-树：一棵 m阶的 B-树，或为空树，或为具有下列性质的 m叉树：
1)树中每个结点有 ≤ m个儿子；
2)除根和叶子结点之外的结点有 ≥ Upper(m/2)个儿子；
3)根结点至少要有两个儿子 (除非它本身又是一个叶子 )；
4)所有的非终端结点中包含下列信息数据 (n,A0,
k1,A1,k2,…,kn,An)；
n：本结点中关键字的个数 ≤ m-1
ki,关键字，从左到右其值按递增次序排列
Ai,指向一个所有关键字都在 ki和 ki+1间的子树形
5)所有的叶子结点都在同一层次上，并且不带信息 (可以看作是查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空 )；
1 18
1 11 1 27
1 35
1 39 1 99
2 43 78
3 47 53 64
a
b c
d e
f
g h
上图中,结点形式为,n 指针 关键字 指针 关键字,....
p0 k1 p1 k2
每一个结点 (除了根结点和叶子 ),有 Upper(4/2)到 4个儿子，
所以可以有 1,2或 3个关键字，根结点允许有 1至 3关键字，此时所有的 叶子都在第四层上。
例：下图所是为一棵 4阶的 B-树，深度为 4
North China Electric Power University
B-树的查找过程：
B-树的查找是一个顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。
结点类型说明如下：
Type mblink=↑mbnode;
mbnode=Record
keynum:integer;
parent:mblink;
keys:Array[1..m-1] of KeyType;
ptrs:Array[0..m-1] of mblink;
End;
Result=Record
p:mblink; i:Integer; tag,(0,1);
End;
North China Electric Power University
查找算法如下：
Function mbsearch(t:mblink;key:KeyType):Result;
Begin
p:=t;q:=nil;key[0]:=-max;{key[0..m]为关键字辅助数组 }
while p< > Nil Do
[ n:=p↑.keynum;key[n+1]:=max;
For j:=1 to n Do
key[j]:=p↑.keys[j];
For j:=0 to n Do
a[j]:=p↑.ptrs[j]; {a[0..m]为指针型辅助数组 }
i:=sqSearch(key,k);
{在数组 key中进行顺序查找直到 key[i]≤k≤ key[i+1]}
if key[i]=k then Return(p,i,1);{查找成功 }
q:=p;p:=a[i]; ]
Return(q,i,0);{查找失败,其中 q,i指示等于 k的关键字在 B-树中应插入的位置 }
End;
North China Electric Power University
在 B-树上进行查找所需时间的分析从上述过程可知，在 B--树上进行查找所需时间取决于两个因素：
⑴等于给定值的关键字所在的层次数 ;
⑵ 结点中关键字的数目。 (较大时可用折半查找 )
显然,节点所在的最大层次数即为树的深度 。 那么,含有 N个关键字的 m阶 B--树的最大深度是多少？
根据 B--树的定义第一层至少有 1个结点第二层至少有 2个结点第三层至少有 2* m/2 个结点
(因为除根之外的每个非终端结点至少有 m/2 个 )
第四层至少有 2* m/2 2个结点
North China Electric Power University
……
最末层 L+1层有 2* m/2 L-1个结点
(因为最末层为叶子,m阶 B树中有 N个关键字,则叶子结点为 N+1
个,由此有 N+1≥2*( m/2 ) L-1
N+1
2 ≥ ( m/2 )
L-1 两边取对数
log( )N+12 ≥ (L-1)log( m/2 )
L-1≤
log( )N+12
log( m/2 )
换底
=
log ( )m/2 N+12
log m/2 2
log ( )m/2 m/2
log m/2 2
North China Electric Power University
=
log ( )m/2 N+12
1 ≤ log ( )m/2
N+1
2
∴L≤ log ( )m/2 N+12 +1
这就是说，在含有 N个关键字的 B--树上，进行查找时，从根 j
结点到关键字所在结点的路径上涉及的结点数不超过
log ( )m/2 N+12 +1个例如,当 N=1999998且 m=199时,L最多为 3。
这就是说，在最坏情况下，一次查找至多需要存取 3个结点。
North China Electric Power University
B-树的插入：
B-树的生成也是从空树起，逐个插入关键字。但由于 B-树结点中的关键字个数必须大于 Upper(m/2)-1，因此，每次插入一个关键字，不是在树中添加一个叶子结点，而是首先在最底层的某个非终端结点中添加一个关键字，若该结点的关键字不超过 m-1，则插入完成，否则要产生结点,分裂,。
例,在如下的 3阶 B-树上分别插入 30,26,85和 7
45
50 100
24
37
53 90
3 12 61 70
a
b
c d
e
f g
h
(图一 )
North China Electric Power University
插入 30 45
50 100
24 53 90
3 12 61 70
a
b
c d
e
f g
h
(图二 )
30 37
插入 26 45
50 100
24 53 90
3 12 61 70
a
b
d
e
f g
(图三 )
26 30 37c
将 26插入 d后，由于 d中的关键字数目超过 2，此时将 d分裂为两个结点,关键字 26及其前后两个指针留在 d中，而 37及其前后两个指针存储到新产生的结点 d‘中，同时将 30和指示结点 d’的指针插入到双亲节点 b中。由于 30插入 b后没超过 2,则插入完成。
h
North China Electric Power University
45
50 10026
53 90
3 12 61 70
a
b
c d
e
f g
h
(图四 )
24 30
37
d’
插入 85
45
50 10026
53 90
3 12 61 70 85
a
b
c d
e
f g
h
(图五 )
24 30
37
d’
85插入 g后,需分裂成两个结点 g,g‘,70插入到 e中,由于 e中关键字 >2个,所以,e又分裂为 e,e‘,70插入 a中。 g,e分裂后的图分别见图六、图七：
North China Electric Power University
45
50 10026
53 70 90
3 12
a
b
c d
e
f g
h
(图六 )
24 30
37
d’
61
g’
85
50 10026
45 70
3 12
a
b
c d
e’
f g
h
(图七 )
24 30
37
d’
61
g’
85
53 90e
North China Electric Power University
插入 7
50 10026
45 70
3 7 12
a
b
c d
e’
f g
h
(图八 )
24 30
37
d’
61
g’
85
53 90e
50 10026
45 70a
b
c d
e’
f g
h
(图九 )
7 24 30
37
d’
61
g’
85
53 90e
3 12
c’
North China Electric Power University
50 10026
24 45 70a
b
c d
e’
f g
h
(图十 )
37
d’
61
g’
85
53 90e
3 12
c’
7 30
50 10026
a
b
c d
e’
f g
h
(图十一 )
37
d’
61
g’
85
53 90e
3 12
c’
7 30
b’
b’
24 70
45
a’
m
North China Electric Power University
North China Electric Power University
一般情况，结点可如下实现,分裂,。 假设 p节点中已有 m-1
个关键字，但插入一个关键字之后，结点中含有信息为：
此时,可将 P节点分裂为 P和 P‘两个节点,
P
P
P'
即把关键字 K 插入到它的父亲结点中，因此在父亲结点中指针 P和 P'是按如下顺序被放置的。
...,P,K,P'...
m/2
m/2
m,A0,K1,A1,K2,A2,,..,Km Am
,A0,K1,A1,…,K,Am/2 -1 m/2 –1 m/2 -1
m- m/2,A,K,A,...Km,Amm/2 m/2 +1 m/2 +1
North China Electric Power University
在 B-树上插入关键字的算法：
Procedure mbinsert(t:mblink;k:KeyType);
Begin
x:=k; ap:=nil; {(x,ap)为插入的一对关键字和指针 }
(q,i,tag):=mbsearch(t,k);{应插入的位置是 q结点中第 i+1个关键字 }
while q< > Nil Do
[ call insert(key,i+1,x);{x插入在数组 key中第 i+1个分量之前 }
call insert(a,i+1,ap);{ap插入在数组 a中第 i+2个分量之前 }
n:=n+1; If n<=m-1 then [call store(n,key,a,q);Return;]
{将插入后的信息存入 q结点 }
s:=[m/2];{取中间位置 }
call move(key,key1,s+1);{将数组 key中从 s+1至 m的分量传送到
key1数组中 }
call move(a,a1,s);{将数组 a中从 s至 m的分量传送到 a1数组中 }
new(q1);
call store(s-1,key,a,q);call store(n-s,key1,a1,q1);
North China Electric Power University
x:=key[s];ap:=q1;{组成一对新的插入信息 }
If q↑.Parent< >Nil then
[ q:=q↑.Parent;
call fetch(q,n,key,a);{取出 q结点的全部信息 }
i:=search(key,x); {继续插入至双亲结点上 }
]
]
new(t);
call store(1,q,x,ap,t);{生成新的根结点信息 }
End;
B-树的删除：
首先要找到关键字所在的结点，并从中删除之，若该结点为最下层非终端结点，其中关键字的数目大于等于 Upper(m/2)，则删除完成，否则要进行,合并,结点的操作。假若所删关键字为非终端结点中的 Ki,则以指针
Ai所指子树中的最小关键字 Y代替 Ki,然后在相应的最下层非终端结点中删去 Y。由此可见，不管删除什么位置的结点中的关键字都要变为删除最下层非终端结点中的关键字。
下面分三种情况讨论：
1)被删关键字所在最下层非终端结点中的关键字数目不小于
Upper(m/2),则只需从该结点中删去关键字 Ki和相应指针 Pi，树的其它部分不变。
North China Electric Power University
45
50 100
24
37
53 90
3 12 61 70
a
b
c d
e
f g
h
删去 12
45
50 100
24
37
53 90
61 70
a
b
c d
e
f g
h3
North China Electric Power University
2)被删关键字所在最下层非终端结点中的关键字数目等于
Upper(m/2)-1,而与该结点相邻的右或左兄弟结点的关键字数目
>Upper(m/2)-1,则需将其兄弟结点中的最小右兄弟或最大左兄弟的关键字上移至双亲结点中,而将双亲结点中小于或大于该上移关键字的关键字下移至被删关键字所在结点中。
删去 50
45
5053 100
24
37
61 90b
d
e
f g
h70
45
50 100
24
37
53 90
61 70
a
b
c d
e
f g
h3
c 3
North China Electric Power University
3)被删关键字所在最下层非终端结点和其相邻的兄弟结点中的关键字数目都等于 Upper(m/2)-1时,假设该结点有右兄弟,且其右兄弟结点地址由双亲结点指针 Aj所指，则在删去关键字之后,它所在结点中剩余的关键字和指针加上双亲结点中的关键字 Kj,一起合并到 Aj所指兄弟结点中 (若无右兄弟,则合并至左兄弟结点中 )。
删去 5345
5053 100
24
37
61 90b
d
e
f g
h70c 3
45
100
24
37
90b
d
e
g
hc 3 61 70 100
45 90 e
g h
61 703 24
删去 37
North China Electric Power University
North China Electric Power University
B+-树
m阶的 B+-树的定义如下：
1)每个非叶结点至可以至多可以有 m个儿子；
2)每个非叶结点 (根结点除外 )必须有 m+1/2 个儿子；
3)根结点至少有两个儿子；
4)有 k个儿子的非叶结点有 k个关键字；
5)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
B+-树和 B-树的主要区别：
1)有 n棵子树的结点中含有 n个关键字 (B树中含有 n-1个关键字 )；
2)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针,且叶子结点本身依关键字的大小从小到大顺序链接；
3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树中最大 (或最小 )的关键字。
North China Electric Power University
下图为一棵 m=2阶 B+-树的例子
70 95
40 70 95
20 40 51 70 91 95
10 20 35 40 44 51 65 70 85 91 93 95
5
10
11
20
30
35
40 44 47
51
61
65
70 80
85
91 92
93
95
North China Electric Power University
通常在 B+-树上有两个头指针：一个指向根结点；另一个指向关键字最小的叶子结点。因此，可以对 B+-树进行两种查找运算，一种是从最小关键字起顺序查找，另一种是从根结点开始随机查找。
在 B+-树上进行随机查找、插入和删除的过程基本上与
B-树类似。只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是沿着左边的指针继续向下直到叶子结点。因此，在 B+-树上，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
数字查找树,又称键树，它是一棵度 ≥ 2的树，树中每个结点不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字是数字，则结点中只包含一个数位，若关键字是单词，则结点中只包含一个字母。
例如,有如下 16个字的关键字的集合 {CAI,CAO,Li,LAN,CHA,
CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,
WU,CHEN} 可对此集合作如下逐层分割：
首先按其首字符的不同将它们分成 5个集合,{CAI,CAO,CHA,
CHANG,CHAO,CHEN},{WEN,WANG,WU},{ZHAO},{LI,LAN,
LONG,LIU},{YUN,YANG},
然后对其中 4个关键字个数大于 1的集合再按其第二个字母的不同进行分割。若所得子集的关键字个数多于 1个，则还需按第三个字符不同再进行分割。依此类推，直至每个子集中只包含一个关键字为止。例如对首字符为 C的集合进行如下分割 {{(CAI),(CAO)},{
{{(CHA),(CHANG),(CHAO),(CHEN)}},显然，如此集合、子集和元素之间的层次关系可以用一棵树来表示，这棵树便为键树。
North China Electric Power University
C
A H
I O
$ $
A
$ N O
E
N
G
$
$ $
L
A I O
N
$
U N
G$
$
W
A E U
N N $
G $
$
Y
A
N
G
$
U
N
$
Z
H
A
O
$
树中根结点的五棵子树分别表示首字符为 C,L,W,Y和 Z的五个关键字子集。从根结点到叶子结点路径上所有结点的字符组成的字符串表示一个关键字，叶子结点中的特殊符号 $表示字符串的结束。
North China Electric Power University
为了查找和插入方便，我们约定键树是有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符 $小于任何字符。
通常，键树有两种存储结构：
1)以树的孩子兄弟链表来表示,则树中每个结点包含三个域：
Symbol域：存储关键字的一个字符；
Son域：存储指向第一棵子树的根的指针；
Brother域：存储指向右兄弟结点的指针；
同时，叶子结点的 Son域存储指向关键字记录的指针。
此时的二叉树又称为双链树。
双链树的查找过程如下：假设给定值为 k(1..n+1),其中 k[1]至 k[n]表示待查关键字中 n各字符,k[n+1]为结束符 $,从双链树的根指针出发，顺 Son指针找到第一棵子树的根结点，以 k[1]和此结点的
Symbol域比较，若相等，则顺 Son域再比较下一字符，否则沿
Brother域顺序查找，若 Symbol<k[1]说明查找的关键字不存在，要进行插入。若查找成功,Search单元中存放已查到的关键字，否则为 Nil.
North China Electric Power University
数据类型说明：
Const length=20;bland=‘$’;
Type ptr=↑node;
node=Record
Symbol:Char; Son:ptr; Brother:ptr;
End;
rptr=↑object;
object=Record
key:Array[1..length] of Char;
End;
Var search:ptr;
{在调用 rdlb之前,search=Nil}
Procedure rdlb(var tree:ptr;var recpte rptr;k:Array [1..length]
of Char);
Var i,j:Integer;
found,past:Boolean;
p,q,father,s:ptr;
North China Electric Power University
Function insert:rptr;
Begin
new(s); s↑.Symbol:=k[i]; s↑.Brother:=p;
if tree=Nil then tree:=s
else if q < >Nil then q↑.Brother:=s
else if father=Nil then tree:=s
else father↑.Son:=s;
j:=i;{insert remaining symbols of the k}
while k[j]< >blank Do
[ father:=s;new(s);
s↑.Symbol:=k[j+1];
father↑.Son:=s;
s↑.Brother:=Nil;j:=j+1
]
s↑.Son:=recptr;
insert:=recptr;
End;
North China Electric Power University
Begin
p:=tree;father:=nil;{father is the father of p}
found:=false;i:=1;
while not found Do
[ q:=Nil; {在兄弟间 q尾随 p}
past:=false;
while (p< >Nil) and (not past) Do
if p↑.Symbol>=k[i] then past:=true
else [q:=p;p:=p↑.Brother;]
found:=true;
if (p=Nil) or (p↑.Symbol>k[i]) then search:=insert{插入记录 }
else if k[i]=bland then search:=p↑.Son{已查到待查关键字 }
else [ father:=p;p:=p↑.Son;found:=false;
i:=i+1; {当 p=k[i]时，准备 p↑.Son是否等于 k[i+1]}
]
]
End;
North China Electric Power University
键树中每个结点的最大度 d和关键字的“基”有关，若关键字是单词，则 d=27,若关键字是数值，则 d=11。键树的深度 h取决于关键字中字符或数位的个数。假设关键字是随机的（即关键字中每一位取基内任何值的概率相同），则在双链树中查找每一位的平均查找长度为 1/2(1+d)。
2)以树的多重链表表示键树,则树的每个结点中有 d个指针域，此时的键树又称为 Trie树。若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上的所有结点压缩成一个“叶子结点”，且在该叶子结点中存储关键字及指向记录的指针等信息。由此，在 Trie树中具有两种结点：分支结点 (含有 d个指针域和一个指示该结点中非空指针域的个数的整数域 )和叶子结点 (含有关键字域和指向记录的指针域 )。在分支结点中不设数据域，每个分支结点所表示的字符由其双亲结点中 (指向该结点 )的指针所在位置决定。
在 Trie树上的查找过程为,从根结点出发，沿和给定值相应的指针逐层向下，直至叶子结点，若该结点中的关键字和给定值相等，则查找成功，否则查找不成功。
North China Electric Power University
Type trieptr=↑nodetype;
nodetype=Record
node=(branch,leaf);
case node of
branch:(ptr:Array[0..26] of trieptr;num:integer);
leaf:(data:KeyType;recptr:↑recordType);
End;
Function triesrch(t:trieptr;k:KeyType):↑recordtype;
Begin
p:=t;i:=1;
while(p< >Nil) and (p↑,node< >leaf) and (i<=k.last) Do
[p:=p↑.ptr[ord(k.ch[i])];i:=i+1;]
{ord将 ch[i]转换成其在字母表中的序号 }
if (p< >Nil) and (p↑.node=leaf) and (p↑.data=k)
then Return(p↑.recptr)
else Return(Nil);
End;
North China Electric Power University
纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。
因此，用这类方法表示的查找表，其平均查找长度都不为零，不同表示方法的差别仅在于：和给定值进行比较的关键字的顺序不同。
对于频繁使用的查找表，希望 ASL=0。即不需要从
,比较,的结果来确定查找成功，只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系 。
★ Hash法什么是 Hash表？
North China Electric Power University
例如：为每年招收的 1000名新生建立一张查找表，其关键字为 xx000--xx999(前两位为年份 )。则可以下标为
000--999 的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。
但是，对于动态查找表而言,1) 表长不确定； 2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况，需建立一个函数关系，以 f(key)作为关键字为 key的记录在表中的位置，通常称这个函数
f(key)为哈希函数。 (注意：这个函数并不一定是数学函数 )
简单地说,哈希表是基于哈希函数建立的一种查找表。
North China Electric Power University
例如：对于如下 9个关键字
{ Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei }
13 8 9 6 11 1 4 12 2
设从这个例子可见，
1.哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可 ;
2.由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生,冲突,现象，即,key1< >key2
，而 f(key1) = f(key2),并且，改进哈希函数只能减少冲突，而不能避免冲突。
North China Electric Power University
因此，在设计哈希函数时，一方面要考虑选择一个,好,
的哈希函数 ;另一方面要选择一种处理冲突的方法。
所谓,好,的哈希函数，指的是，对于集合中的任意一个关键字，经哈希函数,映象,到地址集合中任何一个地址的概率是相同的。称这类哈希函数为,均匀的,哈希函数
。
根据设定的哈希函数 H(key)和所选中的处理冲突的方法，
将一组关键字映象到一个有限的、地址连续的地址集 (区间 )上，并以关键字在地址集中的,象,作为相应记录在表中的存储位置，这种表被称为哈希表。Hash法的关键在于哈希表的构造和冲突的处理
North China Electric Power University
哈希函数的构造方法对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。
1.直接定址法哈希函数为关键字的线性函数
H(key) = key 或者 H(key) = a*key + b
仅限于：地址集合的大小 = 关键字集合的大小例 有一个从 1到 100岁的人口数字统计表,用年龄做关键字，
它采用的 hash函数是第一种 H(K)=K,即 j=k。
地址 01 02 03 … 25 26 27 28 … 100
年龄 1 2 3 … 25 26 27 28 … 100
人数 3000 2000 5000 … 1020 2070 7001 7200 … 10
North China Electric Power University
2.数字分析法例 有七个 8位十进制的关键字（有七个关键字，每个关键字都具有八位十进制数），将其散列在地址为 10-90的表中。
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 地址
k1,5 4 2 4 2 2 4 2 42
k2,5 4 2 8 1 3 6 7 83
k3,5 4 2 2 2 8 1 7 28
k4,5 4 2 3 8 9 6 7 39
k5,5 4 2 5 4 1 5 7 51
k6,5 4 2 6 8 5 3 7 65
k7,5 4 2 1 9 3 5 5 13
仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。
假设关键字集合中的每个关键字都是由 s位数字组成
(k1,k2,…,kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
North China Electric Power University
3.平方取中法若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过,平方,扩大差别
，同时平方值的中间几位受到整个关键字中各位的影响,
4.折迭法若关键字的位数特别多，则可将其分割成几部分，
然后取它们的叠加和为哈希地址。相加的方法有移位法和折叠法。
折叠法：把一关键字看承一张纸条，从一端向另一端沿边界逐层折叠，再把相应的位数加在一起。
移位法：将各部分的最后一位对齐，然后相加。
假定关键字,K=d1d2d3… drdr+1… d2rd2r+1… d3r允许有的存储地址有 r位。
North China Electric Power University
移位法,d1 d2 … dr
dr+1 dr+2 … d2r
+ d2r+1d2r+2… d3r
高进位不要了 得到 r位的存储地址折叠法,d3r d3r-1… d2r+1
dr+1dr+2 … d2r
+ dr dr-1 … d1
d1' d2' … dr'高进位不要了 得到 r位的存储地址例如,K=32834872，允许存储地址为三位十进制数。
位移法,328 折叠法,27
348 348
+ 72 + 823
748 1198
H(K)=748 H(K)=198
North China Electric Power University
5.除留余数法实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况 (包括关键字的范围和形态 )，总的原则是使产生冲突的可能性降到尽可能地小。
设给出关键字 k，存储单元数为 m,则可选一数 p(p<=m)去除 k得到余数 r(以 p为模 )，再用一线性函数 f将 r转换为散列地址 j,即 r=(k) mod p,j=f(r)
例 有一组关键字从 000001-859999，指定的存储单元地址为
1000000-1005999,即 m=6000。选 p=5999 k=172148
r=(172148) mod 5999=4176(mod 5999)
f=1000000+r=1004176
在这里选择 p是关键步骤，若 P为偶数，则凡是奇数的关键字，
都转换为奇数地址，则凡是偶数的关键字地都转换为偶数地址，
显然会出现冲突。一般情况,(1)P尽量接近 m;(2)p为质数。
North China Electric Power University
§ 8.3.2处理冲突的方法处理冲突的方法开放定址法链地址法线性探测再散列二次探测再散列伪随机探测再散列探测,检查关键字是否与 hash向量元素相匹配。
North China Electric Power University
一,开放定址法假设哈希空间为 T(0:m-1),哈希函数为 j=H(key)。
为求得下一个哈希地址,可取 ji=(j+di) MOD m，
i=1,2,3,...,s(s≥ 1),其中 m为哈希表的表长
di为增量序列 。
1.当取 di=1,2,3,....,s时称为 线性探测再散列例如,有一个关键字序列 19,70,33,已存入长度为 16的哈希表中 。
取哈希函数为除留余数法,j=k MOD 13；
North China Electric Power University
0 1 … 4 5 6 7 8 … 15
… …70 19 33 18
现在要把关键字为 18的记录填入表中：
j=18 MOD 13=5 冲突 1次
j1=(5+1)MOD 16=6 冲突
j2=(5+2)MOD 16=7 冲突
j3=(5+3)MOD 16=8 不冲突
Hash地址 是否冲突 冲突次数
2次
3次
j=19 MOD 13=6； j=70 MOD 13=5； j=33 MOD 13=7
North China Electric Power University
2.当取 di=12,-12,22,-22,…,n2,-n2 时称为,
二次探测再散列仍以上例为例,70,19,33已填入哈希表中，再填入关键字为 18的记录,
j1=(5+1) MOD 16=6
0 1 … 4 5 6 7 8 … 15
… …70 19 3318
j=18 MOD 13=5 冲突 1次
Hash地址 是否冲突 冲突次数
j2=(5-1) MOD 16=4 不冲突
2次冲突
North China Electric Power University
3.当取 di=伪随机序列时称为 伪随机探测再散列伪随机序列：随机产生的 n个随机数，表示为
d1,d2,…,dn 伪随机函数为,di =(a*di-1+b) Mod Q
j=18 MOD 13=5 冲突 1次
0 1 … 4 5 6 7 8 … 15
… …70 19 3318
2
仍用上例为例,19,70,33已存入再填入 18，
若伪随机数序列为 13,15,7,2,35,…
Hash地址 是否冲突 冲突次数
j1=(5+13)MOD 16=2 不冲突
North China Electric Power University
说明：
线性探测法可以探测到哈希表中的各个位置，但它容易产生,堆聚,现象。例如，关键字为 21的记录，
由哈希函数得到哈希地址为 8，则产生冲突。但是这种冲突不是由同义词所引起的，而是在解决同义词冲突的过程中又添加出的非同义词冲突。这种现象会使探测次数增加，对查找极为不利。
二次探测法可减少,堆聚,,但由于它不能保证探测到哈希表中的所有位置，所以即使哈希表未满，
也有可能探测不到,空,的位置。（只有当 m=4j+3
(j=1,2,3...)时才能探测到整个哈希表空间。）
North China Electric Power University
伪随机探测法可较好地避免,堆聚,,但应该要求所使用的伪随机数序列能均匀地取 [0:m-1]
中的数。
注意：
按上述方法建立起来的哈希表上一般是不能进行删除操作的 。 因为一旦删除某一记录,探测的地址序列即被中断,从而无法再查到具有相同哈希函数值的后继记录,若要删除,则需要在该记录的位置上填入一个特殊标记 。
另外,当某记录探测不到,空,位置时,需要作相应的溢出处理,将该记录存入溢出表 。 溢出表的结构可以是别的表 。
North China Electric Power University
例如 下列一组关键字在哈希函数 H(key)=key mod
13时,用链地址法处理冲突时的哈希表如下,
0 1 2 3 4 5 6 7 8 9 10 11 12
01
^ ^ ^ ^ ^ ^
(19,14,23,01,68,20,84,27,55,11,10)
二、链地址法将所有关键字为同义词的记录存储到同一线性链表中。
14
55
68
19
84
10
23
^ ^ ^
20
^
11
^
27
^
North China Electric Power University
§ 8.3.3 哈希表的查找设表长为 n的哈希表中，采用线性探测技术查找，插入记录 R,R的地址为 i,R在 A表或溢出表 of1中由 tag等于 0或等于 1标志。
0 在 A表中
1 在 of1表中 (溢出表 )tag=
North China Electric Power University
PROC Lineasrchhash(R,A,n,i,tag);
BEGIN
j:=Hash(R.key)
i:=j-1; tag:=0;
Repeat
i:=(i+1) mod n ｛线性探测｝
Until (A[i].key=R.key) or (A[i]=ф) or (i=j-1);
If A[i].key=R.key ｛查找成功｝
Then write('successful R"s address=',i)
Else If A[i]=ф then
[ A[i]:=R;Write(‘Unsuccessful R Address=‘,’i);
else [ search overflowList(of1,R,i);tag:=1 ]
END;
North China Electric Power University
If q↑record.key=R.key ｛查找成功｝
then [write('hash chain sucessful');exit ]
下面给出采用链地址技术查找，插入记录 R的算法：
Procedure chaininghash(A,R);
｛在哈希表 A中，采用链地址技术查找、插入记录 R｝
Begin
j:=Hash(R.key);
If A[j]≠nil then
[ q:=A[j];
while (q↑.record.key≠R.key) and (q↑.next≠nil) do
q:=q↑.next;
North China Electric Power University
Else [ {A[j]=Nil的情况 }
write('hash chain unsucessful');
new(p);p↑.record:=R;
p↑.next:=nil; A[j]:=p ]
｛ 查找不成功,插入记录 R｝
End;
Else [ write('hash chain unsucessful');
new(p); p↑.record:=R;
p↑.next:=nil; q↑.next:=p ]
]
North China Electric Power University
Hash法的性能分析
North China Electric Power University
决定哈希表查找的 ASL的因素：
一般情况下，可以认为选用的哈希函数是,均匀,
的，则在讨论 ASL时，可以不考虑它的因素。
因此哈希表的 ASL是处理冲突方法和装载因子的函数。
1.选用的哈希函数
2.选用的处理冲突的方法
3.哈希表饱和的程度，装载因子 α =n/m 值的大小。
可以证明：
查找成功时有下列结果：
线性探测再散列随机探测再散列链地址法
North China Electric Power University
对静态查找表，有时也可能找到不发生冲突的哈希函数。即此时的哈希表的 ASL=0,此类哈希函数为理想 (perfect)的哈希函数。
★ 基本概念
★ 静态查找表
★ 动态查找表
★ Hash法
North China Electric Power University
查找表,是一种以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构。
关键字,用来标识数据元素的数据项，简称键。
★ 基本概念主关键字,可以唯一标识一个数据元素的关键字。
次关键字,可以标识若干数据元素的关键字。
查找,根据某个给定的 K值，在查找表中寻找一个键值等于 K的元素，若找到这样的元素，
则称查找成功，此时的运算结果为该数据元素在查找表中的位置，否则称查找不成功，运算结果为一特殊标志。
North China Electric Power University
North China Electric Power University
查找表静态查找表动态查找表
1.建表,Create(st)
2.查找,Search(st,k)
3.读表元,Get(st,pos)
2.查找,Search(st,k)
3.读表元,Get(st,pos)
1.初始化,Initiate(st)
4.插入,Insert(st,k)
5.删除,Delete(st,k)
North China Electric Power University
★ 静态查找表
1)顺序表上的查找,以顺序表作为存储结构，然后在这个存储结构上实现静态查找表的基本运算。
顺序表类型定义如下：
Const maxsize=静态查找表的表长 ;
Type Rec=Record
key:KeyType;
…
End;
sqTable=Array[0..maxsize] of Rec; n:Integer;
顺序查找过程,假定该查找表有 n个记录，首先将要查找的那个关键字赋给实际上并不存在的第 n+1个记录的关键字域，然后从头开始一个一个的向下查找，用 i来计数,查到就送出来看 i是第几个，若 i<=n，则查找成功，若 i=n+1
则查找失败。
North China Electric Power University
Procedure SqSearch(r:sqTable;k:KeyType);
Begin
r[n+1].key:=k;
i:=1;
while (r[i].key< >k) Do
i:=i+1;
if i<=n then Write(‘Succ i=’,i)
else Write(‘Unsucc’);
End;
平均查找长度,为确定某元素在表中某位置所进行的比较次数的期望值。
在长度为 n的表中找某一元素，查找成功的平均查找长度,
ASL=∑P iCi
North China Electric Power University
Pi,为查找表中第 i个元素的概率
Ci,为查到表中第 i个元素时已经进行的比较次数在顺序查找时,Ci取决于所查元素在表中的位置，
Ci =i,设每个元素的查找概率相等，即 Pi=1/n,则,
ASL=∑P iCi=(n+1)/2
查找不成功的查找长度为 n+1。
顺序查找表的优点,算法简单且适应面广，对表的结构无任何要求，无论元素是否按关键字有序都可应用。
顺序查找表的缺点,平均查找长度比较大，特别是当 n
较大时，查找效率较低。
North China Electric Power University
2)折半查找 (有序表上进行查找 )：
基本思想,设三个指针 low,high和 mid分别指示待查有序表的表头，表尾和中间元素，在开始查找时，三个指针的初值分别为,low:=1;high:=n;mid:=(low+high)
div 2 。折半查找是从表的中间元素开始，用待查元素的关键字 k和 r[mid].key比较，此时有三种情况 (假设该查找表按关键字的非递减次序排列 ),
1) 若 r[mid].key=k，则查找成功；
2) 若 r[mid].key>k，则 k必在较低标号的那一半表中，
令 high:=mid-1
3) 若 r[mid].key<k，则 k必在较高标号的那一半表中，
令 low:=mid+1
再取中间项进行比较，直到查找成功或 low>high(查找失败 )为止。
North China Electric Power University
例：给出表元素关键字为,{05,13,19,21,37,56,64,75,80,88,92}
1.查找关键字 k=21 的情况
(1) low:=1;high:=11;mid:=(1+11) div 2=6
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key>k，所以向左找，令 high:=mid-1=5
(2) low:=1;high:=5;mid:=(1+5) div 2=3
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key<k，所以向右找，令 low:=mid+1=4
(3) low:=4;high:=5;mid:=(4+5) div 2=4
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key=k，查找成功，所查元素在表中的序号为 mid 的值
North China Electric Power University
(1) low:=1;high:=11;mid:=(1+11) div 2=6
因为 r[mid].key<k，所以向右找，令 low:=mid+1=7
(2) low:=7;high:=11;mid:=(7+11) div 2=9
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key<k，所以向右找，令 low:=mid+1=10
(3) low:=10;high:=11;mid:=(10+11) div 2=10
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 r[mid].key>k，所以向左找,high:=mid-1=9
2.查找关键字 k=85 的情况
05 13 19 21 37 56 64 75 80 88 92
low mid high
因为 low>high，所以查找失败
North China Electric Power University
Procedure BinSearch(r:sqTable;k:KeyType);
Begin
low:=1;
high:=n;
while low<=high Do
[ mid:=(low+high) div 2;
Case
k>r[mid].key,low:=mid+1;
k=r[mid].key,[Write(mid);Return;]
k<r[mid].key,high:=mid-1;
EndCase;
]
Write(‘Unsucc’);
End;
North China Electric Power University
Procedure BinSearch(r:sqTable;k:KeyType,l,h:Integer);
Begin
low:=l;
high:=h;
if high<low then [Write(‘Unsucc’);Return;]
mid:=(low+high) div 2;
Case
k>r[mid].key,[low:=mid+1;BinSearch(r,k,low,high);
k=r[mid].key,[Write(mid);Return;]
k<r[mid].key,[high:=mid-1;BinSearch(r,k,low,high);
EndCase;
End;
递归算法描述如下：
算法的性能分析：
North China Electric Power University
以上面的 11个元素的查找表为例，找到第 6个元素仅需比较 1次；
找到第 3个和第 9个元素需比较 2次；找到第 1,4,7和 10个元素需比较
3次；找到第 2,5,8和 11个元素需比较 4次。上面的查找过程可以用下图所示的一棵二叉树来表示。
6
3 9
1 4 7 10
112 5 8
树中每一个结点表示表中的一个数据元素，结点中的值为该元素在表中的位置折半查找的平均查找长度为 log2(n+1)-1
找不到元素的过程：正好是从根节点一直走到某个叶子节点的路径，因此所用的比较次数最多等于树的深度。由此看来，无论元素找到或找不到,查找某一元素的比较次数最多等于树的深度,即 log2n 。
那么引出一个问题，折半查找的平均查找长度是多少?
我们用深度为 h的满二叉树描述折半查找来进行分析。
满二叉树的特点是：
层次为 1的结点有 1个 ;
层次为 2的结点有 2个 ;
…,
层次为 h的结点为 2h-1 个 。
若是完全二叉树则节点数 n=2h -1
那么表的长度一定为 n=2h-1,我们假定表中每个元素的查找概率相等,(Pi=1/n),则平均查找长度为,
ASLnS=∑CiPi=1/n∑j*2 j-1i=1n j=1n =(n+1/n)*log2(n+1)-1
North China Electric Power University
North China Electric Power University
3)分块查找,这种查找方法是表里的元素均匀的分成若干块，块与块之间是有序的，块中的元素是无序的，这种查找方法又称为索引顺序查找。
在分块查找中对每一块建立一个索引项，其中包括两项内容：关键字项 (其值为最大关键字或最小关键字 )和指针项 (指示该块的第 1个记录在表中的位置 )。索引表按关键字有序，表分块有序。
分块有序：指第二块中所有记录的关键字均大于 (或小于 )
第一块中最大 (或最小 )关键字，第三块中的所有关键字均大于 (或小于 )第二块中的最大 (或最小 )关键字 …,以此类推。
例,有一个表,各元素的关键字为,
｛ 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47}
把它平均分成三块，按上升的次序排列，如下图所示：
North China Electric Power University
22
12
13
9
8
33
42
44
38
24
48
60
58
74
47
1
2
3
4
5
6
7
8
9
10
11
12
13
1415
第一块第二块第三块
1
6
11
22
44
74
关键字表小大指针表,应该指向各块的第一个关键字。
分成三块每块 5个关键字分块查找的方法,
1)由于索引表按关键字有序，则确定 k在哪一块的查找可以用顺序查找，也可用折半查找。
North China Electric Power University
2)块中的记录是任意排列的，则在块中只能用顺序查找。
分块查找的平均查找长度应该是前两者之和：
即,ASLbs=Lb+Lw
Lb:为查找所在块的平均查找长度。
用顺序查找方法,确定所在的块,则 Lb=1/b∑jj=1
b
用顺序查找方法,查找的元素所在位置,则 Lw=1/s∑ ii=1s
已知表的长度为 n,分成 b小块,每块有 s个元素,那么 b=n/s.若表中各元素的查找概率相等,那么每块的查找概率为 1/b,块中每个元素的查找概率为 1/s.
Lw:为块中查找元素的平均查找长度。
North China Electric Power University
ASLbs=1/b∑j+1/s∑i =(b+1)/2+(s+1)/2
=1/2(n/s+s+2)=1/2(n/s+s)+1j=1
b
i=1
s
可以证明,当 s= 时，平均查找长度最小 = +1
由上式可以看出，分块查找的平均查找长度不仅和表的长度 n有关，而且和每一块中的元素个数 s有关。
n n
用折半查找确定所在的块，则分块查找的平均查找长度为 ASLbs =log2(b+1)-1+(s+1)/2
=log2(n/s+1)+(s-1)/2
分块查找的算法描述如下：
Function Search_idx(st:sqTable,Id:IndexTable;k:KeyType):Integer;
{st为查找表,Id为索引表,k为待查关键字 }
Begin
low:=1;high:=Id.Length;found:=false;
while (low<=high) and (found=false) Do
[ mid=(low+high) div 2;
if(k<Id.Elem[mid].Key) then high:=mid-1
else if (k>Id.Elem[mid].key) then low:=mid+1
else [ found:=true;low:=mid;] ]
s:=Id.Elem[low].stadr;
{经索引表查找后，下一步的查找范围定位在第 low块 }
if (high<Id.Length) then t:=Id.Elem[low+1].stadr-1 else t:=st.length;
if(st.Elem[t].key=k) then Return(t)
else [ st.Elem[0]:=st.Elem[t+1];st.Elem[t+1].key:=k;i:=s;
while (st.Elem[i].Key< >k) Do i:=i+1;
st.Elem[t+1]:=st.Elem[0];
if i< >t+1 then Return(i) else Return(0); ] End;
North China Electric Power University
三种查找方法的比较,
就 平均查找长度 而言，折半查找最小，分块查找次之，顺序查找最大。
就 表的结构 而言，顺序查找对有序表和无序表均可应用，折半查找仅适用有序表，而分块查找要求表中数据是分块有序的，即需要把表分成若干块，块与块之间的记录按关键字有序。
就 表的存储结构 而言，顺序查找和分块查找对两种存储结构 --向量和链表均适用，而折半查找只适用于以向量做存储结构的的表，这就要求表中的元素基本不变，否则，当进行插入和删除运算时为保持表的有序性，便要移动元素，这在一定程度上降低折半查找的效率。
★ 动态查找表二叉排序树,或者是一棵空树，或者是具有下列性质的二叉树,1)若它的左子树不空，则它的左子树上所有结点的值均小于根结点的值； 2)若它的右子树不为空，则它的右子树上所有结点的值均大于或等于它的根结点的值； 3)它的左、右子树均为二叉排序树。
North China Electric Power University
二叉排序树的构造方法：
设 R={R1,R2,…,Rn}为一数列,按下面的原则建立二叉树：
1)令 R1为二叉树的根；
2)若 R2<R1，则令 R2为 R1的左子树的根结点，否则令 R2为
R1的右子树的根结点；
3)对 R3,R4,… Rn重复上述步骤 2)；
North China Electric Power University
例：给定 R={10,18,3,8,12,2,7,3}按上面的原则构造二叉排序树如下：
R2R1 R310
R1为根节点 R3<R1
R2
R2比 R1大
R4
R4<R1 左边
R4>R3 右边
R5
R5>R1 右边
R5<R2 左边
R6
R6<R1 左边
R6<R3 左边
R7
10
18
10
183
10
183
8
10
183
8 12
10
183
8 122
10
183
8 122
7
10
183
8 122
7
3
R8
R7<R1 左边
R7>R3 右边
R&<R4 左边
R8<R1 左边
R8>R3 右边
R8<R4 左边
R8<R7 左边
North China Electric Power University
算法描述如下：
Procedure sortree(m,r,p);{建立一个含有 m 个结点 r[i](1≤i≤m) 的二叉排序树,p为指向二叉树根结点的指针 }
Procedure bsinsert(s,t);{将 s所指结点插入到根结点指针为 t的树中 }
Begin
if t=Nil then t:=s
else if s↑.data<t↑.data
then bsinsert(s,t↑.lchild) else bsinsert(s,t↑.rchild);
End;
Begin
new (q); q↑.data:=r[1];q↑.lchild:=Nil;q↑.Rchild:=Nil;
p:=q;
For i:=2 to m Do
[ new(q); q↑.data:=r[i]; q↑.lchild:=Nil;
q↑.rchild:=Nil; bsinsert(q,p);]
End;
North China Electric Power University
二叉排序树的查找已知要找的那个记录的关键字 k,从根结点的关键字开始比较，有下列三种情况：
1)若两者相等,则说明查找成功,根结点的记录为所找记录
2)若 k小于根结点的关键字，则继续查找左子树
3)若 k大于根结点的关键字，则继续查找右子树若二叉树为空，则查找失败。
Procedure SortSrch(t:Bitptr;k:KeyType);
Begin
if t=Nil then Write(‘Unsucc’)
else if k=t↑.key then [Write(‘Succ’);call outdata;]
else if k<t↑.key
then SortSrch(t↑.lchild,k)
else SortSrch(t↑.rchild,k);
End;
North China Electric Power University
非递归算法如下：
Procedure SortSrch(i,t:Bitptr;k:KeyType);{在二叉排序树 t中查找 k,每个结点有三个字段 lchild,Key,rchild,若 k不在 t中，则返回 B=1，否则，送回 i,结果 i↑.key=k}
Begin
i:=t; B:=1;{当 B=0时查找成功，否则失败 }
while(i< >Nil) and (B=1) Do
Case
k<t↑.key,i:=i↑.lchild;
k=t↑.key,[B:=0;Write(‘Succ’);]
k>t↑.key,i:=i↑.rchild;
EndCase;
End;
North China Electric Power University
二叉排序树在查找过程中的插入、删除
1)二叉排序树的插入,给定关键字 x,如果 x在二叉排序树中，送出指向 x所在结点的指针，否则将 x插入到二叉排序树的合适位置上。
Procedure Bst(t,j:Bitptr;x:Keytype);
Begin
j:=t; B,=1; p:=Nil;
while (j< >Nil) and (B=1) Do
Case x<j↑.key,[ p:=j;j:=j↑.lchild;]
x=j↑.key,[ B:=0;Write(‘Succ’);]
x>j↑.key,[ p:=j;j:=j↑.rchild;]
EndCase;
if B=1 then [new(j); j↑.key:=x; j↑.lchild:=Nil; j↑.rchild:=Nil;
Case t=Nil,t:=j;
x<p↑.key,p↑.lchild:=j;
x>p↑.key,p↑.rchild:=j; EndCase;]
End;
North China Electric Power University
2)二叉排序树的删除,在二叉排序中删除某个结点，删除此结点后仍保持二叉排序树的性质。
下面这棵二叉排序树，我们要删除结点 2：
2是根结点，它有左、右子树，要删除 2,就要找一个新的根结点，从哪儿找呢?从左子树，在左子树中找一个值最大的结点，此结点仅次于根节点，比右子树的所有结点都小，让这个结点做为根结点。
4
2 6
1 3 12
4
1 6
3 12
p
q,j
s
North China Electric Power University
在算法中用了 4个指针：
j:指向被删除结点 ; s:指向新选择的根结点 ;
p:指向被删除结点的双亲 ;q:指向新选择的根结点的双亲 ;
下面分四种情况进行讨论：
① 被删结点是叶子结点即 j↑.lchild=Nil;j↑.rchild=Nil
s=Nil 为选择的合适结点由于删去叶子结点不影响二叉排序树的结构和性质，
所以只需修改其双亲结点的指针即可。若被删结点是 p
的左子树，则 s →p↑.lchild;若被删结点是 p的右子树，
则 s →p↑.rchild
North China Electric Power University
North China Electric Power University
② 被删结点不是叶子,j无左，仅有右子树，则
s=j↑.rchild,s做 p的左 (或右 )子树。
4
1
3
6
12
4
3 6
12
③ 被删结点不是叶子,j有左，无右子树，则
s=j↑.lchild,s 做 p的左 (或右 )子树
p
j
s
4
1
3
6
12
4
3 6
12
p
j
s
North China Electric Power University
④ j既有左，又有右。则沿 j的左子树的右子树方向找，
一直找到按中序遍历 j的直接前趋结点。此结点作为新选的根结点 s,然后做相应的指针修改。
20
10 30
6 15
3 9 13 18
8
p
j
q
s
20
9 30
6 15
3 8 13 18
在上图中,s↑.rchild=Nil;s↑.lchild< >Nil
修改四个指针,1)s↑.rchild:=j↑.rchild;
2)q↑.rchild:=s↑.lchild;
3)s↑.lchild:=j↑.lchild;
4)p↑.lchild:=s;
North China Electric Power University
20
10 30
6 15
3 9 13 18
p
j
q
s
20
9 30
6 15
3 13 18
在上图中,s↑.rchild=s↑.lchild=Nil,仍做前面的四个操作
20
9 30
6 15
3 13 18
p
j,q
s
20
6 30
3 15
13 18
上图中,s↑.rchild=Nil,且 q=j,修改两个指针：
1)s↑.rchild:=j↑.rchild; 2)p↑.lchild:=s;
North China Electric Power University
下面给出在二叉排序树 T中查找结点 j,使 j↑.key=x,如果 x在 T中，则删除 x结点，否则,送出 B=1，说明此树中无被删结点的算法：
Procedure det(t,j,p:Bitptr;x:KeyType);
{j指向被删结点,p指向其双亲，假设树不空 }
Begin
j:=t;B:=1;p:=Nil;
while (j< >Nil) and (B=1) Do
Case
x<j↑.key:[ p:=j;j:=j↑.lchild;]
x=j↑,key,B:=0;
x>j↑.key:[ p:=j;j:=j↑.rchild;]
EndCase;
North China Electric Power University
If B=0
then [ if j↑.lchild=Nil{被删结点无左子树 }
then s:=j↑.rchild
Else if j↑.rchild=nil then s:=j↑.lchild
else [ q:=j;s:=q↑.lchild;
while s↑.rchild< >Nil Do
[ q:=s;s:=s↑.rchild];s↑.rchild:=j↑.rchild;
if q< >j
then [ q↑.rchild:=s↑.lchild;
s↑.lchild:=j↑.lchild;]
]
if p=Nil then t:=s else
[ if j=p↑.lchild then p↑.lchild:=s
else p↑.rchild:=s; ] ]
End;
平衡二叉树 (balanced binary tree)
平衡二叉树,或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过 1。
平衡因子,二叉树中任一结点的左子树的深度与它的右子树的深度之差称为平衡因子。
例,2-1=1
0-0=01-0=1
0-0=0
平衡二叉树
2-3=-1A
B C
D F
G
1-1=0
0-0=0
0-2=-2
1-0=1
0-0=0
0-0=0
非平衡二叉树
A
B C
D
E
North China Electric Power University
二叉排序树的平衡化假设表中的关键字序列为 (13,24,37,90,53)
① 空树和一个结点 的二叉树显然是平衡二叉树,
② 插入 24后仍平衡
13
13
24
-1
0
③ 插入 后结点 的平衡因子为 0-2=-2，不平衡把 从 的右下侧左转到 的右上侧原来 的左为 的右,
新的 的左为
13
24
370
-1
-2
RR型即逆时针旋转
37 13
13
24
37
24 13
13
24 13
24 13
North China Electric Power University
④ 插入 90,53后,又失去平衡,可经过下列步骤转化为平衡二叉树
13
24
37
90
53
2_
0 2_
1
0
13
24
37
90
53
第一次旋转 (顺时针 )以 为轴心,把 从 的右上,转到的右下,的右是,的右为,原 的右变成新 的左。
RL型的第一次旋转 (顺时针 )
13
24
53
9037
RL型的第二次旋转 (逆时针 )
以 为轴心,把 从 的左上转到 的左下,使得 的左是 ;右是,原 的左变成了 的右。
53 90 53 53
37 53 53 90 53 90
53 37 53 53 53
37 90 53 37
North China Electric Power University
一般情况下，假设由于二叉排序树上插入结点而失去平衡的最小子树的根结点指针为 a（即 a是离插入结点最近,且平衡因子绝对值超过 1的祖先结点），则失去平衡后进行调整的规律可归纳为下列四种情况,
⒈ RR型平衡旋转,
b
a br
a1 b1
RRa
ba1
b1 br
-2
-1
hh-1
h-1
插入节点把结点 b从 a的右下侧逆时针 (左转 )转到 a的右上侧，
原 b的左成为 a的右，新 b的左为 a
North China Electric Power University
0
h
h-1
0
h-1
2.LL型平衡旋转,
LL
2
1
h h-1
h-1
a
b ar
brb1
ab1
br ar
0
0
把结点 b从左下侧顺转 (右转 )转到 a的左上侧,原 b的右成为 a的左,新 b的右为 a。
3.RL型平衡旋转,-2
1
h-11
h-1 a1
c
c1 cr
br
h-1 h-2
RL(顺时针 )
c1
a1
cr br
b
a
b
a
c
b
North China Electric Power University
h
h-1
h-1
h-2
h-1
h-1
-1
-1
-2
以 c为轴心，把 b从 c的右上侧顺时针（右转 )到 c的右下侧，从而 a的右是 c,c的右是 b，原 c的右变成 b的左。
以 c为轴心，把 a从 c的左上方，转到 c的左下方，使得 c的左是 a，右是 b，原 c的左子树变成 a的右。
RL(逆时针 )
c1a1 cr br
4.LR型平衡旋转,
c
a b
以 c为轴心把 b从 c的左上侧，逆时针（左转）到 c的左下侧，从而 a的左是 c,c的左是 b，原 c的左变成新 b的右。
North China Electric Power University
c1
a1
cr br
a
c
bh-1
h-2
h-1
h-1
-1
-1
-2
h-1
h-2
h-1
-10
0
LR(逆时针 )
c1
ar
cr
bl
2
-1
1
h-1
h-1 h-2
ar
c1 cr
b1h-1
LR(顺时针 )
c1 arcrbl
再以 c为轴心，把 a从 c的左上方转到 c的右下方，使得
c的右是 a，左是 b，原 c的右子树变成 a的左。
a
b
c
a
c
b
c
b a
North China Electric Power University
h-1 h-1
h-2
h-1
0
2
2
a
c1
ar
cr
bl
c
b
h-1 h-1
h-2
h-1
0
2
2
h-1
0
h-2
h-1
-1
0
North China Electric Power University
B-树
B-树：一棵 m阶的 B-树，或为空树，或为具有下列性质的 m叉树：
1)树中每个结点有 ≤ m个儿子；
2)除根和叶子结点之外的结点有 ≥ Upper(m/2)个儿子；
3)根结点至少要有两个儿子 (除非它本身又是一个叶子 )；
4)所有的非终端结点中包含下列信息数据 (n,A0,
k1,A1,k2,…,kn,An)；
n：本结点中关键字的个数 ≤ m-1
ki,关键字，从左到右其值按递增次序排列
Ai,指向一个所有关键字都在 ki和 ki+1间的子树形
5)所有的叶子结点都在同一层次上，并且不带信息 (可以看作是查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空 )；
1 18
1 11 1 27
1 35
1 39 1 99
2 43 78
3 47 53 64
a
b c
d e
f
g h
上图中,结点形式为,n 指针 关键字 指针 关键字,....
p0 k1 p1 k2
每一个结点 (除了根结点和叶子 ),有 Upper(4/2)到 4个儿子，
所以可以有 1,2或 3个关键字，根结点允许有 1至 3关键字，此时所有的 叶子都在第四层上。
例：下图所是为一棵 4阶的 B-树，深度为 4
North China Electric Power University
B-树的查找过程：
B-树的查找是一个顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。
结点类型说明如下：
Type mblink=↑mbnode;
mbnode=Record
keynum:integer;
parent:mblink;
keys:Array[1..m-1] of KeyType;
ptrs:Array[0..m-1] of mblink;
End;
Result=Record
p:mblink; i:Integer; tag,(0,1);
End;
North China Electric Power University
查找算法如下：
Function mbsearch(t:mblink;key:KeyType):Result;
Begin
p:=t;q:=nil;key[0]:=-max;{key[0..m]为关键字辅助数组 }
while p< > Nil Do
[ n:=p↑.keynum;key[n+1]:=max;
For j:=1 to n Do
key[j]:=p↑.keys[j];
For j:=0 to n Do
a[j]:=p↑.ptrs[j]; {a[0..m]为指针型辅助数组 }
i:=sqSearch(key,k);
{在数组 key中进行顺序查找直到 key[i]≤k≤ key[i+1]}
if key[i]=k then Return(p,i,1);{查找成功 }
q:=p;p:=a[i]; ]
Return(q,i,0);{查找失败,其中 q,i指示等于 k的关键字在 B-树中应插入的位置 }
End;
North China Electric Power University
在 B-树上进行查找所需时间的分析从上述过程可知，在 B--树上进行查找所需时间取决于两个因素：
⑴等于给定值的关键字所在的层次数 ;
⑵ 结点中关键字的数目。 (较大时可用折半查找 )
显然,节点所在的最大层次数即为树的深度 。 那么,含有 N个关键字的 m阶 B--树的最大深度是多少？
根据 B--树的定义第一层至少有 1个结点第二层至少有 2个结点第三层至少有 2* m/2 个结点
(因为除根之外的每个非终端结点至少有 m/2 个 )
第四层至少有 2* m/2 2个结点
North China Electric Power University
……
最末层 L+1层有 2* m/2 L-1个结点
(因为最末层为叶子,m阶 B树中有 N个关键字,则叶子结点为 N+1
个,由此有 N+1≥2*( m/2 ) L-1
N+1
2 ≥ ( m/2 )
L-1 两边取对数
log( )N+12 ≥ (L-1)log( m/2 )
L-1≤
log( )N+12
log( m/2 )
换底
=
log ( )m/2 N+12
log m/2 2
log ( )m/2 m/2
log m/2 2
North China Electric Power University
=
log ( )m/2 N+12
1 ≤ log ( )m/2
N+1
2
∴L≤ log ( )m/2 N+12 +1
这就是说，在含有 N个关键字的 B--树上，进行查找时，从根 j
结点到关键字所在结点的路径上涉及的结点数不超过
log ( )m/2 N+12 +1个例如,当 N=1999998且 m=199时,L最多为 3。
这就是说，在最坏情况下，一次查找至多需要存取 3个结点。
North China Electric Power University
B-树的插入：
B-树的生成也是从空树起，逐个插入关键字。但由于 B-树结点中的关键字个数必须大于 Upper(m/2)-1，因此，每次插入一个关键字，不是在树中添加一个叶子结点，而是首先在最底层的某个非终端结点中添加一个关键字，若该结点的关键字不超过 m-1，则插入完成，否则要产生结点,分裂,。
例,在如下的 3阶 B-树上分别插入 30,26,85和 7
45
50 100
24
37
53 90
3 12 61 70
a
b
c d
e
f g
h
(图一 )
North China Electric Power University
插入 30 45
50 100
24 53 90
3 12 61 70
a
b
c d
e
f g
h
(图二 )
30 37
插入 26 45
50 100
24 53 90
3 12 61 70
a
b
d
e
f g
(图三 )
26 30 37c
将 26插入 d后，由于 d中的关键字数目超过 2，此时将 d分裂为两个结点,关键字 26及其前后两个指针留在 d中，而 37及其前后两个指针存储到新产生的结点 d‘中，同时将 30和指示结点 d’的指针插入到双亲节点 b中。由于 30插入 b后没超过 2,则插入完成。
h
North China Electric Power University
45
50 10026
53 90
3 12 61 70
a
b
c d
e
f g
h
(图四 )
24 30
37
d’
插入 85
45
50 10026
53 90
3 12 61 70 85
a
b
c d
e
f g
h
(图五 )
24 30
37
d’
85插入 g后,需分裂成两个结点 g,g‘,70插入到 e中,由于 e中关键字 >2个,所以,e又分裂为 e,e‘,70插入 a中。 g,e分裂后的图分别见图六、图七：
North China Electric Power University
45
50 10026
53 70 90
3 12
a
b
c d
e
f g
h
(图六 )
24 30
37
d’
61
g’
85
50 10026
45 70
3 12
a
b
c d
e’
f g
h
(图七 )
24 30
37
d’
61
g’
85
53 90e
North China Electric Power University
插入 7
50 10026
45 70
3 7 12
a
b
c d
e’
f g
h
(图八 )
24 30
37
d’
61
g’
85
53 90e
50 10026
45 70a
b
c d
e’
f g
h
(图九 )
7 24 30
37
d’
61
g’
85
53 90e
3 12
c’
North China Electric Power University
50 10026
24 45 70a
b
c d
e’
f g
h
(图十 )
37
d’
61
g’
85
53 90e
3 12
c’
7 30
50 10026
a
b
c d
e’
f g
h
(图十一 )
37
d’
61
g’
85
53 90e
3 12
c’
7 30
b’
b’
24 70
45
a’
m
North China Electric Power University
North China Electric Power University
一般情况，结点可如下实现,分裂,。 假设 p节点中已有 m-1
个关键字，但插入一个关键字之后，结点中含有信息为：
此时,可将 P节点分裂为 P和 P‘两个节点,
P
P
P'
即把关键字 K 插入到它的父亲结点中，因此在父亲结点中指针 P和 P'是按如下顺序被放置的。
...,P,K,P'...
m/2
m/2
m,A0,K1,A1,K2,A2,,..,Km Am
,A0,K1,A1,…,K,Am/2 -1 m/2 –1 m/2 -1
m- m/2,A,K,A,...Km,Amm/2 m/2 +1 m/2 +1
North China Electric Power University
在 B-树上插入关键字的算法：
Procedure mbinsert(t:mblink;k:KeyType);
Begin
x:=k; ap:=nil; {(x,ap)为插入的一对关键字和指针 }
(q,i,tag):=mbsearch(t,k);{应插入的位置是 q结点中第 i+1个关键字 }
while q< > Nil Do
[ call insert(key,i+1,x);{x插入在数组 key中第 i+1个分量之前 }
call insert(a,i+1,ap);{ap插入在数组 a中第 i+2个分量之前 }
n:=n+1; If n<=m-1 then [call store(n,key,a,q);Return;]
{将插入后的信息存入 q结点 }
s:=[m/2];{取中间位置 }
call move(key,key1,s+1);{将数组 key中从 s+1至 m的分量传送到
key1数组中 }
call move(a,a1,s);{将数组 a中从 s至 m的分量传送到 a1数组中 }
new(q1);
call store(s-1,key,a,q);call store(n-s,key1,a1,q1);
North China Electric Power University
x:=key[s];ap:=q1;{组成一对新的插入信息 }
If q↑.Parent< >Nil then
[ q:=q↑.Parent;
call fetch(q,n,key,a);{取出 q结点的全部信息 }
i:=search(key,x); {继续插入至双亲结点上 }
]
]
new(t);
call store(1,q,x,ap,t);{生成新的根结点信息 }
End;
B-树的删除：
首先要找到关键字所在的结点，并从中删除之，若该结点为最下层非终端结点，其中关键字的数目大于等于 Upper(m/2)，则删除完成，否则要进行,合并,结点的操作。假若所删关键字为非终端结点中的 Ki,则以指针
Ai所指子树中的最小关键字 Y代替 Ki,然后在相应的最下层非终端结点中删去 Y。由此可见，不管删除什么位置的结点中的关键字都要变为删除最下层非终端结点中的关键字。
下面分三种情况讨论：
1)被删关键字所在最下层非终端结点中的关键字数目不小于
Upper(m/2),则只需从该结点中删去关键字 Ki和相应指针 Pi，树的其它部分不变。
North China Electric Power University
45
50 100
24
37
53 90
3 12 61 70
a
b
c d
e
f g
h
删去 12
45
50 100
24
37
53 90
61 70
a
b
c d
e
f g
h3
North China Electric Power University
2)被删关键字所在最下层非终端结点中的关键字数目等于
Upper(m/2)-1,而与该结点相邻的右或左兄弟结点的关键字数目
>Upper(m/2)-1,则需将其兄弟结点中的最小右兄弟或最大左兄弟的关键字上移至双亲结点中,而将双亲结点中小于或大于该上移关键字的关键字下移至被删关键字所在结点中。
删去 50
45
5053 100
24
37
61 90b
d
e
f g
h70
45
50 100
24
37
53 90
61 70
a
b
c d
e
f g
h3
c 3
North China Electric Power University
3)被删关键字所在最下层非终端结点和其相邻的兄弟结点中的关键字数目都等于 Upper(m/2)-1时,假设该结点有右兄弟,且其右兄弟结点地址由双亲结点指针 Aj所指，则在删去关键字之后,它所在结点中剩余的关键字和指针加上双亲结点中的关键字 Kj,一起合并到 Aj所指兄弟结点中 (若无右兄弟,则合并至左兄弟结点中 )。
删去 5345
5053 100
24
37
61 90b
d
e
f g
h70c 3
45
100
24
37
90b
d
e
g
hc 3 61 70 100
45 90 e
g h
61 703 24
删去 37
North China Electric Power University
North China Electric Power University
B+-树
m阶的 B+-树的定义如下：
1)每个非叶结点至可以至多可以有 m个儿子；
2)每个非叶结点 (根结点除外 )必须有 m+1/2 个儿子；
3)根结点至少有两个儿子；
4)有 k个儿子的非叶结点有 k个关键字；
5)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
B+-树和 B-树的主要区别：
1)有 n棵子树的结点中含有 n个关键字 (B树中含有 n-1个关键字 )；
2)所有的叶子结点中包含了全部关键字的信息及指向相应记录的指针,且叶子结点本身依关键字的大小从小到大顺序链接；
3)所有的非终端结点可以看成是索引部分,结点中仅含有其子树中最大 (或最小 )的关键字。
North China Electric Power University
下图为一棵 m=2阶 B+-树的例子
70 95
40 70 95
20 40 51 70 91 95
10 20 35 40 44 51 65 70 85 91 93 95
5
10
11
20
30
35
40 44 47
51
61
65
70 80
85
91 92
93
95
North China Electric Power University
通常在 B+-树上有两个头指针：一个指向根结点；另一个指向关键字最小的叶子结点。因此，可以对 B+-树进行两种查找运算，一种是从最小关键字起顺序查找，另一种是从根结点开始随机查找。
在 B+-树上进行随机查找、插入和删除的过程基本上与
B-树类似。只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是沿着左边的指针继续向下直到叶子结点。因此，在 B+-树上，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
数字查找树,又称键树，它是一棵度 ≥ 2的树，树中每个结点不是包含一个或几个关键字，而是只含有组成关键字的符号。例如，若关键字是数字，则结点中只包含一个数位，若关键字是单词，则结点中只包含一个字母。
例如,有如下 16个字的关键字的集合 {CAI,CAO,Li,LAN,CHA,
CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,
WU,CHEN} 可对此集合作如下逐层分割：
首先按其首字符的不同将它们分成 5个集合,{CAI,CAO,CHA,
CHANG,CHAO,CHEN},{WEN,WANG,WU},{ZHAO},{LI,LAN,
LONG,LIU},{YUN,YANG},
然后对其中 4个关键字个数大于 1的集合再按其第二个字母的不同进行分割。若所得子集的关键字个数多于 1个，则还需按第三个字符不同再进行分割。依此类推，直至每个子集中只包含一个关键字为止。例如对首字符为 C的集合进行如下分割 {{(CAI),(CAO)},{
{{(CHA),(CHANG),(CHAO),(CHEN)}},显然，如此集合、子集和元素之间的层次关系可以用一棵树来表示，这棵树便为键树。
North China Electric Power University
C
A H
I O
$ $
A
$ N O
E
N
G
$
$ $
L
A I O
N
$
U N
G$
$
W
A E U
N N $
G $
$
Y
A
N
G
$
U
N
$
Z
H
A
O
$
树中根结点的五棵子树分别表示首字符为 C,L,W,Y和 Z的五个关键字子集。从根结点到叶子结点路径上所有结点的字符组成的字符串表示一个关键字，叶子结点中的特殊符号 $表示字符串的结束。
North China Electric Power University
为了查找和插入方便，我们约定键树是有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符 $小于任何字符。
通常，键树有两种存储结构：
1)以树的孩子兄弟链表来表示,则树中每个结点包含三个域：
Symbol域：存储关键字的一个字符；
Son域：存储指向第一棵子树的根的指针；
Brother域：存储指向右兄弟结点的指针；
同时，叶子结点的 Son域存储指向关键字记录的指针。
此时的二叉树又称为双链树。
双链树的查找过程如下：假设给定值为 k(1..n+1),其中 k[1]至 k[n]表示待查关键字中 n各字符,k[n+1]为结束符 $,从双链树的根指针出发，顺 Son指针找到第一棵子树的根结点，以 k[1]和此结点的
Symbol域比较，若相等，则顺 Son域再比较下一字符，否则沿
Brother域顺序查找，若 Symbol<k[1]说明查找的关键字不存在，要进行插入。若查找成功,Search单元中存放已查到的关键字，否则为 Nil.
North China Electric Power University
数据类型说明：
Const length=20;bland=‘$’;
Type ptr=↑node;
node=Record
Symbol:Char; Son:ptr; Brother:ptr;
End;
rptr=↑object;
object=Record
key:Array[1..length] of Char;
End;
Var search:ptr;
{在调用 rdlb之前,search=Nil}
Procedure rdlb(var tree:ptr;var recpte rptr;k:Array [1..length]
of Char);
Var i,j:Integer;
found,past:Boolean;
p,q,father,s:ptr;
North China Electric Power University
Function insert:rptr;
Begin
new(s); s↑.Symbol:=k[i]; s↑.Brother:=p;
if tree=Nil then tree:=s
else if q < >Nil then q↑.Brother:=s
else if father=Nil then tree:=s
else father↑.Son:=s;
j:=i;{insert remaining symbols of the k}
while k[j]< >blank Do
[ father:=s;new(s);
s↑.Symbol:=k[j+1];
father↑.Son:=s;
s↑.Brother:=Nil;j:=j+1
]
s↑.Son:=recptr;
insert:=recptr;
End;
North China Electric Power University
Begin
p:=tree;father:=nil;{father is the father of p}
found:=false;i:=1;
while not found Do
[ q:=Nil; {在兄弟间 q尾随 p}
past:=false;
while (p< >Nil) and (not past) Do
if p↑.Symbol>=k[i] then past:=true
else [q:=p;p:=p↑.Brother;]
found:=true;
if (p=Nil) or (p↑.Symbol>k[i]) then search:=insert{插入记录 }
else if k[i]=bland then search:=p↑.Son{已查到待查关键字 }
else [ father:=p;p:=p↑.Son;found:=false;
i:=i+1; {当 p=k[i]时，准备 p↑.Son是否等于 k[i+1]}
]
]
End;
North China Electric Power University
键树中每个结点的最大度 d和关键字的“基”有关，若关键字是单词，则 d=27,若关键字是数值，则 d=11。键树的深度 h取决于关键字中字符或数位的个数。假设关键字是随机的（即关键字中每一位取基内任何值的概率相同），则在双链树中查找每一位的平均查找长度为 1/2(1+d)。
2)以树的多重链表表示键树,则树的每个结点中有 d个指针域，此时的键树又称为 Trie树。若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上的所有结点压缩成一个“叶子结点”，且在该叶子结点中存储关键字及指向记录的指针等信息。由此，在 Trie树中具有两种结点：分支结点 (含有 d个指针域和一个指示该结点中非空指针域的个数的整数域 )和叶子结点 (含有关键字域和指向记录的指针域 )。在分支结点中不设数据域，每个分支结点所表示的字符由其双亲结点中 (指向该结点 )的指针所在位置决定。
在 Trie树上的查找过程为,从根结点出发，沿和给定值相应的指针逐层向下，直至叶子结点，若该结点中的关键字和给定值相等，则查找成功，否则查找不成功。
North China Electric Power University
Type trieptr=↑nodetype;
nodetype=Record
node=(branch,leaf);
case node of
branch:(ptr:Array[0..26] of trieptr;num:integer);
leaf:(data:KeyType;recptr:↑recordType);
End;
Function triesrch(t:trieptr;k:KeyType):↑recordtype;
Begin
p:=t;i:=1;
while(p< >Nil) and (p↑,node< >leaf) and (i<=k.last) Do
[p:=p↑.ptr[ord(k.ch[i])];i:=i+1;]
{ord将 ch[i]转换成其在字母表中的序号 }
if (p< >Nil) and (p↑.node=leaf) and (p↑.data=k)
then Return(p↑.recptr)
else Return(Nil);
End;
North China Electric Power University
纵观以上两节讨论的表示查找表的各种结构，有一个共同点：记录在表中的位置和它的关键字之间不存在一个确定的关系，因此，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。
因此，用这类方法表示的查找表，其平均查找长度都不为零，不同表示方法的差别仅在于：和给定值进行比较的关键字的顺序不同。
对于频繁使用的查找表，希望 ASL=0。即不需要从
,比较,的结果来确定查找成功，只有一个办法：预先知道所查关键字在表中的位置，也就是说，记录在表中位置和其关键字之间存在一种确定的关系 。
★ Hash法什么是 Hash表？
North China Electric Power University
例如：为每年招收的 1000名新生建立一张查找表，其关键字为 xx000--xx999(前两位为年份 )。则可以下标为
000--999 的顺序表表示之。由于关键字和记录在表中的序号相同，则不需要经过比较即可确定待查关键字。
但是，对于动态查找表而言,1) 表长不确定； 2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况，需建立一个函数关系，以 f(key)作为关键字为 key的记录在表中的位置，通常称这个函数
f(key)为哈希函数。 (注意：这个函数并不一定是数学函数 )
简单地说,哈希表是基于哈希函数建立的一种查找表。
North China Electric Power University
例如：对于如下 9个关键字
{ Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei }
13 8 9 6 11 1 4 12 2
设从这个例子可见，
1.哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可 ;
2.由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生,冲突,现象，即,key1< >key2
，而 f(key1) = f(key2),并且，改进哈希函数只能减少冲突，而不能避免冲突。
North China Electric Power University
因此，在设计哈希函数时，一方面要考虑选择一个,好,
的哈希函数 ;另一方面要选择一种处理冲突的方法。
所谓,好,的哈希函数，指的是，对于集合中的任意一个关键字，经哈希函数,映象,到地址集合中任何一个地址的概率是相同的。称这类哈希函数为,均匀的,哈希函数
。
根据设定的哈希函数 H(key)和所选中的处理冲突的方法，
将一组关键字映象到一个有限的、地址连续的地址集 (区间 )上，并以关键字在地址集中的,象,作为相应记录在表中的存储位置，这种表被称为哈希表。Hash法的关键在于哈希表的构造和冲突的处理
North China Electric Power University
哈希函数的构造方法对数字的关键字可有下列哈希函数的构造方法，若是非数字关键字，则需先对其进行数字化处理。
1.直接定址法哈希函数为关键字的线性函数
H(key) = key 或者 H(key) = a*key + b
仅限于：地址集合的大小 = 关键字集合的大小例 有一个从 1到 100岁的人口数字统计表,用年龄做关键字，
它采用的 hash函数是第一种 H(K)=K,即 j=k。
地址 01 02 03 … 25 26 27 28 … 100
年龄 1 2 3 … 25 26 27 28 … 100
人数 3000 2000 5000 … 1020 2070 7001 7200 … 10
North China Electric Power University
2.数字分析法例 有七个 8位十进制的关键字（有七个关键字，每个关键字都具有八位十进制数），将其散列在地址为 10-90的表中。
① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 地址
k1,5 4 2 4 2 2 4 2 42
k2,5 4 2 8 1 3 6 7 83
k3,5 4 2 2 2 8 1 7 28
k4,5 4 2 3 8 9 6 7 39
k5,5 4 2 5 4 1 5 7 51
k6,5 4 2 6 8 5 3 7 65
k7,5 4 2 1 9 3 5 5 13
仅限于：能预先估计出全体关键字的每一位上各种数字出现的频度。
假设关键字集合中的每个关键字都是由 s位数字组成
(k1,k2,…,kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
North China Electric Power University
3.平方取中法若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过,平方,扩大差别
，同时平方值的中间几位受到整个关键字中各位的影响,
4.折迭法若关键字的位数特别多，则可将其分割成几部分，
然后取它们的叠加和为哈希地址。相加的方法有移位法和折叠法。
折叠法：把一关键字看承一张纸条，从一端向另一端沿边界逐层折叠，再把相应的位数加在一起。
移位法：将各部分的最后一位对齐，然后相加。
假定关键字,K=d1d2d3… drdr+1… d2rd2r+1… d3r允许有的存储地址有 r位。
North China Electric Power University
移位法,d1 d2 … dr
dr+1 dr+2 … d2r
+ d2r+1d2r+2… d3r
高进位不要了 得到 r位的存储地址折叠法,d3r d3r-1… d2r+1
dr+1dr+2 … d2r
+ dr dr-1 … d1
d1' d2' … dr'高进位不要了 得到 r位的存储地址例如,K=32834872，允许存储地址为三位十进制数。
位移法,328 折叠法,27
348 348
+ 72 + 823
748 1198
H(K)=748 H(K)=198
North China Electric Power University
5.除留余数法实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况 (包括关键字的范围和形态 )，总的原则是使产生冲突的可能性降到尽可能地小。
设给出关键字 k，存储单元数为 m,则可选一数 p(p<=m)去除 k得到余数 r(以 p为模 )，再用一线性函数 f将 r转换为散列地址 j,即 r=(k) mod p,j=f(r)
例 有一组关键字从 000001-859999，指定的存储单元地址为
1000000-1005999,即 m=6000。选 p=5999 k=172148
r=(172148) mod 5999=4176(mod 5999)
f=1000000+r=1004176
在这里选择 p是关键步骤，若 P为偶数，则凡是奇数的关键字，
都转换为奇数地址，则凡是偶数的关键字地都转换为偶数地址，
显然会出现冲突。一般情况,(1)P尽量接近 m;(2)p为质数。
North China Electric Power University
§ 8.3.2处理冲突的方法处理冲突的方法开放定址法链地址法线性探测再散列二次探测再散列伪随机探测再散列探测,检查关键字是否与 hash向量元素相匹配。
North China Electric Power University
一,开放定址法假设哈希空间为 T(0:m-1),哈希函数为 j=H(key)。
为求得下一个哈希地址,可取 ji=(j+di) MOD m，
i=1,2,3,...,s(s≥ 1),其中 m为哈希表的表长
di为增量序列 。
1.当取 di=1,2,3,....,s时称为 线性探测再散列例如,有一个关键字序列 19,70,33,已存入长度为 16的哈希表中 。
取哈希函数为除留余数法,j=k MOD 13；
North China Electric Power University
0 1 … 4 5 6 7 8 … 15
… …70 19 33 18
现在要把关键字为 18的记录填入表中：
j=18 MOD 13=5 冲突 1次
j1=(5+1)MOD 16=6 冲突
j2=(5+2)MOD 16=7 冲突
j3=(5+3)MOD 16=8 不冲突
Hash地址 是否冲突 冲突次数
2次
3次
j=19 MOD 13=6； j=70 MOD 13=5； j=33 MOD 13=7
North China Electric Power University
2.当取 di=12,-12,22,-22,…,n2,-n2 时称为,
二次探测再散列仍以上例为例,70,19,33已填入哈希表中，再填入关键字为 18的记录,
j1=(5+1) MOD 16=6
0 1 … 4 5 6 7 8 … 15
… …70 19 3318
j=18 MOD 13=5 冲突 1次
Hash地址 是否冲突 冲突次数
j2=(5-1) MOD 16=4 不冲突
2次冲突
North China Electric Power University
3.当取 di=伪随机序列时称为 伪随机探测再散列伪随机序列：随机产生的 n个随机数，表示为
d1,d2,…,dn 伪随机函数为,di =(a*di-1+b) Mod Q
j=18 MOD 13=5 冲突 1次
0 1 … 4 5 6 7 8 … 15
… …70 19 3318
2
仍用上例为例,19,70,33已存入再填入 18，
若伪随机数序列为 13,15,7,2,35,…
Hash地址 是否冲突 冲突次数
j1=(5+13)MOD 16=2 不冲突
North China Electric Power University
说明：
线性探测法可以探测到哈希表中的各个位置，但它容易产生,堆聚,现象。例如，关键字为 21的记录，
由哈希函数得到哈希地址为 8，则产生冲突。但是这种冲突不是由同义词所引起的，而是在解决同义词冲突的过程中又添加出的非同义词冲突。这种现象会使探测次数增加，对查找极为不利。
二次探测法可减少,堆聚,,但由于它不能保证探测到哈希表中的所有位置，所以即使哈希表未满，
也有可能探测不到,空,的位置。（只有当 m=4j+3
(j=1,2,3...)时才能探测到整个哈希表空间。）
North China Electric Power University
伪随机探测法可较好地避免,堆聚,,但应该要求所使用的伪随机数序列能均匀地取 [0:m-1]
中的数。
注意：
按上述方法建立起来的哈希表上一般是不能进行删除操作的 。 因为一旦删除某一记录,探测的地址序列即被中断,从而无法再查到具有相同哈希函数值的后继记录,若要删除,则需要在该记录的位置上填入一个特殊标记 。
另外,当某记录探测不到,空,位置时,需要作相应的溢出处理,将该记录存入溢出表 。 溢出表的结构可以是别的表 。
North China Electric Power University
例如 下列一组关键字在哈希函数 H(key)=key mod
13时,用链地址法处理冲突时的哈希表如下,
0 1 2 3 4 5 6 7 8 9 10 11 12
01
^ ^ ^ ^ ^ ^
(19,14,23,01,68,20,84,27,55,11,10)
二、链地址法将所有关键字为同义词的记录存储到同一线性链表中。
14
55
68
19
84
10
23
^ ^ ^
20
^
11
^
27
^
North China Electric Power University
§ 8.3.3 哈希表的查找设表长为 n的哈希表中，采用线性探测技术查找，插入记录 R,R的地址为 i,R在 A表或溢出表 of1中由 tag等于 0或等于 1标志。
0 在 A表中
1 在 of1表中 (溢出表 )tag=
North China Electric Power University
PROC Lineasrchhash(R,A,n,i,tag);
BEGIN
j:=Hash(R.key)
i:=j-1; tag:=0;
Repeat
i:=(i+1) mod n ｛线性探测｝
Until (A[i].key=R.key) or (A[i]=ф) or (i=j-1);
If A[i].key=R.key ｛查找成功｝
Then write('successful R"s address=',i)
Else If A[i]=ф then
[ A[i]:=R;Write(‘Unsuccessful R Address=‘,’i);
else [ search overflowList(of1,R,i);tag:=1 ]
END;
North China Electric Power University
If q↑record.key=R.key ｛查找成功｝
then [write('hash chain sucessful');exit ]
下面给出采用链地址技术查找，插入记录 R的算法：
Procedure chaininghash(A,R);
｛在哈希表 A中，采用链地址技术查找、插入记录 R｝
Begin
j:=Hash(R.key);
If A[j]≠nil then
[ q:=A[j];
while (q↑.record.key≠R.key) and (q↑.next≠nil) do
q:=q↑.next;
North China Electric Power University
Else [ {A[j]=Nil的情况 }
write('hash chain unsucessful');
new(p);p↑.record:=R;
p↑.next:=nil; A[j]:=p ]
｛ 查找不成功,插入记录 R｝
End;
Else [ write('hash chain unsucessful');
new(p); p↑.record:=R;
p↑.next:=nil; q↑.next:=p ]
]
North China Electric Power University
Hash法的性能分析
North China Electric Power University
决定哈希表查找的 ASL的因素：
一般情况下，可以认为选用的哈希函数是,均匀,
的，则在讨论 ASL时，可以不考虑它的因素。
因此哈希表的 ASL是处理冲突方法和装载因子的函数。
1.选用的哈希函数
2.选用的处理冲突的方法
3.哈希表饱和的程度，装载因子 α =n/m 值的大小。
可以证明：
查找成功时有下列结果：
线性探测再散列随机探测再散列链地址法
North China Electric Power University
对静态查找表，有时也可能找到不发生冲突的哈希函数。即此时的哈希表的 ASL=0,此类哈希函数为理想 (perfect)的哈希函数。
