数据结构讲义九：二叉排序树资料课件

动态查找二叉排序树平衡二叉树B-树（B+树）键树二叉排序树二叉排序树：或是一棵空二叉树，或是一棵具有下列性质的二叉树：若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；并且其左、右子树均是二叉排序树。类型定义为：typedef

struct

BSTNode{intkey;∥关键字域

…∥其它数据域

struct

BSTNode*lchild,*rchild;∥左、右孩子指针

}BSTNode,*BSTree;

二叉排序树示例30125332394187189查找71、5

二叉排序树的查找算法假定二叉排序树的根结点指针为root，给定的关键字值为K，则查找算法可描述为：

①置初值：q＝root；

②如果K＝q－＞key，则查找成功，算法结束；

③否则，如果K＜q－＞key，而且q的左子树非空，则将q的左子树根送q，转步骤②；否则，查找失败，结束算法；

④否则，如果K＞q－＞key，而且q的右子树非空，则将q的右子树根送q，转步骤②；否则，查找失败，算法结束。

int

Bstree::Search(KeyTypeK)

{

intflag=0;

BstNode*q=root;

while((q!=NULL)&&(flag==0))

{

if(q->key==K)

{

cout<<"查找成功，找到："<<q->key<<endl;

flag=1;

}

elseif(K<q->key)q=q-lch;

elseq=q->rch;

}

if(flag==0)cout<<"查找失败，无此结点!\n";

returnflag;

}

函数Search中，参数root为根结点指针，K为欲查找的关键字值，这里假定它是整数。函数执行完后，如果查找成功，输出所找到结点的关键字值，并且指针q指向所找到的结点，p指向它的父结点；如果查找失败，q＝NULL，p为q的父结点指针。

二叉排序树查找递归算法二叉排序树查找非递归算法BSTreeSearchBST2(BSTreet,intk){//二叉排序树t中非递归查找某关键字等于k的数据元素，//若查找成功，则返回指向该数据元素结点的指针，//否则返回空指针

p=t;while(p!=NULL&&p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;

}returnp;}//SearchBST2

二叉排序树上结点的插入步骤：（1）若二叉排序树是空树，则k成为二叉排序树的根；（2）若二叉排序树非空，则将k与二叉排序树的根进行比较，如果k的值等于根结点的值，则停止插入；如果k的值小于根结点的值，则将k插入左子树；如果k的值大于根结点的值，则将k插入右子树。

插入算法voidInsertBST(BSTree

t,intk){//若二叉排序树t中没有关键字k，则插入，否则直接返回

p=t;//p的初值指向根结点

while(p)//查找插入位置

{if(p->key==k)return;//已有k，无需插入

f=p;//f保存当前查找的结点

p=(k<p->key)?p->lchild:p->rchild;

//若k<p->key，在左子树上查找，否则在右子树上查找

}

p=(BSTree)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;

if(t==NULL)t=p;elseif(k<f->key)f->lchild=p;elsef->rchild=p;}//InsertBST

123532264520(g)二叉排序树的生成

(b)32(c)3226

(d)322645(a)ø32264535

(e)3226451235

(f)设序列为(32,26,45,35,12,20)记录的关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下：φ636390706390557063906755706390426755706390984267557063908398426755706390二叉排序树上结点的删除假设要删除的结点为*p，结点*p的双亲结点为*f，并假设结点*p是结点*f的左孩子(右孩子的情况类似)。下面分三种情况讨论：①若*p为叶子结点，则可直接将其删除：f->1child＝NULL;free(p)；②若*p结点只有左子树，或只有右子树，则可将*p的左子树或右子树直接改为其双亲结点*f的左子树，即：f->1child=p->1child(或f->1child=p->rchild);free(p)；FP*f*pP1FP1*fFP*f*pPrFPr*f③若*p既有左子树，又有右子树。则：令*p结点的直接前驱（或直接后继）代替*p，然后再从二叉排序树中删除它的直接前驱（或直接后继）。当以直接前驱*s代替*p时，由于*s只有左子树SL，则在删去*s之后，只要令SL为*s的双亲*r的右子树即可RQqFSFRPRpQLrRLSLSRQqFPFRPRpQLrsRLSL二叉排序树上删除10或40或45或555845439832405570639010voidDelete(BSTree

bst,keytypeX)//在二叉排序树bst上，删除其关键字为X的结点。

