? 静态查找表
二叉排序树
平衡二叉树（ AVL树）
小结
B树
哈希表查找 (Search)的概念静态查找表
查找,就是 在数据集合中寻找满足某种条件的数据对象 。
查找表,是由 同一类型的数据元素 (或记录 )
组成的数据集合。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象。
查找不成功,或查找失败。作为结果，
报告一些信息，如失败标志、失败位臵等。
关键字,数据元素中某个数据项的值，用以标识一个数据元素。
主关键字,可唯一地标识一个数据元素的关键字。
次关键字,用以识别若干记录的关键字。
使用基于主关键字的查找，查找结果应是唯一的。
静态查找表（ p214）
动态查找表
9.1 静态查找表基本操作：
Create(&ST,n); //构造含有 n个元素的静态查找表 ST
Destroy(&ST); //销毁表
Search(ST,key); //查找关键字为 key的数据元素
Traverse(ST,visit()); //遍历查找表
衡量一个查找算法的时间效率的标准是,在查找过程中关键字的平均比较次数或平均读写磁盘次数 (只适合于外部查找 ),这个标准也称为平均查找长度 ASL(Average Search Length),通常它是 查找结构中对象总数 n 或文件结构中物理块总数 n 的函数 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题 。
在静态查找表中,数据对象存放于数组中,利用数组元素的下标作为数据对象的存放地址 。
查找算法 根据给定值 x,在数组中进行查找 。
直到找到 x在数组中的存放位臵或可确定在数组中找不到 x为止 。
9.1.1顺序表的查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
存储结构：
typedef struct{
ElemType *elem;
int length;
} SSTable;
查找过程：从表中最后一个元素开始,顺序用各元素的关键字与给定值 x进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位臵；否则,若直到第一个记录仍未找到关键字与 x相等的对象,则查找失败 。
算法 9.1 （ p217）
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
ipA SL
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。
9.1.2 有序表的查找
折半查找：先求位于查找区间正中的对象的下标 mid,用其关键字与给定值 x比较,
Element[mid].getKey( ) = x,查找成功；
Element[mid].getKey( ) > x,把查找区间缩小到表的 前半部分,再继续进行对分查找；
Element[mid].getKey( ) < x,把查找区间缩小到表的 后半部分,再继续进行对分查找 。
每比较一次,查找区间缩小一半 。 如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
9.1.2 有序表的查找
折半查找：
（ 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时,表明查找不成功,查找结束 。
查找成功的例子 查找失败的例子算法 9.2(p220)
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;
}
查找成功的情形 查找不成功的情形从有序表构造出的二叉查找树 (判定树 )
若设 n = 2h-1，则描述对分查找的二叉查找树是高度为 h 的满二叉树。 2h = n+1,h = log2(n+1)。
第 1层结点有 1个，查找第 1层结点要比较 1次；
第 2层结点有 2个，查找第 2层结点要比较 2次； …,
1）分块有序（升序或降序）
——第 I块中的最大（小）值小（大）于第 i+1块中的最（大）小值
2）查找
（ 1）先查索引表 ——折半查找
（ 2）再查顺序表 ——顺序查找块间有序，块内无序
typedef struct
{ int key;} Eletype;
typedef struct {
Elemtype *elem;
int length;
} SSTable;
# define BLOCK_NUM 3
9.1.2 索引顺序表的查找 —— 分块查找
Typedef struct {
int Maxkey;
int next; } BLKNode,IT[BLOCK_Num];
int Search_Bin(SSTable ST,int key) //折半查找
{ int i,p,low,high,mid;
printf(“Create index table,Input Maxkey& nex\n”)
for(i=1;i<=BLOCK_NUM;i++)
scanf(“%d,%d”,&IT[i].Maxkey,&IT[i].next)
if(key>IT[BLOCK_NUM].Maxkey) return(0);
low = 1; high=BLOCK_NUM;
while (low < =high)
{ mid = (low+high)/2;
if (IT[mid].Maxkey>=key)) high=mid-1;
else low=mid+1; }
i=IT[low].next;
ST.ele[0].key = key;
If(low!=BLOCK_NUM) p=IT[low+1].next;
else p=ST.length+1;
while(ST.elem[i%p].key != key ) i++ ;
return( i%p ) ;
}
性能分析：
ASL（ bls） =Lb+Lw=(b+1/)2 +(s+1)/2
=(b+s+2)/2 =(n/s+s)/2+1
b —— 分块的个数 b=n/2
s —— 每块中的记录个数
n —— 记录的总个数
Lb —— 确定所在的块
Lw —— 块内查找
12)1(
22)1( 232211 1221
h
hh
h
hh?
1)1(l o g1)1(l o g
1
))1(l o g)1((
1
)12)1((
1
22
2
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明这样第 i (1? i? h) 层结点有 2i -1个，查找第 i 层结点要比较 i次,… 。假定每个结点的查找概率相等，即
pi = 1/n，则查找成功的平均查找长度为
)22)1( 23
2211(
11
122
1
11
hh
n
i
i
n
i
iis u c c
hh
n
C
n
CPA S L
9.2 动态查找表表结构本身是在查找过程中动态生成的。
基本操作：
InitDSTable(&DT); //构造一个空的动态查找表 DT
DestroyDSTable(&DT); //销毁表
SearchDSTable(DT,key); //查找关键字为 key的数据元素
InsertDSTable(&DT,e);
DeleteDSTable(&DT,key);
TraverseDSTable(DT,visit()); //遍历查找表定义二叉排序树（二叉查找树） 或者是一棵空树，
或者是具有下列性质的二叉树：
每个结点都有一个作为查找依据的关键字
(key)，所有结点的关键字互不相同。
左子树 (若非空 )上所有结点的关键字都小于根结点的关键字。
右子树 (若非空 )上所有结点的关键字都大于根结点的关键字。
左子树和右子树也是二叉排序树。
9.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
每次结点的插入，都要从根结点出发查找插入位臵，然后把新结点作为叶结点插入。
二叉排序树的插入
为了向二叉排序树中插入一个新元素,必须先检查这个元素是否在树中已经存在 。
在插入之前,先使用查找算法在树中检查要插入元素有还是没有 。
查找成功,树中已有这个元素,不再插入 。
查找不成功,树中原来没有关键字等于给定值的结点,把新元素加到查找操作停止的地方 。
int InsertBST(BiTree &T,ElemType e){
//二叉排序树插入算法
BiTree s,p;
if (!SearchBST(T,e.key,NULL,p))
{ s=(BiTree)malloc(sizeof(BiTNode));
s->data=e; s->lchild=s->rchild=NULL;
if (!p) T=s;
else if (LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}
输入数据，建立二叉排序树的过程输入数据序列 { 53,78,65,17,87,09,81,45,23 }
同样 3 个数据 { 1,2,3 }，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。
如果输入序列选得不好，会建立起一棵单支树，
使得二叉排序树的高度达到最大，这样必然会降低查找性能。
{2,1,3}
{1,2,3} {1,3,2} {2,3,1} {3,1,2} {3,2,1}
1
2
3
1
1 1
1
3
2 2
2
3
3
2
3
二叉排序树的删除
在二叉排序树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会失去 。
为保证在执行删除后,树的查找性能不至于降低,还 需要防止重新链接后树的高度增加 。
删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可 。
被删结点缺右子树,可以拿它的左子女结点顶替它的位臵,再释放它 。
被删结点缺左子树,可以拿它的右子女结点顶替它的位臵,再释放它 。
被删结点左、右子树都存在,可以在它的右子树中寻找中序下的第一个结点 (关键字最小 ),用它的值填补到被删结点中，再来处理这个结点的删除问题。或：在它的左子树中寻找中序下的最后一个结点，用它的值替换被删结点，再处理该结点的删除。（书上算法 9.8即为第二种办法）
二叉排序树的删除递归算法（算法 9.7)
int DeleteBST(BiTree &T,KeyType key){
if (!T) return FALSE;
else {
if (EQ(key,T->data.key)) {return Delete(T);}
else if (LT(key,T->data.key)) return DeleteBST(T-
>lchild,key);
else return DeleteBST(T->rchild,key);
}
}
int Delete(BiTree &p){//算法 9.8
BiTree q,s;
if (!p->rchild){
q=p; p=p->lchild; free(q); }
else if (!p->lchild){
q=p; p=q->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;
delete s; }
return TRUE;}
最优二叉查找树
对于有 n 个关键字的集合，其关键字有 n! 种不同的排列，可构成的不同二叉查找树有
(棵 )
如何评价这些二叉查找树，可以用树的查找效率来衡量。
例如，已知关键字集合 { a1,a2,a3 } = { do,if,
to }，对应查找概率为 p1=0.5,p2=0.1,p3=0.05,
在各个查找不成功的间隔内查找概率又分别为
q0=0.15,q1=0.1,q2=0.05,q3=0.05。可能的二叉查找树如下所示。
C n nn 21 1?
(b)
(d)
(a)
(c)
(e)
在扩充二叉查找树中
○ 表示内部结点,包含了关键字集合中的某一个关键字；
□ 表示外部结点,代表造成查找失败的各关键字间隔中的不在关键字集合中的关键字 。
在每两个外部结点之间必然存在一个内部结点 。
设二叉树的内部结点有 n 个，外部结点有 n+1
个。如果定义每个结点的路径长度为该结点的层次，并用 I 表示所有 n 个内部结点的路径长度之和,用 E 表示 n+1 个外部结点的路径长度之和,
可以用归纳法证明,E = I+2n。
一棵扩充二叉查找树的 查找成功的平均查找长度 ASLsucc可以定义为 该树所有内部结点上的权值 p[i]与查找该结点时所需的 关键字比较次数 c[i]
(= l[i] + 1)乘积之和：
).][(*][ 1p
1
i liA S L
n
i
s u c c
扩充二叉查找树 查找不成功的平均查找长度
ASLunsucc为树中所有外部结点上权值 q[j]与到达外部结点所需关键字比较次数 c'[j](= l'[j])乘积之和：
n
j
u n su c c jljA S L
0
q ].[ *][
扩充二叉查找树总的平均查找长度为：
ASL = ASLsucc + ASLunsucc
所有内、外部结点上的权值关系为
n
i
n
j
ji
1 0
qp 1][][
(1) 相等查找概率的情形若设树中所有内,外部结点的查找概率都相等：
p[i] = q[j] = 1/7,1? i? 3,0? j? 3
图 (a),ASLsucc = 1/7*3+1/7*2+1/7*1 = 6/7,
ASLunsucc = 1/7*3*2+1/7*2+1/7*1 = 9/7。
总平均查找长度 ASL = 6/7 + 9/7 = 15/7。
图 (a),ASL = 15/7 图 (d),ASL = 15/7
图 (b),ASL = 13/7 图 (e),ASL = 15/7
图 (c),ASL = 15/7
图 (b)的情形所得的平均查找长度最小。一般把平均查找长度达到最小的扩充二叉查找树称作最优二叉查找树，
在 相等查找概率的情形 下，因为所有内部结点、
外部结点的查找概率都相等，把它们的权值都视为 1。同时，第 k 层有 2k 个结点,k = 0,1,?。则有 n 个内部结点的扩充二叉查找树的内部路径长度 I 至少等于序列
0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…
的前 n项的和。
因此，最优二叉查找树的查找成功的平均查找长度和查找不成功的平均查找长度分别为,
.?
n
i
s u c c iA S L
1
2 1l o g
,?
1n
ni
u n s u c c iA SL
2
1
2l o g
(2) 不相等查找概率的情形
设树中所有内、外部结点的查找概率互不相等,p[1] =
0.5,p[2] = 0.1,p[3] = 0.05
q[0] = 0.15,q[1] = 0.1,q[2] = 0.05,q[3] = 0.05
图 (a),ASLsucc = 0.5*3 + 0.1*2 + 0.05*1 = 1.75，
ASLunsucc = 0.15*3 + 0.1*3 + 0.05*2 + 0.05*1= 0.9。 ASL
= ASLsucc + ASLunsucc = 2.65。
图 (a),ASL = 2.65 图 (d),ASL = 2.15
图 (b),ASL = 1.9 图 (e),ASL = 1.6
图 (c),ASL = 0.85
由此可知，图 (c)的情形下树的平均查找长度达到最小，
因此，图 (c)的情形是最优二叉查找树。
不相等查找概率情形下的最优二叉查找树可能不同于完全二叉树的形态。
考虑在不相等查找概率情形下如何构造最优二叉查找树。
假设关键字集合放在一个 有序的顺序表 中
{ key[1],key[2],key[3],… key[n] }
设最优二叉查找树为 T[0][n]，其平均查找长度为：
n
j
n
i
nCjljiliA S L
01
0q1p ]][[][ *][)][(*][
l [i]是 内部结点 a[i] 所在的层次号,l [j] 是 外部结点 j 所在的层次号。 C[0][n] 是树的代价。
为计算方便，将 p[i] 与 q[j] 化为整数。
构造最优二叉查找树
要构造最优二叉查找树，必须先构造它的左子树和右子树，它们也是最优二叉查找树。
对于任一棵子树 T[i][j]，它由
{ key[i+1],key[i+2],…,key[j] }
组成，其内部结点的权值为
{ p[i+1],p[i+2],…,p[ j] }
外部结点的权值为
{ q[i],q[i+1],q[i+2],…,q[ j] }
使用数组 W[i][j]来存放它的累计权值和：
W[i][j] = q[i] + p[i+1] + q[i+1] + p[i+2] +
+ q[i+2]+…+ p[ j] + q[j],0? i? j? n
计算 W[i][j]可以用递推公式,
W[i][i] = q[i]
//不是二叉树,只有一个外部结点
W[i][i+1] = q[i] + p[i+1] + q[i+1]
= W[i][i] + p[i+1] + q[i+1]
//有一个内部结点及两个外部结点的二叉树
W[i][i+2] = W[i][i+1] + p[i+2] + q[i+2]
//加一个内部结点和一个外部结点的二叉树一般地，
W[i][j] = W[i][j-1] + p[j] + q[j]
//再加一个内部结点和一个外部结点对于一棵包括关键字
{ key[i+1],…,key[k-1],key[k],key[k+1],…,key[j] }
的子树 T[i][j],若设它的 根结点为 k,i < k? j，
它的代价为：
C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j]
C[i][k-1]是其包含关键字 { key[i+1],key[i+2],…,
key[k-1] } 的左子树 T[i][k-1]的代价
C[i][k-1]+W[i][k-1]等于把左子树每个结点的路径长度加 1而计算出的代价
C[k][j]是包含关键字 { key[k+1],key[k+2],…,
key[j] } 的右子树 T[k][j]的代价
C[k][j] + W[k][j]是把右子树每个结点的路径长度加 1之后计算出的代价 。
因此，公式
C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j]
表明：整个树的代价等于其左子树的代价加上其右子树的代价，再加上根的权值。
因为 W[i][j] = p[k] + W[i][k-1] + W[k][j]，
故有
C[i][j] = W[i][j] + C[i][k-1] + C[k][j]
可用 k = i+1,i+2,…,j 分别计算上式，选取使得
C[i][j]达到最小的 k。这样可将最优二叉查找树
T[i][j]构造出来。
构造最优二叉查找树的方法就是 自底向上逐步构造 的方法。
构造的步骤
第一步，构造 只有一个内部结点 的最优查找树：
T[0][1],T[1][2],…,T[n-1][n]。
在 T[i-1][i] (1? i? n) 中只包含关键字 key[i]。其代价分别是 C[i-1][i] = W[i-1][i]。另外设立一个数组 R[0..n][0..n] 存放各最优二叉查找树的根。
R[0][1] = 1,R[1][2] = 2,…,R[n-1][n] = n。
第二步,构造 有两个内部结点 的最优二叉查找树：
T[0][2],T[1][3],…,T[n-2][n]。在 T[i-2][i]中包含两个关键字 { key[i-1],key[i] }。其代价取分别以 key[i-1],key[i] 做根时计算出的 C[i-2][i] 中的小者。
第三步，第四步,…,构造有 3 个内部结点，
有 4 个内部结点,… 的最优二叉查找树。
最后构造出包含有 n 个内部结点的最优二叉查找树。对于这样的最优二叉查找树，若设 根为 k，
则 根 k 的值存于 R[0][n] 中，其 代价存于 C[0][n]
中,左子树的根存于 R[0][k-1]中,右子树的根存于 R[k][n] 中。
例：给出关键字集合和内、外部结点的权值序列第一步关键字集合 key1 key2 key3
实 例 do if to
对应 内部结点 p1=50 p2=10 p3=5
权值 外部结点 q0=15 q1=10 q2=5 q3=5
第二步
C 115 165 50 60
W 90 90 35 35
R 1 2 2 3
左子树 T[0,0] T[0,1] T[1,1] T[1,2]
右子树 T[1,2] T[2,2] T[2,3] T[3,3]
第三步
C 150 190 215
W 100 100 100
R 1 2 3
左子树 T[0,0] T[0,1] T[0,2]
右子树 T[1,3] T[2,3] T[3,3]
0 0 75 115 150
1 0 25 50
2 0 15
3 0
0 15 75 90 100
1 10 25 35
2 5 15
3 5
W[i][j] C[i][j]
R[i][j]
3个关键字 { do,if,to } 的最优二叉查找树
0 1 2 3 0 1 2 3
0 1 2 3
0 0 1 1 1
1 0 2 2
2 0 3
3 0
p1=50,p2=10,p3=5
q0=15,q1=10,q2= 5,q3= 5
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;
基本操作：
void R_Rotate(BSTree &p);
void L_Rotate(BSTree &p);
Status InsertAVL(BSTree &T,ElemType e,Boolean
&taller);
void LeftBalance(BSTree &T);
void RightBalance(BSTree &T);
平衡化旋转
如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，
使之平衡化。
平衡化旋转有两类：
单旋转 (左旋和右旋 )
双旋转 (左平衡和右平衡 )
每插入一个新结点时,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){
//左单旋转的算法 (p236 算法 9.10)
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){
//右单旋转的算法（ p236 算法 9.9）
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
void LeftBalance(BSTree &T){//左平衡化的算法
BSTree lc,rd; lc=T->lchild;
switch(lc->bf){
case LH,T->bf = lc->bf = EH;
R_Rotate(T); break;
case RH,rd=lc->rchild;
switch(rd->bf){
case LH,T->bf=RH; lc->bf=EH; break;
case EH,T->bf=lc->bf=EH; break;
case RH,T->bf = EH; lc->bf=LH; break; }
rd->bf=EH;
L_Rotate(T->lchild);
R_Rotate(T);
}
}
先右后左双旋转 (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
从空树开始的建树过程
AVL树的删除
如果 被删结点 x最多只有一个子女,那么问题比较简单 。 如果 被删结点 x有两个子女,首先查找 x 在 中序次序下的直接前驱 y (同样可以找直接后继 )。 再把结点 y 的内容传送给 结点 x,现在问题转移到删除 结点 y。
把 结点 y当作 被删结点 x。
将 结点 x从树中删去 。 因为结点 x最多有一个子女,
我们可以简单地把 x的双亲结点中原来指向 x的指针改指到这个子女结点 ；如果结点 x没有子女,x双亲结点的相应指针臵为 NULL。 然后将原来以结点 x为根的子树的高度减 1，
必须沿 x 通向根的路径反向追踪高度的变化对路 径上各个结点的影响。
用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance，有时还要依赖子女的 balance 。
布尔变量 shorter 的值初始化为 True。然后对于 从 x
的双亲到根的路径上的各个结点 p，在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成 False，
算法终止。
case 1,当前结点 p 的 balance为 0。如果它的左子树或右子树被缩短，则它的 balance改为
1 或 -1，同时 shorter 臵为 False。
case 2,结点 p 的 balance不为 0，且较高的子树被缩短，则 p 的 balance改为 0，同时
shorter 臵为 True。
case 3,结点 p 的 balance不为 0，且较矮的子树又被缩短，则在结点 p 发生不平衡。需要进行平衡化旋转来恢复平衡。令 p 的较高的子树的根为 q (该子树未被缩短 ),根据 q 的 balance，
有如下 3 种平衡化操作。
case 3a,如果 q 的 balance为 0，执行一个单旋转来恢复结点 p 的平衡，臵 shorter为 False。
case 3b,如果 q 的 balance与 p 的 balance相同，
则执行一个单旋转来恢复平衡，结点 p 和 q 的
balance均改为 0，同时臵 shorter为 True。
case 3c,如果 p 与 q 的 balance相反，则执行一个双旋转来恢复平衡，先围绕 q 转再围绕 p 转。
新的根结点的 balance臵为 0，其它结点的
balance相应处理，同时臵 shorter为 True。
在 case 3a,3b和 3c的情形中，旋转的方向取决于是结点 p 的哪一棵子树被缩短。
AVL树的高度
设在新结点插入前 AVL树的高度为 h,结点个数为 n,则插入一个新结点的时间是 O(h)。 对于 AVL树来说,h多大？
设 Nh 是高度为 h 的 AVL树的最小结点数 。 根的一棵子树的高度为 h-1,另一棵子树的高度为 h-2,这两棵子树也是高度平衡的 。 因此有
N-1 = 0 (空树 )
N0 = 1 (仅有根结点 )
Nh = Nh-1 + Nh-2 +1,h > 0
可以证明,对于 h? 0,有 Nh = Fh+3 -1 成立 。
有 n 个结点的 AVL树的高度不超过
在 AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。
二叉查找树适合于组织在内存中的较小的索引
(或目录 )。对于存放在外存中的较大的文件系统，用二叉查找树来组织索引不太合适。
在文件检索系统中大量使用的是用 B_树或 B+
树做文件索引。
)1(l o g23 2?n
掌握 简单的查找结构：
查找的概念
查找结构
查找的判定树
平均查找长度
静态查找
顺序查找算法、分析
折半查找算法、分析小结 需要复习的知识点
二叉查找树
定义
查找、平均查找长度
插入、删除、
AVL树
定义
插入、平衡化旋转
删除、平衡化旋转
高度
查找的概念
查找结构决定查找的效率
查找算法基于查找结构
查找效率用平均查找长度衡量
平均查找长度表明查找算法的整体性能，避开偶然因素
平均查找长度分查找成功与查找不成功两种情况
静态查找结构
顺序查找 — 顺序表、链表
折半查找 — 有序顺序表
动态查找结构
二叉排序树 — 无重复关键字
AVL树 — 平衡二叉排序树
有序顺序表的顺序查找
( 10,20,30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
2
71
6
1 5
0
i
s u c c iA S L
7
27
61
7
1 5
0
i
u n s u c c
i
A S L
有序顺序表的折半查找
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
二叉查找树
二叉查找树的子树是二叉查找树
35
15 45
50402510
20 30
结点左子树上所有关键字小于结点关键字
右子树上所有关键字大于结点关键字
n 个结点的二叉查找树的数目
【例】 3 个结点的二叉查找树
5
1*2*3
4*5*6*
4
1C
13
1 3
3*2
1
2
2
1
3
3 1 3
2
1
2
3
1
2
3
{123} {132} {213} {231} {312} {321}
查找成功时检测指针停留在树中某个结点。
查找不成功时检测指针停留在某个外结点（失败结点）。
35
15 45
502510
20 30
查找 22
查找 45
A
B
C
E
A
B
C
D
ED
二叉查找树的高度越小，平均查找长度越小。
n 个结点的二叉查找树的高度最大为 n-1,最小为?log2n?.
AVL树
理解,AVL树的子树也是 AVL树
掌握：插入新结点后平衡化旋转的方法
掌握：删除结点后平衡化旋转的方法
掌握：结点高度 h 与结点数 n 的关系二叉排序树的删除
要求：删除一个结点后，仍然保持二叉排序树的有序性删除结点的算法：
（ 1）确定被删除结点：
A,有没有被删除的结点；
B,若有，则确定被删除的结点是根结点还是一般结点
（ 2）如果被删除结点是根结点，则调用删除根结点的算法；
（ 3）如果被删除结点是一般结点，则调用删除一般结点的算法。
删除二叉排序树的根结点的算法
（ 1） 根结点有左右子树的情况下，选择根结点的左子树中的最大结点为新的根结点；
最大结点 —— 中序遍历
（ 2）如果根结点没有左子树，则以右子树的根结点作为新的根结点；
（ 3）如果根结点没有右子树，则以左子树的根结点作为新的根结点删除二叉排序树的一般结点的算法
（ 1） 若被删除结点 P有左、右子树，则按照中序遍历找其左子树中的最大结点，以此最大结点的值代替 P结点的值，然后删除此最大结点（如同删除根结点）
（ 2）若被删除结点 P没有左子树，则把结点 P的右子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
（ 3）若被删除结点 P没有右子树，则把结点 P的左子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
二叉排序树
平衡二叉树（ AVL树）
小结
B树
哈希表查找 (Search)的概念静态查找表
查找,就是 在数据集合中寻找满足某种条件的数据对象 。
查找表,是由 同一类型的数据元素 (或记录 )
组成的数据集合。
查找的结果通常有两种可能：
查找成功,即找到满足条件的数据对象。
查找不成功,或查找失败。作为结果，
报告一些信息，如失败标志、失败位臵等。
关键字,数据元素中某个数据项的值，用以标识一个数据元素。
主关键字,可唯一地标识一个数据元素的关键字。
次关键字,用以识别若干记录的关键字。
使用基于主关键字的查找，查找结果应是唯一的。
静态查找表（ p214）
动态查找表
9.1 静态查找表基本操作：
Create(&ST,n); //构造含有 n个元素的静态查找表 ST
Destroy(&ST); //销毁表
Search(ST,key); //查找关键字为 key的数据元素
Traverse(ST,visit()); //遍历查找表
衡量一个查找算法的时间效率的标准是,在查找过程中关键字的平均比较次数或平均读写磁盘次数 (只适合于外部查找 ),这个标准也称为平均查找长度 ASL(Average Search Length),通常它是 查找结构中对象总数 n 或文件结构中物理块总数 n 的函数 。
另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题 。
在静态查找表中,数据对象存放于数组中,利用数组元素的下标作为数据对象的存放地址 。
查找算法 根据给定值 x,在数组中进行查找 。
直到找到 x在数组中的存放位臵或可确定在数组中找不到 x为止 。
9.1.1顺序表的查找 (Sequential Search)
所谓顺序查找,又称线性查找,主要用于在线性结构中进行查找 。
存储结构：
typedef struct{
ElemType *elem;
int length;
} SSTable;
查找过程：从表中最后一个元素开始,顺序用各元素的关键字与给定值 x进行比较,若找到与其值相等的元素,则查找成功,给出该元素在表中的位臵；否则,若直到第一个记录仍未找到关键字与 x相等的对象,则查找失败 。
算法 9.1 （ p217）
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
ipA SL
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。
9.1.2 有序表的查找
折半查找：先求位于查找区间正中的对象的下标 mid,用其关键字与给定值 x比较,
Element[mid].getKey( ) = x,查找成功；
Element[mid].getKey( ) > x,把查找区间缩小到表的 前半部分,再继续进行对分查找；
Element[mid].getKey( ) < x,把查找区间缩小到表的 后半部分,再继续进行对分查找 。
每比较一次,查找区间缩小一半 。 如果查找区间已缩小到一个对象,仍未找到想要查找的对象,则查找失败 。
9.1.2 有序表的查找
折半查找：
（ 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时,表明查找不成功,查找结束 。
查找成功的例子 查找失败的例子算法 9.2(p220)
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;
}
查找成功的情形 查找不成功的情形从有序表构造出的二叉查找树 (判定树 )
若设 n = 2h-1，则描述对分查找的二叉查找树是高度为 h 的满二叉树。 2h = n+1,h = log2(n+1)。
第 1层结点有 1个，查找第 1层结点要比较 1次；
第 2层结点有 2个，查找第 2层结点要比较 2次； …,
1）分块有序（升序或降序）
——第 I块中的最大（小）值小（大）于第 i+1块中的最（大）小值
2）查找
（ 1）先查索引表 ——折半查找
（ 2）再查顺序表 ——顺序查找块间有序，块内无序
typedef struct
{ int key;} Eletype;
typedef struct {
Elemtype *elem;
int length;
} SSTable;
# define BLOCK_NUM 3
9.1.2 索引顺序表的查找 —— 分块查找
Typedef struct {
int Maxkey;
int next; } BLKNode,IT[BLOCK_Num];
int Search_Bin(SSTable ST,int key) //折半查找
{ int i,p,low,high,mid;
printf(“Create index table,Input Maxkey& nex\n”)
for(i=1;i<=BLOCK_NUM;i++)
scanf(“%d,%d”,&IT[i].Maxkey,&IT[i].next)
if(key>IT[BLOCK_NUM].Maxkey) return(0);
low = 1; high=BLOCK_NUM;
while (low < =high)
{ mid = (low+high)/2;
if (IT[mid].Maxkey>=key)) high=mid-1;
else low=mid+1; }
i=IT[low].next;
ST.ele[0].key = key;
If(low!=BLOCK_NUM) p=IT[low+1].next;
else p=ST.length+1;
while(ST.elem[i%p].key != key ) i++ ;
return( i%p ) ;
}
性能分析：
ASL（ bls） =Lb+Lw=(b+1/)2 +(s+1)/2
=(b+s+2)/2 =(n/s+s)/2+1
b —— 分块的个数 b=n/2
s —— 每块中的记录个数
n —— 记录的总个数
Lb —— 确定所在的块
Lw —— 块内查找
12)1(
22)1( 232211 1221
h
hh
h
hh?
1)1(l o g1)1(l o g
1
))1(l o g)1((
1
)12)1((
1
22
2
nn
n
n
nnn
n
h
n
A S L
h
s u c c
可以用归纳法证明这样第 i (1? i? h) 层结点有 2i -1个，查找第 i 层结点要比较 i次,… 。假定每个结点的查找概率相等，即
pi = 1/n，则查找成功的平均查找长度为
)22)1( 23
2211(
11
122
1
11
hh
n
i
i
n
i
iis u c c
hh
n
C
n
CPA S L
9.2 动态查找表表结构本身是在查找过程中动态生成的。
基本操作：
InitDSTable(&DT); //构造一个空的动态查找表 DT
DestroyDSTable(&DT); //销毁表
SearchDSTable(DT,key); //查找关键字为 key的数据元素
InsertDSTable(&DT,e);
DeleteDSTable(&DT,key);
TraverseDSTable(DT,visit()); //遍历查找表定义二叉排序树（二叉查找树） 或者是一棵空树，
或者是具有下列性质的二叉树：
每个结点都有一个作为查找依据的关键字
(key)，所有结点的关键字互不相同。
左子树 (若非空 )上所有结点的关键字都小于根结点的关键字。
右子树 (若非空 )上所有结点的关键字都大于根结点的关键字。
左子树和右子树也是二叉排序树。
9.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
每次结点的插入，都要从根结点出发查找插入位臵，然后把新结点作为叶结点插入。
二叉排序树的插入
为了向二叉排序树中插入一个新元素,必须先检查这个元素是否在树中已经存在 。
在插入之前,先使用查找算法在树中检查要插入元素有还是没有 。
查找成功,树中已有这个元素,不再插入 。
查找不成功,树中原来没有关键字等于给定值的结点,把新元素加到查找操作停止的地方 。
int InsertBST(BiTree &T,ElemType e){
//二叉排序树插入算法
BiTree s,p;
if (!SearchBST(T,e.key,NULL,p))
{ s=(BiTree)malloc(sizeof(BiTNode));
s->data=e; s->lchild=s->rchild=NULL;
if (!p) T=s;
else if (LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}
输入数据，建立二叉排序树的过程输入数据序列 { 53,78,65,17,87,09,81,45,23 }
同样 3 个数据 { 1,2,3 }，输入顺序不同，建立起来的二叉排序树的形态也不同。这直接影响到二叉排序树的查找性能。
如果输入序列选得不好，会建立起一棵单支树，
使得二叉排序树的高度达到最大，这样必然会降低查找性能。
{2,1,3}
{1,2,3} {1,3,2} {2,3,1} {3,1,2} {3,2,1}
1
2
3
1
1 1
1
3
2 2
2
3
3
2
3
二叉排序树的删除
在二叉排序树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会失去 。
为保证在执行删除后,树的查找性能不至于降低,还 需要防止重新链接后树的高度增加 。
删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可 。
被删结点缺右子树,可以拿它的左子女结点顶替它的位臵,再释放它 。
被删结点缺左子树,可以拿它的右子女结点顶替它的位臵,再释放它 。
被删结点左、右子树都存在,可以在它的右子树中寻找中序下的第一个结点 (关键字最小 ),用它的值填补到被删结点中，再来处理这个结点的删除问题。或：在它的左子树中寻找中序下的最后一个结点，用它的值替换被删结点，再处理该结点的删除。（书上算法 9.8即为第二种办法）
二叉排序树的删除递归算法（算法 9.7)
int DeleteBST(BiTree &T,KeyType key){
if (!T) return FALSE;
else {
if (EQ(key,T->data.key)) {return Delete(T);}
else if (LT(key,T->data.key)) return DeleteBST(T-
>lchild,key);
else return DeleteBST(T->rchild,key);
}
}
int Delete(BiTree &p){//算法 9.8
BiTree q,s;
if (!p->rchild){
q=p; p=p->lchild; free(q); }
else if (!p->lchild){
q=p; p=q->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;
delete s; }
return TRUE;}
最优二叉查找树
对于有 n 个关键字的集合，其关键字有 n! 种不同的排列，可构成的不同二叉查找树有
(棵 )
如何评价这些二叉查找树，可以用树的查找效率来衡量。
例如，已知关键字集合 { a1,a2,a3 } = { do,if,
to }，对应查找概率为 p1=0.5,p2=0.1,p3=0.05,
在各个查找不成功的间隔内查找概率又分别为
q0=0.15,q1=0.1,q2=0.05,q3=0.05。可能的二叉查找树如下所示。
C n nn 21 1?
(b)
(d)
(a)
(c)
(e)
在扩充二叉查找树中
○ 表示内部结点,包含了关键字集合中的某一个关键字；
□ 表示外部结点,代表造成查找失败的各关键字间隔中的不在关键字集合中的关键字 。
在每两个外部结点之间必然存在一个内部结点 。
设二叉树的内部结点有 n 个，外部结点有 n+1
个。如果定义每个结点的路径长度为该结点的层次，并用 I 表示所有 n 个内部结点的路径长度之和,用 E 表示 n+1 个外部结点的路径长度之和,
可以用归纳法证明,E = I+2n。
一棵扩充二叉查找树的 查找成功的平均查找长度 ASLsucc可以定义为 该树所有内部结点上的权值 p[i]与查找该结点时所需的 关键字比较次数 c[i]
(= l[i] + 1)乘积之和：
).][(*][ 1p
1
i liA S L
n
i
s u c c
扩充二叉查找树 查找不成功的平均查找长度
ASLunsucc为树中所有外部结点上权值 q[j]与到达外部结点所需关键字比较次数 c'[j](= l'[j])乘积之和：
n
j
u n su c c jljA S L
0
q ].[ *][
扩充二叉查找树总的平均查找长度为：
ASL = ASLsucc + ASLunsucc
所有内、外部结点上的权值关系为
n
i
n
j
ji
1 0
qp 1][][
(1) 相等查找概率的情形若设树中所有内,外部结点的查找概率都相等：
p[i] = q[j] = 1/7,1? i? 3,0? j? 3
图 (a),ASLsucc = 1/7*3+1/7*2+1/7*1 = 6/7,
ASLunsucc = 1/7*3*2+1/7*2+1/7*1 = 9/7。
总平均查找长度 ASL = 6/7 + 9/7 = 15/7。
图 (a),ASL = 15/7 图 (d),ASL = 15/7
图 (b),ASL = 13/7 图 (e),ASL = 15/7
图 (c),ASL = 15/7
图 (b)的情形所得的平均查找长度最小。一般把平均查找长度达到最小的扩充二叉查找树称作最优二叉查找树，
在 相等查找概率的情形 下，因为所有内部结点、
外部结点的查找概率都相等，把它们的权值都视为 1。同时，第 k 层有 2k 个结点,k = 0,1,?。则有 n 个内部结点的扩充二叉查找树的内部路径长度 I 至少等于序列
0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,…
的前 n项的和。
因此，最优二叉查找树的查找成功的平均查找长度和查找不成功的平均查找长度分别为,
.?
n
i
s u c c iA S L
1
2 1l o g
,?
1n
ni
u n s u c c iA SL
2
1
2l o g
(2) 不相等查找概率的情形
设树中所有内、外部结点的查找概率互不相等,p[1] =
0.5,p[2] = 0.1,p[3] = 0.05
q[0] = 0.15,q[1] = 0.1,q[2] = 0.05,q[3] = 0.05
图 (a),ASLsucc = 0.5*3 + 0.1*2 + 0.05*1 = 1.75，
ASLunsucc = 0.15*3 + 0.1*3 + 0.05*2 + 0.05*1= 0.9。 ASL
= ASLsucc + ASLunsucc = 2.65。
图 (a),ASL = 2.65 图 (d),ASL = 2.15
图 (b),ASL = 1.9 图 (e),ASL = 1.6
图 (c),ASL = 0.85
由此可知，图 (c)的情形下树的平均查找长度达到最小，
因此，图 (c)的情形是最优二叉查找树。
不相等查找概率情形下的最优二叉查找树可能不同于完全二叉树的形态。
考虑在不相等查找概率情形下如何构造最优二叉查找树。
假设关键字集合放在一个 有序的顺序表 中
{ key[1],key[2],key[3],… key[n] }
设最优二叉查找树为 T[0][n]，其平均查找长度为：
n
j
n
i
nCjljiliA S L
01
0q1p ]][[][ *][)][(*][
l [i]是 内部结点 a[i] 所在的层次号,l [j] 是 外部结点 j 所在的层次号。 C[0][n] 是树的代价。
为计算方便，将 p[i] 与 q[j] 化为整数。
构造最优二叉查找树
要构造最优二叉查找树，必须先构造它的左子树和右子树，它们也是最优二叉查找树。
对于任一棵子树 T[i][j]，它由
{ key[i+1],key[i+2],…,key[j] }
组成，其内部结点的权值为
{ p[i+1],p[i+2],…,p[ j] }
外部结点的权值为
{ q[i],q[i+1],q[i+2],…,q[ j] }
使用数组 W[i][j]来存放它的累计权值和：
W[i][j] = q[i] + p[i+1] + q[i+1] + p[i+2] +
+ q[i+2]+…+ p[ j] + q[j],0? i? j? n
计算 W[i][j]可以用递推公式,
W[i][i] = q[i]
//不是二叉树,只有一个外部结点
W[i][i+1] = q[i] + p[i+1] + q[i+1]
= W[i][i] + p[i+1] + q[i+1]
//有一个内部结点及两个外部结点的二叉树
W[i][i+2] = W[i][i+1] + p[i+2] + q[i+2]
//加一个内部结点和一个外部结点的二叉树一般地，
W[i][j] = W[i][j-1] + p[j] + q[j]
//再加一个内部结点和一个外部结点对于一棵包括关键字
{ key[i+1],…,key[k-1],key[k],key[k+1],…,key[j] }
的子树 T[i][j],若设它的 根结点为 k,i < k? j，
它的代价为：
C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j]
C[i][k-1]是其包含关键字 { key[i+1],key[i+2],…,
key[k-1] } 的左子树 T[i][k-1]的代价
C[i][k-1]+W[i][k-1]等于把左子树每个结点的路径长度加 1而计算出的代价
C[k][j]是包含关键字 { key[k+1],key[k+2],…,
key[j] } 的右子树 T[k][j]的代价
C[k][j] + W[k][j]是把右子树每个结点的路径长度加 1之后计算出的代价 。
因此，公式
C[i][j] = p[k]+C[i][k-1]+W[i][k-1]+C[k][j]+W[k][j]
表明：整个树的代价等于其左子树的代价加上其右子树的代价，再加上根的权值。
因为 W[i][j] = p[k] + W[i][k-1] + W[k][j]，
故有
C[i][j] = W[i][j] + C[i][k-1] + C[k][j]
可用 k = i+1,i+2,…,j 分别计算上式，选取使得
C[i][j]达到最小的 k。这样可将最优二叉查找树
T[i][j]构造出来。
构造最优二叉查找树的方法就是 自底向上逐步构造 的方法。
构造的步骤
第一步，构造 只有一个内部结点 的最优查找树：
T[0][1],T[1][2],…,T[n-1][n]。
在 T[i-1][i] (1? i? n) 中只包含关键字 key[i]。其代价分别是 C[i-1][i] = W[i-1][i]。另外设立一个数组 R[0..n][0..n] 存放各最优二叉查找树的根。
R[0][1] = 1,R[1][2] = 2,…,R[n-1][n] = n。
第二步,构造 有两个内部结点 的最优二叉查找树：
T[0][2],T[1][3],…,T[n-2][n]。在 T[i-2][i]中包含两个关键字 { key[i-1],key[i] }。其代价取分别以 key[i-1],key[i] 做根时计算出的 C[i-2][i] 中的小者。
第三步，第四步,…,构造有 3 个内部结点，
有 4 个内部结点,… 的最优二叉查找树。
最后构造出包含有 n 个内部结点的最优二叉查找树。对于这样的最优二叉查找树，若设 根为 k，
则 根 k 的值存于 R[0][n] 中，其 代价存于 C[0][n]
中,左子树的根存于 R[0][k-1]中,右子树的根存于 R[k][n] 中。
例：给出关键字集合和内、外部结点的权值序列第一步关键字集合 key1 key2 key3
实 例 do if to
对应 内部结点 p1=50 p2=10 p3=5
权值 外部结点 q0=15 q1=10 q2=5 q3=5
第二步
C 115 165 50 60
W 90 90 35 35
R 1 2 2 3
左子树 T[0,0] T[0,1] T[1,1] T[1,2]
右子树 T[1,2] T[2,2] T[2,3] T[3,3]
第三步
C 150 190 215
W 100 100 100
R 1 2 3
左子树 T[0,0] T[0,1] T[0,2]
右子树 T[1,3] T[2,3] T[3,3]
0 0 75 115 150
1 0 25 50
2 0 15
3 0
0 15 75 90 100
1 10 25 35
2 5 15
3 5
W[i][j] C[i][j]
R[i][j]
3个关键字 { do,if,to } 的最优二叉查找树
0 1 2 3 0 1 2 3
0 1 2 3
0 0 1 1 1
1 0 2 2
2 0 3
3 0
p1=50,p2=10,p3=5
q0=15,q1=10,q2= 5,q3= 5
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;
基本操作：
void R_Rotate(BSTree &p);
void L_Rotate(BSTree &p);
Status InsertAVL(BSTree &T,ElemType e,Boolean
&taller);
void LeftBalance(BSTree &T);
void RightBalance(BSTree &T);
平衡化旋转
如果在一棵平衡的二叉查找树中插入一个新结点，造成了不平衡。此时必须调整树的结构，
使之平衡化。
平衡化旋转有两类：
单旋转 (左旋和右旋 )
双旋转 (左平衡和右平衡 )
每插入一个新结点时,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){
//左单旋转的算法 (p236 算法 9.10)
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){
//右单旋转的算法（ p236 算法 9.9）
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
void LeftBalance(BSTree &T){//左平衡化的算法
BSTree lc,rd; lc=T->lchild;
switch(lc->bf){
case LH,T->bf = lc->bf = EH;
R_Rotate(T); break;
case RH,rd=lc->rchild;
switch(rd->bf){
case LH,T->bf=RH; lc->bf=EH; break;
case EH,T->bf=lc->bf=EH; break;
case RH,T->bf = EH; lc->bf=LH; break; }
rd->bf=EH;
L_Rotate(T->lchild);
R_Rotate(T);
}
}
先右后左双旋转 (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
从空树开始的建树过程
AVL树的删除
如果 被删结点 x最多只有一个子女,那么问题比较简单 。 如果 被删结点 x有两个子女,首先查找 x 在 中序次序下的直接前驱 y (同样可以找直接后继 )。 再把结点 y 的内容传送给 结点 x,现在问题转移到删除 结点 y。
把 结点 y当作 被删结点 x。
将 结点 x从树中删去 。 因为结点 x最多有一个子女,
我们可以简单地把 x的双亲结点中原来指向 x的指针改指到这个子女结点 ；如果结点 x没有子女,x双亲结点的相应指针臵为 NULL。 然后将原来以结点 x为根的子树的高度减 1，
必须沿 x 通向根的路径反向追踪高度的变化对路 径上各个结点的影响。
用一个布尔变量 shorter 来指明子树的高度是否被缩短。在每个结点上要做的操作取决于 shorter 的值和结点的 balance，有时还要依赖子女的 balance 。
布尔变量 shorter 的值初始化为 True。然后对于 从 x
的双亲到根的路径上的各个结点 p，在 shorter 保持为 True 时执行下面的操作。如果 shorter 变成 False，
算法终止。
case 1,当前结点 p 的 balance为 0。如果它的左子树或右子树被缩短，则它的 balance改为
1 或 -1，同时 shorter 臵为 False。
case 2,结点 p 的 balance不为 0，且较高的子树被缩短，则 p 的 balance改为 0，同时
shorter 臵为 True。
case 3,结点 p 的 balance不为 0，且较矮的子树又被缩短，则在结点 p 发生不平衡。需要进行平衡化旋转来恢复平衡。令 p 的较高的子树的根为 q (该子树未被缩短 ),根据 q 的 balance，
有如下 3 种平衡化操作。
case 3a,如果 q 的 balance为 0，执行一个单旋转来恢复结点 p 的平衡，臵 shorter为 False。
case 3b,如果 q 的 balance与 p 的 balance相同，
则执行一个单旋转来恢复平衡，结点 p 和 q 的
balance均改为 0，同时臵 shorter为 True。
case 3c,如果 p 与 q 的 balance相反，则执行一个双旋转来恢复平衡，先围绕 q 转再围绕 p 转。
新的根结点的 balance臵为 0，其它结点的
balance相应处理，同时臵 shorter为 True。
在 case 3a,3b和 3c的情形中，旋转的方向取决于是结点 p 的哪一棵子树被缩短。
AVL树的高度
设在新结点插入前 AVL树的高度为 h,结点个数为 n,则插入一个新结点的时间是 O(h)。 对于 AVL树来说,h多大？
设 Nh 是高度为 h 的 AVL树的最小结点数 。 根的一棵子树的高度为 h-1,另一棵子树的高度为 h-2,这两棵子树也是高度平衡的 。 因此有
N-1 = 0 (空树 )
N0 = 1 (仅有根结点 )
Nh = Nh-1 + Nh-2 +1,h > 0
可以证明,对于 h? 0,有 Nh = Fh+3 -1 成立 。
有 n 个结点的 AVL树的高度不超过
在 AVL树删除一个结点并做平衡化旋转所需时间为 O(log2n)。
二叉查找树适合于组织在内存中的较小的索引
(或目录 )。对于存放在外存中的较大的文件系统，用二叉查找树来组织索引不太合适。
在文件检索系统中大量使用的是用 B_树或 B+
树做文件索引。
)1(l o g23 2?n
掌握 简单的查找结构：
查找的概念
查找结构
查找的判定树
平均查找长度
静态查找
顺序查找算法、分析
折半查找算法、分析小结 需要复习的知识点
二叉查找树
定义
查找、平均查找长度
插入、删除、
AVL树
定义
插入、平衡化旋转
删除、平衡化旋转
高度
查找的概念
查找结构决定查找的效率
查找算法基于查找结构
查找效率用平均查找长度衡量
平均查找长度表明查找算法的整体性能，避开偶然因素
平均查找长度分查找成功与查找不成功两种情况
静态查找结构
顺序查找 — 顺序表、链表
折半查找 — 有序顺序表
动态查找结构
二叉排序树 — 无重复关键字
AVL树 — 平衡二叉排序树
有序顺序表的顺序查找
( 10,20,30,40,50,60 )
10
50
60
=
=
=
=
=
=
20
30
40
<
<
<
<
<
<
>
>
>
>
>
>
2
71
6
1 5
0
i
s u c c iA S L
7
27
61
7
1 5
0
i
u n s u c c
i
A S L
有序顺序表的折半查找
( 10,20,30,40,50,60 )
10 50
=
=
==
=
=
30
<
<
<
<
<
<
>
>
> >
> >
20 40 60
二叉查找树
二叉查找树的子树是二叉查找树
35
15 45
50402510
20 30
结点左子树上所有关键字小于结点关键字
右子树上所有关键字大于结点关键字
n 个结点的二叉查找树的数目
【例】 3 个结点的二叉查找树
5
1*2*3
4*5*6*
4
1C
13
1 3
3*2
1
2
2
1
3
3 1 3
2
1
2
3
1
2
3
{123} {132} {213} {231} {312} {321}
查找成功时检测指针停留在树中某个结点。
查找不成功时检测指针停留在某个外结点（失败结点）。
35
15 45
502510
20 30
查找 22
查找 45
A
B
C
E
A
B
C
D
ED
二叉查找树的高度越小，平均查找长度越小。
n 个结点的二叉查找树的高度最大为 n-1,最小为?log2n?.
AVL树
理解,AVL树的子树也是 AVL树
掌握：插入新结点后平衡化旋转的方法
掌握：删除结点后平衡化旋转的方法
掌握：结点高度 h 与结点数 n 的关系二叉排序树的删除
要求：删除一个结点后，仍然保持二叉排序树的有序性删除结点的算法：
（ 1）确定被删除结点：
A,有没有被删除的结点；
B,若有，则确定被删除的结点是根结点还是一般结点
（ 2）如果被删除结点是根结点，则调用删除根结点的算法；
（ 3）如果被删除结点是一般结点，则调用删除一般结点的算法。
删除二叉排序树的根结点的算法
（ 1） 根结点有左右子树的情况下，选择根结点的左子树中的最大结点为新的根结点；
最大结点 —— 中序遍历
（ 2）如果根结点没有左子树，则以右子树的根结点作为新的根结点；
（ 3）如果根结点没有右子树，则以左子树的根结点作为新的根结点删除二叉排序树的一般结点的算法
（ 1） 若被删除结点 P有左、右子树，则按照中序遍历找其左子树中的最大结点，以此最大结点的值代替 P结点的值，然后删除此最大结点（如同删除根结点）
（ 2）若被删除结点 P没有左子树，则把结点 P的右子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
（ 3）若被删除结点 P没有右子树，则把结点 P的左子树的全部挂接在 P的双亲上，且位置是 P在其双亲中原来的位置
