? 静态查找表
二叉排序树
平衡二叉树（ AVL树）
哈希表查找 (Search)的概念
8.1 静态查找表
查找,就是 在数据集合中寻找满足某种条件的数据对象 。
查找表,是由 同一类型的数据元素 (或记录 )
组成的数据集合。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象。
查找不成功,或查找失败。作为结果，
报告一些信息，如失败标志、失败位置等。
衡量一个查找算法的时间效率的标准是,在查找过程中关键字的平均比较次数或平均读写磁盘次数 (只适合于外部查找 ),这个标准也称为平均查找长度 ASL(Average Search Length),通常它是 查找结构中对象总数 n 或文件结构中物理块总数 n 的函数 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题 。
在静态查找表中,数据对象存放于数组中,利用数组元素的下标作为数据对象的存放地址 。
查找算法 根据给定值 x,在数组中进行查找 。
直到找到 x在数组中的存放位置或可确定在数组中找不到 x为止 。
8.1.1顺序表的查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
存储结构：
typedef struct{
ElemType *elem;
int length;
} SSTable;
查找过程：从表中最后一个元素开始,顺序用各元素的关键字与给定值 x进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位置；否则,若直到第一个记录仍未找到关键字与 x相等的对象,则查找失败 。
算法 8.1
Search_Seq(SSTable ST,KeyType key){
//顺序查找的算法,0号元素为监视哨
int i；
ST.elem[0].key=key;
for (i=ST.length; !EQ(ST.elem[i].key,key);--i);
return i;
}
顺序查找的平均查找长度
n
i
i
n
i
iis u c c pcpA S L
1
) 1 (,
1
)(
1
1
ipAS L
n
i
is u c c n
.)()(?
n
i
s u c c
nnn
n
i
n
A S L
1 2
1
2
1111 n
设查找 第 i 个 元素的概率为 pi，查找到 第 i 个 元素所需 比较次数 为 ci，则查找成功的平均查找长度,
在顺序查找情形,ci = n-i +1,i = 1,?,n，因此在等概率情形,pi = 1/n,i = 0,1,?,n-1。
8.1.2 有序表的查找
折半查找：先求位于查找区间正中的对象的下标 mid,用其关键字与给定值 x比较,
Element[mid].getKey( ) = x,查找成功；
Element[mid].getKey( ) > x,把查找区间缩小到表的 前半部分,再继续进行对分查找；
Element[mid].getKey( ) < x,把查找区间缩小到表的 后半部分,再继续进行对分查找 。
每比较一次,查找区间缩小一半 。 如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
折半查找：
（ 1） mid=?(low+high)/2?
（ 2） 比较 ST.elem[mid].key = = key?
如果 ST.elem[mid].key = = key,则查找成功,
返回 mid值如果 ST.elem[mid].key > key,则置 high=mid-1
如果 ST.elem[mid].key < key,则置 low=mid+1
(3) 重复计算 mid 以及比较 ST.elem[mid].key与 key，
当 low>high时,表明查找不成功,查找结束 。
查找成功的例子 查找失败的例子算法 8.2
int Search_Bin(SSTable ST,KeyType key) //折半查找
{ int low,high,mid;
low = 1; high=ST.length;
while (low < high)
{ mid = (low+high)/2;
if (EQ(key,ST.elem[mid].key)) return mid;
else if (LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
return 0;
}
8.2 动态查找表表结构本身是在查找过程中动态生成的。
基本操作：
InitDSTable(&DT); //构造一个空的动态查找表 DT
DestroyDSTable(&DT); //销毁表
SearchDSTable(DT,key); //查找关键字为 key的数据元素
InsertDSTable(&DT,e);
DeleteDSTable(&DT,key);
TraverseDSTable(DT,visit()); //遍历查找表定义二叉排序树（二叉查找树） 或者是一棵空树，
或者是具有下列性质的二叉树：
每个结点都有一个作为查找依据的关键字
(key)，所有结点的关键字互不相同。
左子树 (若非空 )上所有结点的关键字都小于根结点的关键字。
右子树 (若非空 )上所有结点的关键字都大于根结点的关键字。
左子树和右子树也是二叉排序树。
8.2.1二叉排序树 ( Binary Sort Tree )
如果对一棵二叉排序树进行 中序 遍历，可以按从小到大的顺序，将各结点关键字排列起来。
几个二叉排序树的例子二叉排序树的构建
—— 如何构造二叉排序树
1) 构造过程：
从空树出发,依次插入 R1～ Rn各数据值：
（ 1） 如果二叉排序树是空树,则插入结点就是二叉排序树的根结点；
（ 2） 如果二叉排序树是非空的,则插入值与根结点比较,若小于根结点的值,就插入到左子树中去；否则插入到右子树中 。
示例：
{ 45,24,53,12,22,90 }
2) 二叉排序树的数据类型描述
typedef struct { int key; } ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;
3) 二叉排序树上插入结点的算法
（ 1） 在二叉排序树上插入一个结点的算法；
（ 2） 依次输入一组数据元素,并插入到二叉排序树中的算法
（ 1） 将指针 S所指的结点插入到根结点指针为 T的二叉排序树中的算法
void Insert_BST( BiTree &T,BiTree S )
{ BiTree p,q;
if(!T) T=S;
else { p=T;
while ( p )
{ q = p;
if (S->data.key < p->data.key) p = p->lchild;
else p = p->rchild;
}
if (S->data.key < q->dat.key) q->lchild = S;
else q->rchild = S;
}
return;
}
（ 2） 输入一组数据元素的序列，构造二叉排序树的算法
void Creat BST( BiTree &T )
{ int x; BiTree S; T=NULL;
while ( scanf (,%d”,&x),x!=0 )
{ S = (BiTNode *) malloc(sizeof(BitNode));
S->data.key = x;
S->lchild = NULL;
S->rchild = NULL;
Insert_BST( T,S );
}
return;
}
4) 二叉排序树上的查找（动态查找）
int Searh_BST( BiTree T,int key )
{ BiTree p,q,S,p = T;
while ( p )
if ( p->data.key == key ) return(1);
else if ( p->data.key > key) { q=p; p=p->lchild; }
else {q=p; p=p->rchild; }
S = (BiTNode *) malloc(sizeof(BitNode));
S->data.key = key; S->lchild=S->rchild=NULL;
if (!T) T=S;
else if ( q->data.key > key ) q->lchild=S;
else q->rchild=S;
return(0);
}
说明,（ 1） 正常情况下,返回 0是未找到,但实际上已经插入；
（ 2） 也可以用 return返回一个自己定义的标志值 。
要求：删除一个结点后，仍然保持二叉排序树的有序性删除结点的算法：
（ 1）确定被删除结点：
A,有没有被删除的结点；
B,若有，则确定被删除的结点是根结点还是一般结点
（ 2）如果被删除结点是根结点，则调用删除根结点的算法；
（ 3）如果被删除结点是一般结点，则调用删除一般结点的算法。
5) 二叉排序树的删除删除二叉排序树的根结点的算法
（ 1） 根结点有左右子树的情况下，选择根结点的左子树中的最大结点为新的根结点； /或者是右子树中的最小结点为新的根结点；
** 最大结点 —— 中序遍历
（ 2）如果根结点没有左子树，则以右子树的根结点作为新的根结点；
（ 3）如果根结点没有右子树，则以左子树的根结点作为新的根结点删除二叉排序树中一般结点的算法
（ 1） 若被删除结点 P有左、右子树，则按照中序遍历找其左子树中的最大结点，以此最大结点的值代替 P结点的值，然后删除此最大结点（如同删除根结点）
（ 2）若被删除结点 P没有左子树，则把结点 P的右子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
（ 3）若被删除结点 P没有右子树，则把结点 P的左子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置删除二叉排序树中叶子结点的算法只需将其双亲结点指向它的指针清零，再释放它即可
int Delete_BST( BiTree &T,int key)
{ BiTree p,f ;
p=T; f=NULL;
while(p)
{ if (p->data.key == key)
{ delNode ( T,p,f ) ; return(1) ;}
else if (p->data.key > key) { f=p; p=p->lchild; }
else { f=p; p=p->rchild; }
}
return(0)
}
删除二叉排序树中结点的算法
—— 寻找被删除的结点
void delNode ( BiTree &T,BiTree p,BiTree f )
{ BiTree s,q ;
int tag ; tag=0;
if (!p->lchild) s=p->rchild;
else if (!p->rchild) s=p->lchild;
else{ q=p; s=p->lchild;
while(s->rchild) { q=s; s=s->rchild; }
p->data=s->data;
if (q==p) q->lchild=s->lchild;
else q->rchild=s->lchild;
free(s);
tag=1; }
if (!tag){ if ( !f ) T=s; //左右孩子中至少有一个不存在
else if ( f->lchild==p ) f->lchild=s;
else f->rchild=s;
free(p);
return;
}
}
删除二叉排序树中结点的算法 —— 删除找到的结点二叉排序树上的查找
在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程 。 它可以是一个递归的过程 。
假设想要在二叉排序树中查找关键字为 x的元素,查找过程从根结点开始 。 如果根指针为
NULL,则查找不成功；否则用给定值 x与根结点的关键字进行比较：
如果给定值等于根结点的关键字,则查找成功 。
如果给定值小于根结点的关键字,则继续递归查找根结点的左子树；
否则 。 递归查找根结点的右子树 。
int SearchBST(BiTree T,KeyType key,BiTree
f,BiTree &p){
//二叉排序树的递归查找算法
if (!T) {p=f; return FALSE;}
else if (EQ(key,T->data.key)){p=T;return
TRUE;}
else if (LT(key,T->data.key)) return
SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
二叉排序树的查找 插入新结点 88
每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。
AVL树 高度平衡的二叉查找树
AVL树的定义一棵 AVL树或者是空树，或者是具有下列性质的二叉查找树,它的左子树和右子树都是 AVL树，且左子树和右子树的高度之差的绝对值不超过 1。
高度不平衡的二叉排序树 高度平衡的二叉查找树结点的平衡因子 balance (balance factor)
每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子 balance。
根据 AVL树的定义，任一结点的平衡因子只能取 -1,0和 1。
如果一个结点的平衡因子的绝对值大于 1，则这棵二叉查找树就失去了平衡，不再是 AVL树。
如果一棵二叉查找树是高度平衡的，它就成为
AVL树。如果它有 n 个结点，其高度可保持在
O(log2n)，平均查找长度也可保持在 O(log2n)。
AVL树的类型定义
typedef struct BSTNode {
ElemType data;
struct BSTNode *lchild,*rchild;
int bf; //结点的平衡因子
} BSTNode,*BSTree;
平衡化旋转
如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，
使之平衡化。
平衡化旋转有两类：
单旋转 (左旋和右旋 )
双旋转 (左平衡和右平衡 )
每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要 从插入位置沿通向根的路径回溯,检查各结点的平衡因子 (左、右子树的高度差 )。
如果在某一结点发现高度不平衡，停止回溯。
从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上，则采用单旋转进行平衡化 。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
如果这三个结点处于一条折线上，则采用双旋转进行平衡化 。双旋转分为先左后右和先右后左两类。
右单旋转 左单旋转 左右双旋转 右左双旋转左单旋转 (RotateLeft )
h
h h
A
C
E
B
D
(a) (b) (c)
h
h
h+
1
B
A
C
ED
h h
h+
1
C
EA
B D
如果在子树 E中插入一个新结点,该子树高度增 1导致结点 A的平衡因子变成 +2,出现不平衡 。
沿插入路径检查三个结点 A,C和 E。 它们处于一条方向为,\”的直线上,需要做左单旋转 。
以结点 C为旋转轴,让结点 A反时针旋转 。
+1 +2
0 +1 0
0
void L_Rotate(BSTree &p) //左单旋转的算法
{
BSTree rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p; p=rc;
}
右单旋转 (RotateRight )
h
h h
A
C
E
B
D
(a) (b) (c)
h
h+
1
B
A
C
ED
h h
h+
1
CE
A
B
D
在左子树 D上插入新结点使其高度增 1，导致结点 A的平衡因子增到 -2，造成了不平衡。
为使树恢复平衡，从 A沿插入路径连续取 3个结点 A、
B和 D，它们处于一条方向为,/”的直线上，需要做右单旋转。
以结点 B为旋转轴，将结点 A顺时针旋转。
h
0
0
0
-1
-1
-2
void R_Rotate(BSTree &p) //右单旋转的算法
{
BSTree lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p; p=lc;
}
先左后右双旋转 (RotationLeftRight)
在子树 F或 G中插入新结点,该子树的高度增 1。 结点
A的平衡因子变为 -2,发生了不平衡 。
从结点 A起沿插入路径选取 3个结点 A,B和 E,它们位于一条形如,?” 的折线上,因此需要进行先左后右的双旋转 。
首先以结点 E为旋转轴,将结点 B反时针旋转,以 E代替原来 B的位置,做左单旋转 。
再以结点 E为旋转轴,将结点 A顺时针旋转,做右单旋转 。 使之平衡化 。
插入左单旋转右单旋转
0
0
-1 -2
+1
-1
0
0
+1
先右后左双旋转 (RotationRightLeft)
右左双旋转是左右双旋转的镜像 。
在子树 F或 G中插入新结点,该子树高度增 1。 结点 A
的平衡因子变为 2,发生了不平衡 。
从结点 A起沿插入路径选取 3个结点 A,C和 D,它们位于一条形如,?” 的折线上,需要进行先右后左的双旋转 。
首先做右单旋转：以结点 D为旋转轴,将结点 C顺时针旋转,以 D代替原来 C的位置 。
再做左单旋转：以结点 D为旋转轴,将结点 A反时针旋转,恢复树的平衡 。
左单旋转插入右单旋转
+1
0
0
0
0-1
-1
+1
+2
AVL树的插入
在向一棵本来是高度平衡的 AVL树中插入一个新结点时,如果树中某个结点的平衡因子的绝对值 |balance| > 1,则出现了不平衡,需要做平衡化处理 。
算法从一棵空树开始，通过输入一系列对象的关键字，逐步建立 AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。
1616
例，输入关键字序列为 { 16,3,7,11,9,26,18,14,
15 },插入和调整过程如下。
0
3
16
3
-1
0
7
0
1
-2
左右双旋 7
3 16
0 0
0
7
3
11
0
-1
1
7
3 16
16
11
9
0
-1
-2
右单旋 3
7
169
0 0
0
1
3
7
11
26
9 16
11
0
1
1
22
18 18
0
3
16
3
-1
0
16
0
2 右左双旋
7
3 9
0
0
0
18
26
11
-1
7
3 26
16
11
9
-1
左单旋
9
7
16
14
0
0
1
7
11
26
269
1
1
11
15
18
2
3
18
16
-2
左右双旋
7
3
0
0
0
11
7
14
9
-1
16
15
0
1
11
26 26
14
1
-2
9
从空树开始的建树过程散列 (Hashing)
在线性表、树结构中查找纪录是通过与关键字的,比较,完成的。
顺序查找，比较的结果为,=”或,≠,
非顺序查找，比较的结果为,<”,,=”,,>”
散列的思想：
根据记录的关键字直接找到记录的存储位置，
即为关键字和记录的存储位置建立一个对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。
对应关系 f为 散列函数,按该思想建立的表为 散列表 。
根据设定的哈希函数 H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，
并以关键字在地址集中的,像,作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
哈希表的定义
散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系 Hash( )，使每个关键字与结构中一个唯一存储位置相对应：
Address ＝ Hash ( Rec.key )
在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，
并按此位置存放。
构造散列函数时的几点要求：
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m个 地址时,其值域必须在 0 到 m-1 之间。
散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取
0到 m-1 中的每一个值。
散列函数应是简单的，能在较短的时间内计算出结果。
哈希函数的构造方法
1,直接定址法此类函数直接取关键字或关键字的某个 线性函数 值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。
但是，它要求散列地址空间的大小与关键字集合的大小相同。
2,数字分析法设有 n个 d位数，每一位可能有 r种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；
在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。
3,平方取中法取关键字平方后的中间几位为 Hash地址,
所取的位数和 Hash地址位数相同 。 这是一种较常用的构造 Hash函数的方法 。 因为通常在选定 Hash函数时不一定能知道关键字的全部情况,难以决定取其中哪几位比较合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机每布的关键字得到的 Hash
地址也是随机的 。
4,折叠法
此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，
然后对齐相加，将相加的结果当做散列地址。
示例：设给定的关键字为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键字可划分为
4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
冲突处理
1,开放定址法开放定址法的基本做法是在发生冲突时,按照某种方法继续探测基本表中的其它存储单元,直到找到一个开放的地址 （ 即空位置 ） 为止 。 显然这种方法需要用某种标记区分空单元与非空单元 。
开放定址法的一般形式可表示为：
Hi（ k） =（ H（ k） +di） mod m（ i=1,2,…,k（ k?m-1））
其中,H（ k） 为键字为 k的直接哈希地址,m为哈希表长,di为每次再探测时的地址增量 。
当 di=1,2,3,…,m-1时,称为线性探测再散列；
当 di=12,-12,22,-22,…,k2,-k2（ k?m/2） 时,称为二次探测再散列；当 di=随机数序列时,称为随机探测再散列 。
例如，有数据（ 654,638,214,357,376,854，
662,392），现采用数字分析法，取得第二位数作为哈希地址，将数据逐个存放入大小为 10的散列表
（此处为顺序表）中。若采用线性探测法解决地址冲突，则 8个数据全部插入完成后，散列表的状态如表 9.2所示。
392 214 638 654 357 376 854 662
0 1 2 3 4 5 6 7 8 9
2,再哈希法采用再哈希法解决冲突的做法是当待存入散列表的某个元素 k在原散列函数 H（ k）的映射下与其它数据发生碰撞时，采用另外一个 Hash函数 Hi（ k）（ i=1，
2,…,n）计算 k的存储地址（ Hi均是不同的 Hash函数），这种计算直到冲突不再发生为止。
3,拉链法拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m，则可将散列表定义为一个由 m个头指针组成的指针数组 T[0..m-1]，凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。
拉链法的缺点主要是指针需要用额外的空间 。
例如,关键字集合为 {1,13,20,5,14,33}，
散列表长度 m=5,现采用除余法为哈希函数并采用拉链法解决地址冲突,所创建的 Hash链表如下图所示 。
t[0]
t[1]
t[2]
t[3]
t[4]
5
1 ^
20 ^
33 13 ^
14 ^
^
掌握 简单的查找结构：
查找的概念
查找结构
查找的判定树
平均查找长度
静态查找
顺序查找算法、分析
折半查找算法、分析小结 需要复习的知识点
二叉查找树
定义
查找、平均查找长度
插入、删除、
AVL树
定义
插入、平衡化旋转
删除、平衡化旋转
高度
查找的概念
查找结构决定查找的效率
查找算法基于查找结构
查找效率用平均查找长度衡量
平均查找长度表明查找算法的整体性能，避开偶然因素
平均查找长度分查找成功与查找不成功两种情况
静态查找结构
顺序查找 — 顺序表、链表
折半查找 — 有序顺序表
动态查找结构
二叉排序树 — 无重复关键字
AVL树 — 平衡二叉排序树
二叉查找树
二叉查找树的子树是二叉查找树
35
15 45
50402510
20 30
结点左子树上所有关键字小于结点关键字
右子树上所有关键字大于结点关键字
查找成功时检测指针停留在树中某个结点。
查找不成功时检测指针停留在某个外结点（失败结点）。
35
15 45
502510
20 30
查找 22
查找 45
AVL树
理解,AVL树的子树也是 AVL树
掌握：插入新结点后平衡化旋转的方法
掌握：删除结点后平衡化旋转的方法
掌握：结点高度 h 与结点数 n 的关系思考题：
1、假定一个线性表为 (38,52,25,74,68,16,30,54,90,72)，
画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
2,假定一个待哈希存储的线性表为
(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为 HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。
3,试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。
二叉排序树
平衡二叉树（ AVL树）
哈希表查找 (Search)的概念
8.1 静态查找表
查找,就是 在数据集合中寻找满足某种条件的数据对象 。
查找表,是由 同一类型的数据元素 (或记录 )
组成的数据集合。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象。
查找不成功,或查找失败。作为结果，
报告一些信息，如失败标志、失败位置等。
衡量一个查找算法的时间效率的标准是,在查找过程中关键字的平均比较次数或平均读写磁盘次数 (只适合于外部查找 ),这个标准也称为平均查找长度 ASL(Average Search Length),通常它是 查找结构中对象总数 n 或文件结构中物理块总数 n 的函数 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题 。
在静态查找表中,数据对象存放于数组中,利用数组元素的下标作为数据对象的存放地址 。
查找算法 根据给定值 x,在数组中进行查找 。
直到找到 x在数组中的存放位置或可确定在数组中找不到 x为止 。
8.1.1顺序表的查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
存储结构：
typedef struct{
ElemType *elem;
int length;
} SSTable;
查找过程：从表中最后一个元素开始,顺序用各元素的关键字与给定值 x进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位置；否则,若直到第一个记录仍未找到关键字与 x相等的对象,则查找失败 。
算法 8.1
Search_Seq(SSTable ST,KeyType key){
//顺序查找的算法,0号元素为监视哨
int i；
ST.elem[0].key=key;
for (i=ST.length; !EQ(ST.elem[i].key,key);--i);
return i;
}
顺序查找的平均查找长度
n
i
i
n
i
iis u c c pcpA S L
1
) 1 (,
1
)(
1
1
ipAS L
n
i
is u c c n
.)()(?
n
i
s u c c
nnn
n
i
n
A S L
1 2
1
2
1111 n
设查找 第 i 个 元素的概率为 pi，查找到 第 i 个 元素所需 比较次数 为 ci，则查找成功的平均查找长度,
在顺序查找情形,ci = n-i +1,i = 1,?,n，因此在等概率情形,pi = 1/n,i = 0,1,?,n-1。
8.1.2 有序表的查找
折半查找：先求位于查找区间正中的对象的下标 mid,用其关键字与给定值 x比较,
Element[mid].getKey( ) = x,查找成功；
Element[mid].getKey( ) > x,把查找区间缩小到表的 前半部分,再继续进行对分查找；
Element[mid].getKey( ) < x,把查找区间缩小到表的 后半部分,再继续进行对分查找 。
每比较一次,查找区间缩小一半 。 如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
折半查找：
（ 1） mid=?(low+high)/2?
（ 2） 比较 ST.elem[mid].key = = key?
如果 ST.elem[mid].key = = key,则查找成功,
返回 mid值如果 ST.elem[mid].key > key,则置 high=mid-1
如果 ST.elem[mid].key < key,则置 low=mid+1
(3) 重复计算 mid 以及比较 ST.elem[mid].key与 key，
当 low>high时,表明查找不成功,查找结束 。
查找成功的例子 查找失败的例子算法 8.2
int Search_Bin(SSTable ST,KeyType key) //折半查找
{ int low,high,mid;
low = 1; high=ST.length;
while (low < high)
{ mid = (low+high)/2;
if (EQ(key,ST.elem[mid].key)) return mid;
else if (LT(key,ST.elem[mid].key)) high=mid-1;
else low=mid+1;
}
return 0;
}
8.2 动态查找表表结构本身是在查找过程中动态生成的。
基本操作：
InitDSTable(&DT); //构造一个空的动态查找表 DT
DestroyDSTable(&DT); //销毁表
SearchDSTable(DT,key); //查找关键字为 key的数据元素
InsertDSTable(&DT,e);
DeleteDSTable(&DT,key);
TraverseDSTable(DT,visit()); //遍历查找表定义二叉排序树（二叉查找树） 或者是一棵空树，
或者是具有下列性质的二叉树：
每个结点都有一个作为查找依据的关键字
(key)，所有结点的关键字互不相同。
左子树 (若非空 )上所有结点的关键字都小于根结点的关键字。
右子树 (若非空 )上所有结点的关键字都大于根结点的关键字。
左子树和右子树也是二叉排序树。
8.2.1二叉排序树 ( Binary Sort Tree )
如果对一棵二叉排序树进行 中序 遍历，可以按从小到大的顺序，将各结点关键字排列起来。
几个二叉排序树的例子二叉排序树的构建
—— 如何构造二叉排序树
1) 构造过程：
从空树出发,依次插入 R1～ Rn各数据值：
（ 1） 如果二叉排序树是空树,则插入结点就是二叉排序树的根结点；
（ 2） 如果二叉排序树是非空的,则插入值与根结点比较,若小于根结点的值,就插入到左子树中去；否则插入到右子树中 。
示例：
{ 45,24,53,12,22,90 }
2) 二叉排序树的数据类型描述
typedef struct { int key; } ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode,* BiTree;
3) 二叉排序树上插入结点的算法
（ 1） 在二叉排序树上插入一个结点的算法；
（ 2） 依次输入一组数据元素,并插入到二叉排序树中的算法
（ 1） 将指针 S所指的结点插入到根结点指针为 T的二叉排序树中的算法
void Insert_BST( BiTree &T,BiTree S )
{ BiTree p,q;
if(!T) T=S;
else { p=T;
while ( p )
{ q = p;
if (S->data.key < p->data.key) p = p->lchild;
else p = p->rchild;
}
if (S->data.key < q->dat.key) q->lchild = S;
else q->rchild = S;
}
return;
}
（ 2） 输入一组数据元素的序列，构造二叉排序树的算法
void Creat BST( BiTree &T )
{ int x; BiTree S; T=NULL;
while ( scanf (,%d”,&x),x!=0 )
{ S = (BiTNode *) malloc(sizeof(BitNode));
S->data.key = x;
S->lchild = NULL;
S->rchild = NULL;
Insert_BST( T,S );
}
return;
}
4) 二叉排序树上的查找（动态查找）
int Searh_BST( BiTree T,int key )
{ BiTree p,q,S,p = T;
while ( p )
if ( p->data.key == key ) return(1);
else if ( p->data.key > key) { q=p; p=p->lchild; }
else {q=p; p=p->rchild; }
S = (BiTNode *) malloc(sizeof(BitNode));
S->data.key = key; S->lchild=S->rchild=NULL;
if (!T) T=S;
else if ( q->data.key > key ) q->lchild=S;
else q->rchild=S;
return(0);
}
说明,（ 1） 正常情况下,返回 0是未找到,但实际上已经插入；
（ 2） 也可以用 return返回一个自己定义的标志值 。
要求：删除一个结点后，仍然保持二叉排序树的有序性删除结点的算法：
（ 1）确定被删除结点：
A,有没有被删除的结点；
B,若有，则确定被删除的结点是根结点还是一般结点
（ 2）如果被删除结点是根结点，则调用删除根结点的算法；
（ 3）如果被删除结点是一般结点，则调用删除一般结点的算法。
5) 二叉排序树的删除删除二叉排序树的根结点的算法
（ 1） 根结点有左右子树的情况下，选择根结点的左子树中的最大结点为新的根结点； /或者是右子树中的最小结点为新的根结点；
** 最大结点 —— 中序遍历
（ 2）如果根结点没有左子树，则以右子树的根结点作为新的根结点；
（ 3）如果根结点没有右子树，则以左子树的根结点作为新的根结点删除二叉排序树中一般结点的算法
（ 1） 若被删除结点 P有左、右子树，则按照中序遍历找其左子树中的最大结点，以此最大结点的值代替 P结点的值，然后删除此最大结点（如同删除根结点）
（ 2）若被删除结点 P没有左子树，则把结点 P的右子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
（ 3）若被删除结点 P没有右子树，则把结点 P的左子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置删除二叉排序树中叶子结点的算法只需将其双亲结点指向它的指针清零，再释放它即可
int Delete_BST( BiTree &T,int key)
{ BiTree p,f ;
p=T; f=NULL;
while(p)
{ if (p->data.key == key)
{ delNode ( T,p,f ) ; return(1) ;}
else if (p->data.key > key) { f=p; p=p->lchild; }
else { f=p; p=p->rchild; }
}
return(0)
}
删除二叉排序树中结点的算法
—— 寻找被删除的结点
void delNode ( BiTree &T,BiTree p,BiTree f )
{ BiTree s,q ;
int tag ; tag=0;
if (!p->lchild) s=p->rchild;
else if (!p->rchild) s=p->lchild;
else{ q=p; s=p->lchild;
while(s->rchild) { q=s; s=s->rchild; }
p->data=s->data;
if (q==p) q->lchild=s->lchild;
else q->rchild=s->lchild;
free(s);
tag=1; }
if (!tag){ if ( !f ) T=s; //左右孩子中至少有一个不存在
else if ( f->lchild==p ) f->lchild=s;
else f->rchild=s;
free(p);
return;
}
}
删除二叉排序树中结点的算法 —— 删除找到的结点二叉排序树上的查找
在二叉排序树上进行查找,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程 。 它可以是一个递归的过程 。
假设想要在二叉排序树中查找关键字为 x的元素,查找过程从根结点开始 。 如果根指针为
NULL,则查找不成功；否则用给定值 x与根结点的关键字进行比较：
如果给定值等于根结点的关键字,则查找成功 。
如果给定值小于根结点的关键字,则继续递归查找根结点的左子树；
否则 。 递归查找根结点的右子树 。
int SearchBST(BiTree T,KeyType key,BiTree
f,BiTree &p){
//二叉排序树的递归查找算法
if (!T) {p=f; return FALSE;}
else if (EQ(key,T->data.key)){p=T;return
TRUE;}
else if (LT(key,T->data.key)) return
SearchBST(T->lchild,key,T,p);
else return SearchBST(T->rchild,key,T,p);
}
二叉排序树的查找 插入新结点 88
每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。
AVL树 高度平衡的二叉查找树
AVL树的定义一棵 AVL树或者是空树，或者是具有下列性质的二叉查找树,它的左子树和右子树都是 AVL树，且左子树和右子树的高度之差的绝对值不超过 1。
高度不平衡的二叉排序树 高度平衡的二叉查找树结点的平衡因子 balance (balance factor)
每个结点附加一个数字，给出该结点右子树的高度减去左子树的高度所得的高度差。这个数字即为结点的平衡因子 balance。
根据 AVL树的定义，任一结点的平衡因子只能取 -1,0和 1。
如果一个结点的平衡因子的绝对值大于 1，则这棵二叉查找树就失去了平衡，不再是 AVL树。
如果一棵二叉查找树是高度平衡的，它就成为
AVL树。如果它有 n 个结点，其高度可保持在
O(log2n)，平均查找长度也可保持在 O(log2n)。
AVL树的类型定义
typedef struct BSTNode {
ElemType data;
struct BSTNode *lchild,*rchild;
int bf; //结点的平衡因子
} BSTNode,*BSTree;
平衡化旋转
如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，
使之平衡化。
平衡化旋转有两类：
单旋转 (左旋和右旋 )
双旋转 (左平衡和右平衡 )
每插入一个新结点时,AVL树中相关结点的平衡状态会发生改变。因此，在插入一个新结点后，需要 从插入位置沿通向根的路径回溯,检查各结点的平衡因子 (左、右子树的高度差 )。
如果在某一结点发现高度不平衡，停止回溯。
从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。
如果这三个结点处于一条直线上，则采用单旋转进行平衡化 。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状相关。
如果这三个结点处于一条折线上，则采用双旋转进行平衡化 。双旋转分为先左后右和先右后左两类。
右单旋转 左单旋转 左右双旋转 右左双旋转左单旋转 (RotateLeft )
h
h h
A
C
E
B
D
(a) (b) (c)
h
h
h+
1
B
A
C
ED
h h
h+
1
C
EA
B D
如果在子树 E中插入一个新结点,该子树高度增 1导致结点 A的平衡因子变成 +2,出现不平衡 。
沿插入路径检查三个结点 A,C和 E。 它们处于一条方向为,\”的直线上,需要做左单旋转 。
以结点 C为旋转轴,让结点 A反时针旋转 。
+1 +2
0 +1 0
0
void L_Rotate(BSTree &p) //左单旋转的算法
{
BSTree rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p; p=rc;
}
右单旋转 (RotateRight )
h
h h
A
C
E
B
D
(a) (b) (c)
h
h+
1
B
A
C
ED
h h
h+
1
CE
A
B
D
在左子树 D上插入新结点使其高度增 1，导致结点 A的平衡因子增到 -2，造成了不平衡。
为使树恢复平衡，从 A沿插入路径连续取 3个结点 A、
B和 D，它们处于一条方向为,/”的直线上，需要做右单旋转。
以结点 B为旋转轴，将结点 A顺时针旋转。
h
0
0
0
-1
-1
-2
void R_Rotate(BSTree &p) //右单旋转的算法
{
BSTree lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p; p=lc;
}
先左后右双旋转 (RotationLeftRight)
在子树 F或 G中插入新结点,该子树的高度增 1。 结点
A的平衡因子变为 -2,发生了不平衡 。
从结点 A起沿插入路径选取 3个结点 A,B和 E,它们位于一条形如,?” 的折线上,因此需要进行先左后右的双旋转 。
首先以结点 E为旋转轴,将结点 B反时针旋转,以 E代替原来 B的位置,做左单旋转 。
再以结点 E为旋转轴,将结点 A顺时针旋转,做右单旋转 。 使之平衡化 。
插入左单旋转右单旋转
0
0
-1 -2
+1
-1
0
0
+1
先右后左双旋转 (RotationRightLeft)
右左双旋转是左右双旋转的镜像 。
在子树 F或 G中插入新结点,该子树高度增 1。 结点 A
的平衡因子变为 2,发生了不平衡 。
从结点 A起沿插入路径选取 3个结点 A,C和 D,它们位于一条形如,?” 的折线上,需要进行先右后左的双旋转 。
首先做右单旋转：以结点 D为旋转轴,将结点 C顺时针旋转,以 D代替原来 C的位置 。
再做左单旋转：以结点 D为旋转轴,将结点 A反时针旋转,恢复树的平衡 。
左单旋转插入右单旋转
+1
0
0
0
0-1
-1
+1
+2
AVL树的插入
在向一棵本来是高度平衡的 AVL树中插入一个新结点时,如果树中某个结点的平衡因子的绝对值 |balance| > 1,则出现了不平衡,需要做平衡化处理 。
算法从一棵空树开始，通过输入一系列对象的关键字，逐步建立 AVL树。在插入新结点时使用了前面所给的算法进行平衡旋转。
1616
例，输入关键字序列为 { 16,3,7,11,9,26,18,14,
15 },插入和调整过程如下。
0
3
16
3
-1
0
7
0
1
-2
左右双旋 7
3 16
0 0
0
7
3
11
0
-1
1
7
3 16
16
11
9
0
-1
-2
右单旋 3
7
169
0 0
0
1
3
7
11
26
9 16
11
0
1
1
22
18 18
0
3
16
3
-1
0
16
0
2 右左双旋
7
3 9
0
0
0
18
26
11
-1
7
3 26
16
11
9
-1
左单旋
9
7
16
14
0
0
1
7
11
26
269
1
1
11
15
18
2
3
18
16
-2
左右双旋
7
3
0
0
0
11
7
14
9
-1
16
15
0
1
11
26 26
14
1
-2
9
从空树开始的建树过程散列 (Hashing)
在线性表、树结构中查找纪录是通过与关键字的,比较,完成的。
顺序查找，比较的结果为,=”或,≠,
非顺序查找，比较的结果为,<”,,=”,,>”
散列的思想：
根据记录的关键字直接找到记录的存储位置，
即为关键字和记录的存储位置建立一个对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。
对应关系 f为 散列函数,按该思想建立的表为 散列表 。
根据设定的哈希函数 H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，
并以关键字在地址集中的,像,作为纪录在表中的存储位置，这种表便称为哈希表，这一影像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
哈希表的定义
散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系 Hash( )，使每个关键字与结构中一个唯一存储位置相对应：
Address ＝ Hash ( Rec.key )
在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，
并按此位置存放。
构造散列函数时的几点要求：
散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m个 地址时,其值域必须在 0 到 m-1 之间。
散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取
0到 m-1 中的每一个值。
散列函数应是简单的，能在较短的时间内计算出结果。
哈希函数的构造方法
1,直接定址法此类函数直接取关键字或关键字的某个 线性函数 值作为散列地址：
Hash ( key ) ＝ a * key + b { a,b为常数 }
这类散列函数是一对一的映射，一般不会产生冲突。
但是，它要求散列地址空间的大小与关键字集合的大小相同。
2,数字分析法设有 n个 d位数，每一位可能有 r种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；
在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。
9 4 2 1 4 8
9 4 1 2 6 9
9 4 0 5 2 7
9 4 1 6 3 0
9 4 1 8 0 5
9 4 1 5 5 8
9 4 2 0 4 7
9 4 0 0 0 1
① ② ③ ④ ⑤ ⑥
数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。
3,平方取中法取关键字平方后的中间几位为 Hash地址,
所取的位数和 Hash地址位数相同 。 这是一种较常用的构造 Hash函数的方法 。 因为通常在选定 Hash函数时不一定能知道关键字的全部情况,难以决定取其中哪几位比较合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机每布的关键字得到的 Hash
地址也是随机的 。
4,折叠法
此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。
把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。
有两种叠加方法：
移位法 — 把各部分的最后一位对齐相加；
分界法 — 各部分不折断，沿各部分的分界来回折叠，
然后对齐相加，将相加的结果当做散列地址。
示例：设给定的关键字为 key = 23938587841，若存储空间限定 3 位,则划分结果为每段 3 位,上述关键字可划分为
4段：
239 385 878 41
把超出地址位数的最高位删去,仅保留最低的 3位，做为可用的散列地址。
冲突处理
1,开放定址法开放定址法的基本做法是在发生冲突时,按照某种方法继续探测基本表中的其它存储单元,直到找到一个开放的地址 （ 即空位置 ） 为止 。 显然这种方法需要用某种标记区分空单元与非空单元 。
开放定址法的一般形式可表示为：
Hi（ k） =（ H（ k） +di） mod m（ i=1,2,…,k（ k?m-1））
其中,H（ k） 为键字为 k的直接哈希地址,m为哈希表长,di为每次再探测时的地址增量 。
当 di=1,2,3,…,m-1时,称为线性探测再散列；
当 di=12,-12,22,-22,…,k2,-k2（ k?m/2） 时,称为二次探测再散列；当 di=随机数序列时,称为随机探测再散列 。
例如，有数据（ 654,638,214,357,376,854，
662,392），现采用数字分析法，取得第二位数作为哈希地址，将数据逐个存放入大小为 10的散列表
（此处为顺序表）中。若采用线性探测法解决地址冲突，则 8个数据全部插入完成后，散列表的状态如表 9.2所示。
392 214 638 654 357 376 854 662
0 1 2 3 4 5 6 7 8 9
2,再哈希法采用再哈希法解决冲突的做法是当待存入散列表的某个元素 k在原散列函数 H（ k）的映射下与其它数据发生碰撞时，采用另外一个 Hash函数 Hi（ k）（ i=1，
2,…,n）计算 k的存储地址（ Hi均是不同的 Hash函数），这种计算直到冲突不再发生为止。
3,拉链法拉链法解决冲突的做法是，将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m，则可将散列表定义为一个由 m个头指针组成的指针数组 T[0..m-1]，凡是散列地址为 i的结点，均插入到以 T[i]为头指针的单链表中。
拉链法的缺点主要是指针需要用额外的空间 。
例如,关键字集合为 {1,13,20,5,14,33}，
散列表长度 m=5,现采用除余法为哈希函数并采用拉链法解决地址冲突,所创建的 Hash链表如下图所示 。
t[0]
t[1]
t[2]
t[3]
t[4]
5
1 ^
20 ^
33 13 ^
14 ^
^
掌握 简单的查找结构：
查找的概念
查找结构
查找的判定树
平均查找长度
静态查找
顺序查找算法、分析
折半查找算法、分析小结 需要复习的知识点
二叉查找树
定义
查找、平均查找长度
插入、删除、
AVL树
定义
插入、平衡化旋转
删除、平衡化旋转
高度
查找的概念
查找结构决定查找的效率
查找算法基于查找结构
查找效率用平均查找长度衡量
平均查找长度表明查找算法的整体性能，避开偶然因素
平均查找长度分查找成功与查找不成功两种情况
静态查找结构
顺序查找 — 顺序表、链表
折半查找 — 有序顺序表
动态查找结构
二叉排序树 — 无重复关键字
AVL树 — 平衡二叉排序树
二叉查找树
二叉查找树的子树是二叉查找树
35
15 45
50402510
20 30
结点左子树上所有关键字小于结点关键字
右子树上所有关键字大于结点关键字
查找成功时检测指针停留在树中某个结点。
查找不成功时检测指针停留在某个外结点（失败结点）。
35
15 45
502510
20 30
查找 22
查找 45
AVL树
理解,AVL树的子树也是 AVL树
掌握：插入新结点后平衡化旋转的方法
掌握：删除结点后平衡化旋转的方法
掌握：结点高度 h 与结点数 n 的关系思考题：
1、假定一个线性表为 (38,52,25,74,68,16,30,54,90,72)，
画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
2,假定一个待哈希存储的线性表为
(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为 HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。
3,试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。
