用C/C++构建自己的Redis——第五章、Redis中的AVL树实现
文章目录
前言
在Redis数据库中，有序集合是一种核心的数据结构，它允许存储具有关联分数的唯一元素。为了实现这种数据结构，Redis采用了AVL树，一种自平衡的二叉搜索树，以确保数据的快速插入、删除和查找操作。这一章我们将一起深入探讨AVL树在Redis有序集合中的应用，包括其节点定义、插入和删除操作、以及如何通过旋转操作保持树的平衡。此外，文章还将介绍如何通过一系列测试案例来验证AVL树的正确性和性能，确保其在实际应用中的可靠性。
原书链接：https://build-your-own.org/redis/
Redis为key-value存储，但是value的部分不仅仅是字节字符串，还可能是更为复杂的数据结构，如列表，哈希表和排序集。
一、键值对集查询概念
1.1 键值对集合查询
1.1.1 范围查询
一个由<score, name>组成的键值对集合有以下两种查询方式：
- 通过name进行查询，和Hashmap一样。
- 范围查询：得到一系列排序的<score, name>：
a. 查询最接近<score, name>的对，可以通过欧氏距离评判。
b. 从某个起始的对开始排序这些<score, name>。
1.1.2 排名查询
键值对集合还可以进行与排名相关的查询：
- 查询键值对的排名
- 根据排名查找键值对
- 查询从指定起始点的子集
1.1.3键值对集使用案例
假设你有一个使用键值对集合的得分表。
查找用户得分。
范围查询： 显示从给定分数开始的列表（分页）。
排名查询：
- 查找用户的排名。
- 查找具有给定排名的用户。
按偏移量而不是分数分页显示列表。
除了排名表，键值对集还可以对任何内容进行排序。假设你有一个按时间排序的帖子列表。您可以通过帖子 ID（名称）查找帖子时间（得分）。
范围查询： 列出从给定时间（分数）开始的帖子。
排名查询：
- 查找帖子在列表中的位置。
- 查找给定位置上的帖子 ID。
- 按偏移量而非时间分页。
- 分值是一个 64 位浮点数；如果排序键无法编码为分值，则可以使用名称来代替排序（固定分值）。
1.1.4 排序集的大 O
- 通过名称查找得分：通过哈希表查找 O(1)。
- 插入一对： O(log(n))。
- 范围查询： O(log(n)).
- 排名查询：
a. 查找数据对的排名： O(log(n))。
b. 按等级查找 O(log(n)).
c. 按偏移查询： O(log(offset))。 - 对于所有实用的排序数据结构，插入和查找的平均成本都是 O(log(n))。
在 SQL 中，由于按偏移量分页查询的成本为 O(偏移量)，因此应避免按偏移量分页查询。然而，这在 Redis 中是可行的，因为成本降低到了 O(log(offset))。
1.2 数据结构排序的复习
排序数组（Sorted Arrays）
- 排序数组 是最简单的排序数据结构。通过二分查找（bisect），可以在 (O(\log(n))) 时间内找到元素的位置，但更新操作（如插入或删除）需要 (O(n)) 时间，因此不够实用。
- LSM树：为了解决更新成本高的问题，可以通过先将更新操作缓存到一个小数组中，然后合并到主数组的方式来摊销更新成本。这种方法导致了LSM树（Log Structured Merge-tree）的产生，尽管它实际上并不是树形结构，并且很少用作内存中的数据结构。
- B+树：将数组分割成多个不重叠的部分可以降低更新成本。这是二叉树的扩展，即n-ary树。
树形数据结构（Tree Data Structures）
- 大多数其他排序数据结构都是树形的：
- 二叉树：包括AVL树（自平衡）、红黑树（自平衡）、Treap（随机化）、伸展树（需要随机访问模式）。
- n-ary树：包括Trie树、B树（自平衡）、跳表（随机化，层次化）。
通过随机性平衡（Balance By Randomness）
- 最简单的树结构是不平衡的二叉树，新节点简单地作为叶子添加，导致树可能不规则且很深。例如，插入一个单调序列后，树就变成了一个线性列表。
- 通过随机性影响树的形状：一种方法是使用随机性。如果随机插入和删除，树的平均深度是 (O(\log(n)))。
- 伸展树 使用查找的随机性，通过将目标节点旋转到根节点来改变树的形状。但是，它仅在最坏情况不重要时才可用，因为连续查找等常见使用模式可能会触发最坏情况。
- Treaps和跳表 比伸展树更好，因为它们的随机性是生成的。它们的最坏情况取决于运气，而不是使用模式。
高度平衡树（Height-Balanced Trees）
- 另一种使树实用的方法是通过某些不变性限制树的高度：
- 红黑树：节点非黑即红，从根到叶子的所有路径上的黑节点数量相同，没有两个连续的红节点。
- AVL树：两个子树的高度可以不同，但只能相差1。
- B树：所有叶子具有相同的高度（仅适用于n-ary树）。在最坏情况下，树的高度是 (O(\log(n)))。
这些数据结构的选择取决于特定应用的需求，如查找、插入和删除操作的频率和性能要求。
下面是对每种树的简要说明：
-
AVL树：
- 最坏情况时间复杂度：O(log(n))，表示在最坏的情况下，如查找、插入和删除操作的时间复杂度。
- 分支因子：2，表示每个节点最多有两个子节点。
- 是否使用随机化：No，AVL树不依赖于随机化来保持平衡。
- 实现难度：Medium，AVL树的实现相对中等难度。
-
RB树（红黑树）：
- 最坏情况时间复杂度：O(log(n))。
- 分支因子：2。
- 是否使用随机化：No。
- 实现难度：High，红黑树的插入和删除操作相对复杂。
-
Treap（树堆）：
- 最坏情况时间复杂度：O(n)，在最坏情况下，性能可能退化到线性时间。
- 分支因子：2。
- 是否使用随机化：Yes，Treap使用随机化来保持平衡。
- 实现难度：Low，Treap的实现相对简单。
-
Splay树（伸展树）：
- 最坏情况时间复杂度：O(n)。
- 分支因子：2。
- 是否使用随机化：Usage，Splay树通过访问模式的随机性来保持平衡。
- 实现难度：Low。
-
B树：
- 最坏情况时间复杂度：O(log(n))。
- 分支因子：n，B树是多路搜索树，每个节点可以有多个子节点。
- 是否使用随机化：No。
- 实现难度：High，B树的实现难度较高，通常用于数据库和文件系统。
-
Skip list（跳表）：
- 最坏情况时间复杂度：O(n)。
- 分支因子：n。
- 是否使用随机化：Yes，跳表通过随机化来选择层级，从而保持平衡。
- 实现难度：Medium。
伸展树（Splay树）由于最坏情况性能不佳，通常不作为通用数据结构，而是用于快速访问“热数据”。B树虽然概念简单，但实现起来并不简单，常用于磁盘存储，因为磁盘存储中使用二叉树是不切实际的。红黑树插入简单，但删除操作复杂且不明显，因此更倾向于使用更简单的AVL树。由于AVL树有界定的最坏情况性能且是最知名的，因此选择使用AVL树。
二、实现
2.1 二叉树的实现
搜索和插入
- 搜索：从根节点开始，如果目标值不在当前节点，则目标值要么在左子树，要么在右子树。搜索过程就是沿着树向下遍历，直到找到目标值或到达叶子节点。
- 插入：插入操作很简单，只需将新节点放置在搜索结束的位置。如果搜索结束于一个叶子节点，那么新节点就作为该叶子节点的子节点插入。
删除
- 删除叶子节点：这是最简单的情况，直接移除叶子节点即可。
- 删除内部节点：
- 如果右子树不为空：将该节点与其右子树中的后继节点（右子树中最左边的节点）交换，然后删除后继节点（位于较低位置的节点）。
- 如果右子树为空：返回左子树作为新的子树。
注意事项
- 删除过程是递归的，最终会结束，因为要删除的目标节点会越来越低。
- 叶子节点的情况是多余的，因为内部节点的情况也适用于叶子节点。
- 树是对称的，所以如果左右子树互换，操作也同样有效。
迭代
- 迭代：后继节点通常是右子树中最左边的节点，除非右子树为空，在这种情况下需要回溯到父节点。这就是为什么树节点包含父节点指针的原因。
- 但是，父节点指针并不是必需的，你也可以使用一个节点栈（路径）来代替，这样可以节省内存，但会使代码变得笨拙。
这些操作是二叉树数据结构的基础，无论是平衡二叉树（如AVL树）还是非平衡二叉树，这些基本操作都是相同的。
2.2 平衡二叉树
2.2.1 不变量：高度差仅1
AVL树是一种特殊的二叉树，它在插入和删除操作之后，会通过一些规则来修复树以保持平衡。
- 高度定义：子树的高度是指从根节点到最远叶子节点的最大距离。
- AVL树的规则：在AVL树中，任意节点的两个子树的高度差最多为1。
2.2.2 规则的统一性
AVL树的特点是，无论是插入还是删除操作，修复树不平衡的规则是相同的。这使得AVL树相对于红黑树（RB树）来说，实现起来更为简单。
2.2.3 旋转保持顺序
旋转操作可以改变子树的形状，但保持节点的顺序不变。文中提到了左旋转的一个示例：
- 左旋转示例：
- 假设有一个节点2，其右子节点是4，4的左右子节点分别是1和5。
- 左旋转操作后，4成为根节点，2成为4的左子节点，1成为4的左子节点，5成为2的右子节点。
旋转操作在AVL树中用于调整树的高度差，以保持树的平衡。插入或删除节点可能会使子树的高度变化，进而影响父节点的高度差，旋转操作可以将高度差恢复到最多为1的状态。
2 4
/ \ / \
1 4 ==> 2 5
/ \ / \
3 5 1 3
2.2.4 旋转调整高度
- 插入或删除节点：插入或删除节点会使得子树的高度发生变化，具体来说，会增加或减少1。
- 父节点高度差：这种变化可能会使得父节点的左右子树高度差达到2，这违反了AVL树的平衡条件（高度差不超过1）。
- 通过旋转恢复平衡：通过旋转操作，可以调整子树的高度，使得高度差恢复到1。
规则1：右旋转恢复平衡
- 条件1：左子树（B）比右子树深2个节点。
- 条件2：左子树的左子树（A）比左子树的右子树（C）更深。
2.2.5 右旋转操作示例
D (h+3) B (h+2)
/ \ / \
B (h+2) E (h) ==> A (h+1) D (h+1)
/ \ / \
A (h+1) C (h) C (h) E (h)
- 操作步骤：
- 将D的左子树B旋转到D的位置。
- 将B的右子树E变为D的右子树。
- 将B的左子树A变为D的左子树。
通过这个右旋转操作，可以使得树的高度差恢复到1，从而保持树的平衡。
这段内容描述的是AVL树的旋转规则，AVL树是一种自平衡二叉搜索树。在AVL树中，每个节点的左子树和右子树的高度最多相差1，如果插入或删除操作导致这个高度差超过1，就需要通过旋转来恢复平衡。
规则2（右旋转规则）：如果一个节点的左子树比右子树高2，并且左子树的左子树比右子树深，那么可以通过右旋转来恢复平衡。右旋转操作会使得右子树比左子树深，同时保持旋转后的高度不变。
右旋转的过程如下：
- 将节点D的左子树B提升为新的根节点。
- 将B的右子树E变为D的右子树。
- 将D变为B的左子树。
旋转前的结构是：
D (h+2)
/ \
B (h+1) E (h)
/ \
A (h-1) C (h)
右旋转后的结构变为：
B (h+2)
/ \
A (h-1) D (h+1)
\ / \
C (h) E (h)
左旋转的过程与右旋转过程相反。
修复不平衡：当插入或删除操作导致不平衡时，从初始节点开始，沿着树向上检查每个节点：
- 检查节点是否平衡（左右子树高度差是否为2）。
- 如果平衡，则停止。
- 如果规则1不适用（条件2不满足），则应用相反的旋转规则2。
- 应用规则1。
- 移动到父节点并重复上述步骤。
这个过程会一直进行，直到达到根节点或找到平衡的节点为止。通过这种方式，AVL树可以保持其平衡特性，确保查找、插入和删除操作的时间复杂度都是O(log n)。
2.3 平衡二叉树代码实现
2.3.1 步骤一：节点定义
struct AVLNode {
uint32_t depth = 0; // subtree height
uint32_t cnt = 0; // subtree size
AVLNode *left = NULL;
AVLNode *right = NULL;
AVLNode *parent = NULL;
};
static void avl_init(AVLNode *node) {
node->depth = 1;
node->cnt = 1;
node->left = node->right = node->parent = NULL;
}
AVL树是一种自平衡二叉搜索树，每个节点存储了子树的高度信息，以保持树的平衡。
-
子树高度存储：在AVL树的实现中，每个节点存储了其左子树和右子树的高度信息。这是实现AVL树最直观的方式，因为它直接反映了每个节点的子树高度。
-
高度差替代精确高度：然而，存储每个节点的确切高度并不是必须的。一些实现中，只存储子树高度的差值，而不是确切的高度。这样做的好处是节省空间，因为高度差的最大值只有1（在AVL树中，任何节点的左右子树高度最多相差1），所以只需要2位就可以表示。
-
指针位的利用：如果只需要2位来存储高度差，那么可以将这2位信息打包到指针中。在64位系统中，指针通常不会使用所有的位，因此可以将高度差信息存储在指针未使用的位中。这种优化可以减少内存的使用。
-
额外字段
cnt：尽管上述优化可以节省空间，但在这段代码的实现中，这种优化并不适用，因为每个节点还有一个额外的字段cnt。cnt字段用于存储以该节点为根的子树中节点的数量，这个信息在进行排名查询时非常有用。 -
辅助函数：为了更新和使用这些辅助数据（如子树的高度和大小），实现中提供了一些辅助函数。这些函数可以帮助维护节点的高度和计数信息，确保AVL树的平衡性。
static uint32_t avl_depth(AVLNode *node) {
return node ? node->depth : 0;
}
static uint32_t avl_cnt(AVLNode *node) {
return node ? node->cnt : 0;
}
// maintain the depth and cnt field
static void avl_update(AVLNode *node) {
node->depth = 1 + max(avl_depth(node->left), avl_depth(node->right));
node->cnt = 1 + avl_cnt(node->left) + avl_cnt(node->right);
}
2.3.1 步骤二：旋转
2 4
/ \ / \
1 4 ==> 2 5
/ \ / \
3 5 1 3
代码的分配情况：一部分用于执行树的旋转操作，另一部分用于维护树结构的其他信息。
static AVLNode *rot_left(AVLNode *node) {
AVLNode *new_node = node->right;
if (new_node->left) {
new_node->left->parent = node;
}
node->right = new_node->left; // rotation
new_node->left = node; // rotation
new_node->parent = node->parent;
node->parent = new_node;
avl_update(node);
avl_update(new_node);
return new_node;
}
static AVLNode *rot_right(AVLNode *node); // mirrored
2.3.1 步骤三：旋转规则
规则 1：右旋转恢复平衡
如果一个节点的左子树比右子树深2个节点，并且左子树的左子树比左子树的右子树深，那么执行右旋转可以恢复平衡。
具体操作如下：
- 将当前节点的左子节点提升为新的根节点。
- 原根节点成为新根节点的右子节点。
- 原根节点的左子节点（也就是新根节点的左子节点的右子节点）成为新根节点的左子节点。
这种旋转操作可以这样理解：原本不平衡的树形结构通过右旋转变成了一个更平衡的结构。
规则 2：左旋转
如果一个节点的右子树比左子树深1个节点，那么执行左旋转可以使左子树比右子树深，同时保持旋转后子树的高度不变。
具体操作如下：
- 将当前节点的右子节点提升为新的根节点。
- 原根节点成为新根节点的左子节点。
- 原根节点的右子节点（也就是新根节点的左子节点的左子节点）成为新根节点的右子节点。
这种旋转操作可以这样理解：原本不平衡的树形结构通过左旋转变成了一个更平衡的结构。
// the left subtree is too deep
static AVLNode *avl_fix_left(AVLNode *root) {
if (avl_depth(root->left->left) < avl_depth(root->left->right)) {
root->left = rot_left(root->left); // rule 2
}
return rot_right(root); // rule 1
}
2.3.1 步骤四：修复平衡
// fix imbalanced nodes and maintain invariants until the root is reached
static AVLNode *avl_fix(AVLNode *node) {
while (true) {
avl_update(node);
uint32_t l = avl_depth(node->left);
uint32_t r = avl_depth(node->right);
AVLNode **from = NULL;
if (AVLNode *p = node->parent) {
from = (p->left == node) ? &p->left : &p->right;
}
if (l == r + 2) {
node = avl_fix_left(node);
} else if (l + 2 == r) {
node = avl_fix_right(node);
}
if (!from) {
return node;
}
*from = node;
node = node->parent;
}
}
2.3.1 步骤五：删除
在二叉搜索树中，删除节点是一个相对复杂的过程，因为需要保持树的二叉搜索性质，即任何节点的左子树上的所有节点的值都小于该节点的值，右子树上的所有节点的值都大于该节点的值。删除操作分为两种情况：
-
如果右子树不为空：
- 交换节点：找到要删除节点的右子树中的后继节点（即右子树中最左侧的节点，也就是右子树中值最小的节点），将其与要删除的节点进行交换。
- 移除后继节点：由于后继节点没有左子节点（否则它就不会是后继节点），我们可以直接移除它。
-
如果右子树为空：
- 返回左子树：直接用左子树替代要删除的节点。
对于AVL树，这是一种自平衡的二叉搜索树，它在每次插入或删除操作后都会通过一系列的旋转操作来保持树的平衡。AVL树的平衡条件是任何节点的两个子树的高度差不能超过1。
avl_fix()：这是AVL树特有的操作，用于在插入或删除节点后调整树以保持其平衡。这个过程是非递归的，它会从被修改的节点开始，一直向上遍历到根节点，确保每个节点都满足AVL树的平衡条件。
// detach a node and returns the new root of the tree
static AVLNode *avl_del(AVLNode *node) {
if (node->right == NULL) {
// no right subtree, replace the node with the left subtree
// link the left subtree to the parent
AVLNode *parent = node->parent;
if (node->left) {
node->left->parent = parent;
}
if (parent) { // attach the left subtree to the parent
(parent->left == node ? parent->left : parent->right) = node->left;
return avl_fix(parent); // AVL-specific!
} else { // removing root?
return node->left;
}
} else {
// detach the successor
AVLNode *victim = node->right;
while (victim->left) {
victim = victim->left;
}
AVLNode *root = avl_del(victim);
// swap with it
*victim = *node;
if (victim->left) {
victim->left->parent = victim;
}
if (victim->right) {
victim->right->parent = victim;
}
if (AVLNode *parent = node->parent) {
(parent->left == node ? parent->left : parent->right) = victim;
return root;
} else { // removing root?
return victim;
}
}
}
2.3.1 步骤六：查询和插入
最后，作者介绍了AVL树的API包含两个主要函数：
avl_fix()：在插入操作后调用，用于修复树以保持其平衡。AVL树是一种自平衡二叉搜索树，它通过在插入或删除节点后进行一系列旋转操作来保持树的平衡，确保树的高度保持在对数级别。
avl_del()：用于删除一个节点，并在删除后调用avl_fix()来修复树。删除操作可能会破坏树的平衡，因此需要通过avl_fix()来恢复平衡。
三、测试
3.1设置测试
struct Data {
AVLNode node;
uint32_t val = 0;
};
struct Container {
AVLNode *root = NULL;
};
插入后修复
static void add(Container &c, uint32_t val) {
Data *data = new Data(); // allocate the data
avl_init(&data->node);
data->val = val;
AVLNode *cur = NULL; // current node
AVLNode **from = &c.root; // the incoming pointer to the next node
while (*from) { // tree search
cur = *from;
uint32_t node_val = container_of(cur, Data, node)->val;
from = (val < node_val) ? &cur->left : &cur->right;
}
*from = &data->node; // attach the new node
data->node.parent = cur;
c.root = avl_fix(&data->node);
}
在处理数据结构时，使用一个指向即将添加的节点的指针可以避免一个特殊情况，即在添加第一个节点时将其作为根节点添加。
搜索和删除
static bool del(Container &c, uint32_t val) {
AVLNode *cur = c.root;
while (cur) {
uint32_t node_val = container_of(cur, Data, node)->val;
if (val == node_val) {
break;
}
cur = val < node_val ? cur->left : cur->right;
}
if (!cur) {
return false;
}
c.root = avl_del(cur);
delete container_of(cur, Data, node);
return true;
}
3.2 验证树结构
static void avl_verify(AVLNode *parent, AVLNode *node) {
if (!node) {
return;
}
// verify subtrees recursively
avl_verify(node, node->left);
avl_verify(node, node->right);
// 1. The parent pointer is correct.
assert(node->parent == parent);
// 2. The auxiliary data is correct.
assert(node->cnt == 1 + avl_cnt(node->left) + avl_cnt(node->right));
uint32_t l = avl_depth(node->left);
uint32_t r = avl_depth(node->right);
assert(node->depth == 1 + max(l, r));
// 3. The height invariant is OK.
assert(l == r || l + 1 == r || l == r + 1);
// 4. The data is ordered.
uint32_t val = container_of(node, Data, node)->val;
if (node->left) {
assert(node->left->parent == node);
assert(container_of(node->left, Data, node)->val <= val);
}
if (node->right) {
assert(node->right->parent == node);
assert(container_of(node->right, Data, node)->val >= val);
}
}
与参考数据结构比较
static void extract(AVLNode *node, std::multiset<uint32_t> &extracted) {
if (!node) {
return;
}
extract(node->left, extracted);
extracted.insert(container_of(node, Data, node)->val);
extract(node->right, extracted);
}
static void container_verify(
Container &c, const std::multiset<uint32_t> &ref)
{
avl_verify(NULL, c.root);
assert(avl_cnt(c.root) == ref.size());
std::multiset<uint32_t> extracted;
extract(c.root, extracted);
assert(extracted == ref);
}
3.3 随机化测试用例
// random insertion
for (uint32_t i = 0; i < 100; i++) {
uint32_t val = (uint32_t)rand() % 1000;
add(c, val);
ref.insert(val);
container_verify(c, ref);
}
// random deletion
for (uint32_t i = 0; i < 200; i++) {
// omitted ...
}
仅仅使用随机数进行测试是不够的。因为随机测试可能难以触及低概率的错误，并且当出现错误时，随机生成的复杂（大型）测试案例可能会很难调试。
为了解决这个问题，作者建议采用更有针对性的测试方法：对于一个给定的树结构，尝试在所有可能的位置插入或删除元素。这种方法可以避免在随机测试中重复相同的测试案例。
具体来说，这种方法包括以下步骤：
-
创建一个给定大小的树：首先创建一个具有特定大小的树，但不包括将要插入或删除的特定值。
-
验证树的结构：在插入或删除之前，先验证当前树的结构是否正确。
-
在特定位置插入或删除：然后，在树中的特定位置插入或删除一个元素。
-
再次验证树的结构：插入或删除操作之后，再次验证树的结构是否仍然正确。
-
清理资源：测试完成后，释放树结构所占用的资源。
通过这种方法，可以更系统地测试树结构的各种可能状态，从而更容易发现和调试潜在的错误。这种方法特别适用于测试小型树，因为小型树的状态数量较少，更容易管理。
static void test_insert(uint32_t sz) {
// for each position in the tree
for (uint32_t val = 0; val < sz; ++val) {
Container c;
std::multiset<uint32_t> ref;
// create the tree of the given size
for (uint32_t i = 0; i < sz; ++i) {
if (i == val) {
continue;
}
add(c, i);
ref.insert(i);
}
container_verify(c, ref);
// insert into the position
add(c, val);
ref.insert(val);
container_verify(c, ref);
dispose(c);
}
}
如何通过从较小的树开始测试来简化调试过程，以及随机测试和有向测试案例的重要性。
-
从较小的树开始测试：
- 测试从较小的树开始，这样如果测试失败，失败的案例也较小，便于调试。
- 较小的树更容易理解和检查，因为它们包含的节点较少。
-
随机测试案例：
- 随机测试案例不能完全被有向测试案例替代，因为树的形状取决于插入顺序。
- 随机测试可以覆盖各种不同的插入顺序，有助于发现低概率的错误。
-
有向测试案例：
- 有向测试案例是指针对特定树结构的测试，例如尝试在所有可能的位置插入或删除节点。
- 这种方法可以避免随机测试中的重复测试，并且可以更系统地测试树的不同形状。
-
树的枚举：
- 可以尝试枚举每种树的形状或插入顺序，但这通常只对非常小的树可行。
- 对于较大的树，枚举所有可能的形状或插入顺序是不现实的。
总结
本文介绍了Redis中的有序集合数据类型，它使用AVL树实现，支持基于分数和名称的索引，以及范围和排名查询。文章详细解释了有序集合在各种用例中的应用，如排名和时间排序帖子列表。同时，还概述了不同的树形数据结构，重点介绍了AVL树的实现细节，包括节点定义、旋转规则、平衡调整和测试方法。
avl.cpp: https://build-your-own.org/redis/10/avl.cpp.htm
test_avl.cpp: https://build-your-own.org/redis/10/avl.cpp.htm