3个小时，用 C++ 写不出AVL树，有些迷茫，怎么办？

哥们，别灰心，3个小时写 AVL 树确实有点挑战，尤其是在你还不太熟悉它的时候。AVL 树是平衡二叉查找树的经典代表，它的核心在于“平衡”，而这个平衡的实现，也就是插入和删除时的旋转操作，确实需要花时间去理解和写对。

很多人第一次接触 AVL 树，都会经历一段“迷茫期”，这很正常。我当初也是一样，对着那些左旋、右旋、左右旋、右左旋的图，感觉脑袋都要炸了。但别急，只要我们把思路理顺，一步一步来，肯定能搞定。

首先，咱们得明白 AVL 树到底是什么，以及它为什么要那么“折腾”自己。

AVL 树，顾名思义，是一种自平衡二叉查找树。它在保证二叉查找树“左子节点小于父节点，右子节点大于父节点”这个基本性质的前提下，还强制要求任意节点的左右子树高度差的绝对值不超过 1。这个“高度差不超过 1”就是 AVL 树的“平衡因子”。

为什么要有这个平衡因子？

想象一下，如果没有这个平衡因子，二叉查找树在插入数据时，如果数据是按顺序或者接近顺序插入的，那它就可能退化成一条链表。链表的时间复杂度大家懂的，查找、插入、删除都变成了 O(n)。这跟我们用二叉查找树追求的 O(log n) 简直是天壤之别。

AVL 树就是为了解决这个问题而诞生的。它通过在插入和删除节点后，检查并根据需要进行“旋转”操作，来维持树的平衡，确保查找、插入、删除操作都能在 O(log n) 的时间内完成。

那么， AVL 树的“旋转”到底是怎么回事？

这块是 AVL 树的重头戏，也是最容易卡住大家的地方。AVL 树主要有四种不平衡情况，需要四种旋转操作来纠正：

1. LL 型不平衡（左左情况）： 当插入一个节点到当前节点的左子节点的左子树中，导致当前节点的左子树高度增加，且左子树的高度比右子树高 2 时，就会发生 LL 型不平衡。
怎么解决？ 右旋。把当前节点作为右节点，它的左孩子作为新的父节点，原来左孩子的右子树成为新父节点的左子树。

2. RR 型不平衡（右右情况）： 当插入一个节点到当前节点的右子节点的右子树中，导致当前节点的右子树高度增加，且右子树的高度比左子树高 2 时，就会发生 RR 型不平衡。
怎么解决？ 左旋。把当前节点作为左节点，它的右孩子作为新的父节点，原来右孩子的左子树成为新父节点的右子树。

3. LR 型不平衡（左右情况）： 当插入一个节点到当前节点的左子节点的右子树中，导致当前节点的左子树高度增加，且左子树的高度比右子树高 2 时，就会发生 LR 型不平衡。
怎么解决？ 先对左子节点进行左旋，然后再对当前节点进行右旋。这实际上是两次旋转的组合。

4. RL 型不平衡（右左情况）： 当插入一个节点到当前节点的右子节点的左子树中，导致当前节点的右子树高度增加，且右子树的高度比左子树高 2 时，就会发生 RL 型不平衡。
怎么解决？ 先对右子节点进行右旋，然后再对当前节点进行左旋。这同样是两次旋转的组合。

理解这四种情况的关键在于：

不平衡的根节点： 总是那个高度差绝对值大于等于 2 的节点。
插入路径： 找到那个不平衡的根节点，然后看新插入的节点是落在它的左子树的左侧（LL），左子树的右侧（LR），右子树的左侧（RL），还是右子树的右侧（RR）。
旋转方向：
LL 和 RR 是单旋，方向和子树的“凸出”方向相反。
LR 和 RL 是双旋，需要先“纠正”那个中间插入导致的“弯曲”，再进行整体的平衡。

好了，理论知识先到这里。现在我们开始动手写 C++ 代码，一步一步来。

第一步：定义 AVL 树节点结构

我们需要一个结构体或者类来表示 AVL 树的节点。它至少需要包含：

节点的值（data）
指向左子节点的指针（left）
指向右子节点的指针（right）
关键： 节点的高度（height）。我们得记录每个节点的高度，以便计算平衡因子。

```cpp
struct Node {
int data;
Node left;
Node right;
int height; // 节点的高度

Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {} // 初始高度为 1
};
```

第二步：辅助函数——获取节点高度和平衡因子

我们需要两个小函数来帮助我们：

