数据结构第九章 查找part6.ppt

* 在查找不成功之后，需进行插入。 显然，关键字插入的位置必定在最下 层的非叶结点，有下列几种情况： 3．插入 1) 插入后，该结点的关键字个数nm， 不修改指针; 2) 插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = ?m/2?， 在原结点中保留 （A0，K1，…… ， Ks-1，As-1）； 建新结点 （As，Ks+1，…… ，Kn，An）； 将（Ks，p）插入双亲结点； 3) 若双亲为空，则建新的根结点。 例如:下列为 3 阶B-树 50 ? 20 ? 40 ? ? 80 ? 插入关键字 = 60, ? 60 ? 80 ? 90, ?60?80?90? ?90? 50 80 ?60? 30, ? 40 ? ? 20 ? 30 50 80 80 30 50 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于?m/2?-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。 4．删除 在B-树中进行查找时，其查找时间主要花费在有哪些信誉好的足球投注网站结点（访问外存）上，即主要取决于B-树的深度。 5．查找性能的分析 问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？ 第 2 层 2 个 先推导每一层所含最少结点数： 第 1 层 1 个 第 H+1 层 2?(?m/2?) H-1 个 第 4 层 2?(?m/2?)2 个 第 3 层 2??m/2? 个 反过来问： 深度为H的B-树中， 至少含有多少个结点？ … … 假设 m 阶 B-树的深度为 H+1，由于 第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个， N+1≥2(?m/2?)H-1 H-1≤log?m/2?((N+1)/2) H≤log?m/2?((N+1)/2)+1 由此可推得下列结果： 在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 log?m/2?((N+1)/2)+1 结论： 是B-树的一种变型 四、B+树 1．B+树的结构特点： ※ 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点； ※ 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； ※ 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 ?m/2?和 m 之间。 50 96 15 50 62 78 96 71 78 84 89 96 56 62 20 26 43 50 3 8 15 sq root 2．查找过程 ※在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； ※ 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； ※若在结点内查找时，给定值≤Ki， 则 应继续在 Ai 所指子树中进行查找。 3．插入和删除的操作 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。 五、键 树 1. 键树 2. .双链树 3. Trie树 键树又称数字查找树，它是一棵度≥2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。 例如，若关键字是数值，则结点中只包含一个数位；若关键字是单词，则结点中只包含一个字母字符。 1. 键树 键树的结构特点： ※ 关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关； ※ 键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。 H A D $ S $ V E $ E $ R $ E $ I G H $ S $ 例如: 表示关键字集合 {HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS } 2. 双链树 — 以二叉链表作存储结构实现的键树 typedef enum { LEAF, BRANCH