1.前言

如果你不知道什么是二叉搜索树，那么请你一定要阅读以下文章。

[c++高阶]二叉搜索树深度剖析-CSDN博客

二叉搜索树如果在已经有序的情况下进行插入的话，那么他的时间复杂度是O(N)，然后有时候的时间复杂度又是O(logN)，因此在实际使用中很少人会使用二叉搜索树。

为了解决上述问题，有2位俄罗斯的天才提出了AVL树的结构，也就是说高度平衡二叉搜索树。

这样二叉搜索树由原来不稳定变成了稳定了。

后面学习AVL树可能有点难，请各位小伙伴耐心阅读。

本章重点：

本章着重讲解AVL树的概念，AVL树性质以及定义、AVL树插入的详解等。

2.AVL树的性质

       当我们向二叉搜索树中插入新节点时，如果能用某种方法时刻保证树中每个节点的左右子树高度之差不超过1，就可以降低整棵树的高度，保证每条分支的平衡。

AVL树的性质如下：

• AVL树可以是空树
• 一颗AVL树的左右子树都是AVL树
• 一颗AVL树的左右子树高度差不超过1

例如：

 3.AVL树的节点的定义

 AVL树一棵高度平衡的二叉树，那么如何通过代码的方式告知他自己是否平衡呢？

我们可以定义一个平衡因子，每一个节点都有一个平衡因子，然后通过判断该节点的平衡因子来判断这棵树或者这棵子树是否平衡。同时，如果左子树比右子树高一层，那么根节点的平衡因子就是-1；如果右子树比左子树高一层，那么根节点的平衡因子就是1，如果左右子树一样高，那么根节点的平衡因子就是0。

并且在定义之前答成一个约定：往左子树插入节点，那么根的平衡因子就--；往右子树插入节点，那么根的平衡因子就++。

因为我们后续在不平衡的时候要进行调整，而调整的过程中，要频繁的知道根节点的平衡因子是多少，所以在AVL树中需要使用三叉链，即在AVL树中，不仅有左指针，右指针，还有一个指向父节点的父指针。

定义代码如下：

template <class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;pair<K, V>  _kv;int _bf;//平衡因子，后续用来判断AVL树是否平衡AVLTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};

可能有的同学对于pair会有一些疑惑，不知道这是什么。简单解释一下：

pair可以将两个数据组成一组元素，因此对于key/value模型这种需要用到两个数据为一组的元素时就可以使用，内部的成员变量为first和second，其主要使用方法为：

pair<T1, T2> p1(v1, v2); //输入两个数据创建pair类型变量
make_pair(v1, v2);       //输入两个数据通过函数创建pair类型变量
p1.first                 //访问p1的第一个数据
p1.second                //访问p1的第二个数据

4.AVL树的插入深度剖析

先给出AVL树的基本结构：

template<class K,class V>
struct AVLTree
{typedef AVLTreeNode<K, V> Node;
private:Node* _root;//定义一个根节点
};

向AVL树中插入节点与向二叉搜索树中插入节点的过程基本相同，唯一的区别就是AVL树在插入节点后可能存在失衡的情况，需要调整。

AVL树的插入的三个步骤：

1.先找到自己对应的位置插入

2.更新平衡因子

3.对于平衡因子过大或者过小的要进行调整

AVL树的插入主要就是对以上三步进行理解，只要能够理解到位，就能够写出相应的代码。

第一步在讲解二叉搜索树的时候，已经说过了再这里就不过的赘述。

现在着重讲解更新平衡因子，以及平衡因子过大或者过小究竟是多大或者多小。

更新平衡因子规则如下：

1.往父节点的左边插入，父节点--

   往父节点的右边插入，父节点++

2.更新完后，看父节点的平衡因子是多少

   如果是1或者-1，那就表明之前是平衡的，现在新加了一个

   可能导致不平衡，所以要顺着这个分支一直遍历到根节点，

   判断是否有不平衡的现象出现。

 

3.如果某一个节点的值时2或者-2出现时，就表示这棵树不平衡了，那么就需要进行调整。