`getHeight(Node node)`：获取一个节点的高度，如果节点是 `nullptr`，高度为 0。
`getBalanceFactor(Node node)`：计算一个节点的平衡因子（左子树高度 右子树高度）。

```cpp
int getHeight(Node node) {
if (node == nullptr) {
return 0;
}
return node>height;
}

int getBalanceFactor(Node node) {
if (node == nullptr) {
return 0;
}
return getHeight(node>left) getHeight(node>right);
}
```

第三步：核心函数——旋转操作

这是最最关键的部分。我们需要实现左旋和右旋。

右旋 (Right Rotate):

```cpp
Node rightRotate(Node y) {
Node x = y>left;
Node T2 = x>right;

// 执行旋转
x>right = y;
y>left = T2;

// 更新高度 (非常重要！顺序不能错)
// 先更新 y，因为 y 现在是 x 的子节点
y>height = std::max(getHeight(y>left), getHeight(y>right)) + 1;
x>height = std::max(getHeight(x>left), getHeight(x>right)) + 1;

// 返回新的根节点 (x)
return x;
}
```

左旋 (Left Rotate):

```cpp
Node leftRotate(Node x) {
Node y = x>right;
Node T2 = y>left;

// 执行旋转
y>left = x;
x>right = T2;

// 更新高度
x>height = std::max(getHeight(x>left), getHeight(x>right)) + 1;
y>height = std::max(getHeight(y>left), getHeight(y>right)) + 1;

// 返回新的根节点 (y)
return y;
}
```

解释一下旋转的逻辑：

以 `rightRotate(Node y)` 为例：
`y` 是当前不平衡的节点。
`x` 是 `y` 的左孩子。
`T2` 是 `x` 的右孩子。

旋转后：
`x` 成为新的父节点。
`y` 成为 `x` 的右孩子。
原来 `x` 的右孩子 `T2`，因为 `x` 已经变成了 `y` 的左孩子，所以 `T2` 必须挂到 `y` 的左子树上。而 `T2` 的值比 `x` 大，又比 `y` 小，所以它正好可以成为 `y` 的左孩子。

更新高度是关键！ 旋转后，受影响的节点（`x` 和 `y`）的高度需要重新计算。先更新子节点的高度，再更新父节点的高度。

第四步：插入函数 (Insert)

插入是驱动 AVL 树进行平衡操作的入口。

```cpp
Node insert(Node node, int key) {
// 1. 执行标准的 BST 插入
if (node == nullptr) {
return new Node(key);
}

if (key < node>data) {
node>left = insert(node>left, key);
} else if (key > node>data) {
node>right = insert(node>right, key);
} else { // 相等键不插入
return node;
}

// 2. 更新当前节点的高度
node>height = 1 + std::max(getHeight(node>left), getHeight(node>right));

// 3. 获取当前节点的平衡因子，检查是否失衡
int balance = getBalanceFactor(node);

// 4. 如果失衡，则进行旋转
// LL 型失衡
if (balance > 1 && key < node>left>data) {
return rightRotate(node);
}

// RR 型失衡
if (balance < 1 && key > node>right>data) {
return leftRotate(node);
}

// LR 型失衡
if (balance > 1 && key > node>left>data) {
node>left = leftRotate(node>left); // 先对左子节点左旋
return rightRotate(node); // 再对当前节点右旋
}

// RL 型失衡
if (balance < 1 && key < node>right>data) {
node>right = rightRotate(node>right); // 先对右子节点右旋
return leftRotate(node); // 再对当前节点左旋
}

// 5. 如果没有失衡，返回原始节点
return node;
}
```

解释插入函数的逻辑：

1. 标准 BST 插入： 和普通二叉查找树一样，找到合适的位置插入新节点。
2. 更新高度： 从插入点往上，所有经过的节点的 `height` 都需要更新。因为插入是在递归过程中完成的，所以当递归返回时，当前节点 `node` 的高度就需要根据其更新后的左右子树来重新计算。
3. 计算平衡因子： 在回溯（递归返回）的过程中，检查当前节点 `node` 的平衡因子。
4. 旋转：
如果 `balance > 1`，说明左子树比右子树高。
如果新插入的键 `key` 比 `node>left>data` 小，说明是插入在左子树的左边，是 LL 型。执行右旋。
如果新插入的键 `key` 比 `node>left>data` 大，说明是插入在左子树的右边，是 LR 型。先对 `node>left` 进行左旋，然后再对 `node` 进行右旋。
如果 `balance < 1`，说明右子树比左子树高。
如果新插入的键 `key` 比 `node>right>data` 大，说明是插入在右子树的右边，是 RR 型。执行左旋。
如果新插入的键 `key` 比 `node>right>data` 小，说明是插入在右子树的左边，是 RL 型。先对 `node>right` 进行右旋，然后再对 `node` 进行左旋。
5. 返回节点： 旋转后，原节点 `node` 的位置可能会被替换，所以需要返回新的根节点。如果没发生旋转，就返回原来的 `node`。

