目录

一、AVL树的基本概念

二、AVL树的结点定义

三、AVL树的插入

四、AVL树的旋转

1. 右单旋

2. 左单旋

3. 右左双旋

4. 左右双旋 

五、AVL树的验证 

六、AVL树的性能

七、源代码 

一、AVL树的基本概念

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

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

1. 树的左右子树都是AVL树。
2. 树的左右子树高度之差（简称平衡因子）的绝对值不超过1（-1/0/1）。

        我们以 右树的高度 - 左树的高度 为例进行标注，只要所有的子树满足其绝对值不超过1，那么该二叉搜索树就是AVL树；

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(logN)，搜索时间复杂度O(logN)。

二、AVL树的结点定义

        这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度 <= 1）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，所以新构造结点的平衡因子初始设置为0即可。

        注意： 给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过会麻烦一点。

template
struct AVLTreeNode
{//三叉链AVLTreeNode* _left;   //该结点的左孩子AVLTreeNode* _right;  //该结点的右孩子AVLTreeNode* _parent; //该结点的父亲//存储键值对pair _kv;//平衡因子 (规则：右子树-左子树<=1)int _bf; //blance factor 平衡因子 //构造函数AVLTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

三、AVL树的插入

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

1. 按照二叉搜索树的插入方法，找到待插入位置并插入到树中。
2. 更新平衡因子，如果出现不平衡，则需要进行旋转。

以上图为例：

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

• 当新插入结点的key值 比 当前结点的key值小就插入到该结点的左子树。
• 当新插入结点的key值 比 当前结点的key值大就插入到该结点的右子树。
• 当新插入结点的key值 和 当前结点的key值相等就插入失败。

        当新增结点插入之前，每个结点的平衡因子都已经确定好了（是满足条件的）；新增结点插入以后，它会影响从根结点到其自身这条路径上的平衡因子（有可能不满足条件），所以就需要我们从新增结点的父节点开始不断向上调整平衡因子（如：新增结点->6->7->5    这条路径的平衡因子）

2. 调整节点的平衡因子 规定如下：

• 新增结点如果在parent的右边，parent的平衡因子++
• 新增结点如果在parent的左边，parent的平衡因子−−

每更新完一个结点的平衡因子后，都需要进行以下判断：

• 如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
• 如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
• 如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。

如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子：

        只有0经过−−/++ 操作后会变成-1/1，说明新增结点的插入使得parent的左子树或右子树增高了，即改变了以parent为根结点的子树的高度，从而会影响parent的父结点的平衡因子，因此需要继续往上更新平衡因子。

-------------------------------------------------------------------------------------------------------------------------

如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了：

        只有-1/1经过 ++/−− 操作后会变成0，说明新增结点插入到了parent左右子树当中高度较矮的一棵子树，插入后使得parent左右子树的高度相等了，此操作并没有改变以parent为根结点的子树的高度，从而不会影响parent的父结点的平衡因子，因此无需继续往上更新平衡因子。

 -------------------------------------------------------------------------------------------------------------------------

如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理：

        此时parent结点的左右子树高度之差的绝对值已经超过1了，不满足AVL树的要求，因此需要进行旋转处理。

         通过对上面的平衡因子分析来看，我们可以发现，当parent的平衡因子为-2/2时，已经反映出对于某个节点的左右子树高度差已经超过了1，就需要进行旋转，对于旋转又分为四种旋转，我们先进行简单的分析：

