数据结构-B树和B键树VIP免费

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))-2251B-树定义查找过程插入操作删除操作查找性能的分析B-树定义B-树是一种平衡的多路查找树：root50157184382026435662788996B-树定义一棵m阶的B-树，或为空树，或为满足下列特性的m叉树1、树中每个结点最多有m棵子树2、若根结点不是叶子结点，则至少有两棵子树3、除根之外的所有非终端（叶子）结点至少有棵子树2/mB-树定义4、所有非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,…,Kn,An)5、所有叶子结点都在同一层，不带信息a.n为关键字的个数，多个关键字自小至大有序排列，即：K1keynum;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