Java数据结构和算法(B树)
前言
B树又叫平衡的多路搜索树；平衡的意思是又满足平衡二叉树的一些性质，左树大于右树；
多路意思是，可以多个结点，不再是像二叉树只有两个结点；
实现原理
B树是一种自平衡的搜索树，通常用于实现数据库和文件系统中的索引。它通过保持节点的平衡结构来保证插入、删除和查找操作在对数时间内完成。B树的具体实现原理包括以下几个方面：
1. 结构
- 节点：每个节点包含多个键和指向子节点的指针。一个节点最多可以包含
m-1个键和m个指针，其中m是B树的阶。 - 根节点：根节点是树的顶部节点，特殊情况下，根节点可以是一个叶子节点（当树为空或只有一个节点时）。
- 内部节点：非叶子节点，包含指向子节点的指针。
- 叶子节点：没有子节点的节点，包含数据记录或指向数据记录的指针。
2. 性质
- 键的顺序：每个节点中的键按升序排列。
- 节点子树：对于一个节点
N和其中的键K_i，所有在K_i左边的子树中的键都小于K_i，所有在K_i右边的子树中的键都大于K_i。 - 平衡性：所有叶子节点位于同一层次，这保证了树的平衡。
- 节点容量：除了根节点外，每个节点至少包含 ⌈m/2⌉ - 1 个键，最多包含
m-1个键。
3. 操作
查找
从根节点开始，逐层向下查找：
- 在当前节点中找到第一个大于或等于目标键的位置
i。 - 如果
K_i正好等于目标键，则查找成功。 - 如果目标键小于
K_i或在所有键后，递归地在对应的子树中继续查找。
插入
- 找到插入位置：从根节点开始，找到插入键的位置。
- 分裂节点：如果插入键导致某个节点的键超过
m-1，则将该节点分裂为两个节点，并将中间键提升到父节点。 - 递归分裂：如果提升的中间键导致父节点也超过
m-1键，则继续向上分裂，直到根节点。如果根节点也需要分裂，则树的高度增加。
删除
- 找到删除位置：从根节点开始，找到要删除的键。
- 叶子节点删除：如果键在叶子节点，直接删除。
- 内部节点删除：如果键在内部节点，找到适当的替代键（前驱或后继），并递归删除替代键。
- 合并节点：如果删除键导致某个节点的键少于 ⌈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:待定