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))-2251B-树定义查找过程插入操作删除操作查找性能的分析B-树定义B-树是一种平衡的多路查找树:root50157184382026435662788996B-树定义一棵m阶的B-树,或为空树,或为满足下列特性的m叉树1、树中每个结点最多有m棵子树2、若根结点不是叶子结点,则至少有两棵子树3、除根之外的所有非终端(叶子)结点至少有棵子树2/mB-树定义4、所有非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)5、所有叶子结点都在同一层,不带信息a.n为关键字的个数,多个关键字自小至大有序排列,即:K1
keynum;i=Search(p,K);//在p->key[1..keynum]中查找i,//使得p->key[i]<=Kkey[i+1],//没找到则i=-1if(i>0&&p->key[i]==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