南京邮电大学数据结构A第7章研讨.ppt

7.3 B-树 7.3.6 B-树的删除 B-树删除中3个重要的操作： (1)替代 (2)删除元素和空指针 (3)借或者并 课堂提要 第7章 搜索树 7.1 二叉搜索树 7.3 B树 7.3.1 m叉搜索树 7.3.2 B-树的定义 7.3.3 B-树的高度 7.3.4 B-树的搜索 7.3.5 B-树的插入 7.3.6 B-树的删除 7.3 B-树 7.3.6 B-树的删除 (1) 替代 从B-树上删除一个指定元素的操作同插入一样，是从叶子结点开始。如果被删除的元素不在叶子结点中，那么由它右子树上的最小元素取代之，即由大于被删除元素的最小元素取代之。这种“替代”使得删除操作成为从B-树的叶子结点中删除一个元素。 35 18 11 27 43 78 47 53 64 99 图7-23 4阶B-树 例如：删除35 39 39 r 7.3 B-树 7.3.6 B-树的删除 (2) 删除元素和空指针 替代以后从r结点中删除39和一个空指针。删除后r结点中的元素个数不足B-树规定的下限（即至少?m/2? -1个元素），从而发生下溢。 39 18 11 27 43 78 47 53 64 99 图7-23 4阶B-树 r 39 7.3 B-树 7.3.6 B-树的删除 (3) 借 发生下溢后，解决这一问题的做法首先检查其左、右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的元素，则从左侧兄弟“借”一个元素；否则，若右侧兄弟有多余的元素，则向右侧兄弟“借”一个元素。 39 18 11 27 78 53 64 99 图7-23 4阶B-树 r 43 47 7.3 B-树 7.3.6 B-树的删除 (3) 借 发生下溢后，解决这一问题的做法首先检查其左、右两侧的兄弟结点中的元素个数，若左侧兄弟有多余的元素，则从左侧兄弟“借”一个元素；否则，若右侧兄弟有多余的元素，则向右侧兄弟“借”一个元素。 39 18 11 27 78 53 64 99 图7-23 4阶B-树 r 43 47 再完整看一遍！ 7.3 B-树 7.3.6 B-树的删除 错误的“借”法一： 直接将兄弟结点中的元素借过来； 39 18 11 27 78 53 64 99 r 43 47 7.3 B-树 7.3.6 B-树的删除 错误的“借”法二： 传递地借元素； 39 18 11 27 86 99 r 43 80 39 69 78 7.3 B-树 7.3.6 B-树的删除 39 18 11 47 78 53 64 99 图7-23 4阶B-树 43 s (4) 或者并 如果一个B-树结点发生下溢时，其左、右两侧兄弟都恰好只有?m/2? -1个元素，那么只能 “并” 。 27 s’ u t 例如：删除27 7.3 B-树 7.3.6 B-树的删除 39 47 78 53 64 99 图7-23 4阶B-树 43 (4) 或者连接 如果一个B-树结点发生下溢时，其左、右两侧兄弟都恰好只有?m/2? -1个元素，那么只能 “连接” 。 s 11 s’ u t 例如：删除27 18 7.3 B-树 7.3.6 B-树的删除 78 53 64 99 图7-23 4阶B-树 43 (4) 或者连接 如果一个B-树结点发生下溢时，其左、右两侧兄弟都恰好只有?m/2? -1个元素，那么只能 “连接” 。 11 18 s’ u t 例如：删除27 39 47 7.3 B-树 7.3.6 B-树的删除 B-树删除元素的方法： (1) 首先搜索被删除的元素，如果不存在，则删除运算失败终止。如果搜索成功，且被删除的元素在叶子结点中，则从该叶子结点中删除该元素；如果被删除的元素不在叶子结点中，那么用它的右侧子树上的最小元素取代之（必定在叶子结点中），然后从叶子结点中删除该替代元素。 (2) 如果删除元素后，当前结点中包含至少?m/2? -1个元素，则删除运算成功结束。 (3) 如果删除元素后，当前结点中包含不足?m/2? -1个元素，则称发生了下溢。处理的方法首先是借元素：如果其左侧兄弟有至少?m/2? 个元素，则可以向其左兄弟“借”一个元素；否则如果其右侧兄弟有多余元素，则向其右侧兄弟借。 7.3 B-树 7.3.6 B-树的删除 B-树删除元素的方法： (4) 如果删除元素后，当前结点产生下溢，且左右两侧兄弟结点都只有?m/2? -1个元素，则只能进行“连接”。 (5) 如果