4.如果父节点由原来的1或者-1变成0的话，那么就表示这棵树由原来的不平衡变成了平衡，那么就不需要向上更新了。

例:

对于不平衡的那么就需要用旋转来进行处理了，由于旋转比较复杂，所以单独介绍旋转。

5.AVL树的旋转剖析

在介绍旋转前，先把前面的代码给出来。

template <class K,class V>
class AVLTree
{
public:typedef AVLTreeNode<K, V> Node;AVLTree()//构造函数{}bool Insert(const pair<K, V>& kv){//1.根节点为空的情况if (_root == nullptr){_root = new Node(kv);return true;}//2.不为空的情况，那么就需要先找到Node* prev = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first > kv.first){prev = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){prev = cur;cur = cur->_right;}else return false;}//3.到这里就找到了cur = new Node(kv);if (prev->_kv.first > kv.first)prev->_left = cur;elseprev->_right = cur;cur->_parent = prev;//4.插入完了之后，就要更新根的平衡因子//然后根据平衡因子的大小来判断是否需要旋转while (prev){//插入左边，高度减-；插入右边，高度加一if (cur == prev->_left)prev->_bf--;elseprev->_bf++;//到这里就需要判断平衡因子是多少了if (prev->_bf == 0)break;else if (prev->_bf == 1 || prev->_bf == -1){//如果是1或者-1，那就表示高度变了，那么就需要向上更新prev = prev->_parent;cur = cur->_parent;}else if (prev->_bf == 2 || prev->_bf == -2){//到这里就需要进行旋转了}}return true;}~AVLTree(){_Destroy(_root);}
private:void _Destroy(Node* root){if (root == nullptr) return;_Destroy(root->_left);_Destroy(root->_right);delete root;root = nullptr;}
private:Node* _root = nullptr;
};

旋转一共有四种情况，不管哪种情况最终的目的

都是为了将不平衡的树变成平衡的树。

情况一：左单旋

简单的例子：

抽象的例子：

左单旋规则：

1.把父节点向左旋转，变成右孩子的左孩子

2.把右孩子的左孩子变成父节点的右孩子

代码如下：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;//开始链接parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//链接完了，更新平衡因子parent->_bf = subR->_bf = 0;
}

情况二：右单旋

简单例子：

抽象的例子：

右单旋的规则：

1.父节点变成左孩子的右孩子，左孩子升级成为左孩子

2.左孩子的右孩子变成父节点的左孩子。

代码如下：

void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;//开始链接parent->_left = subLR;if (subLR)subLR->_parent = parent;parent->_parent = subL;subL->_right = parent;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = subL;else if (pparent->_right == parent)pparent->_right = subL;subL->_parent = pparent;}parent->_bf = subL->_bf = 0;
}

上述两种情况都是在二叉树的最边一侧进行添加孩子，而对于在内侧添加则没有体现。接下来两种情况就是着重介绍在内侧添加的情况。

上述两种情况代码如下：

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;//开始链接parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//链接完了，更新平衡因子parent->_bf = subR->_bf = 0;
}void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;//开始链接parent->_left = subLR;if (subLR)subLR->_parent = parent;parent->_parent = subL;subL->_right = parent;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pparent->_left == parent)pparent->_left = subL;else if (pparent->_right == parent)pparent->_right = subL;subL->_parent = pparent;}parent->_bf = subL->_bf = 0;
}

 上述代码看上去很复杂，其实是因为我们刚开始定义AVL树节点的时候，定义成了三叉链。所以上述都是在修改左右节点链接的对象和父节点链接的对象。

情况三：右左单旋

右左单旋简单理解就是先进行右旋转，然后再进行左旋转。

简单例子：

注意在左旋和右旋的时候，都是通过给出父节点来进行旋转的。

而此处的右旋，是以20节点为父节点进行旋转的，所以在传值的时候要千万小心。

抽象的例子：

注意：这里在b和c处插入，用的旋转都是一样的，只是对最后平衡因子的具体数值有影响。

代码如下：

