Appearance
平衡二叉搜索树与红黑树
平衡树通过在 BST 基础上增加不变量，防止有序输入等场景将树退化为链表。
| 结构 | 保证 | 适合的问题 | 常见 C++ 选择 |
|---|---|---|---|
| AVL 树 | 高度严格平衡 | 查询非常频繁、更新相对少的有序集合 | 自行实现或专业库 |
| 红黑树 | 近似平衡 | 通用有序集合 / 映射，频繁增删 | std::set、std::map 通常使用 |
先理解普通二叉搜索树
二叉搜索树（BST）满足：对任意节点 x，左子树所有键小于 x.key，右子树所有键大于 x.key（重复键的放置策略必须统一）。
因此查找、插入、删除只需沿一条根到叶子的路径，复杂度是 O(h)，h 为树高：
text
平衡时：h = O(log n)
退化成链表时：h = O(n)平衡树的目标正是防止有序输入等情况把 BST 退化为链表。基础 BST 的查找、插入、删除、上下界和验证见树。
AVL 树：高度平衡的 BST
不变量与旋转
AVL 树在 BST 性质外，要求每个节点的平衡因子：
text
balance_factor = height(left) - height(right)始终属于 {-1, 0, 1}。插入或删除后，从受影响节点向根更新高度；若平衡因子绝对值达到 2，就通过旋转修复。
| 失衡形态 | 条件 | 修复 |
|---|---|---|
| LL | 节点左重，左孩子不右重 | 对节点右旋 |
| RR | 节点右重，右孩子不左重 | 对节点左旋 |
| LR | 节点左重，左孩子右重 | 先对左孩子左旋，再对节点右旋 |
| RL | 节点右重，右孩子左重 | 先对右孩子右旋，再对节点左旋 |
以 LL 为例，右旋只改变局部连接，仍保持 BST 的中序顺序：
text
y x
/ \ / \
x C 右旋(y) A y
/ \ ─────────► / \
A B B C操作复杂度
| 操作 | 时间 | 原因 |
|---|---|---|
| 查找 | O(log n) | AVL 树高为 O(log n) |
| 插入 | O(log n) | 找位置和向上更新高度；插入至多修复一个失衡点 |
| 删除 | O(log n) | 删除后可能一路向上出现失衡，需要多次修复 |
| 前驱 / 后继 / 范围查询 | O(log n + k) | 定位边界 O(log n)，输出 k 个元素 |
| 空间 | O(n) | 每个节点保存键、左右孩子和高度 |
"单次旋转是 O(1)"不代表"插入是 O(1)"：找插入位置和更新路径仍是 O(log n)。
可运行的 AVL int 集合
下面的实现包括查找、插入和删除。使用 std::unique_ptr 表达节点唯一所有权，避免手写 delete；为了聚焦平衡逻辑，键类型固定为 int。
cpp
#include <algorithm>
#include <memory>
class AvlSet {
struct Node {
explicit Node(int value) : key(value) {}
int key;
int height = 1;
std::unique_ptr<Node> left;
std::unique_ptr<Node> right;
};
public:
bool contains(int key) const {
const Node* current = root_.get();
while (current) {
if (key < current->key) current = current->left.get();
else if (key > current->key) current = current->right.get();
else return true;
}
return false;
}
bool insert(int key) {
bool inserted = false;
root_ = insert(std::move(root_), key, inserted);
return inserted;
}
bool erase(int key) {
bool erased = false;
root_ = erase(std::move(root_), key, erased);
return erased;
}
private:
static int height(const std::unique_ptr<Node>& node) {
return node ? node->height : 0;
}
static int factor(const std::unique_ptr<Node>& node) {
return node ? height(node->left) - height(node->right) : 0;
}
static void refresh_height(Node& node) {
node.height = 1 + std::max(height(node.left), height(node.right));
}
static std::unique_ptr<Node> rotate_right(std::unique_ptr<Node> root) {
auto pivot = std::move(root->left);
root->left = std::move(pivot->right);
refresh_height(*root);
pivot->right = std::move(root);
refresh_height(*pivot);
return pivot;
}
static std::unique_ptr<Node> rotate_left(std::unique_ptr<Node> root) {
auto pivot = std::move(root->right);
root->right = std::move(pivot->left);
refresh_height(*root);
pivot->left = std::move(root);
refresh_height(*pivot);
return pivot;
}
static std::unique_ptr<Node> rebalance(std::unique_ptr<Node> root) {
refresh_height(*root);
if (factor(root) > 1) {
if (factor(root->left) < 0) {
root->left = rotate_left(std::move(root->left));
}
return rotate_right(std::move(root));
}
if (factor(root) < -1) {
if (factor(root->right) > 0) {
root->right = rotate_right(std::move(root->right));
}
return rotate_left(std::move(root));
}
return root;
}
static std::unique_ptr<Node> insert(
std::unique_ptr<Node> root, int key, bool& inserted) {
if (!root) {
inserted = true;
return std::make_unique<Node>(key);
}
if (key < root->key) {
root->left = insert(std::move(root->left), key, inserted);
} else if (key > root->key) {
root->right = insert(std::move(root->right), key, inserted);
} else {
return root;
}
return rebalance(std::move(root));
}
static Node* minimum(Node* root) {
while (root->left) root = root->left.get();
return root;
}
static std::unique_ptr<Node> erase(
std::unique_ptr<Node> root, int key, bool& erased) {
if (!root) return nullptr;
if (key < root->key) {
root->left = erase(std::move(root->left), key, erased);
} else if (key > root->key) {
root->right = erase(std::move(root->right), key, erased);
} else {
erased = true;
if (!root->left) return std::move(root->right);
if (!root->right) return std::move(root->left);
const int successor = minimum(root->right.get())->key;
root->key = successor;
bool ignored = false;
root->right = erase(std::move(root->right), successor, ignored);
}
return rebalance(std::move(root));
}
std::unique_ptr<Node> root_;
};注意：这份教学实现没有提供迭代器、异构查找、节点分配器、强异常安全保证或线程同步；生产代码通常优先使用经过充分测试的容器。
红黑树：用颜色约束保持近似平衡
红黑树也是二叉搜索树，但不保存每个节点的精确高度，而是用一位颜色和局部旋转约束根到叶子的路径长度。它同时维护 BST 的键顺序和以下五条性质：
- 每个实际节点是红色或黑色；
- 根节点是黑色；
- 所有空孩子都视为黑色叶子；实现常用一个共享哨兵
NIL表示它们； - 红节点的两个孩子都是黑色，即不能出现连续红节点；
- 从任意节点到它的所有后代
NIL，每条路径包含相同数量的黑节点。
颜色不是业务状态，而是维护平衡的不变量。只满足 BST 顺序但破坏任意一条颜色性质，都不能称为合法红黑树。
黑高与高度上界
节点 x 的黑高（black height）是从 x 向下到任意后代 NIL 路径上的黑节点数。这里约定不计 x、计入终点 NIL；性质 5 保证这个值与所选路径无关。不同资料可能采用其他计数约定，推导时不要混用。
高度为什么是 O(log n)：
- 因为红节点不能相邻，一条根到
NIL的路径中，红节点数量不可能超过黑节点数量； - 因此最长路径至多是只含黑节点路径长度的两倍；
- 黑高为
bh的子树至少包含2^bh - 1个实际节点； - 所以对含
n个节点的红黑树，有：
text
height <= 2 × log2(n + 1)这个上界比 AVL 更松，但仍保证查找、插入和删除最坏 O(log n)。红黑树不保证左右子树高度差不超过 1，也不保证每条根叶路径等长。
旋转为什么不破坏 BST 顺序
左旋和右旋只重排局部父子链接，不改变中序顺序。以左旋 x 为例：
text
x y
/ \ / \
A y 左旋(x) x C
/ \ ─────► / \
B C A B
中序顺序始终是：A, x, B, y, C旋转本身只调整结构；插入和删除修复还会配合重新着色。工程实现必须同步维护父指针、根指针以及 NIL / 头哨兵链接，否则即使局部形状正确，迭代器和边界节点也可能损坏。
从 2-3-4 树理解颜色
红黑树可以看作 2-3-4 树的一种二叉表示：把一个黑节点和直接连接的红孩子压缩到一起，就对应一个拥有 1～3 个 key 的 2-node、3-node 或 4-node。所有根到 NIL 的黑高相同，对应 2-3-4 树所有叶子处在同一层。
从这个视角看：
- 红链接表示两个 key 属于同一个多路节点，不应连续出现；
- 叔叔为红时的颜色翻转，类似把一个临时 4-node 向上分裂；
- 旋转是在不改变有序关系的情况下，调整同一个多路节点的二叉表示。
左倾红黑树（LLRB）还额外要求红链接向左倾斜，可用更统一的递归代码模拟 2-3 树；它是红黑树的一种实现变体，不能把“红链接必须左倾”误认为普通红黑树的基本性质。
C++ 标准只规定
std::map/std::set的语义和复杂度，不规定必须使用红黑树；主流实现通常采用红黑树，但业务代码不应依赖这一实现细节。
插入修复：解决“红红冲突”
先按普通 BST 找到位置。新节点通常着为红色：如果直接插入黑节点，经过新节点的所有路径会立刻多一个黑节点，破坏黑高；插入红节点不会改变黑高，只可能产生“父节点也是红色”的局部冲突。
若新节点记为 x，父节点为 p，祖父为 g，叔叔为 u：
x成为根：把它染黑；p为黑：所有性质已经满足；p为红：g必然存在且为黑，需要根据叔叔颜色修复。
叔叔是红色：重新着色并向上继续
text
g(B) g(R)
/ \ / \
p(R) u(R) → p(B) u(B)
/
x(R)把父亲和叔叔染黑、祖父染红，然后令 x = g，继续检查祖父是否与它的父节点形成新的红红冲突。该情况不旋转，但冲突可能沿祖先路径向上传播；最后必须再次把根染黑。
叔叔是黑色：通过旋转结束局部冲突
根据 x-p-g 的方向分为直线和折线：
| 形态 | 第一步 | 第二步 |
|---|---|---|
| LL | 无 | 父染黑、祖父染红，对祖父右旋 |
| RR | 无 | 父染黑、祖父染红，对祖父左旋 |
| LR | 先对父节点左旋，转成 LL | 按 LL 修复 |
| RL | 先对父节点右旋，转成 RR | 按 RR 修复 |
直线情况的一次旋转会让原父节点成为局部根；折线情况先旋转父节点形成直线，再旋转祖父。因此一次插入最多需要 2 次旋转，但重新着色可能向上进行 O(log n) 层。
插入修复可以概括为：
text
叔叔红：颜色上移
叔叔黑：折线先拉直，再旋转祖父并交换父/祖父颜色删除修复：处理“额外黑色”
删除先按普通 BST 处理结构。若目标有两个孩子，实际摘除的通常是它的中序后继，因此要记录真正被摘除节点的原颜色：
- 摘除红节点：不改变任意路径的黑节点数，无需修复；
- 摘除黑节点且替代孩子为红：把替代孩子染黑即可；
- 摘除黑节点且替代孩子也是黑色或
NIL：经过该位置的路径少一个黑节点，可把它抽象成替代节点x携带一层“额外黑色”（double black）。
“额外黑色”只是推导修复过程的概念，不是节点颜色枚举中的第三种实际颜色。删除比插入更复杂，因为它可能让黑高不足一路向根传播。
以下假设 x 是父节点的左孩子，兄弟 s 在右侧；左右互换时完全对称。兄弟孩子中，靠近 x 的称为近侄子，远离 x 的称为远侄子。
| 情况 | 处理 | 目的 |
|---|---|---|
| 兄弟红 | 兄弟染黑、父染红，对父左旋，重新取得新兄弟 | 转换为“兄弟黑”的情况 |
| 兄弟黑，两个侄子都黑 | 兄弟染红，把额外黑色上移到父节点 | 当前两侧黑高恢复，可能继续向上 |
| 兄弟黑，近侄子红、远侄子黑 | 近侄子染黑、兄弟染红，对兄弟右旋 | 转换为远侄子红的最终情况 |
| 兄弟黑，远侄子红 | 兄弟继承父颜色，父和远侄子染黑，对父左旋 | 消除额外黑色，修复结束 |
若额外黑色上移到一个红色父节点，将父节点染黑即可结束；若最终到达根，直接移除“额外黑色”。一次删除修复最多进行常数次旋转（经典实现最多 3 次），但额外黑色可能沿树高向上传播，所以总时间仍为 O(log n)。
使用共享黑色 NIL 哨兵可以让叶子删除和普通节点使用同一套修复逻辑，并允许修复阶段访问 x 的父亲和兄弟。若用 nullptr 表示空孩子，就必须额外保存父节点，不能直接解引用空指针。
操作复杂度
| 操作 | 时间 | 说明 |
|---|---|---|
find / lower_bound | O(log n) | 按 BST 路径定位 |
insert | O(log n) | 最多 2 次旋转，重新着色可能向上 O(log n) 层 |
erase | O(log n) | 最多 3 次旋转，额外黑色可能向上 O(log n) 层 |
| 最小值 / 最大值 | O(log n) | 沿最左 / 最右路径定位；容器可额外缓存边界节点 |
| 范围查询 | O(log n + k) | 定位起点 O(log n)，输出 k 个元素 |
| 有序遍历 | O(n) | 中序遍历按比较器顺序输出 |
| 空间 | O(n) | 每个节点保存颜色和父子链接 |
如何验证一棵红黑树
验证不能只检查“根是黑色”和“没有连续红节点”，还必须同时验证 BST 顺序与所有路径黑高一致。下面的函数把 nullptr 当作黑色 NIL，返回子树黑高；返回 -1 表示不合法：
cpp
#include <limits>
enum class Color { Red, Black };
struct RbNode {
int key;
Color color;
RbNode* left = nullptr;
RbNode* right = nullptr;
};
bool is_red(const RbNode* node) {
return node && node->color == Color::Red;
}
int validate_subtree(const RbNode* node, long long low, long long high) {
if (!node) return 1; // NIL 视为黑色
if (node->key <= low || node->key >= high) return -1;
if (is_red(node) && (is_red(node->left) || is_red(node->right))) {
return -1; // 连续红节点
}
const int left_black_height =
validate_subtree(node->left, low, node->key);
const int right_black_height =
validate_subtree(node->right, node->key, high);
if (left_black_height < 0 || right_black_height < 0 ||
left_black_height != right_black_height) {
return -1;
}
return left_black_height + (node->color == Color::Black ? 1 : 0);
}
bool is_valid_red_black_tree(const RbNode* root) {
if (!root) return true;
if (root->color != Color::Black) return false;
return validate_subtree(root,
std::numeric_limits<long long>::lowest(),
std::numeric_limits<long long>::max()) > 0;
}这段验证采用“不允许重复 key”的集合语义。如果实现允许重复键，左右边界规则必须与插入策略保持一致。
std::set / std::map 的具体用法
cpp
#include <set>
std::set<int> scores{30, 10, 50};
scores.insert(40); // O(log n)
scores.erase(10); // O(log n)
if (scores.contains(30)) { // C++20，O(log n)
auto first_not_less = scores.lower_bound(35);
if (first_not_less != scores.end()) {
// *first_not_less == 40
}
}std::map / std::set 的等价键由比较器定义：若 comp(a, b) 和 comp(b, a) 都为假，两个键视为等价。比较器必须满足严格弱序，不能在元素已经进入容器后改变会影响排序的键。它们是节点式关联容器：插入通常不使已有迭代器失效，删除只使指向被删元素的迭代器失效。
标准要求 begin() 为常数复杂度；常见树实现会在头哨兵中缓存最左节点、最右节点和根节点。手写红黑树若希望支持高效迭代器，也需要维护这些边界链接和父指针，不能只实现颜色修复。
AVL 与红黑树如何选择
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡约束 | 每个节点左右高度差不超过 1 | 黑高一致、红节点不相邻 |
| 树高 | 更严格、更接近最小高度 | 最坏不超过 2 log2(n+1) |
| 查询 | 通常路径稍短 | 仍保证最坏 O(log n) |
| 插入旋转 | 最多 2 次 | 最多 2 次，可能沿途重新着色 |
| 删除修复 | 可能沿祖先路径多次旋转 | 最多 3 次旋转，可能传播额外黑色 |
| 节点元数据 | 高度或平衡因子 | 一位颜色（实现中常占一个字段） |
| 常见场景 | 查询占绝对多数、更新较少 | 通用有序集合 / 映射、增删较频繁 |
面试场景选择
| 需求 | 优先选择 | 原因 |
|---|---|---|
有序字典、范围查询、lower_bound | 红黑树 / std::map | 全局有序，按键 O(log n) |
| 查找多、更新少且想要更小树高 | AVL 树 | 平衡更严格 |
| 高速精确 key 查找，不要求有序 | 哈希表 | 平均 O(1) |
面试中的简洁回答
红黑树是一种自平衡二叉搜索树。它通过根和空叶子为黑、红节点不相邻、任意节点到后代空叶子的黑高相同等约束，使最长路径不超过最短路径的两倍，因此树高最坏 O(log n)。插入先按 BST 插入红节点，再根据叔叔颜色进行重新着色或旋转；删除黑节点可能产生“额外黑色”，再根据兄弟和侄子颜色向上修复。查找、插入、删除最坏都是 O(log n)。相比 AVL，它平衡更宽松，通常适合增删较频繁的通用有序容器；但
std::map是否用红黑树属于实现细节。
易错点
- 写 AVL 时，旋转后必须先更新较低节点的高度，再更新新根；
- 删除 AVL 双孩子节点时，替换后仍要从当前节点向上重新平衡；
- 红黑树不是“每条路径等长”，而是每条到
NIL的路径黑节点数相等； NIL叶子是黑色的逻辑节点，不要在黑高推导中忽略它；- 新插入节点通常染红，目的是不改变现有路径黑高；
- “双黑”只是删除修复的推导状态，不是第三种实际颜色；
- 旋转只保证 BST 中序顺序不变，颜色性质还需要重新着色维护；
- 插入修复关注叔叔颜色，删除修复关注兄弟及其近、远侄子颜色；
- 红黑树和 AVL 的查找、插入、删除都是 O(log n)，单次旋转 O(1) 不代表整个操作 O(1)；
std::map常由红黑树实现，但 C++ 标准没有规定具体数据结构。