数据结构之BST、AVL、红黑树、哈夫曼树与B族树
数据结构之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)是一种特殊的二叉树数据结构,其中每个节点的值都大于其左子树中的任何节点的值,且小于其右子树中的任何节点的值。它的特点使得在搜索、插入和删除操作上具有高效性。
二叉搜索树是一种具有以下特性的二叉树:
- 有序性:
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 递归性:左右子树也必须是二叉搜索树
- 中序遍历结果是有序序列
重要性质
特性 | 说明 |
---|---|
查找效率 | 平均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. 失衡检测流程
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、完整插入流程
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 30
7、典型应用场景
- 数据库索引: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
。
- 第1次合并:选择最小权值
-
验证特性
- WPL计算:
(5+9)*3 + (12+13+16)*2 + 45*1 = 146
- 权重越大越靠近根:最大权值
45
直接作为根的子节点。
- WPL计算:
3. 树结构流程图
流程图说明:
- 根节点权值为
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型:双旋转(先子节点旋转,再父节点旋转)。
示例(插入后修复连续红色冲突):
修复操作:将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。
示例(删除黑色节点后的修复):
修复操作:旋转使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 ≤ 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=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;
}
代码解析:
- 节点结构:每个节点包含键数组、子节点指针数组、键数量及叶子标记。
- 插入逻辑:根节点满时先分裂,确保插入始终从非满节点开始。
- 分裂操作:满子节点分裂为二,中间键提升至父节点。
- 查找逻辑:递归遍历节点,逐层比较键值。