企业网站 留言板,盘州电子商务网站建设,在线网页代理网址,wordpress mv网站模板本文以 2-3-4 树详细讲解了 B 树的概念#xff0c;逐步分析其操作#xff0c;并用 Java 实现了标准的 B 树。
1. 2-3 2-3-4 Trees
上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密#xff0c;如下图右侧所示#xff0c;时间复杂度也就…本文以 2-3-4 树详细讲解了 B 树的概念逐步分析其操作并用 Java 实现了标准的 B 树。
1. 2-3 2-3-4 Trees
上一节课中讲到的二叉搜索树当数据是随机顺序插入的时候能够使得树变得比较茂密如下图右侧所示时间复杂度也就近似 O ( l o g n ) O(log n) O(logn)。但是当数据按顺序插入时二叉搜索树就退化为了链表每个节点都向同一侧倾斜如下图左侧所示这样时间复杂度就退化为 O ( n ) O(n) O(n)。有什么更优化的数据结构呢 B 树B-Trees是一种自平衡的树数据结构适用于在磁盘等存储设备上高效管理大量数据。它通过保持平衡来确保查找、插入、删除操作的时间复杂度为 O ( l o g n ) O(log n) O(logn)。B 树广泛应用于数据库和文件系统。
1.1 插入
假设我们现在有一颗还算完美的二叉搜索树如下图右上角所示接下来如果我们需要插入 {17, 18, 19, ...} 怎么办我们可以通过在叶节点中“过度填充”来避免产生新的叶节点也就是把插入的元素都塞到 16 节点中 但是如果一个节点过于充斥如下图所示那么我们可能就得遍历节点中的所有元素才能找到我们想要的这样效率同样会下降 我们的解决方法是设定一个限制 L L L表示一个节点中最多有几个键值假设我们令 L 3 L 3 L3那么当节点中的键值已经到 {16, 17, 18, 19} 时就已经超过限制了这时我们需要选择一个键值提升到父节点中。
我们会将中间键记为 node[mid]提升到父节点在我们这个例子中键值数量为偶数那么就选择中间偏左的键值 17如下图所示 仔细观察又会发现这样有个问题那就是这时 16 在 {15, 17} 的右侧了这就不是个合法的搜索树了。因此再提完中间键后我们需要将中间键的左右两部分分裂开变成两个节点假设 node 表示提升键值前的原节点 {16, 17, 18, 19}那么分裂操作就是将 node[0 ~ mid - 1] 与 node[mid 1, node.size - 1] 分裂开。
因此我们会将 16 与 {18, 19} 分裂开如下图所示这样小于 15 的键值在左侧子节点可以表示为 {15, 17}.children[0]在 15 ~ 17 之间的键值在左侧第二个子节点可以表示为 {15, 17}.children[1]大于 17 的键值在右侧子节点可以表示为 {15, 17}.children[2] 假设我们继续插入 {20, 21}如下图所示当插入 21 时节点又爆满了将中间靠左的键值 19 提升到父节点中接着原节点分裂开 我们继续插入 {25, 26}流程如下图所示可以看到当非叶子节点分裂时还需要同步处理子节点的引用即分裂非叶子节点 node[0 ~ mid - 1] 与 node[mid 1, node.size - 1] 时还需要顺带分裂 node.children[0, mid] 与 node.children[mid 1, node.size - 1]注意左半部分需要将 mid 包含进去才正确可以结合图片理解 如果我们一直添加到根节点都塞满了怎么办那么就同样将根节点中的中间键往上提这时候就成为了新的根节点树的高度在这时候才加了一层即树的高度只有在分裂根时才会增加此时树还是保持着完美的平衡 我们此前设定的限制 L 3 L 3 L3 就最后就形成了这棵 2-3-4 树当 L 2 L 2 L2 时我们称其为 2-3 树这两种就是相对最常见的 B 树。
1.2 删除
B 树的删除与 BST 一样是比较复杂的有多种情况需要讨论。
1如果要删除的节点为内部节点无论节点中有几个键值那么思想与 BST 类似找到前驱左子树最大键或后继右子树最小键替换要删除的键值然后递归删除叶子节点中的键 在这种情况中我们找到了 18最后将其删去这样看起来很简单因为如果我们从具有多个键值的叶子节点中删除某个值只需要简单将其删去即可。
2如果我们的叶子节点只有一个键我们就不能简单地完全删除节点因为根据 B 树的性质先见第二小节每个拥有 k k k 个键值的节点除叶子都有 k 1 k 1 k1 个子节点因此我们将留下一个必须填充的空节点 如何填充空节点是比较复杂的同样也有多种情况要讨论
Case 1空节点的相邻兄弟节点有多个键值非常难的情况如下图所示我们用哪个键来填充呢 解决思路为
X 先把父节点的键值拿过来然后父节点再从 X 的兄弟节点中拿一个键值过来如果 X 不是叶节点再将其兄弟节点的一个子树拿过来维持 B 树性质。 结合例子看看我们要删除 17首先在右子树找到了后继键值 19将其与 17 交换然后删除 17删除后留下了一个空节点填充时从父节点拿来 21父节点再从另一个兄弟节点拿来 22由于空节点为叶节点因此不进一步拿兄弟节点的子树 Case 2空节点右侧的所有兄弟节点都只有一个键值但是父节点有多个键值同样很困难如下图所示 解决思路为
X 和最右侧的兄弟节点把父节点的键值拿来中间子节点的键值提到父节点中传递中间子节点的子树以便每个节点都有正确的子节点 结合例子看看我们要删除 3首先在右子树中找到了后继键值 4将其与 3 交换然后删除 4删除后留下了一个空节点填充时右侧兄弟节点都只有一个键值因此和最右边的兄弟节点 9 一起分别将父节点的键值拿来然后将中间兄弟节点的键值提到父节点中已经是叶节点了因此不用再调整子树了 Case 3父节点和所有兄弟节点都只有一个键值这种简单点解决思路就是将一个兄弟节点和父节点合并成一个节点替换到 X 上然后将空节点上移一层如果空节点最终作为了根节点那么直接删除空节点即可 结合例子看看我们要删除 6首先在右子树中找到了后继键值 7将其与 6 交换然后删除 7删除后留下了一个空节点填充时右侧兄弟节点与父节点都只有一个键值因此合并兄弟节点和父节点变为 {8, 9}然后将空节点上移一层此时空节点并不是根节点回到了第一种情况兄弟节点有多个键值也就是先把父节点键值 7 拿来然后父节点从有多个键值的子节点那把 4 拿来空节点不是叶节点最后再把兄弟节点的子树 5 拿来当自己的子树 2. Java实现多阶B树
通过上面演示的 B 树我们能发现其具有以下特性我们此处以 m m m 阶 B 树为例进行概括
节点容量 根节点至少有1个键最多 m − 1 m - 1 m−1 个键。内部节点至少 ⌈ m / 2 ⌉ − 1 \lceil m / 2\rceil - 1 ⌈m/2⌉−1个键最多 m − 1 m - 1 m−1 个键。 子节点数量每个拥有 k k k 个键值的节点除叶子节点都有 k 1 k 1 k1 个子节点。平衡性所有叶子节点位于同一层相同深度树是完全平衡的无论怎么添加键值时间复杂度都为 O ( l o g n ) O(log n) O(logn)。有序性节点内的键按升序排列子树遵循二叉搜索树性质。
总结一下 B 树的操作
1查找
从根节点开始逐层向下比较键值
若找到目标键返回 true。否则根据键的大小选择对应的子节点递归查找。到达叶子节点仍未找到返回 false。
2插入
寻找插入位置递归找到对应的叶子节点。插入键将键插入叶子节点。分裂处理 若节点键数超过 m − 1 m - 1 m−1则分裂 中间键提升到父节点原节点分裂为两个子节点。 递归检查父节点是否需要分裂直到根节点。
3删除
定位键找到待删除键的位置。处理内部节点键若键在内部节点用前驱左子树最大键或后继右子树最小键替换转为删除叶子节点中的键。删除叶子键直接删除。处理下溢 借键若兄弟节点有富余键从兄弟借一个键并调整父节点合并若兄弟节点无富余合并当前节点与兄弟并递归调整父节点。
Java 实现 m m m 阶 B 树代码如下可以简单参考一下不一定要完全看明白
package CS61B.Lecture17;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;/*** 标准 m 阶 B 树实现支持插入、查找、删除* 特性* 1. 每个节点最多包含 m - 1 个键* 2. 根节点最少包含 1 个键非根节点最少包含 ⌈m / 2⌉ - 1 个键* 3. 所有叶子节点位于同一层*/
public class BTree {private final int m; // B 树的阶private Node root;public BTree(int m) {this.m m;this.root new Node(true);}/** 节点 */private static class Node {ListInteger keys new ArrayList(); // 存储键值始终保持有序ListNode children new ArrayList(); // 子节点引用非叶子节点使用boolean isLeaf; // 是否为叶子节点Node(boolean isLeaf) {this.isLeaf isLeaf;}}/** 核心操作查找 */public boolean contains(int key) {return search(root, key) ! null;}/** 递归查找实现 */private Integer search(Node node, int key) {// 找到当前节点中第一个不小于 key 的键的位置int i 0;while (i node.keys.size() key node.keys.get(i)) i;if (i node.keys.size() key node.keys.get(i)) { // 在当前节点找到目标键return key;} else if (node.isLeaf) {return null;} else { // 未找到但当前节点非叶子节点return search(node.children.get(i), key); // 递归查找子节点}}/** 核心操作插入 */public void insert(int key) {insert(root, key);// 根节点分裂处理if (root.keys.size() m) {Node newRoot new Node(false);newRoot.children.add(root);splitChild(newRoot, 0);root newRoot;}}/** 递归插入实现 */private void insert(Node node, int key) {int i node.keys.size() - 1;if (node.isLeaf) {// 叶子节点直接插入while (i 0 key node.keys.get(i)) i--; // 找到小于等于 key 的最大值位置node.keys.add(i 1, key); // 在其右侧插入 key} else {// 内部节点找到子节点位置while (i 0 key node.keys.get(i)) i--;i; // 调整到正确的子节点索引因为 node[i] 小于等于 keynode.children[i] 是小于 node[i] 的子树// 子节点已满时先分裂if (node.children.get(i).keys.size() m - 1) {splitChild(node, i);if (key node.keys.get(i)) i; // 分裂后可能需要调整目标子节点索引}insert(node.children.get(i), key);}}/** 分裂子节点核心辅助方法 */private void splitChild(Node parent, int childIndex) {Node child parent.children.get(childIndex);Node sibling new Node(child.isLeaf); // 与原节点在同一层int mid m - 1 1; // 中间键索引// 将右半部分键移动到新节点sibling.keys.addAll(child.keys.subList(mid 1, child.keys.size()));child.keys.subList(mid 1, child.keys.size()).clear(); // 清除原节点右半部分// 非叶子节点处理子节点引用if (!child.isLeaf) {sibling.children.addAll(child.children.subList(mid 1, child.children.size()));child.children.subList(mid 1, child.children.size()).clear();}// 将中间键提升到父节点新节点在原节点的右边parent.keys.add(childIndex, child.keys.remove(mid));parent.children.add(childIndex 1, sibling);}/** 核心操作删除 */public void delete(int key) {delete(root, key);/*根节点为空时降低树高度选择其第一个子节点作为新的根节点当根节点被删除到空时唯一可能的场景是根节点原本只有一个键且该键被删除根节点此时仅剩一个子节点因为如果根节点有多个子节点它必须至少保留一个键来分隔子节点*/if (root.keys.isEmpty() !root.isLeaf) {root root.children.get(0);}}/** 递归删除实现 */private void delete(Node node, int key) {int i 0;while (i node.keys.size() key node.keys.get(i)) i; // 找到大于等于 key 的最小值// Case 1: 当前节点包含目标键if (i node.keys.size() key node.keys.get(i)) {if (node.isLeaf) { // 如果为叶子节点的键则直接删除node.keys.remove(i);} else { // 如果是内部节点则用前驱/后继替换后递归删除handleInternalKey(node, i);}}// Case 2: 目标键可能在子节点中else if (!node.isLeaf) {Node child node.children.get(i);// 子节点键不足时先调整if (child.keys.size() (m 1) / 2) {// 尝试从左兄弟借键if (i 0 node.children.get(i - 1).keys.size() (m 1) / 2) {borrowFromLeftSibling(node, i);}// 尝试从右兄弟借键else if (i node.children.size() - 1 node.children.get(i 1).keys.size() (m 1) / 2) {borrowFromRightSibling(node, i);}// 需要合并节点else {if (i node.children.size() - 1) {mergeChildren(node, i);} else {mergeChildren(node, i - 1);i--; // 合并后索引调整}}}delete(node.children.get(i), key);}}/** 处理内部节点键的删除选择前驱后继时需要注意非根节点最少包含 ⌈m / 2⌉ - 1 个键的性质 */private void handleInternalKey(Node node, int index) {Node leftChild node.children.get(index);Node rightChild node.children.get(index 1);// Case 1: 左子节点的键足够多用前驱替换if (leftChild.keys.size() (m 1) / 2) {int predecessor getPredecessor(leftChild);node.keys.set(index, predecessor);delete(leftChild, predecessor);}// Case 2: 右子节点的键足够多用后继替换else if (rightChild.keys.size() (m 1) / 2) {int successor getSuccessor(rightChild);node.keys.set(index, successor);delete(rightChild, successor);}// Case 3: 否则合并 leftChild 与 rightChild 两个子节点后递归删除else {int keyToDelete node.keys.get(index); // 合并后 node.keys.get(index) 可能已变更需要提前保存mergeChildren(node, index);delete(leftChild, keyToDelete); // 删除已下移到子节点的原键}}/** 获取左子树的最大键前驱 */private int getPredecessor(Node node) {while (!node.isLeaf) {node node.children.get(node.children.size() - 1);}return node.keys.get(node.keys.size() - 1);}/** 获取右子树的最小键后继 */private int getSuccessor(Node node) {while (!node.isLeaf) {node node.children.get(0);}return node.keys.get(0);}/** 从左兄弟借键 */private void borrowFromLeftSibling(Node parent, int childIndex) {Node child parent.children.get(childIndex);Node leftSibling parent.children.get(childIndex - 1);// 父节点键下移左兄弟键上移child.keys.add(0, parent.keys.get(childIndex - 1));parent.keys.set(childIndex - 1, leftSibling.keys.remove(leftSibling.keys.size() - 1));// 移动子节点引用非叶子节点if (!child.isLeaf) {child.children.add(0, leftSibling.children.remove(leftSibling.children.size() - 1));}}/** 从右兄弟借键 */private void borrowFromRightSibling(Node parent, int childIndex) {Node child parent.children.get(childIndex);Node rightSibling parent.children.get(childIndex 1);// 父节点键下移右兄弟键上移child.keys.add(parent.keys.get(childIndex));parent.keys.set(childIndex, rightSibling.keys.remove(0));// 移动子节点引用非叶子节点if (!child.isLeaf) {child.children.add(rightSibling.children.remove(0));}}/** 合并 childIndex 与 childIndex 1 两个位置的子节点 */private void mergeChildren(Node parent, int childIndex) {Node left parent.children.get(childIndex);Node right parent.children.get(childIndex 1);// 提取父节点的键并下移int parentKey parent.keys.get(childIndex);left.keys.add(parentKey);parent.keys.remove(childIndex);// 合并右子节点的键和子节点left.keys.addAll(right.keys);left.children.addAll(right.children);parent.children.remove(childIndex 1);// 若父节点是根且无键降低树高度if (parent root parent.keys.isEmpty()) {root left;}}/** 打印 B 树结构 */public void printTree() {printTree(root, 0);}/** 递归打印 B 树结构 */private void printTree(Node node, int level) {StringBuilder indent new StringBuilder();for (int i 0; i level; i) {indent.append(│ ); // 每层缩进 4 个字符}// 打印当前节点键值System.out.print(indent);if (level 0) {System.out.print(├── );}System.out.print([ String.join(, , node.keys.stream().map(Object::toString).toArray(String[]::new)) ]);if (node.isLeaf) {System.out.print( (Leaf));}System.out.println();// 递归打印子节点for (int i 0; i node.children.size(); i) {Node child node.children.get(i);printTree(child, level 1);}}/** 递归打印 B 树结构添加箭头符号的增强版 */private void printTreeEnhancement(Node node, int level) {// 生成缩进前缀StringBuilder prefix new StringBuilder();for (int i 0; i level; i) {prefix.append(i level - 1 ? │ : );}// 打印当前节点System.out.print(prefix);if (level 0) {System.out.print(└── );}System.out.print([ String.join(, , Arrays.toString(node.keys.stream().map(Object::toString).toArray(String[]::new)) ]));if (node.isLeaf) System.out.print( (Leaf));System.out.println();// 递归子节点for (int i 0; i node.children.size(); i) {Node child node.children.get(i);printTree(child, level 1);}}/** 测试 */public static void main(String[] args) {BTree tree new BTree(4);// 插入测试数据int[] keys {10, 20, 30, 40, 50, 60, 70, 80, 90};for (int key : keys) tree.insert(key);// 验证存在性System.out.println(Contains 30: tree.contains(30)); // trueSystem.out.println(Contains 10: tree.contains(10)); // truetree.printTree();// 删除内部节点键tree.delete(30);System.out.println(Contains 30 after deletion: tree.contains(30)); // falsetree.printTree();// 边界测试删除后树结构调整tree.delete(10);tree.delete(20);tree.delete(40);System.out.println(Contains 50: tree.contains(50)); // trueSystem.out.println(Contains 10 after deletion: tree.contains(10)); // false}
}
