数据结构之BST、AVL、红黑树、哈夫曼树与B族树
- 开源代码
- 2025-08-30 18:42:02
数据结构之BST、AVL、红黑树、哈夫曼树与B族树 数据结构之BST、AVL、红黑树、哈夫曼树与B族树一、二叉搜索树（Binary Search Tree, BST）1. 什么是二叉搜索树？重要性质 2. 二叉搜索树实现1. 节点结构定义2. 核心操作接口3. 插入算法实现4. 删除算法实现（重点）5. 时间复杂度对比 3. 实战测试示例测试代码测试树结构变化 二、平衡二叉搜索树（AVL）1、AVL树的诞生背景2、核心平衡机制1. 平衡因子（Balance Factor）2. 失衡检测流程 3、旋转操作详解**1. LL型失衡（单右旋）****2. RR型失衡（单左旋）****3. LR型失衡（先左旋后右旋）****4. RL型失衡（先右旋后左旋）** 4、完整插入流程5、时间复杂度分析6、实战案例：实现AVL树1. AVL树节点结构2. 单右旋（LL型失衡）3. 单左旋（RR型失衡）4. 获取节点高度、平衡因子5. 插入操作6. 完整实例代码代码说明1. LL型失衡（左左失衡）- 右旋操作2. RR型失衡（右右失衡）- 左旋操作3. LR型失衡（左右失衡）- 先左旋子树再右旋4. RL型失衡（右左失衡）- 先右旋子树再左旋 测试用例输出 7、典型应用场景 三、哈夫曼树（Huffman Tree）1. 哈夫曼树定义2. 哈夫曼树构建过程3. 树结构流程图5. 代码实现6. 关键特性总结 四、红黑树（Red-Black Tree）1. 什么是红黑树2. 红黑树插入3. 红黑树删除4. 红黑树实现测试用例输出红黑树结构流程图 5. 红黑树特性总结 五、B,B+,B*树1. B树2. B+树3. B*树4. B树实现4. B树的C++实现 数据结构之BST、AVL、红黑树、哈夫曼树与B族树
一、二叉搜索树（Binary Search Tree, BST）
1. 什么是二叉搜索树？
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，其中每个节点的值都大于其左子树中的任何节点的值，且小于其右子树中的任何节点的值。它的特点使得在搜索、插入和删除操作上具有高效性。
二叉搜索树是一种具有以下特性的二叉树：
有序性： 左子树所有节点值 < 根节点值右子树所有节点值 > 根节点值 递归性：左右子树也必须是二叉搜索树中序遍历结果是有序序列 #mermaid-svg-oeMoqHbwEiUOu1nX {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .error-icon{fill:#552222;}#mermaid-svg-oeMoqHbwEiUOu1nX .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-oeMoqHbwEiUOu1nX .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-oeMoqHbwEiUOu1nX .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-oeMoqHbwEiUOu1nX .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-oeMoqHbwEiUOu1nX .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-oeMoqHbwEiUOu1nX .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-oeMoqHbwEiUOu1nX .marker{fill:#333333;stroke:#333333;}#mermaid-svg-oeMoqHbwEiUOu1nX .marker.cross{stroke:#333333;}#mermaid-svg-oeMoqHbwEiUOu1nX svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-oeMoqHbwEiUOu1nX .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .cluster-label text{fill:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .cluster-label span{color:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .label text,#mermaid-svg-oeMoqHbwEiUOu1nX span{fill:#333;color:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .node rect,#mermaid-svg-oeMoqHbwEiUOu1nX .node circle,#mermaid-svg-oeMoqHbwEiUOu1nX .node ellipse,#mermaid-svg-oeMoqHbwEiUOu1nX .node polygon,#mermaid-svg-oeMoqHbwEiUOu1nX .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-oeMoqHbwEiUOu1nX .node .label{text-align:center;}#mermaid-svg-oeMoqHbwEiUOu1nX .node.clickable{cursor:pointer;}#mermaid-svg-oeMoqHbwEiUOu1nX .arrowheadPath{fill:#333333;}#mermaid-svg-oeMoqHbwEiUOu1nX .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-oeMoqHbwEiUOu1nX .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-oeMoqHbwEiUOu1nX .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-oeMoqHbwEiUOu1nX .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-oeMoqHbwEiUOu1nX .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-oeMoqHbwEiUOu1nX .cluster text{fill:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX .cluster span{color:#333;}#mermaid-svg-oeMoqHbwEiUOu1nX div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-oeMoqHbwEiUOu1nX :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 8 3 10 1 6 9 14 4 7 重要性质 特性说明查找效率平均O(log n)，最坏O(n)插入顺序影响形态有序插入会退化成链表动态维护有序性无需显式排序，自动维护支持范围查询通过中序遍历实现2. 二叉搜索树实现 1. 节点结构定义 struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; 2. 核心操作接口 class BST { private: TreeNode* root; // 递归查找实现 TreeNode* searchRec(TreeNode* node, int key) { if (!node || node->val == key) return node; return (key < node->val) ? searchRec(node->left, key) : searchRec(node->right, key); } public: BST() : root(nullptr) {} // 查找操作 bool contains(int key) { return searchRec(root, key) != nullptr; } // 插入操作 void insert(int key) { root = insertRec(root, key); } // 删除操作 void remove(int key) { root = deleteRec(root, key); } }; 3. 插入算法实现 TreeNode* insertRec(TreeNode* node, int key) { if (!node) return new TreeNode(key); if (key < node->val) { node->left = insertRec(node->left, key); } else if (key > node->val) { node->right = insertRec(node->right, key); } return node; } 4. 删除算法实现（重点） TreeNode* deleteRec(TreeNode* root, int key) { if (!root) return nullptr; if (key < root->val) { root->left = deleteRec(root->left, key); } else if (key > root->val) { root->right = deleteRec(root->right, key); } else { // Case 1: 无左子树 if (!root->left) { TreeNode* temp = root->right; delete root; return temp; } // Case 2: 无右子树 else if (!root->right) { TreeNode* temp = root->left; delete root; return temp; } // Case 3: 左右子树均存在 TreeNode* minNode = findMin(root->right); root->val = minNode->val; root->right = deleteRec(root->right, minNode->val); } return root; } // 辅助函数：查找子树最小值节点 TreeNode* findMin(TreeNode* node) { while (node && node->left) { node = node->left; } return node; } 5. 时间复杂度对比 操作平均时间复杂度最坏时间复杂度插入O(log n)O(n)删除O(log n)O(n)查找O(log n)O(n)
3. 实战测试示例 测试代码 int main() { BST tree; // 插入测试 vector<int> nums = {8, 3, 10, 1, 6, 14, 4, 7, 13}; for (int num : nums) tree.insert(num); // 查找测试 cout << "Contains 7: " << boolalpha << tree.contains(7) << endl; // true cout << "Contains 5: " << boolalpha << tree.contains(5) << endl; // false // 删除测试 tree.remove(6); cout << "After delete 6, contains 6: " << tree.contains(6) << endl; // false cout << "Now contains 4: " << tree.contains(4) << endl; // true return 0; } 测试树结构变化 删除前： 8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 删除6后： 8 / \ 3 10 / \ \ 1 7 14 / / 4 13
二、平衡二叉搜索树（AVL） 1、AVL树的诞生背景
核心问题：二叉搜索树在极端情况下会退化为链表结构，导致操作时间复杂度退化为O(n)
解决方案： 1962年由Adelson-Velsky和Landis提出，通过动态平衡机制确保树的高度始终保持在O(log n)级别
2、核心平衡机制 1. 平衡因子（Balance Factor） 定义：BF(node) = height(left) - height(right)平衡条件：所有节点的平衡因子绝对值必须 ≤ 1 2. 失衡检测流程 #mermaid-svg-ypD3tRVJPMWUskqV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .error-icon{fill:#552222;}#mermaid-svg-ypD3tRVJPMWUskqV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ypD3tRVJPMWUskqV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ypD3tRVJPMWUskqV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ypD3tRVJPMWUskqV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ypD3tRVJPMWUskqV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ypD3tRVJPMWUskqV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ypD3tRVJPMWUskqV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ypD3tRVJPMWUskqV .marker.cross{stroke:#333333;}#mermaid-svg-ypD3tRVJPMWUskqV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ypD3tRVJPMWUskqV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .cluster-label text{fill:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .cluster-label span{color:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .label text,#mermaid-svg-ypD3tRVJPMWUskqV span{fill:#333;color:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .node rect,#mermaid-svg-ypD3tRVJPMWUskqV .node circle,#mermaid-svg-ypD3tRVJPMWUskqV .node ellipse,#mermaid-svg-ypD3tRVJPMWUskqV .node polygon,#mermaid-svg-ypD3tRVJPMWUskqV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ypD3tRVJPMWUskqV .node .label{text-align:center;}#mermaid-svg-ypD3tRVJPMWUskqV .node.clickable{cursor:pointer;}#mermaid-svg-ypD3tRVJPMWUskqV .arrowheadPath{fill:#333333;}#mermaid-svg-ypD3tRVJPMWUskqV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ypD3tRVJPMWUskqV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ypD3tRVJPMWUskqV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ypD3tRVJPMWUskqV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ypD3tRVJPMWUskqV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ypD3tRVJPMWUskqV .cluster text{fill:#333;}#mermaid-svg-ypD3tRVJPMWUskqV .cluster span{color:#333;}#mermaid-svg-ypD3tRVJPMWUskqV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ypD3tRVJPMWUskqV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} BF > 1 BF < -1 插入/删除节点 向上回溯路径 检查BF值 左子树过高 右子树过高 执行旋转调整
3、旋转操作详解 1. LL型失衡（单右旋）
结构特征
新节点插入在左子树的左子树中失衡节点的平衡因子为 +2，其左子节点的平衡因子为 +1文字示意图
A (BF=+2) → 右旋 → B / / \ B (BF=+1) C A / C (新插入节点)操作步骤
将失衡节点 A 的左子节点 B 提升为新根原根节点 A 成为 B 的右子节点B 的原有右子树（如果有）变为 A 的左子树2. RR型失衡（单左旋）
结构特征
新节点插入在右子树的右子树中失衡节点的平衡因子为 -2，其右子节点的平衡因子为 -1文字示意图
A (BF=-2) → 左旋 → B \ / \ B (BF=-1) A C \ C (新插入节点)操作要点
镜像操作与 LL 型相反注意右子树可能存在的左子树需要重新挂载3. LR型失衡（先左旋后右旋）
结构特征
新节点插入在左子树的右子树中失衡节点的平衡因子为 +2，其左子节点的平衡因子为 -1文字示意图
A (BF=+2) → 对 B 左旋 → A (BF=+2) → 对 A 右旋 → C / / / \ B (BF=-1) C B A \ / C (新插入节点) B关键步骤
先对失衡节点的左子节点 B 执行左旋（转换为 LL 型）再对根节点 A 执行右旋4. RL型失衡（先右旋后左旋）
结构特征
新节点插入在右子树的左子树中失衡节点的平衡因子为 -2，其右子节点的平衡因子为 +1文字示意图
A (BF=-2) → 对 B 右旋 → A (BF=-2) → 对 A 左旋 → C \ \ / \ B (BF=+1) C A B / \ C (新插入节点) B操作要点
先对失衡节点的右子节点 B 执行右旋（转换为 RR 型）再对根节点 A 执行左旋4、完整插入流程 #mermaid-svg-94dZfA6vpq20eVph {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-94dZfA6vpq20eVph .error-icon{fill:#552222;}#mermaid-svg-94dZfA6vpq20eVph .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-94dZfA6vpq20eVph .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-94dZfA6vpq20eVph .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-94dZfA6vpq20eVph .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-94dZfA6vpq20eVph .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-94dZfA6vpq20eVph .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-94dZfA6vpq20eVph .marker{fill:#333333;stroke:#333333;}#mermaid-svg-94dZfA6vpq20eVph .marker.cross{stroke:#333333;}#mermaid-svg-94dZfA6vpq20eVph svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-94dZfA6vpq20eVph .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-94dZfA6vpq20eVph .cluster-label text{fill:#333;}#mermaid-svg-94dZfA6vpq20eVph .cluster-label span{color:#333;}#mermaid-svg-94dZfA6vpq20eVph .label text,#mermaid-svg-94dZfA6vpq20eVph span{fill:#333;color:#333;}#mermaid-svg-94dZfA6vpq20eVph .node rect,#mermaid-svg-94dZfA6vpq20eVph .node circle,#mermaid-svg-94dZfA6vpq20eVph .node ellipse,#mermaid-svg-94dZfA6vpq20eVph .node polygon,#mermaid-svg-94dZfA6vpq20eVph .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-94dZfA6vpq20eVph .node .label{text-align:center;}#mermaid-svg-94dZfA6vpq20eVph .node.clickable{cursor:pointer;}#mermaid-svg-94dZfA6vpq20eVph .arrowheadPath{fill:#333333;}#mermaid-svg-94dZfA6vpq20eVph .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-94dZfA6vpq20eVph .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-94dZfA6vpq20eVph .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-94dZfA6vpq20eVph .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-94dZfA6vpq20eVph .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-94dZfA6vpq20eVph .cluster text{fill:#333;}#mermaid-svg-94dZfA6vpq20eVph .cluster span{color:#333;}#mermaid-svg-94dZfA6vpq20eVph div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-94dZfA6vpq20eVph :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} BF>1 BF<-1 LL型 LR型 RR型 RL型 插入新节点 标准BST插入 更新路径节点高度 回溯检查平衡因子 检查左子树结构 检查右子树结构 执行右旋 执行左右双旋 执行左旋 执行右左双旋
5、时间复杂度分析 操作时间复杂度说明查找O(log n)严格平衡保证树高插入O(log n)最多两次旋转操作删除O(log n)可能传播旋转到根节点空间复杂度O(n)每个节点需存储高度/平衡因子
6、实战案例：实现AVL树 1. AVL树节点结构 struct AVLNode { int val; AVLNode* left; AVLNode* right; int height; // 新增高度字段 AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {} }; 2. 单右旋（LL型失衡） AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; // 执行旋转 x->right = y; y->left = T2; // 更新高度 y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; // 返回新的根节点 } 3. 单左旋（RR型失衡） AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; // 执行旋转 y->left = x; x->right = T2; // 更新高度 x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; // 返回新的根节点 } 4. 获取节点高度、平衡因子 // 获取节点高度 int height(AVLNode* node) { return node ? node->height : 0; } // 获取平衡因子 int getBalance(AVLNode* node) { return node ? height(node->left) - height(node->right) : 0; } 5. 插入操作 AVLNode* insert(AVLNode* node, int key) { // 标准BST插入 if (!node) return new AVLNode(key); if (key < node->val) node->left = insert(node->left, key); else if (key > node->val) node->right = insert(node->right, key); else return node; // 不允许重复值 // 更新高度 node->height = 1 + max(height(node->left), height(node->right)); // 获取平衡因子 int balance = getBalance(node); // LL型失衡 if (balance > 1 && key < node->left->val) return rightRotate(node); // RR型失衡 if (balance < -1 && key > node->right->val) return leftRotate(node); // LR型失衡 if (balance > 1 && key > node->left->val) { node->left = leftRotate(node->left); return rightRotate(node); } // RL型失衡 if (balance < -1 && key < node->right->val) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } 6. 完整实例代码
以下是完整的 AVL树C++实现，包含插入、删除、遍历等功能，并附带测试用例：
#include <iostream> #include <algorithm> #include <queue> using namespace std; struct AVLNode { int val; AVLNode* left; AVLNode* right; int height; AVLNode(int x) : val(x), left(nullptr), right(nullptr), height(1) {} }; class AVLTree { private: AVLNode* root; // 获取节点高度 int height(AVLNode* node) { return node ? node->height : 0; } // 计算平衡因子 int getBalance(AVLNode* node) { return node ? height(node->left) - height(node->right) : 0; } // 单右旋（LL型） AVLNode* rightRotate(AVLNode* y) { AVLNode* x = y->left; AVLNode* T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; } // 单左旋（RR型） AVLNode* leftRotate(AVLNode* x) { AVLNode* y = x->right; AVLNode* T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; } // 查找最小节点 AVLNode* minValueNode(AVLNode* node) { AVLNode* current = node; while (current->left) current = current->left; return current; } public: AVLTree() : root(nullptr) {} // 插入操作（外部接口） void insert(int val) { root = insert(root, val); } // 删除操作（外部接口） void remove(int val) { root = remove(root, val); } // 搜索功能 bool search(int val) { return search(root, val); } // 中序遍历 void inOrder() { inOrder(root); cout << endl; } // 前序遍历 void preOrder() { preOrder(root); cout << endl; } // 层序遍历显示函数（用于验证树结构） void printLevelOrder() { if (!root) { cout << "空树" << endl; return; } queue<AVLNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); while (size--) { AVLNode* node = q.front(); q.pop(); cout << node->val << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } cout << endl; } } private: // 递归插入实现 AVLNode* insert(AVLNode* node, int val) { if (!node) return new AVLNode(val); if (val < node->val) node->left = insert(node->left, val); else if (val > node->val) node->right = insert(node->right, val); else return node; // 不允许重复值 node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); // LL型失衡（直接右旋） if (balance > 1 && val < node->left->val) return rightRotate(node); // RR型失衡（直接左旋） if (balance < -1 && val > node->right->val) return leftRotate(node); // LR型失衡（先左旋左子树，再右旋当前节点） if (balance > 1 && val > node->left->val) { node->left = leftRotate(node->left); return rightRotate(node); } // RL型失衡（先右旋右子树，再左旋当前节点） if (balance < -1 && val < node->right->val) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // 递归删除实现 AVLNode* remove(AVLNode* node, int val) { if (!node) return nullptr; // 1. 标准BST删除 if (val < node->val) { node->left = remove(node->left, val); } else if (val > node->val) { node->right = remove(node->right, val); } else { // 找到要删除的节点 if (!node->left || !node->right) { AVLNode* temp = node->left ? node->left : node->right; if (!temp) { // 无子节点情况 temp = node; node = nullptr; } else { // 单子节点情况 delete node; return temp; } delete temp; } else { // 双子节点情况 AVLNode* temp = minValueNode(node->right); node->val = temp->val; node->right = remove(node->right, temp->val); } } if (!node) return nullptr; // 2. 更新高度 node->height = 1 + max(height(node->left), height(node->right)); // 3. 检查平衡因子 int balance = getBalance(node); // 4. 处理四种失衡情况（关键修改点） // 左左失衡 if (balance > 1 && getBalance(node->left) >= 0) return rightRotate(node); // 左右失衡 if (balance > 1 && getBalance(node->left) < 0) { node->left = leftRotate(node->left); return rightRotate(node); } // 右右失衡 if (balance < -1 && getBalance(node->right) <= 0) return leftRotate(node); // 右左失衡 if (balance < -1 && getBalance(node->right) > 0) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // 中序遍历实现 void inOrder(AVLNode* node) { if (!node) return; inOrder(node->left); cout << node->val << " "; inOrder(node->right); } // 前序遍历实现 void preOrder(AVLNode* node) { if (!node) return; cout << node->val << " "; preOrder(node->left); preOrder(node->right); } // 搜索功能实现 bool search(AVLNode* node, int val) { if (!node) return false; if (val < node->val) return search(node->left, val); if (val > node->val) return search(node->right, val); return true; } }; // 测试用例 void testAVLTree() { AVLTree tree; // LL型失衡测试 cout << "LL型失衡测试:" << endl; int ll_test[] = { 30, 20, 10 }; for (int num : ll_test) { tree.insert(num); } cout << "中序遍历结果: "; tree.inOrder(); cout << "层序遍历结果: " << endl; tree.printLevelOrder(); // 清空树 tree = AVLTree(); // RR型失衡测试 cout << "\nRR型失衡测试:" << endl; int rr_test[] = { 10, 20, 30 }; for (int num : rr_test) { tree.insert(num); } cout << "中序遍历结果: "; tree.inOrder(); cout << "层序遍历结果: " << endl; tree.printLevelOrder(); // 清空树 tree = AVLTree(); // LR型失衡测试 cout << "\nLR型失衡测试:" << endl; int lr_test[] = { 30, 10, 20 }; for (int num : lr_test) { tree.insert(num); } cout << "中序遍历结果: "; tree.inOrder(); cout << "层序遍历结果: " << endl; tree.printLevelOrder(); // 清空树 tree = AVLTree(); // RL型失衡测试 cout << "\nRL型失衡测试:" << endl; int rl_test[] = { 10, 30, 20 }; for (int num : rl_test) { tree.insert(num); } cout << "中序遍历结果: "; tree.inOrder(); cout << "层序遍历结果: " << endl; tree.printLevelOrder(); } int main() { testAVLTree(); return 0; } 代码说明 1. LL型失衡（左左失衡）- 右旋操作插入序列: 30, 20, 10
插入30: 30 插入20: 30 / 20 插入10后(失衡): 右旋后: 30 20 / / \ 20 → 10 30 / 10 2. RR型失衡（右右失衡）- 左旋操作插入序列: 10, 20, 30
插入10: 10 插入20: 10 \ 20 插入30后(失衡): 左旋后: 10 20 \ / \ 20 → 10 30 \ 30 3. LR型失衡（左右失衡）- 先左旋子树再右旋插入序列: 30, 10, 20
插入30: 30 插入10: 30 / 10 插入20后(失衡): 左旋子树后: 右旋根节点后: 30 30 20 / / / \ 10 → 20 → 10 30 \ / 20 10 4. RL型失衡（右左失衡）- 先右旋子树再左旋插入序列: 10, 30, 20
插入10: 10 插入30: 10 \ 30 插入20后(失衡): 右旋子树后: 左旋根节点后: 10 10 20 \ \ / \ 30 → 20 → 10 30 / \ 20 30 测试用例输出 LL型失衡测试: 中序遍历结果: 10 20 30 层序遍历结果: 20 10 30 RR型失衡测试: 中序遍历结果: 10 20 30 层序遍历结果: 20 10 30 LR型失衡测试: 中序遍历结果: 10 20 30 层序遍历结果: 20 10 30 RL型失衡测试: 中序遍历结果: 10 20 30 层序遍历结果: 20 10 307、典型应用场景 数据库索引：MySQL的MEMORY存储引擎文件系统：Windows NT内核的地址空间管理内存受限系统：嵌入式设备的快速查询3D图形计算：场景图的空间划分管理
三、哈夫曼树（Huffman Tree）
1. 哈夫曼树定义
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度（WPL, Weighted Path Length）最短的二叉树。
其特点是：
带权路径最小：叶子节点的权值（如字符频率）乘以路径长度（根到叶子的边数）的总和最小。
应用场景：广泛用于数据压缩，如哈夫曼编码，通过为高频字符分配短编码、低频字符分配长编码，减少整体数据量。
核心特性：权重越大的叶子节点距离根节点越近。
核心应用：数据压缩（哈夫曼编码）、文件编码、加密算法等。
2. 哈夫曼树构建过程
以权值集合 {5, 9, 12, 13, 16, 45} 为例：
初始化森林
将每个权值视为独立的单节点树，组成森林： [5], [9], [12], [13], [16], [45]
合并最小两子树
第1次合并：选择最小权值 5 和 9，生成父节点 14 森林更新：[14], [12], [13], [16], [45]第2次合并：选择 12 和 13，生成父节点 25 森林更新：[14], [16], [25], [45]第3次合并：选择 14 和 16，生成父节点 30 森林更新：[25], [30], [45]第4次合并：选择 25 和 30，生成父节点 55 森林更新：[45], [55]第5次合并：合并 45 和 55，生成父节点 100 最终得到哈夫曼树，根节点权值为 100。验证特性
WPL计算：(5+9)*3 + (12+13+16)*2 + 45*1 = 146权重越大越靠近根：最大权值 45 直接作为根的子节点。3. 树结构流程图 #mermaid-svg-ssN8PuSrTkCKafrL {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .error-icon{fill:#552222;}#mermaid-svg-ssN8PuSrTkCKafrL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ssN8PuSrTkCKafrL .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ssN8PuSrTkCKafrL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ssN8PuSrTkCKafrL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ssN8PuSrTkCKafrL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ssN8PuSrTkCKafrL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ssN8PuSrTkCKafrL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ssN8PuSrTkCKafrL .marker.cross{stroke:#333333;}#mermaid-svg-ssN8PuSrTkCKafrL svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ssN8PuSrTkCKafrL .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .cluster-label text{fill:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .cluster-label span{color:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .label text,#mermaid-svg-ssN8PuSrTkCKafrL span{fill:#333;color:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .node rect,#mermaid-svg-ssN8PuSrTkCKafrL .node circle,#mermaid-svg-ssN8PuSrTkCKafrL .node ellipse,#mermaid-svg-ssN8PuSrTkCKafrL .node polygon,#mermaid-svg-ssN8PuSrTkCKafrL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ssN8PuSrTkCKafrL .node .label{text-align:center;}#mermaid-svg-ssN8PuSrTkCKafrL .node.clickable{cursor:pointer;}#mermaid-svg-ssN8PuSrTkCKafrL .arrowheadPath{fill:#333333;}#mermaid-svg-ssN8PuSrTkCKafrL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ssN8PuSrTkCKafrL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ssN8PuSrTkCKafrL .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ssN8PuSrTkCKafrL .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ssN8PuSrTkCKafrL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ssN8PuSrTkCKafrL .cluster text{fill:#333;}#mermaid-svg-ssN8PuSrTkCKafrL .cluster span{color:#333;}#mermaid-svg-ssN8PuSrTkCKafrL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ssN8PuSrTkCKafrL :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 5 9 12 13 14 16 25 30 45 55 100
流程图说明：
根节点权值为 100（所有原始权值之和：5+9+12+13+16+45）。叶子节点为原始权值，内部节点为合并生成的权值。路径关系：父节点到子节点的连接体现合并顺序。5. 代码实现 #include <iostream> #include <queue> #include <vector> using namespace std; // 哈夫曼树节点定义 struct HuffmanNode { int weight; HuffmanNode *left, *right; HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {} }; // 优先队列比较规则（最小堆） struct Compare { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a->weight > b->weight; } }; // 构建哈夫曼树函数 HuffmanNode* buildHuffmanTree(vector<int>& weights) { priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap; // 初始化所有单节点树 for (int w : weights) { minHeap.push(new HuffmanNode(w)); } // 循环合并最小两树 while (minHeap.size() > 1) { HuffmanNode* left = minHeap.top(); minHeap.pop(); HuffmanNode* right = minHeap.top(); minHeap.pop(); HuffmanNode* parent = new HuffmanNode(left->weight + right->weight); parent->left = left; parent->right = right; minHeap.push(parent); } return minHeap.empty() ? nullptr : minHeap.top(); } // 辅助函数：打印先序遍历结果 void printHuffmanTree(HuffmanNode* root) { if (!root) return; cout << root->weight << " "; printHuffmanTree(root->left); printHuffmanTree(root->right); } int main() { vector<int> weights = {5, 9, 12, 13, 16, 45}; HuffmanNode* root = buildHuffmanTree(weights); cout << "哈夫曼树先序遍历（权值）："; printHuffmanTree(root); // 输出示例：100 45 55 25 12 13 30 14 5 9 16 return 0; }
6. 关键特性总结 特性说明时间复杂度O(n log n)，优先队列操作主导空间复杂度O(n)，存储所有节点唯一性同一权值集合可能有不同形态的哈夫曼树，但WPL一定最小验证方法根节点权值等于初始权值总和，且权重大的节点靠近根
四、红黑树（Red-Black Tree）
1. 什么是红黑树
红黑树是一种自平衡的二叉搜索树（BST），通过颜色属性维护树的平衡性，确保插入、删除、查找的最坏时间复杂度为 O(log n)。
核心性质：
颜色属性：每个节点是红色或黑色。根节点：根节点必须为黑色。叶子节点：所有叶子（NIL节点，空节点）为黑色。红色节点规则：红色节点的子节点必须为黑色（即不能有连续红色节点）。黑高一致：从任意节点到其所有叶子节点的路径上，黑色节点的数量相同。2. 红黑树插入
插入新节点时默认设为红色（避免破坏黑高），可能违反红黑树规则，需通过旋转和颜色调整修复。
插入步骤：
标准BST插入：按二叉搜索树规则插入节点，颜色设为红色。颜色修复： Case 1：父节点是黑色 → 无需调整。Case 2：父节点是红色 → 需要进一步判断叔叔节点颜色： 叔叔为红色：父和叔变黑，祖父变红，递归处理祖父节点。叔叔为黑色或NIL： LL/RR型：单旋转（父节点上升，祖父下沉）。LR/RL型：双旋转（先子节点旋转，再父节点旋转）。示例（插入后修复连续红色冲突）：
#mermaid-svg-R8PIeQDpeJ0LNkmU {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .error-icon{fill:#552222;}#mermaid-svg-R8PIeQDpeJ0LNkmU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-R8PIeQDpeJ0LNkmU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .marker.cross{stroke:#333333;}#mermaid-svg-R8PIeQDpeJ0LNkmU svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .cluster-label text{fill:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .cluster-label span{color:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .label text,#mermaid-svg-R8PIeQDpeJ0LNkmU span{fill:#333;color:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .node rect,#mermaid-svg-R8PIeQDpeJ0LNkmU .node circle,#mermaid-svg-R8PIeQDpeJ0LNkmU .node ellipse,#mermaid-svg-R8PIeQDpeJ0LNkmU .node polygon,#mermaid-svg-R8PIeQDpeJ0LNkmU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .node .label{text-align:center;}#mermaid-svg-R8PIeQDpeJ0LNkmU .node.clickable{cursor:pointer;}#mermaid-svg-R8PIeQDpeJ0LNkmU .arrowheadPath{fill:#333333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-R8PIeQDpeJ0LNkmU .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-R8PIeQDpeJ0LNkmU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-R8PIeQDpeJ0LNkmU .cluster text{fill:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU .cluster span{color:#333;}#mermaid-svg-R8PIeQDpeJ0LNkmU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-R8PIeQDpeJ0LNkmU :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} G:黑 P:红 U:红 新节点:红修复操作：将P和U变黑，G变红，然后以G为起点继续检查。
3. 红黑树删除
删除节点可能导致黑高被破坏，需通过旋转和颜色调整修复。
删除步骤：
标准BST删除：找到待删除节点，若有两个子节点则用后继节点替代。颜色修复： 若删除节点是红色 → 直接删除，无需调整。若删除节点是黑色 → 需从兄弟节点“借”黑色或调整颜色。修复策略（设当前节点为N，父为P，兄弟为S）：
Case 1：S为红色 → 旋转使S变黑，转化为其他情况。Case 2：S为黑色，且S的子节点均为黑色 → S变红，N上移至P递归处理。Case 3：S为黑色，且S的远子节点为红色 → 旋转并重新着色，恢复平衡。Case 4：S为黑色，且S的近子节点为红色 → 旋转调整，转为Case 3。示例（删除黑色节点后的修复）：
#mermaid-svg-Z4JWychd4pAfRzkv {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .error-icon{fill:#552222;}#mermaid-svg-Z4JWychd4pAfRzkv .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Z4JWychd4pAfRzkv .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-Z4JWychd4pAfRzkv .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Z4JWychd4pAfRzkv .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Z4JWychd4pAfRzkv .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Z4JWychd4pAfRzkv .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Z4JWychd4pAfRzkv .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Z4JWychd4pAfRzkv .marker.cross{stroke:#333333;}#mermaid-svg-Z4JWychd4pAfRzkv svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Z4JWychd4pAfRzkv .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .cluster-label text{fill:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .cluster-label span{color:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .label text,#mermaid-svg-Z4JWychd4pAfRzkv span{fill:#333;color:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .node rect,#mermaid-svg-Z4JWychd4pAfRzkv .node circle,#mermaid-svg-Z4JWychd4pAfRzkv .node ellipse,#mermaid-svg-Z4JWychd4pAfRzkv .node polygon,#mermaid-svg-Z4JWychd4pAfRzkv .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Z4JWychd4pAfRzkv .node .label{text-align:center;}#mermaid-svg-Z4JWychd4pAfRzkv .node.clickable{cursor:pointer;}#mermaid-svg-Z4JWychd4pAfRzkv .arrowheadPath{fill:#333333;}#mermaid-svg-Z4JWychd4pAfRzkv .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Z4JWychd4pAfRzkv .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Z4JWychd4pAfRzkv .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-Z4JWychd4pAfRzkv .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-Z4JWychd4pAfRzkv .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Z4JWychd4pAfRzkv .cluster text{fill:#333;}#mermaid-svg-Z4JWychd4pAfRzkv .cluster span{color:#333;}#mermaid-svg-Z4JWychd4pAfRzkv div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Z4JWychd4pAfRzkv :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} P:黑 N:黑 S:红 SL:黑 SR:黑修复操作：旋转使S成为新的父节点，并调整颜色。
4. 红黑树实现 #include <iostream> using namespace std; enum Color { RED, BLACK }; struct Node { int val; Color color; Node* left, * right, * parent; Node(int v) : val(v), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; class RedBlackTree { private: Node* root; Node* nil; // 哨兵节点（代表NIL叶子节点） // 初始化哨兵节点 void initializeNil() { nil = new Node(0); nil->color = BLACK; nil->left = nil->right = nil->parent = nullptr; } // 左旋 void leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left != nil) y->left->parent = x; y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } // 右旋 void rightRotate(Node* x) { Node* y = x->left; x->left = y->right; if (y->right != nil) y->right->parent = x; y->parent = x->parent; if (x->parent == nil) { root = y; } else if (x == x->parent->right) { x->parent->right = y; } else { x->parent->left = y; } y->right = x; x->parent = y; } // 插入修复 void fixInsert(Node* z) { while (z->parent->color == RED) { if (z->parent == z->parent->parent->left) { // 父节点是左孩子 Node* y = z->parent->parent->right; // 叔叔节点 if (y->color == RED) { // Case 1: 叔叔为红 z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->right) { // Case 2: z是右孩子，转Case3 z = z->parent; leftRotate(z); } // Case 3: z是左孩子 z->parent->color = BLACK; z->parent->parent->color = RED; rightRotate(z->parent->parent); } } else { // 对称处理父节点是右孩子的情况 Node* y = z->parent->parent->left; if (y->color == RED) { z->parent->color = BLACK; y->color = BLACK; z->parent->parent->color = RED; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate(z); } z->parent->color = BLACK; z->parent->parent->color = RED; leftRotate(z->parent->parent); } } } root->color = BLACK; } // 删除修复 void fixDelete(Node* x) { while (x != root && x->color == BLACK) { if (x == x->parent->left) { Node* w = x->parent->right; // 兄弟节点 if (w->color == RED) { // Case 1: 兄弟为红 w->color = BLACK; x->parent->color = RED; leftRotate(x->parent); w = x->parent->right; } if (w->left->color == BLACK && w->right->color == BLACK) { // Case 2 w->color = RED; x = x->parent; } else { if (w->right->color == BLACK) { // Case 3: 兄弟的右子为黑 w->left->color = BLACK; w->color = RED; rightRotate(w); w = x->parent->right; } // Case 4: 兄弟的右子为红 w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; leftRotate(x->parent); x = root; } } else { // 对称处理x是右孩子的情况 Node* w = x->parent->left; if (w->color == RED) { w->color = BLACK; x->parent->color = RED; rightRotate(x->parent); w = x->parent->left; } if (w->right->color == BLACK && w->left->color == BLACK) { w->color = RED; x = x->parent; } else { if (w->left->color == BLACK) { w->right->color = BLACK; w->color = RED; leftRotate(w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rightRotate(x->parent); x = root; } } } x->color = BLACK; } // 辅助函数：用v替换u的父节点连接 void transplant(Node* u, Node* v) { if (u->parent == nil) { root = v; } else if (u == u->parent->left) { u->parent->left = v; } else { u->parent->right = v; } v->parent = u->parent; } // 找到最小节点 Node* minimum(Node* node) { while (node->left != nil) { node = node->left; } return node; } public: RedBlackTree() { initializeNil(); root = nil; } // 查找节点 Node* search(int val) { Node* current = root; while (current != nil) { if (val == current->val) return current; else if (val < current->val) current = current->left; else current = current->right; } return nil; } // 插入节点 void insert(int val) { Node* z = new Node(val); Node* y = nil; Node* x = root; while (x != nil) { y = x; if (z->val < x->val) x = x->left; else x = x->right; } z->parent = y; if (y == nil) { root = z; } else if (z->val < y->val) { y->left = z; } else { y->right = z; } z->left = z->right = nil; z->color = RED; fixInsert(z); } // 删除节点 void deleteNode(int val) { Node* z = search(val); if (z == nil) return; Node* y = z; Color yOriginalColor = y->color; Node* x; if (z->left == nil) { x = z->right; transplant(z, z->right); } else if (z->right == nil) { x = z->left; transplant(z, z->left); } else { y = minimum(z->right); yOriginalColor = y->color; x = y->right; if (y->parent == z) { x->parent = y; } else { transplant(y, y->right); y->right = z->right; y->right->parent = y; } transplant(z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } delete z; if (yOriginalColor == BLACK) { fixDelete(x); } } // 中序遍历（测试用） void inorder(Node* node) { if (node != nil) { inorder(node->left); cout << node->val << "(" << (node->color == RED ? "R" : "B") << ") "; inorder(node->right); } } void printTree() { inorder(root); cout << endl; } }; // 测试代码 int main() { RedBlackTree rbt; rbt.insert(10); rbt.insert(20); rbt.insert(5); rbt.insert(15); rbt.insert(25); cout << "插入后: "; rbt.printTree(); rbt.deleteNode(15); cout << "删除15后: "; rbt.printTree(); rbt.deleteNode(10); cout << "删除10后: "; rbt.printTree(); return 0; } 测试用例输出 插入后: 5(B) 10(B) 15(R) 20(B) 25(R) 删除15后: 5(B) 10(B) 20(B) 25(R) 删除10后: 5(B) 20(B) 25(B)
红黑树结构流程图 插入操作后（10,20,5,15,25） 10(B) / \ 5(B) 20(B) / \ 15(R) 25(R) 根节点：10（黑色）20的左子节点：15（红色）20的右子节点：25（红色）所有叶子节点（nil）均为黑色
删除15（红色叶子节点）后 10(B) / \ 5(B) 20(B) \ 25(R) 15被删除，20的右子树仅剩25（红色）无需调整颜色/旋转（删除红色节点不破坏性质）
删除10（根节点）后 20(B) / \ 5(B) 25(B) 根节点替换为20，颜色保持原黑色5和25调整为黑色（保持黑高平衡）
5. 红黑树特性总结 特性说明平衡性通过颜色和旋转规则保证树高近似 log n，避免BST退化成链表时间复杂度插入、删除、查找均为 O(log n)应用场景C++ STL的map/set，Java的TreeMap，数据库索引等与AVL树对比红黑树插入/删除更快（旋转次数少），AVL查询更快（更严格平衡）
五、B,B+,B*树
B树族核心概念对比
特性B树B+树B*树数据存储位置所有节点存储数据仅叶子节点存储数据仅叶子节点存储数据叶子节点链接无有双向链表连接所有叶子节点有双向链表连接所有叶子节点非叶节点键数量m/2 ≤ keys ≤ mm/2 ≤ keys ≤ m(2m-1)/3 ≤ keys ≤ m节点分裂策略直接分裂分裂时向兄弟节点借数据分裂时与兄弟节点共享数据空间利用率约50%约50%约66%适用场景文件系统数据库索引高并发数据库系统 #mermaid-svg-UnM510YxSIqCPRtL {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-UnM510YxSIqCPRtL .error-icon{fill:#552222;}#mermaid-svg-UnM510YxSIqCPRtL .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-UnM510YxSIqCPRtL .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-UnM510YxSIqCPRtL .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-UnM510YxSIqCPRtL .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-UnM510YxSIqCPRtL .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-UnM510YxSIqCPRtL .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-UnM510YxSIqCPRtL .marker{fill:#333333;stroke:#333333;}#mermaid-svg-UnM510YxSIqCPRtL .marker.cross{stroke:#333333;}#mermaid-svg-UnM510YxSIqCPRtL svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-UnM510YxSIqCPRtL .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-UnM510YxSIqCPRtL .cluster-label text{fill:#333;}#mermaid-svg-UnM510YxSIqCPRtL .cluster-label span{color:#333;}#mermaid-svg-UnM510YxSIqCPRtL .label text,#mermaid-svg-UnM510YxSIqCPRtL span{fill:#333;color:#333;}#mermaid-svg-UnM510YxSIqCPRtL .node rect,#mermaid-svg-UnM510YxSIqCPRtL .node circle,#mermaid-svg-UnM510YxSIqCPRtL .node ellipse,#mermaid-svg-UnM510YxSIqCPRtL .node polygon,#mermaid-svg-UnM510YxSIqCPRtL .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-UnM510YxSIqCPRtL .node .label{text-align:center;}#mermaid-svg-UnM510YxSIqCPRtL .node.clickable{cursor:pointer;}#mermaid-svg-UnM510YxSIqCPRtL .arrowheadPath{fill:#333333;}#mermaid-svg-UnM510YxSIqCPRtL .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-UnM510YxSIqCPRtL .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-UnM510YxSIqCPRtL .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-UnM510YxSIqCPRtL .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-UnM510YxSIqCPRtL .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-UnM510YxSIqCPRtL .cluster text{fill:#333;}#mermaid-svg-UnM510YxSIqCPRtL .cluster span{color:#333;}#mermaid-svg-UnM510YxSIqCPRtL div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-UnM510YxSIqCPRtL :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} B*树 子节点1 非叶节点键数下限更高 子节点2 叶子节点存储数据共享键区域 B+树 子节点1 非叶节点仅存储键 子节点2 叶子节点存储数据双向链表连接 叶子节点存储数据双向链表连接 B树 子节点1 非叶节点存储键和数据 子节点2 数据块 数据块 1. B树B树（B-Tree） 是一种自平衡的多路搜索树，广泛应用于数据库和文件系统。其核心特性如下：
#mermaid-svg-df3lYY9NvgOp2diA {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-df3lYY9NvgOp2diA .error-icon{fill:#552222;}#mermaid-svg-df3lYY9NvgOp2diA .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-df3lYY9NvgOp2diA .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-df3lYY9NvgOp2diA .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-df3lYY9NvgOp2diA .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-df3lYY9NvgOp2diA .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-df3lYY9NvgOp2diA .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-df3lYY9NvgOp2diA .marker{fill:#333333;stroke:#333333;}#mermaid-svg-df3lYY9NvgOp2diA .marker.cross{stroke:#333333;}#mermaid-svg-df3lYY9NvgOp2diA svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-df3lYY9NvgOp2diA .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-df3lYY9NvgOp2diA .cluster-label text{fill:#333;}#mermaid-svg-df3lYY9NvgOp2diA .cluster-label span{color:#333;}#mermaid-svg-df3lYY9NvgOp2diA .label text,#mermaid-svg-df3lYY9NvgOp2diA span{fill:#333;color:#333;}#mermaid-svg-df3lYY9NvgOp2diA .node rect,#mermaid-svg-df3lYY9NvgOp2diA .node circle,#mermaid-svg-df3lYY9NvgOp2diA .node ellipse,#mermaid-svg-df3lYY9NvgOp2diA .node polygon,#mermaid-svg-df3lYY9NvgOp2diA .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-df3lYY9NvgOp2diA .node .label{text-align:center;}#mermaid-svg-df3lYY9NvgOp2diA .node.clickable{cursor:pointer;}#mermaid-svg-df3lYY9NvgOp2diA .arrowheadPath{fill:#333333;}#mermaid-svg-df3lYY9NvgOp2diA .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-df3lYY9NvgOp2diA .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-df3lYY9NvgOp2diA .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-df3lYY9NvgOp2diA .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-df3lYY9NvgOp2diA .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-df3lYY9NvgOp2diA .cluster text{fill:#333;}#mermaid-svg-df3lYY9NvgOp2diA .cluster span{color:#333;}#mermaid-svg-df3lYY9NvgOp2diA div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-df3lYY9NvgOp2diA :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 非叶节点键: 20, 40数据: D1, D2 子节点键: 10,15数据: D3,D4 子节点键: 25,30数据: D5,D6 子节点键: 50,60数据: D7,D8 阶数：B树的阶数 m 表示每个节点最多拥有 m 个子节点。键数量：每个节点最多包含：m - 1 个键，最少包含 ⌈m/2⌉ - 1 个键（根节点除外）。平衡性：所有叶子节点位于同一层，保证查询效率稳定。操作：插入和删除可能引发节点分裂或合并，通过递归调整保持平衡。 2. B+树B+树 是B树的变体，优化了范围查询：
#mermaid-svg-ZcqQwOFuoVJxw7V6 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .error-icon{fill:#552222;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .marker.cross{stroke:#333333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .cluster-label text{fill:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .cluster-label span{color:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .label text,#mermaid-svg-ZcqQwOFuoVJxw7V6 span{fill:#333;color:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .node rect,#mermaid-svg-ZcqQwOFuoVJxw7V6 .node circle,#mermaid-svg-ZcqQwOFuoVJxw7V6 .node ellipse,#mermaid-svg-ZcqQwOFuoVJxw7V6 .node polygon,#mermaid-svg-ZcqQwOFuoVJxw7V6 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .node .label{text-align:center;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .node.clickable{cursor:pointer;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .arrowheadPath{fill:#333333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .cluster text{fill:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 .cluster span{color:#333;}#mermaid-svg-ZcqQwOFuoVJxw7V6 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ZcqQwOFuoVJxw7V6 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 双向链表 双向链表 非叶节点键: 20, 40 叶子节点键: 10,15,20数据: D1,D2,D3 叶子节点键: 25,30,40数据: D4,D5,D6 叶子节点键: 50,60,70数据: D7,D8,D9 数据存储：所有数据仅存于叶子节点，内部节点仅存键和子节点指针。链表连接：叶子节点通过指针形成有序链表，便于遍历区间数据。查询特性：查询必须到叶子节点，但内部节点更紧凑，树高更低。 3. B*树B*树 进一步优化空间利用率：
#mermaid-svg-jwMDmZTQHr0ofHdU {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .error-icon{fill:#552222;}#mermaid-svg-jwMDmZTQHr0ofHdU .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-jwMDmZTQHr0ofHdU .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-jwMDmZTQHr0ofHdU .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-jwMDmZTQHr0ofHdU .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-jwMDmZTQHr0ofHdU .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-jwMDmZTQHr0ofHdU .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-jwMDmZTQHr0ofHdU .marker{fill:#333333;stroke:#333333;}#mermaid-svg-jwMDmZTQHr0ofHdU .marker.cross{stroke:#333333;}#mermaid-svg-jwMDmZTQHr0ofHdU svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-jwMDmZTQHr0ofHdU .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .cluster-label text{fill:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .cluster-label span{color:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .label text,#mermaid-svg-jwMDmZTQHr0ofHdU span{fill:#333;color:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .node rect,#mermaid-svg-jwMDmZTQHr0ofHdU .node circle,#mermaid-svg-jwMDmZTQHr0ofHdU .node ellipse,#mermaid-svg-jwMDmZTQHr0ofHdU .node polygon,#mermaid-svg-jwMDmZTQHr0ofHdU .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-jwMDmZTQHr0ofHdU .node .label{text-align:center;}#mermaid-svg-jwMDmZTQHr0ofHdU .node.clickable{cursor:pointer;}#mermaid-svg-jwMDmZTQHr0ofHdU .arrowheadPath{fill:#333333;}#mermaid-svg-jwMDmZTQHr0ofHdU .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-jwMDmZTQHr0ofHdU .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-jwMDmZTQHr0ofHdU .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-jwMDmZTQHr0ofHdU .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-jwMDmZTQHr0ofHdU .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-jwMDmZTQHr0ofHdU .cluster text{fill:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU .cluster span{color:#333;}#mermaid-svg-jwMDmZTQHr0ofHdU div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-jwMDmZTQHr0ofHdU :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 共享键 共享键 节点A键: 10,20,30 子节点B 子节点C 新节点D 节点分裂策略：节点满时，优先将部分键转移至兄弟节点，延迟分裂。填充率：节点最小键数从 ⌈m/2⌉ 提高至 ⌈2m/3⌉，减少空间浪费。 4. B树实现 4. B树的C++实现以下为简化版B树实现（仅插入和查找）：
#include <iostream> using namespace std; class BTree { private: struct Node { int *keys; Node **children; int num_keys; bool is_leaf; int t; // 最小度数 Node(int degree, bool leaf) : t(degree), is_leaf(leaf), num_keys(0) { keys = new int[2 * t - 1]; children = new Node*[2 * t](); } ~Node() { delete[] keys; for (int i = 0; i <= 2 * t; ++i) delete children[i]; delete[] children; } }; Node *root; int t; // 最小度数 void splitChild(Node *parent, int idx) { Node *fullChild = parent->children[idx]; Node *newChild = new Node(t, fullChild->is_leaf); newChild->num_keys = t - 1; // 复制后t-1个键和子节点 for (int i = 0; i < t - 1; ++i) newChild->keys[i] = fullChild->keys[i + t]; if (!fullChild->is_leaf) for (int i = 0; i < t; ++i) newChild->children[i] = fullChild->children[i + t]; fullChild->num_keys = t - 1; // 调整父节点 for (int i = parent->num_keys; i > idx; --i) parent->keys[i] = parent->keys[i - 1]; for (int i = parent->num_keys + 1; i > idx + 1; --i) parent->children[i] = parent->children[i - 1]; parent->keys[idx] = fullChild->keys[t - 1]; parent->children[idx + 1] = newChild; parent->num_keys++; } void insertNonFull(Node *node, int key) { int i = node->num_keys - 1; if (node->is_leaf) { while (i >= 0 && key < node->keys[i]) { node->keys[i + 1] = node->keys[i]; i--; } node->keys[i + 1] = key; node->num_keys++; } else { while (i >= 0 && key < node->keys[i]) i--; i++; if (node->children[i]->num_keys == 2 * t - 1) { splitChild(node, i); if (key > node->keys[i]) i++; } insertNonFull(node->children[i], key); } } public: BTree(int degree) : t(degree), root(nullptr) {} void insert(int key) { if (!root) { root = new Node(t, true); root->keys[0] = key; root->num_keys = 1; } else { if (root->num_keys == 2 * t - 1) { Node *newRoot = new Node(t, false); newRoot->children[0] = root; splitChild(newRoot, 0); root = newRoot; } insertNonFull(root, key); } } bool search(int key) { return search(root, key); } bool search(Node *node, int key) { if (!node) return false; int i = 0; while (i < node->num_keys && key > node->keys[i]) i++; if (i < node->num_keys && key == node->keys[i]) return true; return node->is_leaf ? false : search(node->children[i], key); } }; int main() { BTree t(3); // 最小度数t=3 t.insert(10); t.insert(20); t.insert(5); t.insert(6); t.insert(12); cout << (t.search(6) ? "Found" : "Not Found") << endl; // Found cout << (t.search(15) ? "Found" : "Not Found") << endl; // Not Found return 0; }代码解析：
节点结构：每个节点包含键数组、子节点指针数组、键数量及叶子标记。插入逻辑：根节点满时先分裂，确保插入始终从非满节点开始。分裂操作：满子节点分裂为二，中间键提升至父节点。查找逻辑：递归遍历节点，逐层比较键值。数据结构之BST、AVL、红黑树、哈夫曼树与B族树由讯客互联开源代码栏目发布，感谢您对讯客互联的认可，以及对我们原创作品以及文章的青睐，非常欢迎各位朋友分享到个人网站或者朋友圈，但转载请说明文章出处“数据结构之BST、AVL、红黑树、哈夫曼树与B族树”
