数据结构之BST、AVL、红黑树、哈夫曼树与B族树

数据结构之BST、AVL、红黑树、哈夫曼树与B族树

---

一、二叉搜索树（Binary Search Tree, BST）

---

1. 什么是二叉搜索树？

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树数据结构，其中每个节点的值都大于其左子树中的任何节点的值，且小于其右子树中的任何节点的值。它的特点使得在搜索、插入和删除操作上具有高效性。

二叉搜索树是一种具有以下特性的二叉树：

• 有序性：
  • 左子树所有节点值 < 根节点值
  • 右子树所有节点值 > 根节点值
• 递归性：左右子树也必须是二叉搜索树
• 中序遍历结果是有序序列

重要性质

特性	说明
查找效率	平均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;  // truecout << "Contains 5: " << boolalpha << tree.contains(5) << endl;  // false// 删除测试tree.remove(6);cout << "After delete 6, contains 6: " << tree.contains(6) << endl; // falsecout << "Now contains 4: " << tree.contains(4) << endl; // truereturn 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. 失衡检测流程

---

3、旋转操作详解

1. LL型失衡（单右旋）

结构特征

• 新节点插入在左子树的左子树中
• 失衡节点的平衡因子为 +2，其左子节点的平衡因子为 +1

文字示意图

    A (BF=+2)       → 右旋 →      B/                             / \B (BF=+1)                     C   A/
C (新插入节点)

操作步骤

1. 将失衡节点 A 的左子节点 B 提升为新根
2. 原根节点 A 成为 B 的右子节点
3. 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

关键步骤

1. 先对失衡节点的左子节点 B 执行左旋（转换为 LL 型）
2. 再对根节点 A 执行右旋

---

4. RL型失衡（先右旋后左旋）

结构特征

• 新节点插入在右子树的左子树中
• 失衡节点的平衡因子为 -2，其右子节点的平衡因子为 +1

文字示意图

A (BF=-2)           → 对 B 右旋 →   A (BF=-2)    → 对 A 左旋 →     C\                                   \                           / \B (BF=+1)                           C                         A   B/                                     \
C (新插入节点)                           B

操作要点

1. 先对失衡节点的右子节点 B 执行右旋（转换为 RR 型）
2. 再对根节点 A 执行左旋

---

4、完整插入流程

---

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);elsereturn 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 30 

---

7、典型应用场景

1. 数据库索引：MySQL的MEMORY存储引擎
2. 文件系统：Windows NT内核的地址空间管理
3. 内存受限系统：嵌入式设备的快速查询
4. 3D图形计算：场景图的空间划分管理

---

三、哈夫曼树（Huffman Tree）

---

1. 哈夫曼树定义

哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度（WPL, Weighted Path Length）最短的二叉树。

其特点是：

• 带权路径最小：叶子节点的权值（如字符频率）乘以路径长度（根到叶子的边数）的总和最小。

• 应用场景：广泛用于数据压缩，如哈夫曼编码，通过为高频字符分配短编码、低频字符分配长编码，减少整体数据量。

• 核心特性：权重越大的叶子节点距离根节点越近。

• 核心应用：数据压缩（哈夫曼编码）、文件编码、加密算法等。

---

2. 哈夫曼树构建过程

以权值集合 {5, 9, 12, 13, 16, 45} 为例：

1. 初始化森林

   将每个权值视为独立的单节点树，组成森林：
   [5], [9], [12], [13], [16], [45]

2. 合并最小两子树

   • 第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。

3. 验证特性

   • WPL计算：(5+9)*3 + (12+13+16)*2 + 45*1 = 146
   • 权重越大越靠近根：最大权值 45 直接作为根的子节点。

---

3. 树结构流程图

流程图说明：

1. 根节点权值为 100（所有原始权值之和：5+9+12+13+16+45）。
2. 叶子节点为原始权值，内部节点为合并生成的权值。
3. 路径关系：父节点到子节点的连接体现合并顺序。

---

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 16return 0;
}

---

6. 关键特性总结

特性	说明
时间复杂度	O(n log n)，优先队列操作主导
空间复杂度	O(n)，存储所有节点
唯一性	同一权值集合可能有不同形态的哈夫曼树，但WPL一定最小
验证方法	根节点权值等于初始权值总和，且权重大的节点靠近根

---

---

四、红黑树（Red-Black Tree）

---

1. 什么是红黑树

红黑树是一种自平衡的二叉搜索树（BST），通过颜色属性维护树的平衡性，确保插入、删除、查找的最坏时间复杂度为 O(log n)。

核心性质：

