数据结构-b树和b键树

《数据结构-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-树删