一、什么是AVL树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

AVL树相比前边的二叉搜索树，最大的区别就是在插入后判断左右子树的高度差，若不满足条件，就要进行旋转使高度差满足条件。

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

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

对于一颗AVL树而言，不仅要求这个数的根节点在左右子树是高度平衡的，并且要求每一个结点的左右子树都是高度平衡的。如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在$O(lo{g}_{2}n)$，搜索时间复杂度O($lo{g}_{2}n$)。

二、AVL树的定义

在实现AVL树之前，需要先实现一个AVL树的节点，由于在后边要实现map的需要，所以实现key-value结构，所以树节点的值就是一个键值对，并且为了方便查找父结点的值，选择三叉链结构。
我们也控制了一个节点的平衡因子，是为了更方便控制是否平衡。

template<class K,class V>
class treeNode
{
public:treeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr),_bf(0),_kv(kv){}treeNode<K,V>* _left;treeNode<K, V>* _right;treeNode<K, V>* _parent;int _bf;pair<K, V> _kv;
};

三、AVL树的插入

1.理论讲解

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。

平衡因子如何控制？

当在一个节点的左边插入节点时，那么该节点的平衡因子- -
当在一个节点的右边插入节点时，那么该节点的平衡因子++

那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点

和前边二叉搜索树的方法类似，当插入值大于某节点值时，继续与其右子树判断，如果插入值小于某结点值时，继续与其左子树判断，知道判断到空，如果要插入结点的值与某一节点值相同时，那么就返回false，这是因为不能插入相同的值。

2. 调整节点的平衡因子

当在合适的位置插入新节点之后，就必须对其父结点的平衡因子进行判断，那么就会有以下的几种情况：

1.父结点的平衡因子为0

那么说明插入前父结点的平衡因子一定是-1或1，说明本来父结点的左右子树高度不相等，但是在插入之后，左右子树的高度相同了，插入的结点把本来空缺的位置补齐了。

2.父结点的平衡因子为-1或1

那么说明插入前父结点的平衡因子一定为0，不可能为2或-2，因为如果为-2和2就会发生旋转，所以插入后导致父结点不平衡，所以必须向上修改平衡因子。

3.父结点的平衡因子为-2或2

那么插入前父节点平衡因子一定为1或-1，此时就要进行旋转，调整结点的位置，使其再次成为AVL树。

当出现了平衡因子为-2或2时，根据情况不同就有四种旋转方法：

1.当父结点的平衡因子为2，子节点的平衡因子为1。

那么此时说明右边的高度大，那么就要进行左旋使其左右高度趋于平衡。

2.当父结点的平衡因子为-2，子节点的平衡因子为-1。

那么此时左边的高度大，要进行右旋使其左右高度趋于平衡。

3.当父结点的平衡因子为-2，子节点的平衡因子为1。

此时要进行左右双旋。

4.当父结点的平衡因子为2，子节点的平衡因子为-1。

此时要进行右左双旋。

2.代码实现

	bool insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;while (parent){if (cur == parent->_left){parent->_bf--;}if (cur == parent->_right){parent->_bf++;}if (parent->_bf == 0){break;}else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent-> _bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}}}

四、AVL树的旋转

1.左单旋

当父结点的平衡因子为2，且子节点的平衡因子为1时，即右边高度大于左边，进行左旋。

此处的a，b，c的高度都是h，所以h可能是0，1，2或者很长，所以代表着无数种情况。

在c处插入一个节点后，c高度变为和h+1，所以60结点的平衡因子变为1,30这个节点的平衡因子变为2，符合我们前边提提到做单旋的情况，所以进行左单旋。

对父节点进行左单旋，要进行以下的几步：

1.将子节点的左子树成为父结点的右子树。
2.将父结点变为子节点的左子树。
3.更新平衡因子parent结点和其右节点subR的平衡因子都变为0。

感性来看，就是把父结点往下压成为子节点的左子树的过程，称为左单旋，但是还有一点要注意就是在旋转完之后，需要判断父节点是否为根节点，若为根节点，就对根节点重新赋值，若不为根节点，就必须保存原父结点的父结点，就必须让子节点与这个保存的结点连接。

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_parent = subR;subR->_left = parent;parent->_right = subRL;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parent == pparent->_left){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}subR->_bf = parent->_bf = 0;}

2.右单旋

右单旋为左单旋类似，只是在左边的高度较大时进行右单旋，当父节点的平衡因子为-2，子节点平衡因子为-1时进行右单旋。

在进行右单旋时进行以下的步骤：

1.将子节点的右子树作为父结点的左子树
2.将父结点作为子节点的右子树
3.调整平衡因子都有0

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

3.左右双旋

当父节点的平衡因子为-2，而子节点的平衡因子为1时，就要进行左右双旋。
左右双旋的会有以下的几步:

先对父结点的左节点进行左单旋.
再去父结点进行右单旋。

