【C++高阶】掌握AVL树：构建与维护平衡二叉搜索树的艺术

📝个人主页🌹：Eternity._
⏩收录专栏⏪：C++ “ 登神长阶 ”
🤡往期回顾🤡：STL-> map与set
🌹🌹期待您的关注 🌹🌹

在这里插入图片描述

❀AVL树

📒1. AVL树的概念
📙2. AVL树节点的定义
📜3. AVL树的插入
📚4. AVL树的旋转
- 🌈右单旋
- 🌞左单旋
- 🌙左右双旋
- ⭐右左双旋
📝5. AVL树的验证
📘6. AVL树的缺陷
📖7. 总结

前言： 在数据结构的浩瀚海洋中，AVL树（Adelson-Velsky和Landis发明的树）以其独特的平衡机制和高效的搜索性能，成为了一颗璀璨的明星。它不仅解决了二叉搜索树在数据插入和删除时可能产生的失衡问题，更通过旋转操作，使得树的高度始终保持在一个相对较低的水平，从而保证了搜索的高效性

AVL树的学习并非一蹴而就。它需要我们深入理解其背后的数学原理和算法思想，掌握其插入、和旋转等操作的具体实现，并在实践中不断摸索和优化。只有经过这样的过程，我们才能真正掌握AVL树的精髓，并在实际项目中灵活运用

本篇我们将详细介绍AVL树的基本概念、性质、插入操作的具体实现、旋转操作的原理和技巧等内容！

让我们一起踏上学习 AVL树的旅程，探索它带来的无尽可能！

📒1. AVL树的概念

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

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：

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

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

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

在这里插入图片描述
注意： 如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )

📙2. AVL树节点的定义

AVL树节点的定义通常包含以下几个关键部分：

基本元素：

_left：指向节点的左子节点的指针
_right：指向节点的右子节点的指针
_parent：指向节点的父节点的指针
_kv：一个结构体或配对（pair），包含节点的键值（key）和值（value）。这取决于AVL树的具体用途，可能只包含键或包含键值对。

平衡因子（_bf）：

一个整数，表示节点左子树和右子树的高度差。AVL树的性质要求任何节点的平衡因子的绝对值不超过1（-1, 0, 1）

构造函数：

初始化一个新节点时，通常需要一个构造函数，它接受一个键值对（或仅键），并设置节点的左子节点、右子节点、父节点和平衡因子（初始化为0）

节点定义示例(C++)：

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left; // 该节点的左孩子AVLTreeNode<K, V>* _right; // 该节点的右孩子AVLTreeNode<K, V>* _parent; // 该节点的父亲pair<K, V> _kv;  // pairint _bf; // balance factor 该节点的平衡因子AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

📜3. AVL树的插入

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

按照二叉搜索树的方式插入新节点
调整节点的平衡因子

在我们进行插入操作之前，我们先定义一个AVL树的类

AVL树定义示例(C++)：

template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:// 其他未实现的成员函数
private:Node* _root = nullptr;
};

cur插入后，parent的平衡因子一定需要调整

在插入之前，parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

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

插入后，parent的平衡因子可能有三种情况：0，正负1，正负2

如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整
成0，此时满足AVL树的性质，插入成功
如果parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更
新成正负1，此时以parent为根的树的高度增加，需要继续向上更新
如果parent的平衡因子为正负2，则parent的平衡因子违反平衡树的性质，需要对其进
行旋转处理

AVL树的插入操作类似于我们之前二叉搜索树的插入，只不过AVL树的插入操作涉及到旋转操作，我们先演示一下它的全部代码

AVL树插入示例(C++)：

bool Insert(const pair<K, V>& kv)
{// 当根节点为空时直接插入if (_root == nullptr){_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;// 寻找插入位置while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}// 链接新节点cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}// 更改平衡因子while (parent){if (cur == parent->_left){parent->_bf--;}else{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){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);}}return true;
}

📚4. AVL树的旋转

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

🌈右单旋

新节点插入较高左子树的左侧—左左：

此处旋转是将30的右子树变成60的左子树，然后让60成为30的右子树

在旋转中有几点要注意：

30这个节点的右孩子可能不存在
60这个节点可能是根节点，也可能是子树

如果是根节点，旋转完成后，要更新根节点
如果是子树，可能是某个节点的左子树，也可能是右子树