{BSTree

f,p=bst;while(p&&p->key!=X)//查找值为X的结点

if(p->key>X){f=p;p=p->lchild;}else{f=p;p=p->rchild;}if(p==null){printf(“无关键字为X的结点\n”);exit(0);}

if{p->lchild==null}//被删结点无左子树

if(f->lchild==p)f->lchild=p->rchild;//将被删结点的右子树接到其双亲上

elsef->rchild=p->rchild;

else//被删结点有左子树

{q=p;s=p->lchild;//s指向被删结点左子树的根

while(s->rchild!=null)//查左子树中最右下的结点（中序最后结点）

{q=s;s=s->rchild;}p->key=s->key;//结点值用其左子树最右下的结点的值代替

if(q==p)p->lchild=s->lchild;//被删结点左子树的根结点无右子女

elseq->rchild=s->lchild;//s是被删结点左子树中序最后一个结点

free(s);}}//算法结束

最佳二叉排序树定义：平均查找长度最小的二叉排序树。

举例：形如满二叉树或完全二叉树的二叉排序树。非常难于构造。折中：平衡二叉树。平衡二叉树定义：它或者是一棵空二叉树，或者是二叉树中任一结点的左、右子树高度之差的绝对值不大于1，则称这棵二叉树为平衡二叉树

平衡因子(bf)：结点的左、右子树高度差为该结点的平衡因子

平衡的二叉树示例01-1001-110100不平衡的二叉树示例210-1001-201000平衡二叉树的类型定义typedef

struct

AVLNode{intkey;

intbf;//结点的平衡因子

struct

AVLNode*lchild,*rchild;

//左、右孩子指针

}AVLNode,*AVLTree;

构造平衡二叉树方法：每当插入一个结点时，首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二叉排序树的平衡，则找出其中最小不平衡子树。所谓最小不平衡子树是指离插入结点最近，且平衡因子的绝对值大于1的结点，因为此结点失去平衡，使得该结点的祖先结点也可能随之失去平衡。所以，失衡后应该调整以该结点为根的子树。失去平衡的四种情况321223131132LL型RR型失去平衡的四种情况312233121132LR型RL型二叉平衡树插入结点(结点旁的数字为其平衡因子)

示例15152127152121271521154327关键字的插入顺序为(15，21，27，43，36，8，11)

RR示例关键字的插入顺序为(15，21，27，43，36，8，11)

2127154336212715368432127154336示例关键字的插入顺序为(15，21，27，43，36，8，11)

15211136827431521364327118(i)(j)LL型调整操作示意图BABRBLAR0BAARBLSBR21

(b)调整后恢复平衡(a)插入结点S后失去平衡LL型调整的两个例子01613125031251251631002(a)

BL、BR、AR

都是空树(b)BL、BR、AR

都是非空树9281631254728925163147281631254701010000010000210RR型调整操作示意图BBRAALBL

(a)插入结点*s后失去平衡(b)调整后恢复平衡AAL-2BBRBL-1SRR型调整的两个例子(a)AL、BL、BR

都是空树69-1314703147-1473169000-20025470-1-2-100473169254700-100000-1031766940402576316940(b)AL、BL、BR

都是非空树LR型调整操作示意图(b)调整后恢复平衡

CACRAR0BBLCL00BAARCLCR2-1BLCS

(a)插入结点*s后失去平衡LR型调整的三个例子281312503125-128253100020261628253147312547-10226281610031254700128160000000-10

(b)LR(L)型调整(a)LR(0)型调整LR型调整的三个例子312547-102302816-1003125470012816000301628253147001000(c)LR(R)型调整RL型调整操作示意图

(b)调整后恢复平衡CBCRBRAALCLBAALBRCLSCCR

(a)插入结点*s后失去平衡RL型调整的三个例子(a)RL(0)型调整40-13147031471403147000-20(b)

RL(L)型调整31254701-236406910031254700-169400003625403147690000-10RL型调整的三个例子

(c)RL(R)型调整31254701-24369400-1031254700-16940000432540314769001000AVL树上结点的插入

结点插入后，若平衡二叉树失去了平衡，则要找到最小不平衡子树当插入树中后，修改有关结点的平衡因子如何判断根的子树是否失去平衡，若失去平衡则要作相应的处理AVL树查找分析

深度为h的平衡二叉树所具有的最少结点数。设以Nh表示深度为h的平衡二叉树中含有的最少结点数。N0＝0，N1=1，N2=2，并且Nh＝Nh-1+Nh-2+1。利用归纳法可证明：当h≥0时，Nh=Fh+2-1。含有n个结点的平衡二叉树的最大深度，即在AVL上进行查找的时间复杂度为O(logn)。B-树1970年Bayer提出B-树多路平衡外查找树。前面讨论的查找方法适用于组织规模较小、内存中能容纳的数据，是内查找方法