        我们假设新增结点为cur，父节点为parent，更新平衡因子的操作就是通过不断调整cur和parent的位置是更新平衡因子，就有如下操作

cur = parent;             //新增结点更新到其父节点的位置
parent = parent->_parent; //父节点更新到自己父节点的位置

先简单介绍一下四种情况，后面具体介绍：

情况1：当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋

情况2：当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋

情况3：当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋

情况4：当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋

以下是基本的代码结构：

bool Insert(const pair& kv)
{if (_root == nullptr)//若AVL树为空树，则插入结点直接作为根结点{_root = new Node(kv);return true;}//按照二叉搜索树的插入规则，先找到正确的插入点Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first)//待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first)//待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_left;}else  //待插入结点的key值等于当前结点的key值{return false;   //插入失败}}cur = new Node(kv);//直接new一个节点插入if (parent->_kv.first < kv.first)//新结点的key值大于parent的key值{//插入到parent的右边parent->_right = cur;cur->_parent = parent;}else  //新结点的key值小于parent的key值{//插入到parent的左边parent->_left = cur;cur->_parent = parent;}/*控制平衡1.更新平衡因子---更新新增结点到根结点的祖先路劲2.出现异常平衡因子，那么就需要旋转平衡处理*/while (parent) //最坏的情况一路更新到根结点{if (cur == parent->_left)//cur插入在parent的左边{parent->_bf--;  //parent的平衡因子--}else   //cur插入在parent的右边{parent->_bf++;  //parent的平衡因子++}//判断是否更新结束或需要进行旋转if (parent->_bf == 0)//更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）{break;}else if (parent->_bf == 1 || parent->_bf == -1)//需要继续往上更新平衡因子{cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//需要进行旋转（此时parent树已经不平衡了）{//旋转处理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;//部分子树旋转完毕后高度和插入之前一样，不会影响上一层，可以直接break}else //说明插入,更新平衡因子之前，树中平衡因子就有问题了{			assert(false);}}return true; //插入成功
}

四、AVL树的旋转

1. 右单旋

        从下面的抽象图可以看出树是处于平衡的一种状态，当h变化时，所得到的的树是不同的，当h=2时当然不只有这一种情况，所以我们就不可能将所有情况都画出来一一分析，对于右单旋来说，是因为插入的结点导致原本平衡的树，其左子树变高了，所以我们就要试图改变右子树的高度来解决左子树和右子树的高度差 <= 1;那么就需要对其进行右单旋的操作。

        当我们在a这棵树插入一个结点的时候，就会导致该树左子树高了，分别对应到h=0/1/2的情况，都是类似的，这样子思考下来整体就容易理解了；

我们先对h=0/1/2这三种情况在a出进行插入节点，然后来进行右单旋

新节点插入较高左子树的左侧---左左：右单旋（抽象图旋转演示）

右单旋代码如下：

void RotateR(Node* parent)
{//首先确定好subL/subLR的位置Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;     //让父节点指向subLRif (subLR){subLR->_parent = parent;//如果subLR不为空，我们需要维护三叉链的关系，确定好subLR的父节点}Node* parentParent = parent->_parent;//记录一下父节点的父节点subL->_right = parent;  //让subL的右子树指向父节点parent->_parent = subL; //让subL作为parent的父亲if (parent == _root)//这里表明parent原来是根，让subL作为新的根{_root = subL;_root->_parent = nullptr;}else//这里表明parent是这棵树的局部子树，parent可能是某个节点的左孩子或右孩子{if (parentParent->_left == parent)//如果parent是某个节点的左孩子{parentParent->_left = subL;//让subL成为新的左孩子}else{parentParent->_right = subL;//如果parent是某个节点的右孩子}subL->_parent = parentParent;//让subL成为新的右孩子}subL->_bf = parent->_bf = 0;//更新平衡因子
}

2. 左单旋

 左单旋和右单旋如出一辙

 我们先对h=0/1/2这三种情况在c出进行插入节点，然后来进行左单旋

新节点插入较高右子树的右侧---右右：左单旋（抽象图旋转演示）

左单旋代码如下： 

//左单选
void RotateL(Node* parent)
{//首先确定好subR/subRL的位置Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL; //让父节点指向subRLif (subRL){subRL->_parent = parent;//如果subRL不为空，我们需要维护三叉链的关系，确定好subRL的父节点}Node* parentParent = parent->_parent;//记录一下父节点的父节点subR->_left = parent;   //让subR的左子树指向父节点parent->_parent = subR; //让subR作为parent的父亲if (parent == _root)//这里表明parent原来是根，让subR作为新的根{_root = subR;		subR->_parent = nullptr;}else //这里表明parent是这棵树的局部子树，parent可能是某个节点的左孩子或右孩子{if (parentParent->_left == parent)//如果parent是某个节点的左孩子{parentParent->_left = subR; //让subR成为新的左孩子}else  //如果parent是某个节点的右孩子{parentParent->_right = subR;}subR->_parent = parentParent; //让subR成为新的右孩子}subR->_bf = parent->_bf = 0;//更新平衡因子
}

3. 右左双旋

