目录
1.什么是AVL树
1.1 树的结构
1.2平衡因子的引入
1.3 旋转操作的大致说明
1.4 插入与删除操作
1.5AVL树的优点和缺点
2.AVL树的实现
2.1 AVL树的整体框架
2.2 AVL树的插入
2.2.1 AVL树插入一个值的过程
2.2.2 平衡因子更新
更新原则
更新停止条件
旋转的目标
2.2.3 结点插入和平衡因子的更新
2.3 旋转
2.3.1 旋转的原则
2.3.2 右单旋
2.3.3 左单旋
2.3.4 左右双旋
2.3.5 右左双旋
2.4 AVL树的查找
2.5 AVL树平衡检测（了解）
3. 完整代码（附测试代码函数）
结束语
1.什么是AVL树
AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉查找树（Binary Search Tree, BST），它的特点是每个节点的左子树和右子树的高度差（称为平衡因子）不能超过1。AVL树是由俄罗斯数学家Adelson-Velsky和Landis于1962年提出的。
1.1 树的结构
AVL树与普通的二叉搜索树一样，满足以下两个条件：
1. 二叉查找树性质：对于树中的任意一个节点，左子树的所有节点的值小于该节点的值，右子树的所有节点的值大于该节点的值。
2. 平衡性：对于树中的每个节点，左子树和右子树的高度差的绝对值（即平衡因子）不能大于1。
1.2平衡因子的引入
对于树中某个节点 ( N )，其平衡因子 ( BF(N) ) 定义为：
BF(N) = 右子树高度-左子树高度
- 如果 BF(N) = 0 ，表示该节点的左右子树高度相等。
- 如果 BF(N) = 1 ，表示该节点的左子树比右子树高1。
- 如果 BF(N) = -1 ，表示该节点的右子树比左子树高1。
- 如果 ( |BF(N)| > 1 )，表示该节点的子树不平衡，需进行旋转操作来恢复平衡。
1.3 旋转操作的大致说明
为了保持AVL树的平衡性，当插入或删除节点后，树可能会失去平衡。此时需要通过旋转操作来恢复平衡。常见的旋转操作有四种：
1. 右旋转（Single Rotation, Right Rotation）：适用于左子树过高（左重）的情况。
2. 左旋转（Single Rotation, Left Rotation）：适用于右子树过高（右重）的情况。
3. 左-右旋转（Double Rotation, Left-Right Rotation）： 适用于左子树的右子树过高的情况。
4. 右-左旋转（Double Rotation, Right-Left Rotation）： 适用于右子树的左子树过高的情况。
1.4 插入与删除操作
- 插入操作：当一个新节点插入AVL树时，首先按照二叉查找树的方式插入节点。然后，通过遍历树的路径来检查是否有节点失衡，如果有，进行相应的旋转操作。
- 删除操作：删除节点后，可能导致树的不平衡，需要检查并恢复平衡，通常需要进行旋转操作。
平衡性与时间复杂度
- 插入、删除、查找操作的时间复杂度为 O(log n) ，其中 n 是树中节点的数量。由于AVL树保证了平衡，因此在最坏情况下，树的高度为 O(log n) )，使得这些操作的时间复杂度得到保证。
1.5AVL树的优点和缺点
优点：
- 相比普通的二叉查找树，AVL树提供了更稳定的查询时间，因为它保持了树的平衡性。
- 对于频繁进行查找操作的应用，AVL树的性能较好。
缺点：
- 由于在插入和删除操作后需要进行旋转操作，AVL树的插入和删除操作较为复杂。
- 相比于其他自平衡树（如红黑树），AVL树的维护成本稍高，因为它需要频繁检查并调整平衡。
部分图例展示
该图就是要进行旋转操作
2.AVL树的实现
2.1 AVL树的整体框架
AVL树的结构跟二叉搜索树几乎是类似的，我们需要添加一个int变量来记录平衡因子，且增加一个parent结点指针来辅助平衡因子的找寻和修改，在后续的旋转操作我们会认识到它的作用。
#define _CRT_SECURE_NO_WARNINGS#include <iostream>using namespace std;template<class K, class V>struct AVLTreeNode {pair<K, V> _kv;AVLTreeNode<K, V>* _parent;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;int _BF;AVLTreeNode(const pair<K, V>& kv): _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _BF(0){}};template<class K,class V>class AVLTree {using Node = AVLTreeNode<K, V>;public://AVL树的构建和操作bool Insert(const pair<K, V>& kv) {}void RotateR(Node* parent) {}void RotateL(Node* parent){}void RotateLR(Node* parent) {}void RotateRL(Node* parent) {}Node Find(const K& key){}private:Node* _root = nullptr;};int main() {return 0;}2.2 AVL树的插入
2.2.1 AVL树插入一个值的过程
1. 插入一个值按二叉搜索树规则进行插入。 2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。 3. 更新平衡因子过程中没有出现问题，则插入结束 4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。
2.2.2 平衡因子更新
更新原则
平衡因子 = 右子树高度-左子树高度 只有子树高度变化才会影响当前结点平衡因子。 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在 parent的左子树，parent平衡因子-- parent所在子树的高度是否变化决定了是否会继续往上更新更新停止条件
更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前 parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会 影响parent的父亲结点的平衡因子，更新结束。 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说 明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理。旋转的目标
1、把 parent子树旋转平衡。
2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。
图例展示
更新到10结点，发现平衡因子变为2，破坏了10子树结构，需要进行旋转。
更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束
最坏的情况一直更新到根结点
2.2.3 结点插入和平衡因子的更新
当一个新节点插入AVL树时，首先按照二叉查找树的方式插入节点。然后，通过遍历树的路径来检查是否有节点失衡，如果有，进行相应的旋转操作。
先找到插入结点的位置，在进行插入，然后检查更新平衡因子，这里我们在前面定义的_parent的作用就逐渐体现出来了。
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->_right;}else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);if (kv.first < parent->_kv.first) {parent->_left = cur;}elseparent->_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) {//旋转处理break;}elsereturn false;}}2.3 旋转
2.3.1 旋转的原则
保持搜索树的规则，让旋转的树从不满足变平衡，其次降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。
说明：下面的图中，有些结点给的是具体值，方便观察。2.3.2 右单旋
图例文字描述
图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要 求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是⾼度为h的子树， 是一种概括抽象表示，代表了所有右单旋的场景，实际右单旋形态有很多种。
在a子树中插入一个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平 衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。 旋转核心步骤，因为5 < b子树的值 < 10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原 则。如果插入之前10是整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
右单旋的详细描述 
右单旋代码
void RotateR(Node* 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;// parent有可能是整棵树的根，也可能是局部的⼦树// 如果是整棵树的根，要修改_root// 如果是局部的指针要跟上⼀层链接if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}parent->_bf = subL->_bf = 0;}
2.3.3 左单旋
图例文字描述
展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，代表了所有左单旋的场景，实际左单旋形态有很多种，具体跟上面右旋类似。 在a子树中插入一个新结点，导致a子树的⾼度从h变成h+1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。 旋转核心步骤，因为10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵 树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转 原则。如果插入之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了。
左单旋代码
void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* parent_Parent = parent->_parent;parent->_parent = subR;if (parent_Parent == nullptr) {_root = subR;subR->_parent = nullptr;}else {if (parent == parent_Parent->_left)parent_Parent->_left = subR;elseparent_Parent->_right = subR;subR->_parent = parent_Parent;}parent->_BF = subR->_BF = 0;}2.3.4 左右双旋
图形文字描述
通过下面的图可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变 成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边高，但是插入在b子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，以10为旋转点进行一个右单旋，这棵树这棵树就平衡了。
只进行了右旋的错误示范图
场景3：h == 0时，a/b/c都是空树，b自己就是一个新增结点，不断更新5->10平衡因子，引发旋 转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。 
代码书写
void RotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_BF;RotateL(parent->_left);RotateR(parent);if (bf == 0) {subLR->_BF = 0;parent->_BF = 0;subL->_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);}}重点是平衡因子的更新
2.3.5 右左双旋
跟左右双旋类似，下面将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的 细节进一步展开为12和左子树高度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单旋，右单旋需要动b树中的右子树。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察12的平衡因子不同，这里同样要分三个场景讨论。
场景1：h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因 子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。 
代码展示
void RotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_BF;RotateR(parent->_right);RotateL(parent);if (bf == 0) {subR->_BF = 0;subRL->_BF = 0;parent->_BF = 0;}else if (bf == 1) {subR->_BF = 0;subRL->_BF = 0;parent->_BF = -1;}else if (bf == -1) {subR->_BF = 1;subRL->_BF = 0;parent->_BF = 0;}else {assert(false);}}2.4 AVL树的查找
仿照二叉搜索树的逻辑进行查找，效率O(log n)
Node*Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first > key)cur = cur->_left;else if (cur->_kv.first < key)cur = cur->_right;elsereturn cur;}return nullptr;}2.5 AVL树平衡检测（了解）
实现的AVL树是否合格，我们通过检查左右子树高度差的的程序进行反向验证，同时检查⼀下结点的平衡因子更新是否出现了问题。
bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_BF != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}我们仿照前面二叉树的学习将高度和大小，中序遍历求解也写下
void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root) {if (root == nullptr) {return 0;}int Left_height = _Height(root->_left);int Right_height = _Height(root->_right);return Left_height > Right_height ? Left_height + 1 : Right_height + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}我们同样按照二叉搜索树一样是将这些函数封装在private中，在public中在定义函数调用这些函数，不然在外面传根节点有点麻烦。
3. 完整代码（附测试代码函数）
#define _CRT_SECURE_NO_WARNINGS#include <iostream>#include <assert.h>#include <vector>using namespace std;template<class K, class V>struct AVLTreeNode {pair<K, V> _kv;AVLTreeNode<K, V>* _parent;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;int _BF;AVLTreeNode(const pair<K, V>& kv): _kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _BF(0){}};template<class K,class V>class AVLTree {using Node = AVLTreeNode<K, V>;public://AVL树的构建和操作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->_right;}else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);if (kv.first < parent->_kv.first) {parent->_left = cur;}elseparent->_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) RotateRL(parent);else if (parent->_BF == -2 && cur->_BF == 1) RotateLR(parent);else assert(false);break;}else return false;}return true;}void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parent_Parent = parent->_parent;subL->_right = parent;parent->_parent = subL;//parent可能是整棵树的根，也可能是局部根//局部根要向上链接，更新祖父的结点信息if(parent_Parent==nullptr){_root = subL;subL->_parent = nullptr;}else {if (parent_Parent->_left == parent)parent_Parent->_left = subL;elseparent_Parent->_right = subL;subL->_parent = parent_Parent;}parent->_BF = subL->_BF = 0;}void RotateL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* parent_Parent = parent->_parent;parent->_parent = subR;// 更新 parent_Parent 的子节点指针if (parent_Parent == nullptr) {_root = subR;subR->_parent = nullptr;}else {if (parent == parent_Parent->_left)parent_Parent->_left = subR;elseparent_Parent->_right = subR;subR->_parent = parent_Parent;}parent->_BF = subR->_BF = 0;}void RotateLR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_BF;RotateL(parent->_left);RotateR(parent);if (bf == 0) {subLR->_BF = 0;parent->_BF = 0;subL->_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);}}void RotateRL(Node* parent) {Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_BF;RotateR(parent->_right);RotateL(parent);if (bf == 0) {subR->_BF = 0;subRL->_BF = 0;parent->_BF = 0;}else if (bf == 1) {subR->_BF = 0;subRL->_BF = 0;parent->_BF = -1;}else if (bf == -1) {subR->_BF = 1;subRL->_BF = 0;parent->_BF = 0;}else {assert(false);}}Node*Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first > key)cur = cur->_left;else if (cur->_kv.first < key)cur = cur->_right;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}int Height(){return _Height(_root);}int Size(){return _Size(_root);}bool IsBalanceTree(){return _IsBalanceTree(_root);}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}int _Height(Node* root) {if (root == nullptr) {return 0;}int Left_height = _Height(root->_left);int Right_height = _Height(root->_right);return Left_height > Right_height ? Left_height + 1 : Right_height + 1;}int _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_BF != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}private:Node* _root = nullptr;};void TestAVLTree1(){AVLTree<int, int> t;// 常规的测试用例int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };// 特殊的带有双旋场景的测试用例//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto e : a){t.Insert({ e, e });}t.InOrder();cout << t.IsBalanceTree() << endl;}void test2() {AVLTree<int, int> tree;const int N = 100000;vector<int> v;v.reserve(N);srand(time(0));for (int i = 0; i < N; i++) {v.push_back(rand() + i);}for (auto e : v) {tree.Insert({ e, e });}size_t end2 = clock();cout << tree.IsBalanceTree() << endl;cout << "Height:" << tree.Height() << endl;cout << "Size:" << tree.Size() << endl;size_t begin1 = clock();// 确定在的值for (auto e : v){tree.Find(e);}// 随机值/*for (size_t i = 0; i < N; i++){t.Find((rand() + i));}*/}int main() {//test2();TestAVLTree1();return 0;}测试部分我们用了随机的数据插入来验证AVL树更具有说服力。
结束语
AVL树是一种自平衡的二叉查找树，能够保证在插入、删除、查找等操作中的时间复杂度为 O(log n) 。通过平衡因子的控制和旋转操作，AVL树保持了树的平衡性，有效地避免了树变成链表的情况，从而提升了操作效率。
本节内容就到此结束了，感谢友友们的阅读和支持！！！