void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);//这里也是更新平衡因子if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else{parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}
}

 这里面还加了更新平衡因子的代码。具体解释如下图：

1.旋转玩之后平衡因子全为0的情况：

 2.旋转之后父节点变成了-1，而其他节点变成了0的情况

见图抽象的例子那一张

3.旋转之后父节点的右孩子变成了1，而其他节点变成了0，主要就是看新增节点是放在了b,还是放在了c下面。

直接给出最后旋转成功的图：

唯一的区别就是插入的位置不同，导致最后的平衡因子的不同。

情况四、左右单旋

与情况三类似，此处只是先进行左旋转，然后再进行右旋转。

简单例子：

抽象例子：

PS：不管是左右单旋还是右左单旋在第一个旋转的时候都是用父节点的孩子来作为传递值进行旋转。

代码如下：

	void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);//最后就是更新平衡因子了if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else{parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}}

左右单旋的平衡因子的更新和上面左右单旋是一样的，就不做过多的解释了。有兴趣的小伙伴可以根据下图自己去推导推导

 6.AVL树的验证

6.1验证有序

最重要的插入节点部分完成了，不过在验证是否符合AVL树性质前，我们首先需要验证其是否是一棵二叉搜索树

在之前讲解二叉搜索树中提到过，如果中序遍历能够得到一个有序的序列，就说明是二叉搜索树

直接上代码：

void Inorder()
{_Inorder(_root);cout << endl;
}
void _Inorder(Node* root)
{if (root == nullptr) return;_Inorder(root->_left);cout << root->_kv.first << " ";_Inorder(root->_right);
}

插入测试用例：

int a[] = { 16,3,7,11,9,26,18,14,15 };

输出：3,7,9,11,14,15,16,18,26

有序的话就代表其符合二叉搜索树的性质

6.2验证是否平衡

验证是否平衡也很好判断，只需要判断左右子树的高度的差不超过1即可

在这里千万要注意，不能直接使用平衡因子来判断是否平衡，因为平衡因子也是可以进行修改的，只需要在最后面退出的时候，修改某一个值的平衡因子，然后一棵是平衡的二叉树就有可能因为平衡因子的修改，被误判成了不是平衡的。

通过递归来判断是否是一个平衡的二叉树：

代码如下：

bool IsBalance()
{if (_IsAVLTree(_root)) return true;else return false;
}
bool _IsAVLTree(Node* root)
{if (root == nullptr) return true;int left = IsHeight(root->_left);int right = IsHeight(root->_right);if (right - left != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(left - right) < 1 && _IsAVLTree(root->_left) && _IsAVLTree(root->_right);
}
int IsHeight(Node* root)
{if (root == nullptr) return 0;int lefth = IsHeight(root->_left);int righth = IsHeight(root->_right);return lefth > righth ? lefth + 1 : righth + 1;
}

测试用例的话，大家可以自己随机生成一些值，然后进行测试。或者用我上述使用的过的例子。

7.AVL的删除

有了插入的旋转之后，AVL的删除就不应该是这里的主角了，并且在学了旋转之后，会发现删除还是比较简单的。只有三种情况：左为空，右为空，左右不为空（找左子树的最右值或者右子树的最左值来进行替换）。删除之后再判断是否需要进行旋转即可。

感兴趣的可以阅读这篇文章,这里面详细介绍了二叉搜索树的删除

[c++高阶]二叉搜索树深度剖析-CSDN博客

8.总结与拓展

AVL树是一棵高度严格平衡的二叉树，这样的二叉树对于查找来说效率就是O（logN），但是 我们需要进行多次的旋转来保持它的平衡，这样在一定程度上就会影响效率，尤其是在删除的时候，删除了某一个值，可能一直要旋转，旋转到根的位置。这样就极大地影响它的效率，因此有没有更好的办法呢？有，红黑树。后续文章中会详细介绍红黑树。

AVL树的插入代码还是很难写的，有很多的情况要进行考虑，希望各位小伙伴能够多理解几遍然后再动手去写，一定要边写变画图。

行文至此，AVL树就讲解完毕了，要是有不对的地方，还请大家批评指正。