C++: AVL树（实现旋转操作）

前言

map/set容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，有了AVL树。

（一）AVL树介绍

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis

在1962年发明了一种解决上述问题的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

（1）AVL树的概念

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

        -它的左右子树都是AVL树

        -左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

平衡因子=右子树的高度-左子树的高度。

平衡因子是一个存在于二叉树中的变量

（实现AVL树不一定需要引入平衡因子，可以计算右子树高度和左子树高度差进行平衡比较）

1.新增结点在左，parent平衡因子减减
2、新增在右，parent平衡因子加加
3、更新后parent平衡因子==0，说明parent所在的子树的高度不变，不会再影响祖先，不用再继续沿着到root的路径往上更新
4、更新后parent平衡因子=1 or -1，说明parent所在的子树的高度变化，会再影响祖先，需要继续沿着到root的路径往上更新
5、更新后parent平衡因子==2or-2，说明parent所在的子树的高度变化且不平衡，对parent所在子树进行旋转，让他平衡

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 log(n),搜索时间复杂度O(logN)。

（二）AVL树的实现

这里我通过引入平衡因子来进行AVL树的旋转操作。

（1）AVL树节点的定义

数据存放在pair中：

pair是一种STL中的类，该类将一对不同类型的值(T1和T2)耦合在一起。单个值可以通过它的公共成员first和second来访问。

key和value：

key是存取时进行比较大小的标准，val是key对应的值。他们是一组键值对pair{key，val}，key和val可以是相同的类型，也可以是不同的。

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode(const pair<K, V>& kv = pair<K,V>()): _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}AVLTreeNode<K, V>* _left;    // 该节点的左孩子AVLTreeNode<K, V>* _right;	// 该节点的右孩子AVLTreeNode<K, V>* _parent; // 该节点的双亲pair<K, V> _kv;    //数据存在与pair中int _bf;   // 节点的平衡因子 balance factor
};

（2）AVL树的旋转

AVL树的旋转总结来说一共右四种情况，分别是：左单旋，右单旋，左右双旋，右左双旋。

只有当平衡因子 = 2 或者 -2 时，才需要进行旋转平衡）

（i）左单旋（新节点插入较高右子树的右侧）

       当插入节点在c的节点上时，进行左旋。（不能在a或者b中，这样不是左单旋）

parent的平衡因子为2，cur的平衡因子为1。

如何进行左单旋的旋转操作？

i.将parent的right指向curleft，curleft的父亲改为parent（需要判断curleft是否为空）。

ii. 将parent的parent记录下来(Pparent)，因为parent上面可能还有节点。

iii. cur的left指向parent，然后将parent的parent指向cur。

iiii. 判断Pparent是否为空，若为空则将cur的parent指向空。

若Pparent不为空，则需要判断原先的parent是Pparent的左孩子还是右孩子，将Pparent的左孩子（或者右孩子）指向cur。

iiiii. 最后要修改cur和 parent的平衡因子为 0；

代码如下：

	void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}Node* Pparent = parent->_parent;cur->_left = parent;parent->_parent = cur;if (Pparent == nullptr){cur->_parent = nullptr;}else //父亲的父亲不是空{if (Pparent->_kv.first < cur->_kv.first){Pparent->_right = cur;}else{Pparent->_left = cur;}cur->_parent = Pparent;}cur->_bf = parent->_bf = 0;}

（ii）右单旋（新节点插入较高左子树的左侧）

        当插入节点在a的节点上时，进行右旋。（不能在b或者c中，这样不是左单旋）

parent的平衡因子为-2，cur的平衡因子为-1。

如何进行右单旋的旋转操作？

        i.将parent的left指向curright，curright的父亲改为parent（需要判断curright是否为空）。

ii. 将parent的parent记录下来(Pparent)，因为parent上面可能还有节点。

iii. cur的right指向parent，然后将parent的parent指向cur。

iiii. 判断Pparent是否为空，若为空则将cur的parent指向空。

若Pparent不为空，则需要判断原先的parent是Pparent的左孩子还是右孩子，将Pparent的左孩子（或者右孩子）指向cur。

iiiii. 最后要修改cur和 parent的平衡因子为 0；

代码如下：

void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright){curright->_parent = parent;}Node* Pparent = parent->_parent;cur->_right = parent;parent->_parent = cur;if (Pparent == nullptr){cur->_parent = nullptr;}else{if (Pparent->_kv.first < cur->_kv.first){Pparent->_right = cur;}else{Pparent->_left = cur;}cur->_parent = Pparent;}cur->_bf = parent->_bf = 0;
}

（iii）右左双旋（新节点插入较高右子树的左侧）

        当插入节点在b或c的节点上时，进行右左旋。

        parent的平衡因子为2，cur的平衡因子为-1。

