数据结构树和键树

数据结构树和键树第一页，共四十七页，2022年，8月28日复习ABCX2LLABCX2LRABCX-2RRABCX-2RL第二页，共四十七页，2022年，8月28日复习2、已知长度为11的表{xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon}，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。1、按次序输入关键字：7,6,5,4,3,2,1，试画出AVL树的构造和调整过程。第三页，共四十七页，2022年，8月28日复习含有n个结点的二叉平衡树能达到的最大深度：

hn=log(5(n+1))-2第四页，共四十七页，2022年，8月28日B-树定义查找过程插入操作删除操作查找性能的分析第五页，共四十七页，2022年，8月28日B-树定义B-树是一种平衡的多路查找树：第六页，共四十七页，2022年，8月28日B-树定义一棵m阶的B-树，或为空树，或为满足下列特性的m叉树1、树中每个结点最多有m棵子树2、若根结点不是叶子结点，则至少有两棵子树3、除根之外的所有非终端（叶子）结点至少有棵子树第七页，共四十七页，2022年，8月28日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;第八页，共四十七页，2022年，8月28日B-树的查找过程从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。第九页，共四十七页，2022年，8月28日B-树的查找过程typedefstruct{BTNode*pt;//指向找到的结点的指针inti;//1..m，在结点中的关键字序号inttag;//标志查找成功(=1)或失败(=0)}Result;//在B树的查找结果类型假设返回的是如下所述结构的记录:第十页，共四十七页，2022年，8月28日B-树的查找算法ResultSearchBTree(BTreeT,KeyTypeK){

//在m阶的B-树T中查找关键字K,

//返回查找结果(pt,i,tag)。

//若查找成功，则特征值tag=1,

//指针pt所指结点中第i个关键字等于K;

//否则特征值tag=0,等于K的关键字应插入在

//指针pt所指结点中第i个关键字

//和第i+1个关键字之间}//SearchBTree……第十一页，共四十七页，2022年，8月28日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]<=K<p->key[i+1],//没找到则i=-1

if(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);//查找不成功第十二页，共四十七页，2022年，8月28日B-树插入结点在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的叶子结点，有下列几种情况：1）插入后，该结点的关键字个数n<m，不需要修改指针;如插入关键字6050204080

6080第十三页，共四十七页，2022年，8月28日B-树插入结点2）插入后，该结点的关键字个数n=m，则需进行“结点分裂”：

令s=m/2a.在原结点中保留

（A0，K1，。。。，Ks-1，As-1）；b.建新结点

（As，Ks+1，。。。，Kn，An）；c.将（Ks，p）插入双亲结点第十四页，共四十七页，2022年，8月28日B-树插入结点502040

6080再插入关键字90

60809060905080第十五页，共四十七页，2022年，8月28日8030B-树插入结点3）若双亲为空，则建新的根结点。204060905080再插入关键字302030

402040

30508050第十六页，共四十七页，2022年，8月28日B-树删除结点删除操作和插入结点的考虑相反1）首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-12）否则，要从其左(或右)兄弟结点“借调”关键字3）若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。第十七页，共四十七页，2022年，8月28日B-树删除结点1.被删除结点上关键字个数不少于m/2-1，那么只需从该结点上删除该关键字Ki和相应的指针Ai。例如下图3-阶B树中删除关键字12时，直接将12删除即可。539024501003

12

374561703abcdefgh第十八页，共四十七页，2022年，8月28日B-树删除结点2.如果被删除结点上关键字个数等于m/2-1，而与其相邻的右兄弟结点（或左兄弟）结点中关键字的个数大于m/2-1上图为删除50前、后的3阶B-树。53902450100337456170abcdefgh70619053第十九页，共四十七页，2022年，8月28日B-树删除结点3.被删除关键字所在结点和其相邻的右兄弟结点（或左兄弟）结点中关键字的个数均等于m/2-1，9061902410033745abcdefgh7053删除关键字5361

70第二十页，共四十七页，2022年，8月28日90B-树删除结点2410033745abcdegh练习：从上面的B树中删除关键字3761

70第二十一页，共四十七页，2022年，8月28日^^24^3^3^2490B-树删除结点1003745abcdegh练习：从上面的B树中删除关键字3761

7037没有右兄弟且其左兄弟也只有一个关键字，把37双亲结点中小于37的关键字24与左兄弟中的3合并成一个结点。此时，发现左右子树高度不同，必须调整成B-树。4590100ech32461

70g第二十二页，共四十七页，2022年，8月28日4590B-树删除结点100ech练习：从上面的B树中删除关键字37^3^24^61

70g调整后的B-树，如下所示第二十三页，共四十七页，2022年，8月28日B-树查找性能分析在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。问：1）含N个关键字的m阶B-树可能达到的最大深度H为多少？第二十四页，共四十七页，2022年，8月28日B-树查找性能分析2）深度为H的B-树中，至少含有多少个结点？第2层2个先推导每一层所含最少结点数：第1层

1个第H+1层2(m/2)H-1个第4层2(m/2)2个第3层2m/2个

……第二十五页，共四十七页，2022年，8月28日B-树查找性能分析假设m阶B-树的深度为H+1，由于第H+1层为叶子结点，而当前树中含有N个关键字，则叶子结点必为N+1个，N+1≥2(m/2)H-1H-1≤logm/2((N+1)/2)H≤logm/2((N+1)/2)+1由此可推得下列结果：第二十六页，共四十七页，2022年，8月28日B-树查找性能分析在含n个关键字的B-树上进行一次查找，需访问的结点个数不超过

logm/2((n+1)/2)+1结论：第二十七页，共四十七页，2022年，8月28日B+树特点是B-树的一种变型。1）有n棵子树的结点中含有n个关键字2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；3）每个非叶结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值；第二十八页，共四十七页，2022年，8月28日5096155062

78

96717884

89

965662202643503815sqrootB+树特点第二十九页，共四十七页，2022年，8月28日B+树查找过程1）在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找；2）在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；3）若在结点内查找时，给定值≤Ki，则应继续在Ai所指子树中进行查找；第三十页，共四十七页，2022年，8月28日B+树插入和删除操作类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。第三十一页，共四十七页，2022年，8月28日键树键树的结构特点双链树Trie树第三十二页，共四十七页，2022年，8月28日键树的结构特点HAD$S$VE$E$R$E$IGH$S$表示关键字集合{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS}第三十三页，共四十七页，2022年，8月28日键树定义键树又称为数字查找树，它是一棵度>=2的树，其中的每个结点中不是包含一个或者几个关键字，而是只包含组成关键字的符号。第三十四页，共四十七页，2022年，8月28日键树的结构特点1）关键字中的各个符号分布在从根结点到叶结点的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关;2）键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。第三十五页，共四十七页，2022年，8月28日双链树—以二叉链表作存储结构实现的键树结点结构:first

symbol

next分支结点infoptr

symbol

next叶子结点指向孩子结点的指针指向兄弟结点的指针指向记录的指针typedefenum{LEAF,

BRANCH}NodeKind;//两种结点：{叶子和分支}第三十六页，共四十七页，2022年，8月28日HAD$HADE$R$$ES$GH$IHEHERHEREHIGHHIS…T叶子结点分支结点含关键字的记录第三十七页，共四十七页，2022年，8月28日双链树typedefstructDLTNode{charsymbol;

structDLTNode*next;//指向兄弟结点的指针NodeKindkind;

union{Record*infoptr;//叶子结点内的记录指针

structDLTNode*first;//分支结点内的孩子链指针}}DLTNode,*DLTree;//双链树的类型第三十八页，共四十七页，2022年，8月28日双链树#defineMAXKEYLEN16//关键字的最大长度typedefstruct{charch[MAXKEYLEN];//关键字intnum;//关键字长度}KeysType;//关键字类型第三十九页，共四十七页，2022年，8月28日双链树查找过程假设:T为指向双链树根结点的指针，K.ch[0..K.num-1]为待查关键字(给定值)。则查找过程中的基本操作为进行下列比较:K.ch[i]=?p->symbol

其中:0≤i≤K.num-1，p指向双链树中某个结点第四十页，共四十七页，2022年，8月28日双链树查找过程1.初始状态:p=T->first;i=0;2.若(p&&p->symbol==K.ch[i]&&i<K.num-1)则继续和给定值的下一位进行比较

p=p->first;i++;3.若(p&&p->symbol!=K.ch[i])则继续在键树的同一层上进行查找p=p->next;第四十一页，共四十七页，2022年，8月28日双链树查找过程若(p&&p->symbol==K.ch[i]&&i==K.num-1)则查找成功，返回指向相应记录的指针p->infoptr4.若(p==NULL)则表明查找不成功，返回“空指针”;第四十二页，共四十七页，2022年，8月28日Trie树—以多重链表作存储结构实现的键树结点结构:分支结点叶子结点指向记录的指针012345……

242526关键字指向下层结点的指针每个域对应一个“字母”第四十三页，共四十七页，2022年，8月28日01(A)345(E)9(I)……

268(H)4(D)19(S)22(V)018(R)7(G)1905(E)THADHASHAVHEHERHEREHIGHIS叶子结点分支结点指向记录的指针第四十四页，共四十七页，2022年，8月28日typedefstructTrieNode{NodeKindkind;//结点类型union{struct{KeyTypeK;Record*infoptr}lf;