平衡二叉树
10.1 用于排序的有序集合
有序集合是一个由已排序的（分数，名称）对组成的集合。
std::set<std::pair<double, std::string>> by_score;一个明显的应用场景是排名，例如，从高分榜中检索前k个项目。但它足够通用，适用于任何需要排序的场景。
源代码在文章末尾
元组比较
（分数，名称）对是根据两个字段进行排序的，类似于数据库的多列索引。
(s1, n1) < (s2, n2) ⟹ s1 < s2 || (s1 = s2 && n1 < n2)
一个应用场景是为所有的对使用相同的分数，这样它们就仅根据名称进行排序。“名称”是一个字节字符串，但可以将任何内容编码为字节，同时保持排序顺序，所以有序集合可以对任何内容进行排序。
多索引数据
分数是一个64位浮点数，它可以不是唯一的。名称是唯一的，你可以通过名称删除一个对，或者通过名称更新分数。所以这个集合有两种索引方式：
struct SortedSet {
std::set<std::pair<double, std::string>> by_score;
std::unordered_map<std::string, double> by_name;
};在数据库中，对同一数据建立多个索引是很常见的。
CREATE TABLE sorted_set (
`name` string,
`score` double,
PRIMARY KEY `name`, -- 主索引
INDEX by_score (`score`, `name`) -- 辅助索引
);排序索引
按分数建立索引需要一个排序数据结构。在数据库中，排序索引要么是B+树，要么是LSM树，这两种都不简单。对于内存数据存储，有更多的选择，包括各种二叉树。
很多数据库的使用都涉及到对数据进行排序，这就是为什么数据库索引大多是树结构而不是哈希表，即使树的速度较慢。一个内存数据存储可以同时拥有这两种索引，就像Redis的有序集合一样。
STL中的排序数据结构是基于红黑树（std::map和std::set）。真正的Redis使用跳表来实现有序集合。我们将编写一个简单得多的AVL树来代替。
10.2 树数据结构
通过分治法进行数据排序
几乎所有的排序数据结构都是树，因为树节点将数据分成不重叠的子树。
8 (根节点)
┌───────┴───┐
4 ┆ a
┌───┴───┐ ┆ ┌─┴───┐
2 ┆ 6 ┆ 9 ┆ c
┌─┴─┐ ┆ ┌─┴─┐ ┆ ┆ ┆ ┌─┴─┐
1 ┆ 3 ┆ 5 ┆ 7 ┆ ┆ ┆ b ┆ d
┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
│1│2│3│4│5│6│7│8│9│a│b│c│d│
└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘根节点表示范围(−∞, +∞)。通过跟随子节点，范围会缩小。要在树中搜索一个键，在向下遍历的过程中要保持键在范围内。
不平衡二叉树
要将一个键插入到树中，首先进行搜索，直到到达一个叶节点，然后将新节点放置在它的一个空的子指针位置。插入顺序会影响树的形状。
插入顺序：2, 5, 6, 8, 9：
2 2 2 2 2
⇨ └─┐ └─┐ └─┐ └─┐
5 ⇨ 5 5 5
└─┐ ⇨ └─┐ └─┐
6 6 ⇨ 6
└─┐ └─┐
8 8
└─┐
9相同的数据，不同的顺序：5, 8, 2, 6, 9：
5 5 5 5 5
⇨ └─┐ ⇨ ┌─┴─┐ ┌─┴───┐ ┌─┴───┐
8 2 8 ⇨ 2 8 ⇨ 2 8
┌─┘ ┌─┴─┐
6 6 9在第一个例子中，节点是按排序顺序插入的，结果得到一个很深的树，类似于链表。这是最坏的情况，搜索复杂度为O(N)。而平均情况下，假设插入顺序是随机的，树的深度为O(log N)。
高度平衡树
你无法控制插入到树中的内容，但你可以在插入后重塑树的形状，以避免得到一个非常深的树。目标是在最坏情况下将树的最大深度限制为O(log N)。这被称为高度平衡树，通过保持一些不变量来实现：
- 1. B树：所有叶节点高度相同的N叉树。
- 2. 红黑树：最大叶节点高度在最小叶节点高度的2倍以内。
- 3. AVL树：两个子树的高度最多相差1。
有些树不保证最坏情况，但通常也足够好：
- 1. 树堆（Treap）：随机旋转节点来重塑树的形状。比不平衡树好，但无法达到最坏情况的目标。
- 2. 跳表：等同于n叉树，像树堆一样使用随机性。真正的Redis使用这个。我还没有找到一种能在几句话内描述它的方法。
B树 -> 2-3树 -> 红黑树
B树能实现统一的高度，因为一个节点可以存储可变数量的键，这对于二叉树来说是不可能的。然而，可以将一个包含2个键的B树节点表示为2个二叉节点。
┌──┬──┐ k2
│k1┆k2│ ┌───┴─┐
├──┼──┤ ◄──► k1 C
┌┘ │ └┐ ┌─┴─┐
A B C A B一个节点可以存储1个或2个键的n叉树被称为2-3树。用2个二叉节点替换包含2个键的节点就得到了红黑树。
树的比较
所有的排序数据结构在它们的能力方面是相等的：查询、修改、迭代。我们将选择能实现最坏情况目标的最简单的选项：AVL树。
| 树 | 最坏情况 | 分支数 | 随机性 | 难度 |
| AVL树 | O(log N) | 2 | 否 | 中等 |
| 红黑树 | O(log N) | 2 | 否 | 高 |
| B树 | O(log N) | n | 否 | 高 |
| 跳表 | O(N) | n | 是 | 中等 |
| 树堆 | O(N) | 2 | 是 | 低 |
10.3 基本二叉树操作
平衡二叉树只是在不平衡二叉树的基础上，增加了在插入和删除操作后恢复平衡的额外代码。搜索和迭代操作对于所有二叉树来说都是相同的。
struct Node { Node *left; Node *right; };搜索和插入
从根节点开始，如果没有找到目标节点，目标节点要么在左子树，要么在右子树。
// 伪代码
Node **tree_search(Node **from, int32_t (*cmp)(Node *, void *), void *key) {
Node *node = *from
if (!node) {
return from; // 空节点
}
int32_t r = cmp(node, key);
if (r < 0) { // node < key
return tree_search(&node->right, cmp, key);
} else if (r > 0) { // node > key
return tree_search(&node->left, cmp, key);
} else { // node == key
return from;
}
}这里使用了哈希表章节中传入指针的技巧。它返回指向目标节点的指针的地址，所以如果搜索在一个空指针处结束，这个地址可以用于插入操作。
struct Data { Node node; T key; }; // 侵入式
Data *new_data = make_some_data();
Node **child = tree_search(&root, cmp, &new_data->key);
if (!*child) { // 未找到
*child = &new_data->node; // 插入
} // 否则：找到重复项分离节点
简单情况：一个有0个或1个孩子的节点。只需用孩子节点替换该子树。
b b b b
┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
a X ─► a y a X ─► a w
└─┐ ┌─┘
y w困难情况：一个有两个孩子的节点。
- 1. 分离后继节点。
- 2. 与后继节点交换。
这是可行的，因为：
- 1. 后继节点是右子树中最左边的节点，由于它的左孩子为空，所以可以通过简单情况将其分离。
- 2. 用后继节点替换一个节点不会改变数据的顺序。
树是对称的，所以如果你使用前驱节点而不是后继节点，这同样可行。
// 伪代码。返回移除节点后的新树。
Node *node_detach(Node *node) {
// 简单情况：其中一个子树为空，返回另一个子树
if (!node->right) {
return node->left;
}
// 找到后继节点
Node **to_victim = &node->right; // 传入指针
while ((*to_victim)->left) {
to_victim = &(*to_victim)->left;
}
Node *victim = *to_victim;
// 通过简单情况分离后继节点
*to_victim = victim->right;
// 与后继节点交换
*victim = *node;
return victim;
}搜索和删除
这个伪代码没有使用父节点指针，所以node_detach()只能递归使用，调用者需要将父节点链接到新的子树。
Node *tree_delete(Node *node, int32_t (*cmp)(Node *, void *), void *key) {
if (!node) {
return NULL; // 未找到
}
int32_t r = cmp(node, key);
if (r < 0) { // node < key
node->right = tree_delete(node->right, cmp, key);
return node;
} else if (r > 0) { // node > key
node->left = tree_delete(node->left, cmp, key);
return node;
} else { // node == key
return node_detach(node);
}
}
Node *root = make_a_tree();
root = tree_delete(root, cmp, key);按排序顺序迭代
后继节点是右子树中最左边的节点，除非右子树为空，这时你必须回溯。这就是为什么树节点通常包含一个父节点指针。如果没有父节点指针，迭代器必须存储节点的整个路径。
父节点指针
有了父节点指针，只需一个指向节点的指针就可以删除一个节点。这很方便，因为你可能通过另一个索引（例如，多索引有序集合）得到一个节点的引用。
上面的代码假设没有父节点指针，所以我们不会使用它们。
10.4 AVL树是如何工作的？
不变量：高度差最多为1
子树的高度是从根节点到叶节点的最大距离（空树的高度为0）。对于AVL树中的任何节点，它的两个子树的高度可以不同，但最多相差1。以下是有效的AVL树：
same-height left-taller right-taller
c c c
L=1 ┌─┴─┐ R=1 L=1 ┌─┘ R=0 L=1 ┌─┴─┐ R=2
b d b b d
└─┐ R=1
e以下不是有效的AVL树，因为高度差为2：
left-too-tall right-too-tall
c a
L=2 ┌───┘ R=0 L=0 └─┐ R=2
a b
└─┐ └─┐
b c打破不变量
从一个有效的AVL树开始，然后进行二叉树的插入或删除操作，某些子树的高度可能会增加或减少1，这可能会导致高度差为2。下一步是重塑这个有问题的子树。
二叉树旋转保持顺序
旋转操作可以改变子树的形状，同时保持其顺序。
B D
┌─┴───┐ rotate-left ┌───┴─┐
a ┆ D ─────────────► B ┆ e
┆ ┆ ┌─┴─┐ ◄───────────── ┌─┴─┐ ┆ ┆
┆ ┆ c ┆ e rotate-right a ┆ c ┆ ┆
┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆ ┆
a B c D e a B c D e节点B和D交换了它们的父子关系。它们与三个（可能为空）子树a、c、e的链接被重新定位。数据的顺序没有改变，只有两个链接被改变：
- 1. B和D之间的链接被交换，其中一个是父节点。
- 2. 内部子树c被连接到B或D上。
a和e的链接保持不变。
Node *rot_left(Node *node) {
Node *new_node = node->right;
Node *inner = new_node->left;
node->right = inner; // node -> inner
new_node->left = node; // new_node -> node
return new_node;
}二叉树旋转改变高度
二叉树旋转在AVL树、红黑树、树堆中都有使用。它可以在保持数据顺序的同时改变树的高度。让我们修复左子树B比右子树E高2的情况。
变换1：
left-too-tall balanced
D(h+3) B(h+2)
┌────┴────┐ rotate-right ┌────┴────┐
B(h+2) E(h) ──────────────► A(h+1) D(h+1)
┌────┴────┐ ┌───┴───┐
A(h+1) C(h) C(h) E(h)假设B的子树A、C是有效的AVL树，我们有三种情况：
case 1: outer-taller case 2: inner-taller case 3: both-too-tall
D(h+3) D(h+3) D(h+3)
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
B(h+2) E(h) B(h+2) E(h) B(h+2) E(h)
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
A(h+1) C(h) A(h) C(h+1) A(h+1) C(h+1)变换1修复了情况1，即外部子树A比内部子树C高。
情况3，即A和C的高度都是h + 1，是不可能的，因为一次插入或删除操作只会影响其中一个子树；如果B太高，那是由A或C引起的，而不是两者同时。
情况2可以通过旋转B转化为情况1。
变换2：
B(h+2) C(h+2)
┌────┴────┐ rotate-left ┌────┴────┐
A(h) C(h+1) ─────────────► B(h+1) q(h)
┌──┴──┐ ┌──┴──┐
p(h) q(h) A(h) p(h)如果右子树更高，一次左旋转会使左子树变得更高。
C的子树p、q的高度不一定是h，其中一个可以是h - 1。然而，效果仍然是一样的，并且接下来的变换1仍然适用。这个可视化过程留给读者作为练习。
结论：有两种情况会导致子树高度差为2，通过一次或两次旋转可以修复。
10.5 AVL树的实际应用
基于不平衡二叉树，我们将添加AVL树的代码来修复不平衡的情况。
步骤1：树节点中的辅助数据
一个侵入式树节点（参考哈希表章节）不包含数据，除了AVL树使用的辅助数据，即子树高度。高度存储在节点中，无需遍历树来获取。
struct AVLNode {
AVLNode *parent = NULL; // 新增
AVLNode *left = NULL;
AVLNode *right = NULL;
uint32_t height = 0; // AVL树的辅助数据
};
inline void avl_init(AVLNode *node) {
node->left = node->right = node->parent = NULL;
node->height = 1;
}
static uint32_t avl_height(AVLNode *node) {
return node? node->height : 0;
}
static void avl_update(AVLNode *node) {
node->height = 1 + max(avl_height(node->left), avl_height(node->right));
}树的更新是自底向上的，所以高度变化会从子节点传播到父节点。
旁注：用2位存储高度差
确切的高度值并非必要，因为只使用高度差。只有3种有效的高度差，所以可以用2位来存储。
这2位可以存储在一个指针中，因为在主要平台上，malloc()分配的内存至少按8字节对齐，这意味着最低的3位是未使用的。
static uint8_t avl_get_height_diff(AVLNode *node) {
uintptr_t p = (uintptr_t)node->parent;
return p & 0b11; // 从最低有效位获取数据
}
static AVLNode *avl_get_parent(AVLNode *node) {
uintptr_t p = (uintptr_t)node->parent;
return (AVLNode *)(p & (~0b11)); // 清除最低有效位
}一些红黑树使用这种空间优化。我们不会为此烦恼，因为下一章会添加更多辅助数据，这使得这种优化变得没有意义。
步骤2：旋转
B D
┌─┴───┐ rotate-left ┌───┴─┐
a D ─────────────► B e
┌─┴─┐ ◄───────────── ┌─┴─┐
c e rotate-right a c没有父节点指针时，旋转操作很简单：
Node *rot_left(Node *node) {
Node *new_node = node->right;
Node *inner = new_node->left;
node->right = inner; // node -> inner
new_node->left = node; // new_node -> node
return new_node;
}为父节点指针和辅助数据添加几行代码：
static AVLNode *rot_left(AVLNode *node) {
AVLNode *parent = node->parent;
AVLNode *new_node = node->right;
AVLNode *inner = new_node->left;
// node <-> inner
node->right = inner;
if (inner) {
inner->parent = node;
}
// parent <- new_node
new_node->parent = parent; // 注意：可能为NULL
// new_node <-> node
new_node->left = node;
node->parent = new_node;
// 辅助数据
avl_update(node);
avl_update(new_node);
return new_node;
}旋转后的节点链接到父节点，但这里没有更新父节点到子节点的链接。这是因为旋转后的节点可能是没有父节点的根节点，只有调用者知道如何链接根节点，所以这个链接留给调用者处理。
步骤3：修复高度差为2的情况
变换1：如果左子树比右子树高2，并且左子树的左子树比左子树的右子树高，通过一次右旋转可以恢复平衡。
left-too-tall balanced
D(h+3) B(h+2)
┌────┴────┐ rotate-right ┌────┴────┐
B(h+2) E(h) ──────────────► A(h+1) D(h+1)
┌────┴────┐ ┌───┴───┐
A(h+1) C(h) C(h) E(h)变换2：如果右子树更高，一次左旋转会使左子树更高。
B(h+2) C(h+2)
┌────┴────┐ rotate-left ┌────┴────┐
A(h) C(h+1) ─────────────► B(h+1) q(h)
┌──┴──┐ ┌──┴──┐
p(h) q(h) A(h) p(h)static AVLNode *avl_fix_left(AVLNode *node) { // 左子树太高
if (avl_height(node->left->left) < avl_height(node->left->right)) {
node->left = rot_left(node->left); // 变换2
}
return rot_right(node); // 变换1
}rot_left()的结果赋值给父节点以完成双向链接。rot_right()的结果留给avl_fix_left()的调用者处理。
步骤4：插入或删除后修复不平衡
树的高度从更新的节点传播到根节点，在传播过程中修复任何不平衡。修复操作可能会改变根节点，所以返回根节点，因为数据结构不存储根指针。
// 对更新的节点调用：
// - 传播辅助数据。
// - 修复不平衡。
// - 返回新的根节点。
AVLNode *avl_fix(AVLNode *node) {
while (true) {
AVLNode **from = &node; // 在此处保存修复后的子树
AVLNode *parent = node->parent;
if (parent) {
// 将修复后的子树连接到父节点
from = parent->left == node? &parent->left : &parent->right;
} // 否则：保存到局部变量`node`
// 辅助数据
avl_update(node);
// 修复高度差为2的情况
uint32_t l = avl_height(node->left);
uint32_t r = avl_height(node->right);
if (l == r + 2) {
*from = avl_fix_left(node);
} else if (l + 2 == r) {
*from = avl_fix_right(node);
}
// 根节点，停止
if (!parent) {
return *from;
}
// 继续处理父节点，因为它的高度可能已改变
node = parent;
}
}avl_fix_*()的结果赋值给父节点以完成链接。如果没有父节点，直接返回新的根节点。
步骤5：分离节点：简单情况
对于分离只有一个孩子的节点的简单情况，只需用该孩子替换子树。但有了父节点指针后，代码行数会多很多：
// 分离一个最多有一个孩子的节点
static AVLNode *avl_del_easy(AVLNode *node) {
assert(!node->left ||!node->right); // 最多一个孩子
AVLNode *child = node->left? node->left : node->right; // 可以为NULL
AVLNode *parent = node->parent;
// 更新孩子的父节点指针
if (child) {
child->parent = parent; // 可以为NULL
}
// 将孩子连接到祖父节点
if (!parent) {
return child; // 移除根节点
}
AVLNode **from = parent->left == node? &parent->left : &parent->right;
*from = child;
// 重新平衡更新后的树
return avl_fix(parent);
}分离节点的父节点通过avl_fix()进行修复，并返回根节点。
步骤6：分离节点：困难情况
有两个孩子的困难情况：只需在node_detach()中添加父节点指针。
// 分离一个节点并返回树的新根节点
AVLNode *avl_del(AVLNode *node) {
// 有0个或1个孩子的简单情况
if (!node->left ||!node->right) {
return avl_del_easy(node);
}
// 找到后继节点
AVLNode *victim = node->right;
while (victim->left) {
victim = victim->left;
}
// 分离后继节点
AVLNode *root = avl_del_easy(victim);
// 与后继节点交换
*victim = *node; // left, right, parent
if (victim->left) {
victim->left->parent = victim;
}
if (victim->right) {
victim->right->parent = victim;
}
// 将后继节点连接到父节点，或更新根指针
AVLNode **from = &root;
AVLNode *parent = node->parent;
if (parent) {
from = parent->left == node? &parent->left : &parent->right;
}
*from = victim;
return root;
}结论：AVL树的API
对于侵入式树，一个通用的搜索函数可能没有必要，因为它太简单了。一个没有比较回调的自定义搜索函数更灵活且性能更好。我们的AVL树API只有两个函数：
- 1.
avl_fix()：在插入操作后，在父节点上调用以恢复平衡。 - 2.
avl_del()：分离一个节点。这意味着会调用avl_fix()。
一些伪代码展示如何使用它们：
void search_and_insert(
AVLNode **root, AVLNode *new_node, bool (*less)(AVLNode *, AVLNode *))
{
// 找到插入位置
AVLNode *parent = NULL; // 将新节点作为其孩子放置
AVLNode **from = root; // 将新节点放置在此处
for (AVLNode *node = *root; node; ) {
from = less(new_node, node)? &node->left : &node->right;
parent = node;
node = *from;
}
// 链接新节点
*from = new_node;
new_node->parent = parent;
// 修复更新的节点
*root = avl_fix(new_node);
}
AVLNode* search_and_delete(
AVLNode **root, int32_t (*cmp)(AVLNode *, void *), void *key)
{
for (AVLNode *node = *root; node; ) {
int32_t r = cmp(node, key);
if (r < 0) { // node < key
node = node->right;
} else if (r > 0) { // node > key
node = node->left;
} else { // 找到
*root = avl_del(node);
return node;
}
}
return NULL; // 未找到
}代码测试建议
- 1. 用代码生成测试用例。
- 2. 验证数据结构的属性和不变量。
- 3. 与参考数据结构（如
std::set）进行比较。
源代码：