我们可以直接复用前边写好的左单旋和右单旋，其实左右双旋最难控制的是平衡因子怎么变化。
我们先来看上图
当在b出插入一个值时，此时的subLR的平衡因子为-1，在进行左右双旋之后，parent的平衡因子变为1，而subL的平衡因子变为0。
再来看下边这张图：

当subLR的平衡因子为1时，在进行左右双旋之后，parent的平衡因子为0，而subL的平衡因子为-1.

最后一种情况就是h的高度为0时，更新好的平衡因子都是0.

void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//Node* pparent = parent->_parent;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;}else if(bf == 0){parent->_bf = subL->_bf = 0;}else{assert(false);}}

4.右左双旋

在当父结点在平衡因子为2，而子节点的平衡因子为-1时，要对父节点进行右左双旋。
进行右左双旋要进行以下的步骤：

1.对父节点的右子树进行右单旋。
2.对父节点进行左单旋。
3.更新平衡因子。

与左右双旋类似，前边的旋转可以直接复用左单旋与右单旋，而关键的是更新平衡因子。
我们通过以下的图片来判断如果更新平衡因子：

当subRL的平衡因子为1，即在c处插入

当subRL的平衡因子为-1，即在b处插入

void RotateRL(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;parent->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;}else if(bf==0){subR->_bf = parent->_bf = 0;}else{assert(false);}}

五、 AVL树的验证

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

1. 验证其为二叉搜索树
   如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2. 验证其为平衡树

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

节点的平衡因子是否计算正确

public:void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}int Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}

我们通过生成随机数来检测是否为AVL树：

void TestAVLTree2()
{size_t N = 100;srand(time(0));AVL<int, int> t1;for (size_t i = 0; i < N; ++i){int x = rand();t1.insert(make_pair(x, i));bool ret = t1.IsBalance();if (ret == false){int u = 1;}else{cout << "Insert:" << x << " IsBalance:" <<ret<< endl;}}cout << "IsBalance:" << t1.IsBalance() << endl;
}

六、完整源码

AVL.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;template<class K,class V>
class treeNode
{
public:treeNode(const pair<K,V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr),_bf(0),_kv(kv){}treeNode<K,V>* _left;treeNode<K, V>* _right;treeNode<K, V>* _parent;int _bf;pair<K, V> _kv;
};template<class K,class V>
class AVL
{
public:typedef treeNode<K, V> Node;//AVL()//{//}//~AVL()//{//}bool insert(const pair<K,V>& kv){if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;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->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;while (parent){if (cur == parent->_left){parent->_bf--;}if (cur == parent->_right){parent->_bf++;}if (parent->_bf == 0){break;}else if (abs(parent->_bf) == 1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent-> _bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}}}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){return _IsBalance(_root);}
private:void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;Node* pparent = parent->_parent;parent->_parent = subL;subL->_right = parent;parent->_left = subLR;if(subLR)subLR->_parent = parent;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parent == pparent->_left){pparent->_left = subL;}else{pparent->_right = subL;}subL->_parent = pparent;}subL->_bf = parent->_bf = 0;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* pparent = parent->_parent;parent->_parent = subR;subR->_left = parent;parent->_right = subRL;if(subRL)subRL->_parent = parent;if (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (parent == pparent->_left){pparent->_left = subR;}else{pparent->_right = subR;}subR->_parent = pparent;}subR->_bf = parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;//Node* pparent = parent->_parent;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){parent->_bf = 1;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;}else if(bf == 0){parent->_bf = subL->_bf = 0;}else{assert(false);}}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;//Node* pparent = parent->_parent;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == -1){subR->_bf = 1;parent->_bf = 0;}else if (bf == 1){parent->_bf = -1;subR->_bf = 0;}else if(bf==0){subR->_bf = parent->_bf = 0;}else{assert(false);}}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool _IsBalance(Node* root){if (root == nullptr){return true;}int leftHT = Height(root->_left);int rightHT = Height(root->_right);int diff = rightHT - leftHT;if (diff != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(diff) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}int Height(Node* root){if (root == nullptr)return 0;return max(Height(root->_left), Height(root->_right)) + 1;}Node* _root = nullptr;
};//void testAVL()
//{
//	AVL<int, int> a;
//	
//}
void TestAVLTree1()
{int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };  // 测试双旋平衡因子调节//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVL<int, int> t1;for (auto e : a){t1.insert(make_pair(e, e));}t1.InOrder();cout << "IsBalance:" << t1.IsBalance() << endl;
}
void TestAVLTree2()
{size_t N = 100;srand(time(0));AVL<int, int> t1;for (size_t i = 0; i < N; ++i){int x = rand();t1.insert(make_pair(x, i));bool ret = t1.IsBalance();if (ret == false){int u = 1;}else{cout << "Insert:" << x << " IsBalance:" <<ret<< endl;}}cout << "IsBalance:" << t1.IsBalance() << endl;
}

test.cpp

#include"AVL.h"int main()
{//TestAVLTree1();TestAVLTree2();return 0;
}