数据结构-B树和B键树

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为关键字的个数，多个关键字自小至大有序排列，即：K1K2…Kn;b.且Ai-1所指子树上所有关键字均小于Ki;c.Ai所指子树上所有关键字均大于Ki;d.关键字的个数比子树的个数小1;B-树的查找过程从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。B-树的查找过程typedefstruct{BTNode*pt;//指向找到的结点的指针inti;//1..m，在结点中的关键字序号inttag;//标志查找成功(=1)或失败(=0)}Result;//在B树的查找结果类型假设返回的是如下所述结构的记录:B-树的查找算法ResultSearchBTree(BTreeT,KeyTypeK){//在m阶的B-树T中查找关键字K,//返回查找结果(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]=Kp-key[i+1],//没找到则i=-1if(i0&&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）插入后，该结点的关键字个数nm，不需要修改指针;如插入关键字60502040806080B-树插入结点2）插入后，该结点的关键字个数n=m，则需进行“结点分裂”：令s=m/2a.在原结点中保留（A0，K1，。。。，Ks-1，As-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）若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。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abcdefgh70619053B-树删除结点3.被删除关键字所在结点和其相邻的右兄弟结点（或左兄弟）结点中关键字的个数均等于m/2-1，9061902410033745abcdefgh7053删除关键字53617090B-树删除结点2410033745abcdegh练习：从上面的B树中删除关键字376170^^24^3^3^2490B-树删除结点1003745abcdegh练习：从上面的B树中删除关键字37617037没有右兄弟且其左兄弟也只有一个关键字，把37双亲结点中小于37的关键字24与左兄弟中的3合并成一个结点。此时，发现左右子树高度不同，必须调整成B-树。4590100ech3246170g4590B-树删除结点100ech练习：从上面的B树中删除关键字37^3^24^6170g调整后的B-树，如下所示B-树查找性能分析在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。问：1）含N个关键字的m阶B-树可能达到的最大深度H为多少？B-树查找性能分析2）深度为H的B-树中，至少含有多少个结点？第2层2个先推导每一层所含最少结点数：第1层1个第H+1层2(m/2)H-1个第4层2(m/2)2个第3层2m/2个……B-树查找性能分析假设m阶B-树的深度为H+1，由于第H+1层为叶子结点，而当前树中含有N个关键字，则叶子结点必为N+1个，N+1≥2(m/2)H-1H-1≤logm/2((N+1)/2)H≤logm/2((N+1)/2)+1由此可推得下列结果：B-树查找性能分析在含n个关键字的B-树上进行一次查找，需访问的结点个数不超过logm/2((n+1)/2)+1结论：B+树特点是B-树的一种变型。1）有n棵子树的结点中含有n个关键字2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；3）每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值；5096155062789671788489965662202643503815sqrootB+树特点B+树查找过程1）在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找；2）在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；3）若在结点内查找时，给定值≤Ki，则应继续在Ai所指子树中进行查找；B+树插入和删除操作类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。键树键树的结构特点双链树Trie树键树的结构特点HAD$S$VE$E$R$E$IGH$S$表示关键字集合{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS}键树定义键树又称为数字查找树，它是一棵度=2的树，其中的每个结点中不是包含一个或者几个关键字，而是只包含组成关键字的符号。键树的结构特点1）关键字中的各个符号分布在从根结点到叶结点的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关;2）键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。双链树—以二叉链表作存储结构实现的键树结点结构:firstsymbolnext分支结点infoptrsymbolnext叶子结点指向孩子结点的指针指向兄弟结点的指针指向记录的指针typedefenum{LEAF,BRANCH}NodeKind;//两种结点：{叶子和分支}HAD$HADE$R$$ES$GH$IHEHERHEREHIGHHIS…T叶子结点分支结点含关键字的记录双链树typedefstructDLTNode{charsymbol;structDLTNode*next;//指向兄弟结点的指针NodeKindkind;union{Record*infoptr;//叶子结点内的记录指针structDLTNode*first;//分支结点内的孩子链指针}}DLTNode,*DLTree;//双链树的类型双链树#defineMAXKEYLEN16//关键字的最大长度typedefstruct{charch[MAXKEYLEN];//关键字intnum;//关键字长度}KeysType;//关键字类型双链树查找过程假设:T为指向双链树根结点的指针，K.ch[0..K.num-1]为待查关键字(给定值)。则查找过程中的基本操作为进行下列比较:K.ch[i]=?p-symbol其中:0≤i≤K.num-1，p指向双链树中某个结点双链树查找过程1.初始状态:p=T-first;i=0;2.若(p&&p-symbol==K.ch[i]&&iK.num-1)则继续和给定值的下一位进行比较p=p-first;i++;3.若(p&&p-symbol!=K.ch[i])则继续在键树的同一层上进行查找p=p-next;双链树查找过程若(p&&p-symbol==K.ch[i]&&i==K.num-1)则查找成功，返回指向相应记录的指针p-infoptr4.若(p==NULL)则表明查找不成功，返回“空指针”;Trie树—以多重链表作存储结构实现的键树结点结构:分支结点叶子结点指向记录的指针012345……242526关键字指向下层结点的指针每个域对应一个“字母”01(A)345(E)9(I)……268(H)4(D)19(S)22(V)018(R)7(G)1905(E)THADHASHAVHEHERHEREHIGHIS叶子结点分支结点指向记录的指针typedefstructTrieNode{NodeKindkind;//结点类型union{struct{KeyTypeK;Record*infoptr}lf;//叶子结点(关键字和指向记录的指针)struct{TrieNode*ptr[27];intnum}bh;//分支结点(27个指向下一层结点的指针)}}TrieNode,*TrieTree;//键树类型结点结构的C语言描述:Trie树Trie树查找过程在Trie树中查找记录的过程:假设:T为指向Trie树根结点的指针，K.num是字符的个数，K.ch[0..K.num-1]为待查关键字(给定值)。则查找过程中的基本操作为：搜索和对应字母相应的指针:若p不空，且p所指为分支结点，则p=p-bh.Ptr[ord(K.ch[i])];//ord将字母影射成在字母表中的位置(其中:0≤i≤K.num-1)Trie树查找过程初始状态:p=T;i=0;若(p&&p-kind==BRANCH&&iK.num)则继续搜索下一层的结点p=p-bh.ptr[ord(K.ch[i])];i++;若(p&&p-kind==LEAF&&p-lf.K==K)则查找成功，返回指向相应记录的指针p-lf.infoptr反之，即(!p||p-kind==LEAF&&p-l