在平衡中追寻高度：探秘AVL树的自我调节之美

---

前言

继上篇C++探索之旅：打造高效二叉搜索树的奥秘与实践，我们继续探讨二叉搜索树的PLUS版——AVL树
在数据结构的世界里，树木生长的过程并非一帆风顺。如何在高度与平衡间取得微妙的和谐？AVL树，这个优雅的自平衡二叉搜索树，便是自然之道的程序化呈现。它在每次插入与删除中，仿佛有一双看不见的手，悄然调整，维持着一种动态的平衡，使得查找效率始终如一。本文将带您深入探究AVL树的构造、平衡因子、旋转操作，让每一行代码都成为追寻平衡的过程。

---

🎓一、AVL树的概念

AVL树的概念可以从以下几个方面进行阐述：

1.1 定义与性质

AVL树是一种自平衡二叉查找树，它的任何节点的两个子树的高度最大差别为1，因此也被称为高度平衡树。AVL树的增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G.M. Adelson-Velsky和E.M. Landis。AVL树具有二叉查找树的全部特性，每个节点的左子树的高度和右子树高度差值小于等于1。左旋是AVL树中的一种操作，它是逆时针旋转两个节点，原先的右节点成为新的父节点，原先的父节点成为原先的右节点的左子节点。右旋是左旋的镜像操作。AVL树的查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。

1.2 平衡因子

在AVL树中，每个节点都有一个平衡因子（Balance Factor），它表示该节点的右子树高度减左子树高度的差。平衡因子的值可以是**-1、0或1**。当插入或删除节点导致某个节点的平衡因子超出这个范围时，就需要进行旋转操作来恢复树的平衡。

• 如果一颗二叉搜索树是高度平均的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O ( log2ⁿ )，搜索时间复杂度为 O(log2ⁿ )。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0，这是做不到的，以两个结点为例，根节点的平衡因子只可能是 1 或者 -1，不可能是 0。二叉搜索树在实际中基本不太可能实现完全平衡，但是理论上可以，即满二叉树。后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。

1.3 旋转操作

AVL树的平衡是通过四种旋转操作来实现的：

1. 左旋转（Left Rotation）：当某个节点的右子树高度较高时，通过左旋转来降低右子树的高度。
2. 右旋转（Right Rotation）：当某个节点的左子树高度较高时，通过右旋转来降低左子树的高度。
3. 左右旋转（Left-Right Rotation）：当某个节点的左子树的右子树高度较高时，通过先对左子树进行左旋转，再对根节点进行右旋转来调整树的平衡。
4. 右左旋转（Right-Left Rotation）：当某个节点的右子树的左子树高度较高时，通过先对右子树进行右旋转，再对根节点进行左旋转来调整树的平衡。

🎓二、AVL 树结点的定义

template<class K, class V>
class AVLTreeNode {
public:pair<K, V> _kv;				//存储key和valueAVLTreeNode<K, V>* left;	//指向左孩子AVLTreeNode<K, V>* right;	//指向右孩子AVLTreeNode<K, V>* _parent;	//指向父亲结点int bf = 0;				// 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),left(nullptr),right(nullptr),_parent(nullptr){}
};

🎓三、AVL 树的框架

template<class K, class V>
class AVLTree{typedef AVLTreeNode<K, V> Node;typedef pair<K, V> pr;
public:// ...成员函数
private:Node* _root = nullptr;
};

🎓四、AVL 树的插入

AVL 树就是在二叉搜索树的基础上引入平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点。

2. 调整结点的平衡因子。

4.1 平衡因子的更新

新结点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了 AVL 树的平衡性。假设新插入的结点为 cur，那么 cur 的平衡因子一定是 0，因为它的左后孩子都是 nullptr。但是 cur 的双亲结点 parent 的平衡因子一定需要调整，在插入之前，parent 的平衡因子分为三种情况：-1、0、1。对 parent 平衡因子的调整分为以下两种情况：

• 如果 cur 插入到 parent 的左侧，只需要给 parent 的平衡因子 − 1 即可。

• 如果 cur 插入到 parent 的右侧，只需要给 parent 的平衡因子 + 1 即可。

此时更新后 parent 的平衡因子有以下三种情况：0 、± 1 、± 2

