前言：本篇文章将紧随二叉搜索树的节奏，分享一个新的数据结构——AVL树。
目录
一.AVL树概念
二.AVL树插入规则
三.AVL树实现
1.基本框架
2.插入
3.旋转
1）左\右单旋
2）左右/右左双旋
4.遍历
5.求树高度
6.判断平衡
7.求树高度
总结
一.AVL树概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
但是当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
所以AVL树即：一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
二.AVL树插入规则
由于AVL树的独特结构，我们给出以下的插入规则：
1.按照搜索树规则插入。
2.更新插入节点的祖先节点的平衡因子：
a.插入父亲的左边，父亲的平衡因子--。
b.插入父亲的右边，父亲的平衡因子++。
c.父亲的平衡因子 == 0，父亲所在的子树高度不变，不再往上更新，插入结束。
d.父亲平衡因子 == 1 or -1，父亲所在的子树高度变了，往上更新，重复以上步骤。
e.父亲平衡因子 == 2 or -2，父亲所在的子树已经不平衡了，需要旋转处理。
三.AVL树实现
1.基本框架
template<class K,class V>
struct AVLTreeNode
{struct AVLTreeNode<K,V>* _left;struct AVLTreeNode<K,V>* _right;struct AVLTreeNode<K,V>* _parent;int _bf;pair<K, V> _kv;AVLTreeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr),_parent(nullptr), _kv(kv),_bf(0){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
private:Node* _root;
};基本框架与平衡二叉树类似，区别在于AVL树的节点为键值对。
同时我们还需增加平衡因子_bf和父节点_parent，方便我们进行调整。
2.插入
//插入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;//更新平衡因子return true;}基本的插入步骤与平衡二叉树一模一样，需要关注的就是插入的节点变为键值对。
下面我们单独来看如何更新平衡因子：
while (parent){if (cur == cur->_parent->_left)parent->_bf--;elseparent->_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;}elseassert(false);}按照我们上边的规则其实很好写出上述代码，要注意循环条件为parent，如果没有父亲，也就是到达了根节点，那就无法再进行调整。
下面我们来重点关注，如何进行旋转。
3.旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
- 新节点插入较高左子树的左侧---左左：右单旋。
- 新节点插入较高右子树的右侧---右右：左单旋。
- 新节点插入较高左子树的右侧---左右：先左单旋再右单旋。
- 新节点插入较高右子树的左侧---右左：先右单旋再左单旋。
下面我们就一一来看这四种情况。
1）左\右单旋
先来看右单旋，可以抽象理解为，左子树过高，需要向右边旋转拉低。
从上图能够看出，右单旋的步骤为：
- 让平衡因子为-2的节点成为它的左子节点的右子节点；
- 同时让该左子节点的右子节点成为平衡因子为-2的节点的左子节点。
同时我们需要关注的细节是：
- 平衡因子为-2的节点是否为根节点。如果不是根节点则需要调整其父节点的指向。
- 左子节点的右子节点是否为空。
通过这样的调整，就可以实现平衡，同时调整的两个关键节点的平衡因子均归0。
下面来看代码：
void RotateR(Node* parent){//定义左子节点Node* subL = parent->_left;//定义左子节点的右子节点Node* subLR = subL->_right;//调整parent->_left = subLR;//判空if (subLR)subLR->_parent = parent;//调整subL->_right = parent;Node* ppNode = parent->_parent;parent->_parent = subL;if (parent == _root)//判断是否为根{_root = subL;_root->_parent = nullptr;}else//不是根节点，调整父节点指向{if (ppNode->_left == parent)ppNode->_left = subL;elseppNode->_right = subL;subL->_parent = ppNode;}//平衡因子归0parent->_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* ppNode = parent->_parent;parent->_parent = subR;if (parent == _root)//判断是否为根{_root = subR;_root->_parent = nullptr;}else//不是根节点，调整父节点指向{if (ppNode->_left == parent)ppNode->_left = subR;elseppNode->_right = subR;subR->_parent = ppNode;}//平衡因子归0parent->_bf = subR->_bf = 0;}2）左右/右左双旋
如果说树并不是子树的一条斜边独高，而是折线型的一颗子树高，此时单靠单旋是解决不了问题的，因此需要通过双旋来解决。
上图所示为先左后右的折线型，所以我们需要进行左右双旋，步骤为：
- 先从折线的折点位置，即上图的30位置，进行左单旋，使树变为左边一条斜边独高的树。
- 在从折线起点位置进行右单旋。
- 更新平衡因子。
其中更新平衡因子也分为不同的情况，以上图为例：
- 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
- 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
- 如果新节点就是60，那么三者的平衡因子均为0。
下面上代码：
//左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}注意更新平衡因子是通过初始时折线末点的平衡因子判断的，所以要提前记录。
再来看右左双旋：
与左右双旋相反，右左双旋是先右后左的折线，所以其操作步骤与之相反：
- 先从折线的折点位置，即上图的90位置，进行右单旋，使树变为右边一条斜边独高的树。
- 在从折线起点位置进行左单旋。
- 更新平衡因子。
其中更新平衡因子也同样分为不同的情况，以上图为例：
- 如果新节点插入位置为60的左，那么旋转后60为0,30为0,90为1。
- 如果新节点插入位置为60的右，那么旋转后60为0,30为-1,90为0。
- 如果新节点就是60，那么三者的平衡因子均为0。
代码如下：
//右左双旋void RotateLR(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}根据父节点及其左右子节点的平衡因子，即可判断对应的旋转方式，下面补充插入步骤：
else if (parent->_bf == 2 || parent->_bf == -2){//出现问题，进行旋转//左单旋if (parent->_bf == -2 && parent->_left->_bf == -1){RotateL(parent);}//右单旋else if (parent->_bf == 2 && parent->_right->_bf == 1){RotateR(parent);}//左右单旋else if (parent->_bf == -2 && parent->_left->_bf == 1){RotateLR(parent);}//右左单旋else{RotateRL(parent);}break;}4.遍历
遍历操作与二叉搜索树类似，需要修改的是我们需要将键值对均打印出来：
//遍历void InOrder(){inOrder(_root);cout << endl;}void inOrder(const Node* root){if (root == nullptr){return;}inOrder(root->_left);cout << root->_kv.first << ':' << root->_kv.second << " ";inOrder(root->_right);}为了方便调用函数而无需传参，我们采用如上方式进行代码编写。
5.求树高度
求树高度我们前边在讲解二叉树的时候已经分享过了，只需求出左右子树高度的最大值＋1即可，通过递归计算：
//求树高度int Height(const Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}6.判断平衡
判断树是否平衡，即判断两棵子树的高度差是否大于等于2：
//判断平衡bool IsBalance(){return isBalance(_root);}bool isBalance(const Node* root){if (root == nullptr)return true;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (abs(leftHeight - rightHeight) >= 2)return false;//检查平衡因子if (rightHeight - leftHeight != root->_bf)return false;return isBalance(root->_left) && isBalance(root->_right);}同时还需要通过递归来判断各个子树是否平衡。
7.求树高度
求树的大小，通过递归即求左子树的大小+右子树的大小+根节点：
//求树大小int Size(){return size(_root);}int size(const Node* root){if (root == nullptr)return 0;return size(root->_left) + size(root->_right) + 1;}总结
关于AVL树的基本内容就分享这么多，喜欢本篇文章的小伙伴记得一键三连，我们下期再见！