        从下面给出的抽象图可以看出，当h=0/1/2时，和左单旋给出的图是一样的，只不过刚刚是在90的右侧插入的（即：新节点插入较高右子树的右侧---右右：左单旋），那我们在90的左侧插入一个新结点（即：新节点插入较高右子树的左侧---左右：先右单旋再左单旋），此时单旋是解决不了问题的。

为什么一个单旋解决不了问题？

        从上面给出的旋转图可以看出，我们将90的右子树给到30的右边，然后将30给到90的左边，然后更新平衡因子，按照正常更新完毕后的状态，平衡因子应该都是0，但是此图还是一种不平衡的状态，所以单旋解决不了问题。

 我们先对h=0/1/2这三种情况在90左侧进行插入节点，然后来进行右左双旋

 新节点插入较高右子树的左侧---左右：先右单旋再左单旋（抽象图旋转演示）

 旋转步骤:

1. 以subR为旋转点进行右单旋。
2. 以parent为旋转点进行左单旋。
3. 更新平衡因子。

右左双旋代码如下：

//右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);   //1、以subR为轴进行右单旋RotateL(parent); //2、以parent为轴进行左单旋//3、更新平衡因子if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);//在旋转前树的平衡因子就有问题}
}

4. 左右双旋 

左右双旋和右左双旋如出一辙，这里就不做过多的演示

 左右双旋代码如下：

//左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);//1、以subL为旋转点进行左单旋RotateR(parent); //2、以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 if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false); //在旋转前树的平衡因子就有问题}
}

五、AVL树的验证 

        AVL树是在二叉搜索树的基础上加入了平衡性的限制，也就是说AVL树也是二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断二叉树是否为二叉搜索树。 

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

        对于中序遍历只能保证它是二叉搜索树，要保证该二叉搜索树是否平衡还需要判断其平衡因子是否正确；

bool IsBalance()
{return _IsBalance(_root);
}bool _IsBalance(Node* root)
{if (root == nullptr){return true;}//对当前树进行检查int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}int Height(Node* root)
{if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

六、AVL树的性能

        AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如： 插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树， 但一个结构经常修改，就不太适合。

七、源代码 

AVLTree.h

#pragma once#include 
#include template
struct AVLTreeNode
{AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;pair _kv;int _bf; //blance factor 平衡因子 (规则：右子树-左子树<=1)AVLTreeNode(const pair& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template
class AVLTree
{typedef AVLTreeNode Node;
public:AVLTree():_root(nullptr){}bool Insert(const pair& 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;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}//控制平衡//1.更新平衡因子---更新新增结点到根结点的祖先路劲//2.出现异常平衡因子，那么就需要旋转平衡处理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){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;//部分子树旋转完毕后高度和插入之前一样，不会影响上一层，可以直接break}else//说明插入,更新平衡因子之前，树中平衡因子就有问题了{			assert(false);}}return true;}//左单选void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root)//这里表明原来是根{_root = subR;		subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}subR->_bf = parent->_bf = 0;}//由单旋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;if (parent == _root)//这里表明原来是根{_root = subL;_root->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}subL->_bf = parent->_bf = 0;}//左右双旋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 if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else{assert(false);}}//右左双旋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 = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 0){parent->_bf = 0;subR->_bf = 0;subRL->_bf = 0;}else{assert(false);}}void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}bool IsBalance(){return _IsBalance(_root);}bool _IsBalance(Node* root){if (root == nullptr){return true;}//对当前树进行检查int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "现在是：" << root->_bf << endl;cout << root->_kv.first << "应该是：" << rightHeight - leftHeight << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);}int Height(Node* root){if (root == nullptr){return 0;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}private:Node* _root;
};void test1()
{AVLTree t;//int a[] = { 5,4,3,2,1,0 };//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(make_pair(e, e));cout << "Insert" << e << ":" <<  t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}