AVL树右单旋示例(C++)：

void RotateR(Node* parent)
{// 定义parent的左孩子 和 parent的左孩子的右孩子Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR){subLR->_parent = parent;}// 当旋转点是子树时，保留父亲节点Node* Parentparent = parent->_parent;subL->_right = parent;parent->_parent = subL;// 当旋转点是根时，跟新根节点if (_root == parent){_root = subL;subL->_parent = nullptr;}// 当旋转点是子树时，更新链接else{if (parent == Parentparent->_left){Parentparent->_left = subL;}else{Parentparent->_right = subL;}subL->_parent = Parentparent;}// 更新平衡因子为0parent->_bf = subL->_bf = 0;
}

🌞左单旋

新节点插入较高右子树的右侧—右右：
在这里插入图片描述
左单旋与单旋类似，所以我们直接来看代码

AVL树左单旋示例(C++)：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* Parentparent = parent->_parent;parent->_parent = subR;if (subRL){subRL->_parent = parent;}// 判断parent是不是根节点if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parent == Parentparent->_left){Parentparent->_left = subR;}else{Parentparent->_right = subR;}subR->_parent = Parentparent;}parent->_bf = subR->_bf = 0;
}

🌙左右双旋

新节点插入较高左子树的右侧—左右：
在这里插入图片描述
这里是将双旋变成单旋后再旋转，先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新

这里单旋可以复用上面讲的

AVL树左右双旋示例(C++)：

void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 根据右子树的右孩子的平衡因子，判断旋转后的平衡因子情况// 复用单旋RotateL(parent->_left);RotateR(parent);// subLR就是新插入节点if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == 1){subLR->_bf = 0;parent->_bf = 0;subL->_bf = -1;}else if (bf == -1){subLR->_bf = 0;parent->_bf = 1;subL->_bf = 0;}else{assert(false);}
}

⭐右左双旋

新节点插入较高右子树的左侧—右左：
在这里插入图片描述
右左双旋和左右双旋类似，我们直接看代码

AVL树右左双旋示例(C++)：

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;// 复用单旋RotateR(parent->_right);RotateL(parent);if (bf == 0){parent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{assert(false);}
}

总结：

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR
当subR的平衡因子为1时，执行左单旋
当subR的平衡因子为-1时，执行右左双旋
parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL
当subL的平衡因子为-1是，执行右单旋
当subL的平衡因子为1时，执行左右双旋

旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新

📝5. AVL树的验证

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

验证其为二叉搜索树

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

代码演示示例(C++)：

// 中序遍历
void InOrder()
{_InOrder(_root);cout << endl;
}void _InOrder(Node* root)
{if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}

验证其为平衡树

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

代码演示示例(C++)：

bool IsBalance()
{return _IsBalance(_root);
}int _Height(Node* root)
{if (root == nullptr){return;}int rightHeight = _Height(root->_right);int leftHeight = _Height(root->_left);return rightHeight > leftHeight ? rightHeight + 1 : leftHeight + 1;
}bool _IsBalance(Node* root)
{if (root == nullptr){return true;}int rightHeight = _Height(root->_right);int leftHeight = _Height(root->_left);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子有误" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}

验证用例

int main()
{// 这里会进行双旋int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;return 0;
}

在这里插入图片描述

📘6. AVL树的缺陷

缺陷	原因
插入操作复杂	为了保持树的平衡，每次插入或删除节点时，AVL树可能需要进行多次旋转操作。具体来说，插入一个节点可能需要单旋转或双旋转来重新平衡树结构，而删除节点后可能需要从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级最坏情况下为O(logN)。这增加了操作的复杂性并可能影响性能。
维护成本高	由于AVL树要求每个节点的左右子树高度差不超过1，因此需要频繁地检查和调整树的结构。这种严格的平衡要求导致了相对较高的维护成本，特别是在频繁进行插入和删除操作的情况下。
空间开销较大	虽然AVL树在查找效率上具有优势，但由于其需要频繁地进行旋转操作以维持平衡，这可能导致额外的空间开销。尤其是在处理大量数据时，这种开销可能会更加明显。
不适用于所有场景	AVL树适用于查找操作远多于插入和删除操作的场景。如果在一个应用中插入和删除操作也非常频繁，那么AVL树可能不是最优选择，因为每次插入和删除都需要进行平衡调整，这会影响性能。