数据结构-B树和B键树_第1页
数据结构-B树和B键树_第2页
数据结构-B树和B键树_第3页
数据结构-B树和B键树_第4页
数据结构-B树和B键树_第5页
已阅读5页，还剩43页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、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阶

2、的B-树，或为空树，或为满足下列特性的m叉树,1、树中每个结点最多有m棵子树,2、若根结点不是叶子结点，则至少有两棵子树,3、除根之外的所有非终端（叶子）结点至少有棵子树,B-树定义,4、所有非终端结点中包含下列信息数据,(n,A0,K1,A1,K2,A2,Kn,An),5、所有叶子结点都在同一层，不带信息,a.n为关键字的个数，多个关键字自小至大有序排列，即：K1K2symbol其中:0iK.num-1，p指向双链树中某个结点,双链树查找过程,1.初始状态:p=T-first;i=0;,2.若(p,3.若(p,双链树查找过程,若(p,Trie树,以多重链表作存储结构实现的键树,结点结构:,分

3、支结点,叶子结点,指向记录的指针,指向下层结点的指针每个域对应一个“字母”,01(A)345(E)9(I)26,8(H),4(D)19(S)22(V)018(R)7(G)19,05(E),T,HAD,HAS,HAV,HE,HER,HERE,HIG,HIS,叶子结点,分支结点,指向记录的指针,typedefstructTrieNodeNodeKindkind;/结点类型unionstructKeyTypeK;Record*infoptrlf;/叶子结点(关键字和指向记录的指针)structTrieNode*ptr27;intnumbh;/分支结点(27个指向下一层结点的指针)TrieNode,*

4、TrieTree;/键树类型,结点结构的C语言描述:,Trie树,Trie树查找过程,在Trie树中查找记录的过程:,假设:T为指向Trie树根结点的指针，K.num是字符的个数，K.ch0.K.num-1为待查关键字(给定值)。,则查找过程中的基本操作为：搜索和对应字母相应的指针:若p不空，且p所指为分支结点，则p=p-bh.Ptrord(K.chi);/ord将字母影射成在字母表中的位置(其中:0iK.num-1),Trie树查找过程,初始状态:p=T;i=0;,若(p,若(p&p-kind=LEAF&p-lf.K=K)则查找成功，返回指向相应记录的指针ptr,反之，即(!p|p-kind=LEAF,小结和作业,1.B-树

人人文库> 全部分类> 应用文书 > 项目管理

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论