数据结构-B树和B键树.ppt

B-树，B+树和键树,B-树,B+树,键树,小结和作业,复习,复习,复习,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) - 2,B-树,定义,查找过程,删除操作,查找性能的分析,B-树定义,B-树是一种平衡的多路查找树：,B-树定义,一棵m阶的B-树，或为空树，或为满足下列特性的m叉树,1、树中每个结点最多有m棵子树,2、若根结点不是叶子结点，则至少有两棵子树,3、除根之外的所有非终端（叶子）结点至少有 棵子树,B-树定义,4、所有非终端结点中包含下列信息数据,(n, A0, K1, A1, K2, A2, , Kn, An),5、所有叶子结点都在同一层，不带信息,a. n为关键字的个数，多个关键字自小至大有序排列，即：K1 K2 Kn; b.且 Ai-1 所指子树上所有关键字均小于Ki; c.Ai 所指子树上所有关键字均大于Ki; d.关键字的个数比子树的个数小1;,B-树的查找过程,从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。,若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；,若查找不成功，则返回插入位置。,B-树的查找过程,typedef struct BTNode *pt; / 指向找到的结点的指针 int i; / 1m，在结点中的关键字序号 int tag; / 标志查找成功(=1)或失败(=0) Result; / 在B树的查找结果类型,假设返回的是如下所述结构的记录:,B-树的查找算法,Result SearchBTree(BTree T, KeyType K) / 在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 / 查找不成功,B-树插入结点,在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的叶子结点，有下列几种情况：,1）插入后，该结点的关键字个数nm，不需要修改指针; 如插入关键字60,50, 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 ,50 80,80,30,B-树插入结点,3）若双亲为空，则建新的根结点。, 20 40 , 60 , 90 ,50 80,再插入关键字30, 20 30 40 , 20 , 40 ,30 50 80,50,B-树删除结点,删除操作和插入结点的考虑相反 1）首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1 2）否则，要从其左(或右)兄弟结点“借调”关键字 3）若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。,B-树删除结点,1.被删除结点上关键字个数不少于m/2 -1，那么只需从该结点上删除该关键字Ki和相应的指针Ai。 例如下图3-阶B树中删除关键字12时，直接将12 删除即可。,53 90,24, 50 , 100 , 3 12 , 37 ,45, 61 70 , 3 ,a,b,c,d,e,f,g,h,B-树删除结点,2.如果被删除结点上关键字个数等于m/2 -1，而与其相邻的右兄弟结点（或左兄弟）结点中关键字的个数大于m/2 -1,上图为删除50前、后的3阶B-树。,53 90,24, 50 , 100 , 3 , 37 ,45, 61 70 ,a,b,c,d,e,f,g,h,70 ,61 90, 53 ,B-树删除结点,3.被删除关键字所在结点和其相邻的右兄弟结点（或左兄弟）结点中关键字的个数均等于m/2 -1，,90,61 90,24, 100 , 3 , 37 ,45,a,b,c,d,e,f,g,h,70 , 53 ,删除关键字53,61 70 ,90,B-树删除结点,24, 100 , 3 , 37 ,45,a,b,c,d,e,g,h,练习：从上面的B树中删除关键字37,61 70 ,24, 3 ,3 24,90,B-树删除结点, 100 , 37 ,45,a,b,c,d,e,g,h,练习：从上面的B树中删除关键字37,61 70 ,37没有右兄弟且其左兄弟也只有一个关键字， 把37 双亲结点中小于37 的关键字24 与左兄弟中的3合并成一个结点。 此时，发现左右子树高度不同，必须调整成B-树。,45 90, 100 ,e,c,h,3 24,61 70 ,g,45 90,B-树删除结点, 100 ,e,c,h,练习：从上面的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 层 2m/2 个, ,B-树查找性能分析,假设 m 阶 B-树的深度为 H+1，由于第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个，,N+12(m/2)H-1 H-1logm/2(N+1)/2) Hlogm/2(N+1)/2)+1,由此可推得下列结果：,B-树查找性能分析,在含 n 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 logm/2(n+1)/2)+1,结论：,B+树特点,是B-树的一种变型。 1）有n棵子树的结点中含有n个关键字,2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；,3）每个非叶结点中的关键字Ki 即为其相应指针Ai 所指子树中关键字的最大值；,50 96,15 50,62 78 96,71 78,84 89 96,56 62,20 26 43 50,3 8 15,sq,root,B+树特点,B+树查找过程,1）在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；,2）在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；,3）若在结点内查找时，给定值Ki，则应继续在 Ai 所指子树中进行查找；,B+树插入和删除操作,类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。,键树,键树的结构特点,双链树,Trie树,键树的结构特点,表示关键字集合 HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS ,键树定义,键树又称为数字查找树，它是一棵度=2的树，其中的每个结点中不是包含一个或者几个关键字，而是只包含组成关键字的符号。,键树的结构特点,1）关键字中的各个符号分布在从根结点到叶结点的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关;,2）键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符$小于任何其它符号。,双链树, 以二叉链表作存储结构实现的键树,结点结构:,first symbol next,分支结点,infoptr symbol next,叶子结点,指向孩子结点 的指针,指向兄弟结点 的指针,指向记录 的指针,typedef enum LEAF, BRANCH NodeKind; / 两种结点：叶子 和 分支,H,A,D,$,HAD,E,$,R,$,$,E,S,$,G,H,$,I,HE,HER,HERE,HIGH,HIS,T,叶子结点,分支结点,含关键字 的记录,双链树,typedef struct DLTNode char symbol; struct DLTNode *next; / 指向兄弟结点的指针 NodeKind kind; union Record *infoptr; / 叶子结点内的记录指针 struct DLTNode *first; / 分支结点内的孩子链指针 DLTNode, *DLTree; / 双链树的类型,双链树,#define MAXKEYLEN 16 /关键字的最大长度,typedef struct char chMAXKEYLEN; / 关键字 int num; / 关键字长度 KeysType; / 关键字类型,双链树查找过程,假设: T 为指向双链树根结点的指针， K.ch0K.num-1 为待查关键字(给定值)。,则查找过程中的基本操作为进行下列比较: K.chi =? p-symbol 其中:0 i K.num-1， p 指向双链树中某个结点,双链树查找过程,1.初始状态: p=T-first; i = 0;,2.若 ( p ,3.若 ( p ,双链树查找过程,若 ( p & p-symbol=K.chi & i=K.num-1) 则 查找成功，返回指向相应记录的指针 p-infoptr,4.若 ( p = NULL) 则表明查找不成功，返回“空指针”;,Trie树, 以多重链表作存储结构实现的键树,结点结构:,分支结点,叶子结点,指向记录 的指针,指向下层结点的指针 每个域对应一个“字母”,0 1(A) 3 4 5(E) 9(I) 26,8(H),4(D) 19(S) 22(V) 0 18(R) 7(G) 19,0 5(E),T,HAD,HAS,HAV,HE,HER,HERE,HIG,HIS,叶子结点,分支结点,指向记录 的指针,typedef struct TrieNode NodeKind kind; / 结点类型 union struct KeyType K; Record *infoptr lf; / 叶子结点(关键字和指向记录的指针) struct TrieNode *ptr27; int num bh; / 分支结点(27个指向下一层结点的指针) TrieNode, *TrieTree; / 键树类型,结点结构的 C 语言描述:,Trie树,Trie树查找过程,在 Trie 树中查找记录的过程:,假设: T 为指向 Trie 树根结点的指针， K.num是字符的个数， K.ch0K.num-1 为待查关键字(给定值)。,则查找过程中的基本操作为： 搜索和对应字母相应的指针: 若 p 不空，且 p 所指为分支结点， 则 p = p-bh.