如何进行右左双旋的旋转操作？

i.对cur所在树进行右旋操作。

ii. 再对parent所在树进行左旋操作。

需要注意的是我的左右旋操作都会将平衡因子改为 0，所以需要将行旋转后需要修改平衡因子：

（1）若插入的地方为c时，即curleft的平衡因子为 1 时，由于右旋操作，已经将c连接到了cur的左孩子上，（此时cur的左右孩子高度相同）所以此时cur平衡因子为0，而b 经过左旋被连接到了parent的右孩子上（此时parent的左孩子高度比右孩子高1），此时parent的平衡因子为-1。

（2）若插入的地方为b时，同理可知，此时parent的平衡因子为 0，cur的平衡因子为1。

代码如下：

	void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;  //记录bf的值RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curleft->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;curleft = 0;}else if (bf == -1){parent->_bf = 0;cur->_bf = 1;curleft->_bf = 0;}}

（iiii）左右双旋（新节点插入较高左子树的右侧）

当插入节点在b或c的节点上时，进行左右旋。

parent的平衡因子为-2，cur的平衡因子为1。

如何进行左右双旋的旋转操作？

i.对cur所在树进行左旋操作。

ii. 再对parent所在树进行右旋操作。

需要注意的是我的左右旋操作都会将平衡因子改为 0，所以需要将行旋转后需要修改平衡因子：

（1）若插入的地方为c时，即curright的平衡因子为 1 时，由于左旋操作b连接到了cur的右孩子上，（此时cur的左孩子高度比右孩子高1）所以此时cur平衡因子为-1，而c 经过右旋被连接到了parent的左孩子上（此时parent的左右孩子高度相同），此时parent的平衡因子为0。

（2）若插入的地方为b时，同理可知，此时parent的平衡因子为 1，cur的平衡因子为0。

代码如下：

	void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}}

（3） AVL树的插入

AVL树的插入过程分为两个步骤：

（1）与普通二叉树相同的插入操作；

（2）调整节点的平衡因子，根据平衡因子，判断是否要进行旋转操作。

代码如下：

	bool Insert(const pair<K, V>& kv){//如果_root 等于空if (_root == nullptr){_root = new Node(kv);}Node* parent = nullptr;Node* cur = _root;//找到插入值，应该插入在哪个位置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;}}cur = new Node(kv);//将插入结点的值进行连接if (parent->_kv.first > kv.first){parent->_left = cur;}else if (parent->_kv.first < kv.first){parent->_right = cur;}cur->_parent = parent;//平衡因子，满足AVL树的性质while (parent)  //当到空时，平衡退出（根结点的父亲是空）{if (cur == parent->_right){parent->_bf++;}else if (cur == parent->_left){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 (parent->_bf == 2 && cur->_bf == 1) //左旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1)  //右旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1)  //先右再左{RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1) //先左后右{RotateLR(parent);}break;}else{assert(false);}		}return true;}

（三） AVL树的验证

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

        1. 验证其为二叉搜索树

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

        2. 验证其为平衡树

        每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

        节点的平衡因子是否计算正确
// AVL树的验证
bool IsAVLTree()
{return _IsAVLTree(_root);
}size_t _Height(Node* root)
{if (root == nullptr){return 0;}int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1;
}// 根据AVL树的概念验证Root是否为有效的AVL树
bool _IsAVLTree(Node* root)
{if (root == nullptr)return true;int LeftHeight = _Height(root->_left);int RightHeight = _Height(root->_right);if (RightHeight - LeftHeight != root->_bf){cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;return false;}return abs(LeftHeight - RightHeight) <= 1 && _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}

（四）AVL树总结

1. 基本特性

AVL树是一种严格平衡的二叉搜索树，通过维护每个节点的平衡因子（左子树高度与右子树高度之差）确保树的高度平衡。其平衡条件要求所有节点的平衡因子绝对值不超过1。

2. 时间复杂度

插入、删除、查找操作：时间复杂度均为O(log⁡n)。
由于AVL树始终保持高度平衡，树的高度严格满足h≤1.44log⁡2(n+1)h≤1.44log2(n+1)，这使得其查询效率接近最优。
平衡操作：插入或删除节点后可能需要通过旋转操作恢复平衡，单次旋转的时间复杂度为O(1)，但最坏情况下可能需要从插入点回溯到根节点调整平衡因子，因此平衡操作的总体时间复杂度仍为O(log⁡n)。

3. 性能优缺点

优点：
严格平衡保证查询效率极高，适合读多写少的场景（如数据库索引）。
时间复杂度稳定，无极端退化情况。

缺点：
插入和删除时需频繁调整平衡因子和旋转，写操作开销较大。
与红黑树相比，平衡操作更复杂，可能影响实际性能