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

  1. 1、本文档共48页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构-B树和B键树

B+树插入和删除操作 类似于B-树进行,即必要时,也需要进行结点的“分裂”或“归并”。 键树 键树的结构特点 双链树 Trie树 键树的结构特点 H A D $ S $ V E $ E $ R $ E $ I G H $ S $ 表示关键字集合 {HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS } 键树定义 键树又称为数字查找树,它是一棵度=2的树,其中的每个结点中不是包含一个或者几个关键字,而是只包含组成关键字的符号。 * * B-树,B+树和键树 B-树 B+树 键树 小结和作业 复习 复习 A B C X 2 LL A B C X 2 LR A B C X -2 RR A B C X -2 RL 复习 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; // 1..m,在结点中的关键字序号 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 !found) { n=p-keynum; i=Search(p, K); // 在p-key[1..keynum]中查找 i , // 使得 p-key[i]=Kp-key[i+1], //没找到则i=-1 if (i0 p-key[i]==K) found=TRUE; else { q=p; p=p-ptr[i]; } // q 指示 p 的双亲 } if (found) return (p,i,1); // 查找成功 else return (q,i,0); // 查找不成功 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.建新结点

文档评论(0)

wyjy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档