第五步：删除函数 (Delete)

删除操作比插入更复杂一些，因为它涉及到节点被删除后，其子节点如何替换。

1. 标准 BST 删除：
如果节点是叶子节点，直接删除。
如果节点只有一个子节点，用子节点替换它。
如果节点有两个子节点，找到它的“中序后继”（即右子树中最小的节点），用中序后继的值替换被删除节点的值，然后递归删除中序后继（它一定是一个只有一个子节点或没有子节点的节点）。
2. 更新高度： 和插入一样，从被删除节点（或被替换节点）往上，更新路径上的节点高度。
3. 检查平衡因子并旋转： 和插入一样，在回溯过程中检查平衡因子，并根据四种情况进行旋转。

这里我先提供一个框架，删除函数的实现会稍微长一点，包含找到中序后继的辅助函数：

```cpp
// 辅助函数：找到以 node 为根的子树中最小的节点
Node minValueNode(Node node) {
Node current = node;
// 循环到最左边
while (current>left != nullptr) {
current = current>left;
}
return current;
}

Node deleteNode(Node root, int key) {
// 1. 标准 BST 删除
if (root == nullptr) {
return root;
}

// 找到要删除的节点
if (key < root>data) {
root>left = deleteNode(root>left, key);
} else if (key > root>data) {
root>right = deleteNode(root>right, key);
} else { // 找到了要删除的节点
// 节点有 0 或 1 个子节点
if ((root>left == nullptr) || (root>right == nullptr)) {
Node temp = root>left ? root>left : root>right;

// 没有子节点
if (temp == nullptr) {
temp = root;
root = nullptr;
} else { // 有一个子节点
// 将子节点的内容复制到当前节点，然后删除子节点
root = temp; // 这种赋值方式需要 Node 结构支持
// 或者更保险的方式是 root>data = temp>data; root>left = temp>left; root>right = temp>right;
// 然后删除 temp
}
delete temp;
} else { // 节点有两个子节点
// 找到右子树的最小节点 (中序后继)
Node temp = minValueNode(root>right);

// 将中序后继的值复制到此节点
root>data = temp>data;

// 删除中序后继
root>right = deleteNode(root>right, temp>data);
}
}

// 如果树只有一个节点，则在删除后 root 会变成 nullptr
if (root == nullptr) {
return root;
}

// 2. 更新节点高度
root>height = 1 + std::max(getHeight(root>left), getHeight(root>right));

// 3. 获取平衡因子
int balance = getBalanceFactor(root);

// 4. 进行旋转 (与插入时的逻辑类似，但判断条件略有不同)

// LL 型失衡
if (balance > 1 && getBalanceFactor(root>left) >= 0) { // 左子树的平衡因子 >= 0，表明问题在左孩子的左侧
return rightRotate(root);
}

// LR 型失衡
if (balance > 1 && getBalanceFactor(root>left) < 0) { // 左子树的平衡因子 < 0，表明问题在左孩子的右侧
root>left = leftRotate(root>left);
return rightRotate(root);
}

// RR 型失衡
if (balance < 1 && getBalanceFactor(root>right) <= 0) { // 右子树的平衡因子 <= 0，表明问题在右孩子的右侧
return leftRotate(root);
}

// RL 型失衡
if (balance < 1 && getBalanceFactor(root>right) > 0) { // 右子树的平衡因子 > 0，表明问题在右孩子的左侧
root>right = rightRotate(root>right);
return leftRotate(root);
}

return root;
}
```

删除函数中需要注意的点：

