数据结构-b树和b键树

数据结构-b树和b键树

ID:26241984

大小:507.37 KB

页数:48页

时间:2018-11-25

数据结构-b树和b键树_第1页
数据结构-b树和b键树_第2页
数据结构-b树和b键树_第3页
数据结构-b树和b键树_第4页
数据结构-b树和b键树_第5页
资源描述:

《数据结构-b树和b键树》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、B-树,B+树和键树B-树B+树键树小结和作业复习复习ABCX2LLABCX2LRABCX-2RRABCX-2RL复习2、已知长度为11的表{xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon},按表中元素顺序依次插入一棵初始为空的平衡二叉排序树,画出插入完成后的平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。1、按次序输入关键字:7,6,5,4,3,2,1,试画出AVL树的构造和调整过程。复习含有n个结点的二叉平衡树能达到的最大深度:hn=log(5(n+1))-2B-树定义查找过程插入操作删除操作查找性能的

2、分析B-树定义B-树是一种平衡的多路查找树:B-树定义一棵m阶的B-树,或为空树,或为满足下列特性的m叉树1、树中每个结点最多有m棵子树2、若根结点不是叶子结点,则至少有两棵子树3、除根之外的所有非终端(叶子)结点至少有棵子树B-树定义4、所有非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)5、所有叶子结点都在同一层,不带信息a.n为关键字的个数,多个关键字自小至大有序排列,即:K1

3、找过程从根结点出发,沿指针搜索结点和在结点内进行顺序(或折半)查找两个过程交叉进行。若查找成功,则返回指向被查关键字所在结点的指针和关键字在结点中的位置;若查找不成功,则返回插入位置。B-树的查找过程typedefstruct{BTNode*pt;//指向找到的结点的指针inti;//1..m,在结点中的关键字序号inttag;//标志查找成功(=1)或失败(=0)}Result;//在B树的查找结果类型假设返回的是如下所述结构的记录:B-树的查找算法ResultSearchBTree(BTreeT,KeyTypeK){//在m阶的B-树T中查找关键字K,//

4、返回查找结果(pt,i,tag)。//若查找成功,则特征值tag=1,//指针pt所指结点中第i个关键字等于K;//否则特征值tag=0,等于K的关键字应插入在//指针pt所指结点中第i个关键字//和第i+1个关键字之间}//SearchBTree……B-树查找算法p=T;q=NULL;found=FALSE;i=0;while(p&&!found){n=p->keynum;i=Search(p,K);//在p->key[1..keynum]中查找i,//使得p->key[i]<=Kkey[i+1],//没找到则i=-1if(i>0&&p->key[i

5、]==K)found=TRUE;else{q=p;p=p->ptr[i];}//q指示p的双亲}if(found)return(p,i,1);//查找成功elsereturn(q,i,0);//查找不成功B-树插入结点在查找不成功之后,需进行插入。显然,关键字插入的位置必定在最下层的叶子结点,有下列几种情况:1)插入后,该结点的关键字个数n

6、1);b.建新结点(As,Ks+1,。。。,Kn,An);c.将(Ks,p)插入双亲结点B-树插入结点5020406080再插入关键字90608090609050808030B-树插入结点3)若双亲为空,则建新的根结点。204060905080再插入关键字30203040204030508050B-树删除结点删除操作和插入结点的考虑相反1)首先必须找到待删关键字所在结点,并且要求删除之后,结点中关键字的个数不能小于m/2-12)否则,要从其左(或右)兄弟结点“借调”关键字3)若其左和右兄弟结点均无关

7、键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。B-树删除结点1.被删除结点上关键字个数不少于m/2-1,那么只需从该结点上删除该关键字Ki和相应的指针Ai。例如下图3-阶B树中删除关键字12时,直接将12删除即可。53902450100312374561703abcdefghB-树删除结点2.如果被删除结点上关键字个数等于m/2-1,而与其相邻的右兄弟结点(或左兄弟)结点中关键字的个数大于m/2-1上图为删除50前、后的3阶B-树。53902450100337456170abcde

8、fgh70619053B-树删

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。