Java数据结构和算法(B树)

前言

B树又叫平衡的多路搜索树；平衡的意思是又满足平衡二叉树的一些性质，左树大于右树；
多路意思是，可以多个结点，不再是像二叉树只有两个结点；

实现原理

B树是一种自平衡的搜索树，通常用于实现数据库和文件系统中的索引。它通过保持节点的平衡结构来保证插入、删除和查找操作在对数时间内完成。B树的具体实现原理包括以下几个方面：

1. 结构

• 节点：每个节点包含多个键和指向子节点的指针。一个节点最多可以包含 m-1 个键和 m 个指针，其中 m 是B树的阶。
• 根节点：根节点是树的顶部节点，特殊情况下，根节点可以是一个叶子节点（当树为空或只有一个节点时）。
• 内部节点：非叶子节点，包含指向子节点的指针。
• 叶子节点：没有子节点的节点，包含数据记录或指向数据记录的指针。

2. 性质

1. 键的顺序：每个节点中的键按升序排列。
2. 节点子树：对于一个节点 N 和其中的键 K_i，所有在 K_i 左边的子树中的键都小于 K_i，所有在 K_i 右边的子树中的键都大于 K_i。
3. 平衡性：所有叶子节点位于同一层次，这保证了树的平衡。
4. 节点容量：除了根节点外，每个节点至少包含 ⌈m/2⌉ - 1 个键，最多包含 m-1 个键。

3. 操作

查找

从根节点开始，逐层向下查找：

1. 在当前节点中找到第一个大于或等于目标键的位置 i。
2. 如果 K_i 正好等于目标键，则查找成功。
3. 如果目标键小于 K_i 或在所有键后，递归地在对应的子树中继续查找。

插入

1. 找到插入位置：从根节点开始，找到插入键的位置。
2. 分裂节点：如果插入键导致某个节点的键超过 m-1，则将该节点分裂为两个节点，并将中间键提升到父节点。
3. 递归分裂：如果提升的中间键导致父节点也超过 m-1 键，则继续向上分裂，直到根节点。如果根节点也需要分裂，则树的高度增加。

删除

1. 找到删除位置：从根节点开始，找到要删除的键。
2. 叶子节点删除：如果键在叶子节点，直接删除。
3. 内部节点删除：如果键在内部节点，找到适当的替代键（前驱或后继），并递归删除替代键。
4. 合并节点：如果删除键导致某个节点的键少于 ⌈m/2⌉ - 1，需要通过与兄弟节点合并或借用兄弟节点的键来维持B树性质。

具体代码实现

class AVLTreeNode {int key;int height;AVLTreeNode left;AVLTreeNode right;AVLTreeNode(int key) {this.key = key;this.height = 0;this.left = this.right = null;}
}public class AVLTree {private AVLTreeNode root;public AVLTree() {root = null;}// 获取以节点为根的树的高度private int height(AVLTreeNode node) {if (node == null) {return 0;}return node.height;}// 更新节点的高度private void updateHeight(AVLTreeNode node) {node.height = Math.max(height(node.left), height(node.right)) + 1;}// 左旋private AVLTreeNode rotateLeft(AVLTreeNode node) {AVLTreeNode rightNode = node.right;node.right = rightNode.left;rightNode.left = node;updateHeight(node);updateHeight(rightNode);return rightNode;}// 右旋private AVLTreeNode rotateRight(AVLTreeNode node) {AVLTreeNode leftNode = node.left;node.left = leftNode.right;leftNode.right = node;updateHeight(node);updateHeight(leftNode);return leftNode;}// 左右旋（先左后右）private AVLTreeNode rotateLR(AVLTreeNode node) {node.left = rotateLeft(node.left);return rotateRight(node);}// 右左旋（先右后左）private AVLTreeNode rotateRL(AVLTreeNode node) {node.right = rotateRight(node.right);return rotateLeft(node);}// 插入节点public void insert(int key) {root = insert(root, key);}// 递归插入并平衡private AVLTreeNode insert(AVLTreeNode node, int key) {if (node == null) {return new AVLTreeNode(key);}if (key < node.key) {node.left = insert(node.left, key);if (height(node.left) - height(node.right) == 2) {if (key < node.left.key) {node = rotateRight(node);} else {node = rotateLR(node);}}} else if (key > node.key) {node.right = insert(node.right, key);if (height(node.right) - height(node.left) == 2) {if (key > node.right.key) {node = rotateLeft(node);} else {node = rotateRL(node);}}}updateHeight(node);return node;}
}

QA:待定