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