B-树是一种平衡、有序、多路、动态的查找树，它是磁盘文件系统中索引技术常用的一种数据结构形式，如磁盘管理系统中的目录管理以及数据文件中的索引机构大多采用B-树B-树B-树的定义一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：(1)树中每个结点至多有m棵子树；(2)若根结点不是叶子结点，则至少有两棵子树；(3)除根结点之外的所有非终端结点至少有棵子树；(4)所有的非终端结点中包含下列信息数据（n,P0,K1,P1,K2,P2,…,Kn,Pn），其中：Ki(i=1,…,n)为关键字，且Ki<Ki+1(i=1,…,n-1)，Pi(i=0,…,n)为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki(i=1,…,n)，Pn所指子树中所有结点的关键字均大于Kn，n（m/2-1≤n≤m-1）为关键字的个数。(5)所有叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。B-树示例256154071502386345301058024016121109223177162294281273336320317375363487456419890782613568abcdefghijk一棵5阶B-树B-树的查找查找过程包括两种基本操作

(1)顺指针查找结点；(2)在结点中顺序查找关键字；

查找算法TreeSearchBTree(BTree

t,int

k,int*pos){//在B-树查找关键字k，成功时返回结点的地址及k在其中的位置*pos，失败返回NULLt->key[0]=k;//设置哨兵，下面用顺序查找key[1..keynum]

for(i=t->keynum;k<t->key[i];i--);

//从后向前找第1个小于等于k的关键字

if(i>0&&t->key[i]==k)//查找成功，返回t及i{*pos=i;returnt;}//结点内查找失败，但t->key[i]<k<t->key[i+1]下一个查找结点应为son[i]

if(!t->son[i])//*t为叶子，在叶子中仍未找到k，则查找过程失败

returnNULL;

DiskRead[t->son[i]];//从磁盘上读入下一个查找的树结点到内存中

returnSearchBTree(t->son[i],k,pos);//递归的继续查找子树t->son[i]}//

SearchBTree

B-树查找分析在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过

若N=1,999,999,m=199，则查找次数至多为4。B-树查找长度分析第一层至少有1个结点；第二层至少有2个结点；第三层至少有2*m/2个结点，…，依次类推;第L+1层至少有2*(m/2)L-1个结点；而L+1层的结点为叶子结点,数量为N+1;N+1>=2*(m/2)L-1;即L<=logm/2((N+1)/2)+1

。附：S=N+1的推导设B-树某结点的子树数为Ci，则该结点的关键字数Ni=Ci-1。对于有k个结点的B-树，有∑Ni=∑(Ci-1)=∑Ci-k（1≤i≤k）

（1）因为B树上的关键字数，即∑Ni=N（1≤i≤k）（2）而B-树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为S；则∑Ci=(k-1)+S（1≤i≤k）（3）综合（1）（2）（3）式，有s=n+1。证毕。B-树的插入插入操作先要通过查找确定插入的位置，然后可按以下三种情形分别进行处理：情形2：插入关键字的结点在插入后，关键字的个数超过m-1，则进行分裂处理。假设当前处理的结点由q指向，以为界，将结点*q分裂成两个结点，前面-1个关键字组成一部分仍由q指向，其余后面的一部分由q1指向，而中间的一个关键字带着指针ql被“上挤”到双亲结点中。

情形3：在执行情形2的“上挤”处理后，双亲结点中的关键字个数也超过了m-1个，则必须以该双亲结点为当前结点，进行相同的处理，也就是说要继续“上挤”直至根结点。一旦根结点中的关键字个数超过了m-1个，对根结点进行分裂处理后，整个B-树的层数即增加一层

情形1：插入关键字的结点在插入后，关键字的个数不超过m-1，则将给定的关键字插入到该结点的相应位置，插入过程即完成。插入结点后的分裂插入后：m,P0,(K1,P1,),…,(Km,Pm);

Ki<Ki+1(1<=i<m)

分成*p’和*q’两个结点:p’:m/2-1,P0,(K1,P1),…,(Km/2-1,Pm/2-1)q’:m-m/2,Pm/2,(Km/2+1,Pm/2+1),…,(Km,Pm)Km/2和p’一起插入到P结点中。B-树上插入结点3阶B-树上插入结点561824q2031q1(c)561881(e)18

5681bt(d)5618202431q(b)24

315618(a)插入结点示例56183572(a)5618357283(b)567283182135(c)215618728335(d)插入结点示例21561835697283(e)

56217218356983(g)(f)

21567218356983B-树的删除

在B-树上删除一个关键字，则首先要找到该关键字所在的结点，并从中删除之。若该结点为最下层的非终端结点，且其中的关键字个数不少于