• 如果 parent 的平衡因子为 0 ，说明插入前 parent 的平衡因子一定为 ± 1 ，即左右孩子中一定有一个是 nullptr，并且新结点就插入在为空的一侧，插入后平衡因子被调整成 0 ，整棵树的高度任然不变，满足 AVL 树的性质，插入成功。
  

• 如果 parent 的平衡因子是 ± 1 ，说明插入前 parent 的平衡因子一定是 0 ，即插入前 parent 的左右孩子都为 nullptr，并未新结点就插入在 parent 的任意一侧，所以插入后平衡因子被调整成了 ± 1 ，此时以 parent 为根的树的高度增加了，需要继续沿着祖先结点向上更新，知道某一个祖先节点的平衡因子变成了 0 ，此时更新结束，插入成功。
  

• 如果 parent 的平衡因子为 ± 2 ，则 parent 的平衡因子违反了平衡树的性质，需要对其进行旋转处理。
  

4.2 AVL 树的旋转

如果在一颗原本是平衡的 AVL 树中插入一个新结点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据结点插入位置的不同，AVL 树的旋转分为四种：

4.2.1 左单旋

新结点插入在较高右子树的右侧----右右：即 parent 的平衡因子是 2，cur 的平衡因子是 1 ，此时就需要左单旋。下面举两个左单旋的例子。

无论是这四种旋转中的哪一个，都要保证以下两点：首先在旋转的过程中要保证这棵树是搜索树，其次经过旋转后，这棵树应该变成平衡树，且降低这个子树的高度。这两点就决定了左旋的核心操作就是将 cur 的左子树给 parent 的右子树，再让 parent 成为 cur 的左子树。

void RotateL(Node* parent) {// cur为parent的右子节点，将要成为新父节点Node* cur = parent->right;// cur的左子节点（可能为空），会变为parent的右子节点Node* curleft = cur->left;// 将parent的右子节点更新为cur的左子节点parent->right = curleft;// cur的左子节点更新为parent，完成旋转cur->left = parent;// 如果cur有左子节点，更新其父节点为parentif (curleft) curleft->_parent = parent;// 保存parent的父节点ppnode，旋转后cur成为新的父节点Node* ppnode = parent->_parent;parent->_parent = cur;// 如果parent是根节点，更新根节点为curif (parent == _root) {_root = cur;cur->_parent = nullptr; // cur成为新的根节点，父节点为空} // 否则更新ppnode的子节点指针else {// 如果parent是ppnode的左子节点，更新ppnode的左子节点为curif (ppnode->left == parent) ppnode->left = cur;// 如果parent是ppnode的右子节点，更新ppnode的右子节点为curelse ppnode->right = cur; // cur的父节点更新为ppnodecur->_parent = ppnode;}// 旋转后更新parent和cur的平衡因子parent->bf = cur->bf = 0;
}

4.2.2 右单旋

新结点插入在较高左子树的右侧----左左：即 parent 的平衡因子是 2，cur 的平衡因子是 1 ，此时就需要右单旋。下面举出右单旋的抽象图。

void RotateR(Node* parent) {Node* cur = parent->left;Node* curright = cur->right;parent->left = curright;cur->right = parent;if(curright) curright->_parent = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root) {_root = cur;cur->_parent = nullptr;}else {if (ppnode->left == parent) ppnode->left = cur;else ppnode->right = cur;cur->_parent = ppnode;}parent->bf = cur->bf = 0;
}

4.2.3 右左双旋

下面以三种情况探讨右左双旋的奥秘。

代码片段：

void RotateRL(Node* parent) {Node* cur = parent->right;Node* curleft = cur->left;int bf = curleft->bf;RotateR(parent->right);RotateL(parent);if (bf == 0) {cur->bf = curleft->bf = parent->bf = 0;}else if (bf == -1) {cur->bf = 1;curleft->bf = parent->bf = 0;}else if (bf == 1) {parent->bf = 1;curleft->bf = cur->bf = 0;}else assert(false);
}

4.2.4 左右双旋

下面以三种情况探讨左右双旋的奥秘。

代码片段：