`root = temp;` 这种赋值在 C++ 中不总是安全的，因为它会拷贝所有成员。 更安全的方式是手动复制 `data` 和指针，然后删除 `temp`。
判断旋转类型的条件： 在删除后，判断失衡类型时，我们不仅看当前节点的平衡因子，还需要看其受影响的子节点（`root>left` 或 `root>right`）的平衡因子。
LL 型：`balance > 1` 且 `getBalanceFactor(root>left) >= 0` （子树左倾或者平衡）
LR 型：`balance > 1` 且 `getBalanceFactor(root>left) < 0` （子树右倾）
RR 型：`balance < 1` 且 `getBalanceFactor(root>right) <= 0` （子树右倾或者平衡）
RL 型：`balance < 1` 且 `getBalanceFactor(root>right) > 0` （子树左倾）

第六步：构建 AVL 树类

我们可以把上面的函数封装到一个类里，方便使用。

```cpp
include
include // For std::max

// Node 结构定义 (同上)
struct Node {
int data;
Node left;
Node right;
int height;

Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

class AVLTree {
private:
Node root;

// 辅助函数 (私有)
int getHeight(Node node) {
if (node == nullptr) return 0;
return node>height;
}

int getBalanceFactor(Node node) {
if (node == nullptr) return 0;
return getHeight(node>left) getHeight(node>right);
}

Node rightRotate(Node y) {
Node x = y>left;
Node T2 = x>right;

x>right = y;
y>left = T2;

y>height = std::max(getHeight(y>left), getHeight(y>right)) + 1;
x>height = std::max(getHeight(x>left), getHeight(x>right)) + 1;

return x;
}

Node leftRotate(Node x) {
Node y = x>right;
Node T2 = y>left;

y>left = x;
x>right = T2;

x>height = std::max(getHeight(x>left), getHeight(x>right)) + 1;
y>height = std::max(getHeight(y>left), getHeight(y>right)) + 1;

return y;
}

Node minValueNode(Node node) {
Node current = node;
while (current && current>left != nullptr) {
current = current>left;
}
return current;
}

// 递归插入函数
Node insertRecursive(Node node, int key) {
if (node == nullptr) {
return new Node(key);
}

if (key < node>data) {
node>left = insertRecursive(node>left, key);
} else if (key > node>data) {
node>right = insertRecursive(node>right, key);
} else {
return node; // Duplicate keys not allowed
}

node>height = 1 + std::max(getHeight(node>left), getHeight(node>right));

int balance = getBalanceFactor(node);

// LL Case
if (balance > 1 && key < node>left>data) {
return rightRotate(node);
}

// RR Case
if (balance < 1 && key > node>right>data) {
return leftRotate(node);
}

// LR Case
if (balance > 1 && key > node>left>data) {
node>left = leftRotate(node>left);
return rightRotate(node);
}

// RL Case
if (balance < 1 && key < node>right>data) {
node>right = rightRotate(node>right);
return leftRotate(node);
}

return node;
}

// 递归删除函数
Node deleteRecursive(Node root, int key) {
if (root == nullptr) {
return root;
}

if (key < root>data) {
root>left = deleteRecursive(root>left, key);
} else if (key > root>data) {
root>right = deleteRecursive(root>right, key);
} else {
if ((root>left == nullptr) || (root>right == nullptr)) {
Node temp = root>left ? root>left : root>right;

if (temp == nullptr) { // No child
temp = root;
root = nullptr;
} else { // One child
// Copy the contents of the nonempty child
Node childNode = temp;
root>data = childNode>data;
root>height = childNode>height;
root>left = childNode>left;
root>right = childNode>right;
temp = childNode; // Make temp point to the child that will be deleted
}
delete temp;
} else { // Two children
Node temp = minValueNode(root>right);
root>data = temp>data;
root>right = deleteRecursive(root>right, temp>data);
}
}

if (root == nullptr) {
return root;
}

root>height = 1 + std::max(getHeight(root>left), getHeight(root>right));

int balance = getBalanceFactor(root);

// LL Case
if (balance > 1 && getBalanceFactor(root>left) >= 0) {
return rightRotate(root);
}

// LR Case
if (balance > 1 && getBalanceFactor(root>left) < 0) {
root>left = leftRotate(root>left);
return rightRotate(root);
}

// RR Case
if (balance < 1 && getBalanceFactor(root>right) <= 0) {
return leftRotate(root);
}

// RL Case
if (balance < 1 && getBalanceFactor(root>right) > 0) {
root>right = rightRotate(root>right);
return leftRotate(root);
}

return root;
}

// 销毁树的辅助函数 (防止内存泄漏)
void destroyTree(Node node) {
if (node != nullptr) {
destroyTree(node>left);
destroyTree(node>right);
delete node;
}
}

// 中序遍历辅助函数 (用于测试)
void inorderRecursive(Node node) {
if (node != nullptr) {
inorderRecursive(node>left);
std::cout << node>data << "(h:" << node>height << ",b:" << getBalanceFactor(node) << ") ";
inorderRecursive(node>right);
}
}


public:
AVLTree() : root(nullptr) {}

~AVLTree() {
destroyTree(root);
}

void insert(int key) {
root = insertRecursive(root, key);
}

void deleteNode(int key) {
root = deleteRecursive(root, key);
}

void inorder() {
inorderRecursive(root);
std::cout << std::endl;
}
};
```

