问题

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

网友意见

user avatar

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

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

=== 割之割之 ===

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

类似的话题

本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度google,bing,sogou

© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有