1. 颜色属性：每个节点是红色或黑色。
2. 根节点：根节点必须为黑色。
3. 叶子节点：所有叶子（NIL节点，空节点）为黑色。
4. 红色节点规则：红色节点的子节点必须为黑色（即不能有连续红色节点）。
5. 黑高一致：从任意节点到其所有叶子节点的路径上，黑色节点的数量相同。

---

2. 红黑树插入

插入新节点时默认设为红色（避免破坏黑高），可能违反红黑树规则，需通过旋转和颜色调整修复。

插入步骤：

1. 标准BST插入：按二叉搜索树规则插入节点，颜色设为红色。
2. 颜色修复：
   • Case 1：父节点是黑色 → 无需调整。
   • Case 2：父节点是红色 → 需要进一步判断叔叔节点颜色：
     • 叔叔为红色：父和叔变黑，祖父变红，递归处理祖父节点。
     • 叔叔为黑色或NIL：
       • LL/RR型：单旋转（父节点上升，祖父下沉）。
       • LR/RL型：双旋转（先子节点旋转，再父节点旋转）。

示例（插入后修复连续红色冲突）：

修复操作：将P和U变黑，G变红，然后以G为起点继续检查。

---

3. 红黑树删除

删除节点可能导致黑高被破坏，需通过旋转和颜色调整修复。

删除步骤：

1. 标准BST删除：找到待删除节点，若有两个子节点则用后继节点替代。
2. 颜色修复：
   • 若删除节点是红色 → 直接删除，无需调整。
   • 若删除节点是黑色 → 需从兄弟节点“借”黑色或调整颜色。

修复策略（设当前节点为N，父为P，兄弟为S）：

• Case 1：S为红色 → 旋转使S变黑，转化为其他情况。
• Case 2：S为黑色，且S的子节点均为黑色 → S变红，N上移至P递归处理。
• Case 3：S为黑色，且S的远子节点为红色 → 旋转并重新着色，恢复平衡。
• Case 4：S为黑色，且S的近子节点为红色 → 旋转调整，转为Case 3。

示例（删除黑色节点后的修复）：

修复操作：旋转使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是右孩子，转Case3z = 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 2w->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)

---

红黑树结构流程图

1. 插入操作后（10,20,5,15,25）

        10(B)/     \5(B)     20(B)/     \15(R)   25(R)

• 根节点：10（黑色）
• 20的左子节点：15（红色）
• 20的右子节点：25（红色）
• 所有叶子节点（nil）均为黑色

---

2. 删除15（红色叶子节点）后

        10(B)/     \5(B)     20(B)\25(R)

• 15被删除，20的右子树仅剩25（红色）
• 无需调整颜色/旋转（删除红色节点不破坏性质）

---

3. 删除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 ≤ m	m/2 ≤ keys ≤ m	(2m-1)/3 ≤ keys ≤ m
节点分裂策略	直接分裂	分裂时向兄弟节点借数据	分裂时与兄弟节点共享数据
空间利用率	约50%	约50%	约66%
适用场景	文件系统	数据库索引	高并发数据库系统

1. B树

B树（B-Tree） 是一种自平衡的多路搜索树，广泛应用于数据库和文件系统。其核心特性如下：

• 阶数：B树的阶数 m 表示每个节点最多拥有 m 个子节点。
• 键数量：每个节点最多包含：m - 1 个键，最少包含 ⌈m/2⌉ - 1 个键（根节点除外）。
• 平衡性：所有叶子节点位于同一层，保证查询效率稳定。
• 操作：插入和删除可能引发节点分裂或合并，通过递归调整保持平衡。

2. B+树

B+树 是B树的变体，优化了范围查询：

• 数据存储：所有数据仅存于叶子节点，内部节点仅存键和子节点指针。
• 链表连接：叶子节点通过指针形成有序链表，便于遍历区间数据。
• 查询特性：查询必须到叶子节点，但内部节点更紧凑，树高更低。

3. B*树

B*树 进一步优化空间利用率：

• 节点分裂策略：节点满时，优先将部分键转移至兄弟节点，延迟分裂。
• 填充率：节点最小键数从 ⌈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=3t.insert(10);t.insert(20);t.insert(5);t.insert(6);t.insert(12);cout << (t.search(6) ? "Found" : "Not Found") << endl; // Foundcout << (t.search(15) ? "Found" : "Not Found") << endl; // Not Foundreturn 0;
}

代码解析：

• 节点结构：每个节点包含键数组、子节点指针数组、键数量及叶子标记。
• 插入逻辑：根节点满时先分裂，确保插入始终从非满节点开始。
• 分裂操作：满子节点分裂为二，中间键提升至父节点。
• 查找逻辑：递归遍历节点，逐层比较键值。