B树（B-Tree）的删除操作 B树是一种自平衡的多路搜索树，广泛应用于数据库和文件系统中。删除操作是B树中最复杂的操作之一，因为它需要维护B树的所有性质：节点关键字数量在特定范围内、所有叶子节点在同一层等。 删除操作的基本情况分析 删除操作需要区分三种基本情况： 删除关键字在叶子节点中 删除关键字在内部节点中 删除后需要重新平衡 情况1：删除叶子节点中的关键字 这是最简单的情况，直接删除关键字即可，但删除后需要检查节点是否满足B树的最小关键字数要求。 假设B树的最小度数为t（每个节点至少包含t-1个关键字，最多2t-1个关键字）： 如果删除后节点关键字数 ≥ t-1：操作完成 如果删除后节点关键字数 < t-1：需要重新平衡 情况2：删除内部节点中的关键字 当要删除的关键字在内部节点时，不能直接删除，需要找到合适的替代关键字： 前驱替代法 ：找到该关键字在左子树中的最大关键字（前驱） 后继替代法 ：找到该关键字在右子树中的最小关键字（后继） 用前驱或后继替换要删除的关键字，然后在子树中递归删除这个前驱或后继。 删除操作的重新平衡策略 当节点关键字数不足时，需要通过以下方法重新平衡： 从兄弟节点借关键字 （旋转操作） 与兄弟节点合并 详细的删除步骤 步骤1：查找要删除的关键字 从根节点开始，按照搜索树的规则查找关键字的位置。 步骤2：处理内部节点的关键字删除 如果关键字在内部节点中： 找到关键字k在节点x中的位置i 检查左子节点（y）的关键字数： 如果y的关键字数 ≥ t：找到k的前驱（y子树中的最大关键字），用前驱替换k，在y中递归删除前驱 否则检查右子节点（z）的关键字数： 如果z的关键字数 ≥ t：找到k的后继（z子树中的最小关键字），用后继替换k，在z中递归删除后继 如果左右子节点关键字数都 = t-1：合并y、k和z，然后在合并后的节点中递归删除k 步骤3：处理叶子节点的关键字删除 如果关键字在叶子节点中： 直接删除关键字 检查删除后节点关键字数： 如果 ≥ t-1：操作完成 如果 < t-1：需要重新平衡 步骤4：重新平衡操作 对于关键字数不足的节点x： 检查左兄弟 ： 如果左兄弟关键字数 ≥ t：从父节点借一个关键字，从左兄弟借一个最大的关键字给父节点 检查右兄弟 ： 如果右兄弟关键字数 ≥ t：从父节点借一个关键字，从右兄弟借一个最小的关键字给父节点 合并操作 ： 如果左右兄弟关键字数都 = t-1：与一个兄弟节点和父节点的分隔符合并 具体示例说明 假设t=2的B树（2-3树），每个节点1-3个关键字： 删除关键字"F"（在叶子节点）： 直接删除"F" 检查节点关键字数：删除后为0，需要重新平衡 向右兄弟借关键字"J"，父节点的"I"下移 父节点的"H"上移到原来"I"的位置 特殊情况处理 根节点的特殊处理 ： 如果根节点关键字数变为0，但还有子节点，则让子节点成为新的根节点 这是B树高度降低的唯一情况 合并操作的级联效应 ： 合并操作可能导致父节点关键字数不足 需要递归向上检查并重新平衡，直到根节点 时间复杂度分析 查找路径：O(log_ t n) 重新平衡：O(log_ t n) 总时间复杂度：O(log_ t n) B树的删除操作虽然复杂，但通过精心设计的重新平衡策略，能够保证树的平衡性和高效性，这是B树在数据库和文件系统中得到广泛应用的重要原因。