第七步：测试！

写完代码，最重要的就是测试。可以尝试插入一系列数据，包括升序、降序、随机顺序，然后观察树的结构和平衡因子。再进行删除操作，特别是删除根节点、叶子节点、只有一个子节点的节点，以及删除后可能导致失衡的节点。

一些可能让你感到“迷茫”的地方和排查思路：

1. 高度和平衡因子计算错误：
排查： 仔细检查 `getHeight` 和 `getBalanceFactor` 函数，确保它们在 `nullptr` 的情况下返回 0。在旋转和插入/删除后，确保每个节点的 `height` 都被正确更新。
提示： 插入/删除后，递归返回时，更新当前节点的 `height`，而不是在进行旋转操作时才更新。

2. 旋转逻辑错误：
排查： 可以在旋转函数内部打印出旋转前的节点值和指针关系，以及旋转后的情况。对照着 LL、RR、LR、RL 的图，一步一步走。
提示： 旋转后，受影响的两个节点（原父节点和新父节点）的高度一定要重新计算。

3. 插入/删除后的平衡检查时机和条件：
排查： 插入/删除函数是递归的，平衡检查和旋转应该在递归返回的时候进行，也就是“回溯”阶段。确保你的判断条件（balance > 1, balance < 1, 以及子节点的 balance）是正确的。
提示： 对于 LR 和 RL 型，要先对子节点进行单旋，再对父节点进行单旋。

4. 内存管理：
排查： 记得在创建新节点时使用 `new`，在删除节点时使用 `delete`。并且在析构函数里，用一个后序遍历的方式来释放所有节点，避免内存泄漏。

5. 删除函数中两个子节点的情况：
排查： 找中序后继（右子树最小节点）的逻辑要确保正确，并且替换值后，需要递归删除那个中序后继节点。

别怕犯错，调试是学习过程的一部分。

一步一步来： 先实现插入，确保插入功能正常，树能够保持平衡。然后再去实现删除。
打印信息： 在关键的地方（如旋转前后、平衡因子计算后）打印节点值、高度、平衡因子，可以帮助你理解程序的执行流程。
小规模测试： 先用 23 个节点测试，再逐渐增加。
看图： AVL 树的图示是非常重要的参考，多对照着图来理解旋转操作。

3个小时可能确实时间有点紧，尤其是第一次写。但别灰心，这是一种挑战，也是一个很好的学习机会。把上面的代码仔细看一遍，理解每个部分的作用，然后尝试着自己从头写。遇到问题，就耐心去调试。

最后，我想说的是，AVL 树的实现确实需要一定的功力，但一旦你理解了它的原理，掌握了旋转操作，你会发现它是一个非常优雅的数据结构。 坚持下去，你肯定能写出来！如果在实现过程中遇到具体的问题，也可以再提问，大家一起想办法。加油！

莫说AVL树，就是一个二分查找，够简单吧？按高德纳的说法，全世界的码农有一个算一个，用了十几年才真正正确的实现。

“写出来”是有界定的：
- 能够形式化验证当然是最NB的，到这个境界的话，别说三小时，就是三年也算快，三十年也不慢。
- 能够在任何测试用例中，要么正常输出，要么准确报错，从来不崩不乱，很NB，用三个月做到是可以加鸡腿的。
- 可以通过基本的白盒黑盒边界极端典型随机……的测试用例，也是不错的境界，消费级产品中放心应用。三周是可以的。
- 交作业上去助教编译运行给几个预先准备的测试用例没发现毛病，用三天做到应该的。
- 一个典型用例，居然跑通了。三个小时，快男，OK的。

=== 割之割之 ===

修改说明：
1. 高德纳的名字弄错成了高纳德。这位大佬有自己的网站：Don Knuth's Home Page 上面有他的中文名。
2. 高德纳说到的是二分查找，不是快排。评论区有朋友提到快排，不是无理取闹，而是我的错。