前言
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:待定