void RotateLR(Node* parent) {Node* cur = parent->left;Node* curright = cur->right;int bf = curright->bf;RotateL(parent->left);RotateR(parent);if (bf == 0) {cur->bf = parent->bf = curright->bf = 0;}else if (bf == -1) {parent->bf = -1;cur->bf = curright->bf = 0;}else if (bf == 1) {cur->bf = -1;curright->bf = parent->bf = 0;}else assert(false);
}

4.3 插入过程的完整代码

bool insert(const pr& kv) {if (!_root) {_root = new Node(kv);return true;}// 定义当前节点curNode* cur = _root;Node* parent = nullptr;while (cur) {if (cur->_kv.first < kv.first) {parent = cur;cur = cur->right;}else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->left;}else return false; // 不可能出现相等的情况插入}// 创建新的Node实例cur，并将它插入到适当的位置cur = new Node(kv);if (parent->_kv.first < kv.first) {parent->right = cur;}else {parent->left = cur;}cur->_parent = parent;// ... 控制平衡// 更新平衡因子while (parent) {//更新平衡因子if (cur == parent->left) {--(parent->bf);}else /*if (cur == parent->right)*/ {++(parent->bf);}if (parent->bf == 0) break;else if (parent->bf == -1 || parent->bf == 1) {// 继续往上更新cur = parent;parent = parent->_parent;}else if (parent->bf == -2 || parent->bf == 2){//需要旋转//左单旋if (cur->bf == 1 && parent->bf == 2) {RotateL(parent);}//右单旋else if (cur->bf == -1 && parent->bf == -2) {RotateR(parent);}//右左单旋else if (cur->bf == -1 && parent->bf == 2) {RotateRL(parent);}//左右单旋else if (cur->bf == 1 && parent->bf == -2) {RotateLR(parent);}break;}else assert(false);}return true;
}

4.4 检查平衡

AVL 树是在二叉搜索树的基础上加入了平衡的限制，因此要验证 AVL 树，可以分为两步：

• 验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列，就说明为二叉搜索树。

• 验证其为平衡树。每个结点左右子树高度差的绝对值不超过1。其次检查结点的平衡因子是否计算正确。

// 返回树的高度
int Height(Node* root) {if (!root) return 0;int leftHeight = Height(root->left);int rightHeight = Height(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}// 调用检查平衡因子的函数
bool isBalance() {return isBalance(_root);
}// 检查平衡因子
bool isBalance(Node* root){if (!root) return true;int leftHeight = Height(root->left);int rightHeight = Height(root->right);if (rightHeight - leftHeight != root->bf){cout << "平衡因子异常:" << root->bf << endl;return false;}return abs(leftHeight - rightHeight) < 2&& isBalance(root->left)&& isBalance(root->right);
}// 中序遍历
void inOrder(Node* root) {if (!root) return;inOrder(root->left);cout << root->_kv.first << " ";inOrder(root->right);
}// 调用中序遍历的函数
void inOrder() {return inOrder(_root);
}

• 注意：这里函数名相同却能成功调用的原因是构成了函数重载

测试代码：

#include "AVLTree.h"int main() {int a[] = { 16,23,5,7,8,6,9,14 };AVLTree<int, int> t;for (auto e : a) {t.insert(make_pair(e, e));t.inOrder();cout << endl;if (t.isBalance()) {cout << "插入成功" << endl;}else {cout << "插入失败" << endl;}}return 0;
}

输出：

🎓五、AVL 树的删除

因为 AVL 树也是二叉搜索树，可以按照二叉搜索树的方式将结点删除，然后再更新平衡因子，只不过与删除插入不同的是，删除结点后的平衡因子更新，最差情况下一直要调整到根结点的位置。具体的实现感兴趣的小伙伴可以参考《算法导论》或者《数据结构-用面向对象方法与C++描述》殷人昆版。

🎓六、AVL 树的性能

AVL 树是一颗绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过1，这样在查询时可以保证高效的时间复杂度，即O(log2ⁿ)。但是如果要对 AVL 树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑 AVL 树，但一个结构经常修改，就不太适合。

---

结语

AVL树向我们展示了一个动态平衡的世界，在每次操作后依旧屹立如初。它提醒我们，即使不断变化，也可以通过智慧与设计找到一种持久的稳定。愿这篇文章成为您在数据结构之路上的一盏灯，带您窥见代码背后那精妙的平衡哲学。

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！