高级树 | 自在学高级树
在之前的学习中，我们认识了二叉树这一基础数据结构，它通过层次化的节点组织方式为我们提供了高效的数据管理能力。然而，普通的二叉搜索树存在一个严重的性能问题：树的不平衡性。
当我们将有序序列（如 1, 2, 3, 4, 5...）依次插入一个标准的二叉搜索树时，树会退化为线性链表结构。这种退化导致树的高度从理想的 ⌈log2(n+1)⌉ 增长到 n，使得查找、插入和删除操作的时间复杂度从最优的 O(logn) 恶化到最坏的 O(n)，完全丧失了二叉搜索树的分治优势。
为了解决这一根本性问题，计算机科学家们设计了一系列自平衡二叉搜索树（Self-Balancing Binary Search Trees）。这些数据结构通过维护特定的结构不变性（structural invariants），在每次插入或删除操作后自动进行结构调整，确保树的高度始终保持在 O(logn) 的量级，从而保证所有基本操作的时间复杂度为 O(logn)。
这节课，我们将系统学习四种重要的自平衡树结构：二叉搜索树（作为基础）、AVL树、红黑树和B-树，深入理解它们的设计原理、平衡维护机制以及在不同应用场景下的性能特征。
二叉搜索树 (Binary Search Tree, BST)
在学习自平衡树结构之前，我们需要深入理解二叉搜索树（BST）这一基础数据结构。虽然BST本身不具备自平衡能力，但它所遵循的BST不变性（BST Invariant） 是所有自平衡树结构的理论基础。
BST 不变性定义
二叉搜索树必须满足以下BST不变性：
对于树中的任意节点 v，设其存储的键值为 k(v)，则：
- 左子树不变性：对于 v 的左子树中的任意节点 u，有 k(u)<k(v)
- 右子树不变性：对于 v 的右子树中的任意节点 w，有
这一不变性确保了BST具有有序性（ordering property），使得我们可以通过比较操作在树中进行高效的二分查找。
BST不变性赋予了树结构高效的查找能力。查找算法从根节点开始，通过比较目标键值与当前节点键值的大小关系，决定向左子树或右子树递归搜索。每一步比较都能排除掉一半的搜索空间，这与二分查找算法的思想完全一致。在平衡的BST中，查找操作的时间复杂度为 O(logn)，其中 n 为树中节点的数量。
BST 的 C++ 实现
下面我们给出一个完整的、生产级别的BST实现，包含错误处理、内存管理和完整的接口设计。
#include <iostream>
#include <functional>
#include <stdexcept>
#include <algorithm>
/**
* BST节点结构
* @tparam T 节点存储的数据类型，必须支持比较操作（<, >, ==）
*/
template <typename T>
struct Node {
T data; // 节点存储的键值
Node* left; // 左子树指针
Node* right; // 右子树指针
explicit Node(const
删除操作的算法分析
删除操作是BST中最复杂的操作，需要维护BST不变性。删除算法根据目标节点的子节点数量分为三种情况：
情况1：叶子节点删除
当目标节点 v 没有子节点时，直接将其从父节点中移除并释放内存。时间复杂度为 O(1)。
情况2：单子节点删除
当目标节点 v 只有一个子节点时，用其唯一的子节点替换 v 的位置。这一操作保持BST不变性，因为 v 的子节点必然满足BST性质。时间复杂度为 O(1)。
情况3：双子节点删除
当目标节点 v 有两个子节点时，算法采用中序后继替换策略：
- 在 v 的右子树中找到最小节点 s（中序后继），满足 s=min{u∈right(v)}
- 将 s 的键值复制到 v：
这一策略的正确性基于以下事实：
- 中序后继 s 是右子树中的最小节点，因此 s 最多只有一个右子节点
- 用 s 的值替换 v 的值后，BST不变性仍然成立
- 删除 s 的问题转化为情况1或情况2，可以高效处理
时间复杂度为 O(h)，其中 h 为树高。
二叉搜索树演示
AVL树：严格平衡的自平衡二叉搜索树
AVL树（Adelson-Velsky和Landis树）是最早被提出的自平衡二叉搜索树，由G. M. Adelson-Velsky和E. M. Landis在1962年发明。AVL树通过维护严格的平衡条件，确保树的高度始终为 O(logn)。
AVL树的平衡条件
AVL树要求对于树中的任意节点 v，其**平衡因子（Balance Factor）**的绝对值不超过1。平衡因子定义为：
BF(v)=h(left(v))−h(right(v))
其中 h(⋅) 表示子树的高度。因此，AVL树的平衡条件为：
∣BF(v)∣≤1,∀v∈V
这一条件确保了AVL树的高度上界。设 Nh 表示高度为 h 的AVL树的最少节点数，则有递推关系：
Nh=Nh−1+Nh−2+
其中 N0=1，N1=2。这一递推关系与斐波那契数列相关，可以证明 h，因此AVL树的高度为 。
平衡维护机制 - 旋转操作
当插入或删除操作导致某个节点的平衡因子变为 −2 或 +2 时，AVL树通过**旋转操作（Rotation）**来恢复平衡。旋转操作在保持BST不变性的同时，调整树的结构以降低高度。
旋转操作的类型与实现
旋转操作是AVL树平衡维护的核心机制。根据不平衡节点的子节点结构，存在四种不平衡情况，对应不同的旋转策略：
1. 左-左（LL）不平衡：右旋转（Right Rotation）
当节点 v 的平衡因子为 +2，且其左子节点 u 的平衡因子为 +1 或 0 时，发生LL不平衡。此时左子树过高，需要执行右旋转。
设 u=left(v)，T1、T2、 分别为 的左子树、 的右子树和 的右子树。右旋转操作将 提升为新的根节点， 成为 的右子节点， 成为 的左子树。旋转后，树的高度降低1，平衡因子得到修正。
2. 右-右（RR）不平衡：左旋转（Left Rotation）
当节点 v 的平衡因子为 −2，且其右子节点 w 的平衡因子为 −1 或 0 时，发生RR不平衡。此时右子树过高，需要执行左旋转。
设 w=right(v)，T1、T2、 分别为 的左子树、 的左子树和 的右子树。左旋转操作将 提升为新的根节点， 成为 的左子节点， 成为 的右子树。
3. 左-右（LR）不平衡：先左旋子树，再右旋根节点
当节点 v 的平衡因子为 +2，但其左子节点 u 的平衡因子为 −1 时，发生LR不平衡。此时左子树的右子树过高，需要执行双旋转。
首先对 u 执行左旋转，将LR不平衡转化为LL不平衡。然后对 v 执行右旋转，恢复平衡。两次旋转的时间复杂度均为 O(1)，总时间复杂度为 O(1)。
4. 右-左（RL）不平衡：先右旋子树，再左旋根节点
当节点 v 的平衡因子为 −2，但其右子节点 w 的平衡因子为 +1 时，发生RL不平衡。此时右子树的左子树过高，需要执行双旋转。
首先对 w 执行右旋转，将RL不平衡转化为RR不平衡。然后对 v 执行左旋转，恢复平衡。
旋转操作保证了AVL树在每次插入或删除后都能恢复平衡，从而维持 O(logn) 的高度。虽然严格的平衡条件使得插入和删除操作可能需要 O(logn) 次旋转，但查询操作始终保持在 O(logn) 的时间复杂度，且常数因子较小。
AVL树的C++实现
#include <iostream>
#include <algorithm>
#include <stdexcept>
/**
* AVL树节点结构
*/
struct AVLNode {
int data; // 节点存储的键值
int height; // 节点的高度（用于计算平衡因子）
AVLNode* left; // 左子树指针
AVLNode* right; // 右子树指针
explicit AVLNode(int val)
: data(val),
AVL树可视化
红黑树
红黑树是一种近似平衡的二叉搜索树，由Rudolf Bayer在1972年发明。与AVL树的严格平衡策略不同，红黑树采用放宽的平衡条件，通过颜色属性和结构约束来维持树的平衡性。这种设计使得红黑树在修改密集型应用场景中具有更好的性能表现。
红黑树的高度上界
红黑树通过约束确保最长路径长度不超过最短路径长度的2倍。设 h 为树的高度，bh 为从根节点到任意叶节点的黑高（black height）（即路径上黑色节点的数量），则有：
bh≥⌈h/2⌉
由于黑高的一致性，可以证明红黑树的高度满足：
h≤2log2(n+1)
因此，红黑树的所有基本操作时间复杂度为 O(logn)，虽然常数因子略大于AVL树，但修改操作的摊销成本更低。
红黑树的性质定义
红黑树必须满足以下五个不变性质（Invariant Properties）：
- 节点着色：每个节点要么是红色，要么是黑色。
- 根节点约束：根节点必须是黑色。
- 叶节点约束：所有NIL节点（外部节点）为黑色。
- 红色节点约束：红色节点的子节点必须是黑色。
- 黑高一致性：从任意节点到其后代叶节点的简单路径上，黑色节点数量相同。
红黑树结构示例
平衡维护机制
红黑树通过重新着色（Recoloring） 和旋转操作（Rotation） 来维护五个不变性质。当插入或删除操作违反红黑树性质时，算法通过以下策略修复：
插入修复策略：
插入操作将新节点着色为红色（保持性质5），然后通过以下情况修复可能的违反：
-
情况1：父节点和叔节点均为红色
将父节点和叔节点着色为黑色，祖父节点着色为红色，然后递归向上检查。
-
情况2：父节点为红色，叔节点为黑色，且新节点与父节点方向不一致
通过旋转将情况转化为情况3。
-
情况3：父节点为红色，叔节点为黑色，且新节点与父节点方向一致
将父节点着色为黑色，祖父节点着色为红色，然后执行旋转。
删除修复策略：
删除操作可能引入双重黑色节点，通过重新着色和旋转逐步向上修复，最多需要 O(logn) 次操作。
旋转操作与AVL树类似，但需要同时调整节点颜色以维护红黑树性质。
性能分析与应用场景
时间复杂度分析：
- 查找操作：O(logn)，由树高上界 h≤2log2(n+1) 保证
- 插入操作：，最多需要 次重新着色和最多2次旋转
空间复杂度： O(n)，每个节点需要额外的1位存储颜色信息。
实际应用：
- C++ STL：
std::map、std::set、std::multimap、std::multiset 的底层实现
- Java 集合框架：
TreeMap、TreeSet 的实现
- Linux 内核：完全公平调度器（CFS）的运行队列、虚拟内存管理
- 数据库系统：某些内存索引结构、B+树的内部节点实现
工程价值：
红黑树在插入/删除密集型场景下表现优异。虽然其查找性能的常数因子略大于AVL树，但其修改操作的摊销成本更低，且实现相对简单，这使得它成为许多实际系统中平衡二叉搜索树的首选实现。
红黑树的C++实现
#include <iostream>
#include <functional>
#include <stdexcept>
/**
* 节点颜色枚举
*/
enum class Color { RED, BLACK };
/**
* 红黑树节点结构
*/
struct RBNode {
int data; // 节点存储的键值
Color color; // 节点颜色
RBNode* left; // 左子树指针
RBNode* right; // 右子树指针
B-树
前面讨论的BST、AVL树和红黑树都是内存数据结构，假设所有数据都存储在快速访问的内存中。然而，当数据规模达到TB甚至PB级别时，数据必须存储在外部存储设备（如磁盘） 中。
磁盘I/O的性能瓶颈
磁盘访问与内存访问存在数量级的性能差异：
- 内存访问延迟：约 100 纳秒
- 磁盘访问延迟：约 10 毫秒（包括寻道时间、旋转延迟和传输时间）
这意味着一次磁盘I/O操作的时间相当于约 105 次内存访问。因此，对于外部存储数据结构，优化目标从减少比较次数转变为最小化磁盘I/O次数。
B-树的设计原理
B-树（Bayer和McCreight，1972）是一种专为外部存储设计的多路平衡搜索树。与二叉搜索树不同，B-树的每个节点可以存储多个键值和多个子节点指针，这种设计使得B-树具有以下特征：
- 高分支因子（High Branching Factor）：每个内部节点有 t 到 2t 个子节点，其中 t≥2 称为B-树的最小度数（minimum degree）
- 低树高（Low Height）：由于高分支因子，B-树的高度被极大压缩。对于存储 n 个键的B-树，其高度 h 满足：
h≤logt2n+1
对于典型的 t=256 的B-树，即使存储 109 条记录，树高也仅为 3-4 层。这意味着查找任意记录最多只需要 3-4 次磁盘I/O操作。
- 节点大小优化：B-树节点的大小通常设计为磁盘页大小（如4KB），使得每次磁盘读取都能获取最大量的决策信息。
B-树的结构定义
B-树必须满足以下性质：
- 节点键值数量：每个节点最多存储 2t−1 个键，最少存储 t−1 个键（根节点除外，根节点至少1个键）
- 节点子节点数量：每个内部节点最多有 2t 个子节点，最少有 t 个子节点（根节点除外）
- 有序性：节点内的键值按升序排列
- BST性质：对于节点中的键 k，其左子树的所有键小于 ，右子树的所有键大于
B-树的操作策略
查找操作：
从根节点开始，在节点内使用二分查找定位键值范围，然后递归进入相应的子节点。由于节点大小与磁盘页匹配，每次磁盘读取都能获取大量键值信息，从而最小化磁盘I/O次数。
插入操作：
采用自顶向下分裂策略：在向下遍历路径中，如果遇到满节点（2t−1 个键），先进行分裂，然后再继续插入。这确保了插入路径上的所有节点都有空间，避免了回溯操作。
删除操作：
删除操作需要处理节点键值数量不足的情况，可能涉及键值合并和重新分配，但保证最多需要 O(logtn) 次磁盘I/O。
B-树的应用
B-树及其变体（如B+树）是现代数据库系统和文件系统的核心数据结构：
- 关系型数据库：MySQL、PostgreSQL、Oracle等使用B+树作为索引结构
- 文件系统：NTFS、ext4等使用B-树变体管理文件元数据
- NoSQL数据库：MongoDB、CouchDB等使用B-树管理文档索引
B-树通过优化磁盘I/O模式，使得大规模数据管理成为可能，是现代数据系统的基石。
B-树的C++实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>
/**
* B-树节点类
*
* 节点约束：
* - 最多存储 2t-1 个键（根节点除外）
* - 最多有 2t 个子节点
* - 内部节点至少有 t 个子节点（根节点除外）
*/
class BTreeNode {
public:
std::vector<int> keys; // 键值数组（有序）
std::vector<BTreeNode*> children; // 子节点指针数组
bool isLeaf; // 是否为叶子节点
数据结构选择指南
在实际应用中，选择合适的树结构需要综合考虑数据规模、访问模式、存储介质和性能要求。下面我们系统分析各种树结构的适用场景。
二叉搜索树的适用场景 (BST)
适用场景：
- 教学和原型开发
- 数据规模小（< 1000 个元素）
- 数据插入顺序随机
- 对性能要求不严格的场景
局限性：
- 最坏情况时间复杂度为 O(n)（退化为链表）
- 不适合生产环境
结论： BST主要用于理解树结构的基本原理，不推荐用于生产环境。
AVL树的适用场景
适用场景：
- 读密集型应用：查询操作远多于插入和删除
- 对查询性能要求极高的场景
- 数据规模中等（内存可容纳）
- 需要保证最坏情况性能的场景
性能特征：
- 查询性能最优（树高最小，常数因子小）
- 插入/删除操作可能需要 O(logn) 次旋转
- 适合静态或半静态数据集
实际应用： 某些数据库索引、内存中的有序集合（当查询频率远高于修改频率时）
红黑树的适用场景
适用场景：
- 修改密集型应用：插入和删除操作频繁
- 需要平衡的读写性能
- 通用目的的有序数据结构
- 标准库实现（如C++ STL、Java集合框架）
性能特征：
- 查询性能略逊于AVL树（树高上界为 2log2(n+1)）
- 插入/删除操作的摊销成本更低
- 实现相对简单，维护成本低
实际应用： std::map、std::set、TreeMap、TreeSet、Linux内核调度器
B-树的适用场景
适用场景：
- 外部存储数据结构：数据存储在磁盘上
- 大规模数据管理（TB级及以上）
- 数据库索引和文件系统
- 需要最小化磁盘I/O的场景
性能特征：
- 通过高分支因子最小化磁盘I/O次数
- 节点大小匹配磁盘页大小（如4KB）
- 树高极低（即使存储 109 条记录，树高也仅为3-4层）
实际应用： MySQL、PostgreSQL、Oracle等数据库的索引，NTFS、ext4等文件系统
选择决策树
总结：
- 内存小规模数据 + 读多写少 → AVL树
- 内存小规模数据 + 读写平衡 → 红黑树（推荐）
- 磁盘大规模数据 → B-树或B+树
- 教学和原型 → BST（仅用于理解）
小练习
- 在一个AVL树中，节点v的左子树高度为3，右子树高度为4，平衡因子BF(v)是多少？
- 在红黑树中，如果节点v为红色，其父节点p(v)也为红色，这违反了哪条性质？
k(w)>k(v)
递归性：v 的每个子节点及其所有后代节点都必须递归地满足上述不变性 T
&
val
) :
data
(val),
left
(
nullptr
),
right
(
nullptr
) {}
};
/**
* 二叉搜索树实现
* @tparam T 元素类型，必须支持比较操作
*
* 时间复杂度：
* - 查找：O(h)，其中 h 为树高，最坏情况 O(n)，最好情况 O(log n)
* - 插入：O(h)
* - 删除：O(h)
*
* 空间复杂度：O(n) 用于存储节点
*/
template <typename T>
class BST {
private:
Node<T>* root; // 根节点指针
/**
* 递归插入节点
* @param node 当前子树根节点
* @param value 要插入的值
* @return 更新后的子树根节点
* @throws std::bad_alloc 当内存分配失败时
*/
Node<T>* insertRecursive(Node<T>* node, const T& value) {
if (node == nullptr) {
return new Node<T>(value);
}
if (value < node->data) {
node->left = insertRecursive(node->left, value);
} else if (value > node->data) {
node->right = insertRecursive(node->right, value);
}
// 如果 value == node->data，不插入重复值，保持BST的唯一性
return node;
}
/**
* 递归搜索节点
* @param node 当前子树根节点
* @param value 要搜索的值
* @return 如果找到返回 true，否则返回 false
*/
bool searchRecursive(const Node<T>* node, const T& value) const {
if (node == nullptr) {
return false;
}
if (value == node->data) {
return true;
}
return value < node->data
? searchRecursive(node->left, value)
: searchRecursive(node->right, value);
}
/**
* 查找子树中的最小节点（中序后继的前驱）
* @param node 子树根节点
* @return 最小节点的指针，如果子树为空返回 nullptr
*/
Node<T>* findMin(Node<T>* node) const {
if (node == nullptr) {
return nullptr;
}
while (node->left != nullptr) {
node = node->left;
}
return node;
}
/**
* 查找子树中的最大节点
* @param node 子树根节点
* @return 最大节点的指针，如果子树为空返回 nullptr
*/
Node<T>* findMax(Node<T>* node) const {
if (node == nullptr) {
return nullptr;
}
while (node->right != nullptr) {
node = node->right;
}
return node;
}
/**
* 递归删除节点
* @param node 当前子树根节点
* @param value 要删除的值
* @return 更新后的子树根节点
*
* 删除策略：
* 1. 叶子节点或单子节点：直接用子节点替换
* 2. 双子节点：用中序后继的值替换，然后递归删除中序后继节点
*/
Node<T>* removeRecursive(Node<T>* node, const T& value) {
if (node == nullptr) {
return nullptr; // 未找到要删除的节点
}
// 定位要删除的节点
if (value < node->data) {
node->left = removeRecursive(node->left, value);
} else if (value > node->data) {
node->right = removeRecursive(node->right, value);
} else {
// 找到要删除的节点
// 情况1：左子树为空
if (node->left == nullptr) {
Node<T>* temp = node->right;
delete node;
return temp;
}
// 情况2：右子树为空
else if (node->right == nullptr) {
Node<T>* temp = node->left;
delete node;
return temp;
}
// 情况3：左右子树均非空
else {
// 找到右子树中的最小节点（中序后继）
Node<T>* successor = findMin(node->right);
// 用中序后继的值替换当前节点的值
node->data = successor->data;
// 递归删除中序后继节点（该节点最多只有一个右子节点）
node->right = removeRecursive(node->right, successor->data);
}
}
return node;
}
/**
* 后序遍历释放所有节点内存
* @param node 当前子树根节点
*/
void destroyRecursive(Node<T>* node) {
if (node != nullptr) {
destroyRecursive(node->left);
destroyRecursive(node->right);
delete node;
}
}
/**
* 中序遍历，按升序访问所有节点
* @param node 当前子树根节点
* @param visit 访问函数，对每个节点调用 visit(node->data)
*/
void inorderRecursive(const Node<T>* node, std::function<void(const T&)> visit) const {
if (node != nullptr) {
inorderRecursive(node->left, visit);
visit(node->data);
inorderRecursive(node->right, visit);
}
}
/**
* 计算树的高度
* @param node 当前子树根节点
* @return 树的高度（空树高度为0）
*/
int getHeight(const Node<T>* node) const {
if (node == nullptr) {
return 0;
}
return 1 + std::max(getHeight(node->left), getHeight(node->right));
}
/**
* 验证BST不变性
* @param node 当前子树根节点
* @param minVal 允许的最小值（用于验证）
* @param maxVal 允许的最大值（用于验证）
* @return 如果满足BST性质返回 true
*/
bool isValidBST(const Node<T>* node, const T* minVal, const T* maxVal) const {
if (node == nullptr) {
return true;
}
if ((minVal != nullptr && node->data <= *minVal) ||
(maxVal != nullptr && node->data >= *maxVal)) {
return false;
}
return isValidBST(node->left, minVal, &node->data) &&
isValidBST(node->right, &node->data, maxVal);
}
// 禁用拷贝构造和赋值操作（简化实现，生产环境应实现深拷贝）
BST(const BST&) = delete;
BST& operator=(const BST&) = delete;
public:
/**
* 构造函数：创建空BST
*/
BST() : root(nullptr) {}
/**
* 析构函数：释放所有节点内存
*/
~BST() {
destroyRecursive(root);
}
/**
* 插入元素
* @param value 要插入的值
* @throws std::bad_alloc 当内存分配失败时
*/
void insert(const T& value) {
root = insertRecursive(root, value);
}
/**
* 查找元素
* @param value 要查找的值
* @return 如果找到返回 true，否则返回 false
*/
bool search(const T& value) const {
return searchRecursive(root, value);
}
/**
* 删除元素
* @param value 要删除的值
*/
void remove(const T& value) {
root = removeRecursive(root, value);
}
/**
* 中序遍历
* @param visit 访问函数
*/
void inorderTraversal(std::function<void(const T&)> visit) const {
inorderRecursive(root, visit);
}
/**
* 获取树的高度
* @return 树的高度
*/
int height() const {
return getHeight(root);
}
/**
* 验证BST不变性
* @return 如果满足BST性质返回 true
*/
bool isValid() const {
return isValidBST(root, nullptr, nullptr);
}
/**
* 检查树是否为空
* @return 如果树为空返回 true
*/
bool empty() const {
return root == nullptr;
}
};
k(v)←k(s)
1
≤
1.44log2(n+
2)−
0.328
T3
T3
height
(
1
),
left
(
nullptr
),
right
(
nullptr
) {}
};
/**
* AVL树实现
*
* 时间复杂度：
* - 查找：O(log n)
* - 插入：O(log n)，最多需要 O(log n) 次旋转
* - 删除：O(log n)，最多需要 O(log n) 次旋转
*
* 空间复杂度：O(n)
*/
class AVLTree {
private:
AVLNode* root;
/**
* 获取节点高度（空节点高度为0）
*/
int getHeight(const AVLNode* node) const {
return node ? node->height : 0;
}
/**
* 计算平衡因子
* @return 左子树高度 - 右子树高度
*/
int getBalanceFactor(const AVLNode* node) const {
if (node == nullptr) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
/**
* 更新节点高度
* 高度 = 1 + max(左子树高度, 右子树高度)
*/
void updateHeight(AVLNode* node) {
if (node != nullptr) {
node->height = 1 + std::max(
getHeight(node->left),
getHeight(node->right)
);
}
}
/**
* 右旋转：解决LL不平衡
*
* y x
* / \ / \
* x T3 => T1 y
* / \ / \
* T1 T2 T2 T3
*
* @param y 不平衡节点
* @return 旋转后的新根节点
*/
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
// 执行旋转
x->right = y;
y->left = T2;
// 更新高度（先更新子树，再更新根）
updateHeight(y);
updateHeight(x);
return x; // 返回新的根节点
}
/**
* 左旋转：解决RR不平衡
*
* x y
* / \ / \
* T1 y => x T3
* / \ / \
* T2 T3 T1 T2
*
* @param x 不平衡节点
* @return 旋转后的新根节点
*/
AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
// 执行旋转
y->left = x;
x->right = T2;
// 更新高度
updateHeight(x);
updateHeight(y);
return y; // 返回新的根节点
}
/**
* 递归插入节点
* @param node 当前子树根节点
* @param data 要插入的值
* @return 更新后的子树根节点
*/
AVLNode* insertRecursive(AVLNode* node, int data) {
// 1. 执行标准BST插入
if (node == nullptr) {
return new AVLNode(data);
}
if (data < node->data) {
node->left = insertRecursive(node->left, data);
} else if (data > node->data) {
node->right = insertRecursive(node->right, data);
} else {
return node; // 不允许重复值
}
// 2. 更新当前节点的高度
updateHeight(node);
// 3. 计算平衡因子
int balance = getBalanceFactor(node);
// 4. 根据不平衡类型执行相应的旋转
// LL情况：左子树左子节点导致不平衡
if (balance > 1 && data < node->left->data) {
return rotateRight(node);
}
// RR情况：右子树右子节点导致不平衡
if (balance < -1 && data > node->right->data) {
return rotateLeft(node);
}
// LR情况：左子树右子节点导致不平衡
if (balance > 1 && data > node->left->data) {
node->left = rotateLeft(node->left); // 先左旋左子树
return rotateRight(node); // 再右旋当前节点
}
// RL情况：右子树左子节点导致不平衡
if (balance < -1 && data < node->right->data) {
node->right = rotateRight(node->right); // 先右旋右子树
return rotateLeft(node); // 再左旋当前节点
}
return node; // 树已平衡，无需旋转
}
/**
* 验证AVL树性质
* @param node 当前子树根节点
* @return 如果满足AVL性质返回 true
*/
bool isValidAVL(const AVLNode* node) const {
if (node == nullptr) {
return true;
}
int balance = getBalanceFactor(node);
if (balance < -1 || balance > 1) {
return false; // 平衡因子超出范围
}
return isValidAVL(node->left) && isValidAVL(node->right);
}
/**
* 后序遍历释放内存
*/
void destroyRecursive(AVLNode* node) {
if (node != nullptr) {
destroyRecursive(node->left);
destroyRecursive(node->right);
delete node;
}
}
/**
* 中序遍历
*/
void inorderRecursive(const AVLNode* node,
std::function<void(int)> visit) const {
if (node != nullptr) {
inorderRecursive(node->left, visit);
visit(node->data);
inorderRecursive(node->right, visit);
}
}
// 禁用拷贝构造和赋值
AVLTree(const AVLTree&) = delete;
AVLTree& operator=(const AVLTree&) = delete;
public:
AVLTree() : root(nullptr) {}
~AVLTree() {
destroyRecursive(root);
}
/**
* 插入元素
* @param data 要插入的值
*/
void insert(int data) {
root = insertRecursive(root, data);
}
/**
* 验证AVL树性质
*/
bool isValid() const {
return isValidAVL(root);
}
/**
* 获取树的高度
*/
int height() const {
return getHeight(root);
}
/**
* 中序遍历
*/
void inorderTraversal(std::function<void(int)> visit) const {
inorderRecursive(root, visit);
}
/**
* 检查树是否为空
*/
bool empty() const {
return root == nullptr;
}
};
// 使用示例
int main() {
AVLTree avl;
// 插入数据，演示自动平衡
avl.insert(10);
avl.insert(20);
avl.insert(30); // 触发RR不平衡，执行左旋转
avl.insert(40);
avl.insert(50); // 触发RR不平衡，执行左旋转
avl.insert(25); // 触发RL不平衡，执行双旋转
// 验证AVL性质
std::cout << "AVL树是否有效: " << (avl.isValid() ? "是" : "否") << std::endl;
std::cout << "树的高度: " << avl.height() << std::endl;
// 中序遍历（输出有序序列）
std::cout << "中序遍历: ";
avl.inorderTraversal([](int val) { std::cout << val << " "; });
std::cout << std::endl;
return 0;
}
O
(
log
n
)
删除操作：O(logn)，最多需要 O(logn) 次重新着色和最多3次旋转 RBNode* parent; // 父节点指针（用于旋转和修复）
explicit RBNode(int val)
: data(val), color(Color::RED),
left(nullptr), right(nullptr), parent(nullptr) {}
};
/**
* 红黑树实现
*
* 时间复杂度：所有操作均为 O(log n)
* 空间复杂度：O(n)
*/
class RedBlackTree {
private:
RBNode* root; // 根节点指针
RBNode* NIL; // 哨兵节点（代表所有NIL叶子节点）
/**
* 左旋转
*
* x y
* / \ / \
* T1 y => x T3
* / \ / \
* T2 T3 T1 T2
*/
void rotateLeft(RBNode* x) {
RBNode* y = x->right;
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
/**
* 右旋转
*
* y x
* / \ / \
* x T3 => T1 y
* / \ / \
* T1 T2 T2 T3
*/
void rotateRight(RBNode* y) {
RBNode* x = y->left;
y->left = x->right;
if (x->right != NIL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == nullptr) {
root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
/**
* 插入后修复红黑树性质
* 修复违反的性质4（红色节点的子节点必须是黑色）
*
* @param z 新插入的节点
*/
void insertFixup(RBNode* z) {
while (z->parent != nullptr && z->parent->color == Color::RED) {
if (z->parent == z->parent->parent->left) {
// 父节点是祖父节点的左子节点
RBNode* uncle = z->parent->parent->right;
if (uncle->color == Color::RED) {
// 情况1：叔节点为红色
// 重新着色：父节点和叔节点变黑，祖父节点变红
z->parent->color = Color::BLACK;
uncle->color = Color::BLACK;
z->parent->parent->color = Color::RED;
z = z->parent->parent; // 向上检查
} else {
// 情况2和3：叔节点为黑色
if (z == z->parent->right) {
// 情况2：z是右子节点，转换为情况3
z = z->parent;
rotateLeft(z);
}
// 情况3：z是左子节点
z->parent->color = Color::BLACK;
z->parent->parent->color = Color::RED;
rotateRight(z->parent->parent);
}
} else {
// 对称情况：父节点是祖父节点的右子节点
RBNode* uncle = z->parent->parent->left;
if (uncle->color == Color::RED) {
z->parent->color = Color::BLACK;
uncle->color = Color::BLACK;
z->parent->parent->color = Color::RED;
z = z->parent->parent;
} else {
if (z == z->parent->left) {
z = z->parent;
rotateRight(z);
}
z->parent->color = Color::BLACK;
z->parent->parent->color = Color::RED;
rotateLeft(z->parent->parent);
}
}
}
// 确保根节点为黑色（性质2）
root->color = Color::BLACK;
}
/**
* 验证红黑树性质
* @param node 当前节点
* @param blackCount 当前路径的黑高
* @param pathBlackCount 参考路径的黑高（用于验证性质5）
* @return 如果满足所有性质返回 true
*/
bool isValidRB(const RBNode* node, int blackCount, int& pathBlackCount) const {
if (node == NIL) {
if (pathBlackCount == -1) {
pathBlackCount = blackCount;
}
return blackCount == pathBlackCount; // 验证性质5
}
// 验证性质4：红色节点的子节点必须是黑色
if (node->color == Color::RED) {
if ((node->left != NIL && node->left->color == Color::RED) ||
(node->right != NIL && node->right->color == Color::RED)) {
return false;
}
}
// 递归验证左右子树
int nextBlackCount = blackCount +
(node->color == Color::BLACK ? 1 : 0);
return isValidRB(node->left, nextBlackCount, pathBlackCount) &&
isValidRB(node->right, nextBlackCount, pathBlackCount);
}
/**
* 后序遍历释放内存
*/
void destroyRecursive(RBNode* node) {
if (node != NIL && node != nullptr) {
destroyRecursive(node->left);
destroyRecursive(node->right);
delete node;
}
}
/**
* 中序遍历
*/
void inorderRecursive(const RBNode* node,
std::function<void(int, Color)> visit) const {
if (node != NIL) {
inorderRecursive(node->left, visit);
visit(node->data, node->color);
inorderRecursive(node->right, visit);
}
}
// 禁用拷贝构造和赋值
RedBlackTree(const RedBlackTree&) = delete;
RedBlackTree& operator=(const RedBlackTree&) = delete;
public:
/**
* 构造函数：初始化空树和NIL节点
*/
RedBlackTree() {
NIL = new RBNode(0);
NIL->color = Color::BLACK; // NIL节点为黑色（性质3）
NIL->left = NIL->right = NIL->parent = nullptr;
root = NIL;
}
/**
* 析构函数：释放所有节点内存
*/
~RedBlackTree() {
destroyRecursive(root);
delete NIL;
}
/**
* 插入节点
* @param data 要插入的值
*/
void insert(int data) {
RBNode* newNode = new RBNode(data);
newNode->left = newNode->right = NIL;
RBNode* parent = nullptr;
RBNode* current = root;
// 标准BST插入：找到插入位置
while (current != NIL) {
parent = current;
if (data < current->data) {
current = current->left;
} else if (data > current->data) {
current = current->right;
} else {
// 不允许重复值
delete newNode;
return;
}
}
newNode->parent = parent;
if (parent == nullptr) {
root = newNode; // 插入根节点
} else if (data < parent->data) {
parent->left = newNode;
} else {
parent->right = newNode;
}
// 修复红黑树性质
insertFixup(newNode);
}
/**
* 验证红黑树性质
* @return 如果满足所有性质返回 true
*/
bool isValid() const {
if (root == NIL) {
return true; // 空树满足所有性质
}
// 验证性质2：根节点为黑色
if (root->color != Color::BLACK) {
return false;
}
int pathBlackCount = -1;
return isValidRB(root, 0, pathBlackCount);
}
/**
* 中序遍历
* @param visit 访问函数，参数为 (键值, 颜色)
*/
void inorderTraversal(std::function<void(int, Color)> visit) const {
inorderRecursive(root, visit);
}
/**
* 检查树是否为空
*/
bool empty() const {
return root == NIL;
}
};
// 使用示例
int main() {
RedBlackTree rbt;
// 插入数据
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
rbt.insert(25);
rbt.insert(5);
// 验证红黑树性质
std::cout << "红黑树是否有效: " << (rbt.isValid() ? "是" : "否") << std::endl;
// 中序遍历
std::cout << "中序遍历: ";
rbt.inorderTraversal([](int val, Color color) {
std::cout << val << "(" << (color == Color::RED ? "R" : "B") << ") ";
});
std::cout << std::endl;
return 0;
}
i
平衡性：所有叶节点位于同一层 int minDegree; // 最小度数 t
/**
* 构造函数
* @param degree 最小度数 t
* @param leaf 是否为叶子节点
*/
BTreeNode(int degree, bool leaf)
: minDegree(degree), isLeaf(leaf) {
keys.reserve(2 * degree - 1);
children.reserve(2 * degree);
}
/**
* 在非满节点中插入键值
* @param key 要插入的键值
*/
void insertNonFull(int key) {
int i = static_cast<int>(keys.size()) - 1;
if (isLeaf) {
// 叶子节点：直接插入并保持有序
keys.push_back(0); // 扩展空间
while (i >= 0 && keys[i] > key) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = key;
} else {
// 内部节点：找到应该插入的子节点
while (i >= 0 && keys[i] > key) {
i--;
}
i++;
// 如果子节点已满，先分裂
if (children[i]->keys.size() == 2 * minDegree - 1) {
splitChild(i, children[i]);
// 分裂后，中间键值提升到当前节点
if (keys[i] < key) {
i++;
}
}
children[i]->insertNonFull(key);
}
}
/**
* 分裂满的子节点
*
* 将满节点（2t-1个键）分裂为两个节点（各t-1个键），
* 中间键值提升到父节点
*
* @param index 子节点在children数组中的索引
* @param fullChild 要分裂的满子节点
*/
void splitChild(int index, BTreeNode* fullChild) {
// 创建新节点（右半部分）
BTreeNode* newChild = new BTreeNode(fullChild->minDegree,
fullChild->isLeaf);
// 移动后半部分键值（索引 t 到 2t-2）
for (int j = 0; j < minDegree - 1; j++) {
newChild->keys.push_back(fullChild->keys[j + minDegree]);
}
// 如果不是叶子节点，移动后半部分子节点指针
if (!fullChild->isLeaf) {
for (int j = 0; j < minDegree; j++) {
newChild->children.push_back(fullChild->children[j + minDegree]);
}
fullChild->children.resize(minDegree);
}
// 提取中间键值（索引 t-1）
int midKey = fullChild->keys[minDegree - 1];
fullChild->keys.resize(minDegree - 1);
// 在当前节点中插入中间键值和新子节点
children.insert(children.begin() + index + 1, newChild);
keys.insert(keys.begin() + index, midKey);
}
/**
* 搜索键值
* @param key 要搜索的键值
* @return 如果找到返回 true
*/
bool search(int key) {
// 在节点内查找键值位置
size_t i = 0;
while (i < keys.size() && key > keys[i]) {
i++;
}
// 如果找到键值
if (i < keys.size() && keys[i] == key) {
return true;
}
// 如果是叶子节点且未找到，返回false
if (isLeaf) {
return false;
}
// 在相应的子节点中继续搜索
return children[i]->search(key);
}
/**
* 中序遍历（按升序输出所有键值）
* @param visit 访问函数
*/
void traverse(std::function<void(int)> visit) {
size_t i;
for (i = 0; i < keys.size(); i++) {
// 先遍历左子树
if (!isLeaf) {
children[i]->traverse(visit);
}
// 访问当前键值
visit(keys[i]);
}
// 遍历最后一个子树
if (!isLeaf) {
children[i]->traverse(visit);
}
}
/**
* 析构函数：递归释放所有子节点
*/
~BTreeNode() {
if (!isLeaf) {
for (BTreeNode* child : children) {
delete child;
}
}
}
// 禁用拷贝构造和赋值
BTreeNode(const BTreeNode&) = delete;
BTreeNode& operator=(const BTreeNode&) = delete;
};
/**
* B-树类
*
* 时间复杂度：
* - 查找：O(log_t n)，其中 t 为最小度数
* - 插入：O(log_t n)
* - 删除：O(log_t n)
*
* 空间复杂度：O(n)
*/
class BTree {
private:
BTreeNode* root; // 根节点指针
int minDegree; // 最小度数 t
public:
/**
* 构造函数
* @param degree 最小度数 t（必须 >= 2）
*/
explicit BTree(int degree) : root(nullptr), minDegree(degree) {
if (degree < 2) {
throw std::invalid_argument("最小度数必须 >= 2");
}
}
/**
* 析构函数
*/
~BTree() {
delete root;
}
/**
* 搜索键值
* @param key 要搜索的键值
* @return 如果找到返回 true
*/
bool search(int key) const {
return root ? root->search(key) : false;
}
/**
* 插入键值
* @param key 要插入的键值
*/
void insert(int key) {
if (root == nullptr) {
// 创建根节点（叶子节点）
root = new BTreeNode(minDegree, true);
root->keys.push_back(key);
} else {
// 如果根节点已满，需要分裂并创建新根
if (root->keys.size() == 2 * minDegree - 1) {
BTreeNode* newRoot = new BTreeNode(minDegree, false);
newRoot->children.push_back(root);
newRoot->splitChild(0, root);
// 确定新键值应该插入哪个子节点
int i = 0;
if (newRoot->keys[0] < key) {
i++;
}
newRoot->children[i]->insertNonFull(key);
root = newRoot;
} else {
root->insertNonFull(key);
}
}
}
/**
* 中序遍历
* @param visit 访问函数
*/
void traverse(std::function<void(int)> visit) const {
if (root) {
root->traverse(visit);
}
}
/**
* 检查树是否为空
*/
bool empty() const {
return root == nullptr;
}
};
// 使用示例
int main() {
BTree btree(3); // 创建最小度数为3的B-树
// 插入数据
std::vector<int> data = {10, 20, 5, 6, 12, 30, 7, 17, 1, 25, 40, 50};
std::cout << "插入数据: ";
for (int val : data) {
std::cout << val << " ";
btree.insert(val);
}
std::cout << std::endl;
// 中序遍历（输出有序序列）
std::cout << "B-树中序遍历: ";
btree.traverse([](int key) { std::cout << key << " "; });
std::cout << std::endl;
// 搜索测试
std::cout << "\n搜索测试:" << std::endl;
std::cout << "搜索 6: " << (btree.search(6) ? "找到" : "未找到") << std::endl;
std::cout << "搜索 15: " << (btree.search(15) ? "找到" : "未找到") << std::endl;
std::cout << "搜索 30: " << (btree.search(30) ? "找到" : "未找到") << std::endl;
return 0;
}