一. 什么是AVL树

二. AVL树的节点定义

三. AVL树的插入操作

3.1 寻找插入位置

3.2 更新平衡因子

3.3 AVL树的旋转调整

3.4 AVL树插入操作的整体实现

四. AVL树的检验

附录：AVL树的实现完整代码

AVL树定义代码 -- AVLTree.h

AVL树检验代码 -- test.cpp

一. 什么是AVL树

AVL树，是二叉搜索树的一种特殊形式。一般的二叉搜索树，如果插入节点的数据有序或十分接近有序，那么二叉搜索树就会退化为近似单叉树，这样查找数据的时间复杂度就会变为O(1)，从而失去高效查找的能力。

为了解决普通二叉搜索树的这一缺陷，两位俄罗斯数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种二叉搜索树的平衡模式 -- AVL树，AVL树的左右子树的高度差不超过1，因此可以保证时间复杂度为O(logN)的查找。

AVL树要么为空树，要么满足以下三个条件：

左右子树均为AVL树。
左右子树的高度差（平衡因子）不超过1。
节点的数据满足二叉搜索树（左子树节点小于根节点，右子树节点大于根节点）

其中，平衡因子 = 右子树高度 - 左子树高度。

二. AVL树的节点定义

AVL树一般定义为三叉链结构，每个节点包含3个指针，分别为：指向左子树根节点的指针_left、指向右子树根节点的指针_right、指向父亲节点的指针_parent。同时，每个节点还应当记录该节点的平衡因子_bf以及节点数据_kv（键值对）。

代码2.1：（AVL树节点定义）

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;std::pair<K, V> _kv;int _bf;   //平衡因子AVLTreeNode(const std::pair<K, V>& kv)   //构造函数: _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){ }
};

三. AVL树的插入操作

3.1 寻找插入位置

AVL树寻找插入位置的操作规则，与普通的二叉搜索树一致，为：

如果当前位置为nullptr，那么该位置为插入节点的位置。
如果当前节点值大于要插入的值，到该节点的左子树去查找。
如果当前节点值小于要插入的值，到该节点的右子树去查找。
如果当前节点值等于要插入的值，则插入失败。（二叉搜索树一般不允许存在相同的节点）。

代码3.1：（查找插入位置并插入节点）

	//找要插入节点的位置Node* cur = _root;   //root为AVL树的根节点Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//插入节点Node* newNode = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = newNode;newNode->_parent = parent;}else{parent->_right = newNode;newNode->_parent = parent;}

3.2 更新平衡因子

由于插入节点会影响新插入节点的父亲节点的左右子树高度，因此，父亲节点的平衡因子需要更新，平衡因子的更新遵循以下几条规则。

如果新节点插入在右子树，那么父亲节点的平衡因子+1。
如果新节点插入在左子树，那么父亲节点的平衡因子-1。
若插入节点后，parent->_bf == 1或-1成立，说明parent节点原来的平衡因子为0，左右子树高度相同，那么新插入的节点引发了parent的高度变化，但还没有打破平衡，需要继续向上更新。
如果插入节点后，parent->_bf == 0成立，那么原来父亲节点的平衡因子为-1或1，且插入在了父亲节点较矮的子树中，parent的高度没有发生改变，不继续向上更新。
若插入节点后，parent->_bf == 2或-2成立，那么parent原来的平衡因子为1或-1，处于平衡的临界状态，继续插入节点平衡被打破，不再满足AVL树的结构要求，需要进行旋转调整(详见3.3)。
若插入节点后，parent->_bf>=3或parent->_bf<=-3，那说明之前的插入操作存在问题，需要进行检查排错。

代码3.2：（调整平衡因子）

	//调整平衡因子cur = newNode;  //新节点while (parent){//如果新插入的节点位于右子树，那么父亲节点平衡因子+1if (parent->_right == cur){++parent->_bf;}else if (parent->_left == cur){//如果新插入的节点位于左子树，那么父亲节点的平衡因子-1--parent->_bf;}else{//int a = 0;assert(false);}if (parent->_bf == 0){//如果插入节点后父亲节点的平衡因子变为0，那么父亲节点原来的平衡因子为1或-1//那么插入节点在较矮的一侧，树的高度没有发生变化break;}else if (parent->_bf == 1 || parent->_bf == -1){//说明原来父亲节点的平衡因子为0，插入后树的高度发生变化，要继续向上更改平衡因子parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//在较长的一边插入，此时结构已不满足AVL树的结构，要进行旋转// ......  旋转调整代码略break;}else if (parent->_bf >= 3 || parent->_bf <= -3){assert(false);}}

3.3 AVL树的旋转调整

如果插入新节点后，parent->_bf == 2/-2成立，那么就需要通过旋转调整来使树的结构平衡，对于AVL树的选择，可以分为以下四种情况来讨论。

如果插入节点在较高右子树的右子树 -- 右右：单左旋调整
如果插入节点在较高左子树的左子树 -- 左左：单右旋调整
如果插入节点在较高右子树的左子树 -- 右左：先进行单右旋再进行单左旋（右左双旋调整）
如果插入节点在较高左子树的右子树 -- 左右：先进行单左旋再进行单右旋（左右双旋调整）

左单旋

将右子节点的左子节点托管给parent的右子节点，然后将parent节点托管给右子节点的左子节点。之后，将原父亲节点和右子节点的平衡因子全部更新为0。

代码3.3：（左单旋）

	void RotateL(Node* parent)   //左单旋函数{Node* ppNode = parent->_parent;Node* pR = parent->_right;Node* pRL = pR->_left;//右子节点的左子节点托管给父亲节点的右子节点parent->_right = pRL;if (pRL != nullptr){pRL->_parent = parent;}//父亲节点托管给右子节点的左子节点pR->_left = parent;parent->_parent = pR;if (_root == parent){_root = pR;pR->_parent = nullptr;}else{pR->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = pR;}else{ppNode->_right = pR;}}parent->_bf = 0;pR->_bf = 0;}

右单旋

将左子节点的右子节点托管给parent的左子节点，然后将parent节点托管给原左子节点的右子节点，更新原parent节点和左子节点的平衡因子为1。

代码3.4：（右单旋）

	void RotateR(Node* parent)    //右单旋函数{Node* ppNode = parent->_parent;Node* pL = parent->_left;Node* pLR = pL->_right;//将左子节点的右子节点托管给父亲节点的左子节点parent->_left = pLR;if (pLR != nullptr){pLR->_parent = parent;}//将父亲节点托管给左子节点的右子节点pL->_right = parent;parent->_parent = pL;if (_root == parent){_root = pL;pL->_parent = nullptr;}else{pL->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = pL;}else{ppNode->_right = pL;}}pL->_bf = 0;parent->_bf = 0;}

右左双旋

先对parent节点的右子节点pR进行右单旋操作，然后对parent节点进行左单旋操作。根据pR的左子节点pRL的平衡因子（三种情况讨论），确定旋转后每个节点的平衡因子进行更新。

代码3.5：（右左双旋）

	void RotateRL(Node* parent)   //右左双旋函数{Node* pR = parent->_right;Node* pRL = pR->_left;int bf = pRL->_bf;    //右子节点的左子节点的平衡因子RotateR(pR);  //对右子节点进行右单旋RotateL(parent);  //对父亲节点进行左单旋//更新平衡因子if (bf == 1){pR->_bf = 0;parent->_bf = -1;pRL->_bf = 0;}else if (bf == -1){pR->_bf = 1;parent->_bf = 0;pRL->_bf = 0;}else if(bf == 0){pRL->_bf = 0;pR->_bf = 0;parent->_bf = 0;}else{assert(false);}}

左右双旋

先针对parent节点的左子节点pL进行单左旋，然后再对parent节点进行单右旋，最后根据pL节点的右子节点pLR的平衡因子，更改每个节点的平衡因子。

代码3.6：（左右双旋）

	void RotateLR(Node* parent){Node* pL = parent->_left;Node* pLR = pL->_right;int bf = pLR->_bf;RotateL(pL);RotateR(parent);   //前后执行左右单旋if (bf == 1){pL->_bf = -1;parent->_bf = 0;pLR->_bf = 0;}else if (bf == -1){pL->_bf = 0;parent->_bf = 1;pLR->_bf = 0;}else if(bf == 0){pL->_bf = 0;parent->_bf = 0;pLR->_bf = 0;}else{assert(false);}}

3.4 AVL树插入操作的整体实现

通过3.1~3.3的分析，我们可以总结出，AVL树的插入操作步骤如下：

查找插入位置，找到了就新建节点插入，找不到函数终止运行。
调整平衡因子。
如果出现parent->_bf == 2或parent->_bf == -2，那么就对AVL树进行旋转调整。

代码3.7：（AVL树插入操作的主函数）

    bool insert(const std::pair<K, V>& kv)  //节点插入函数{if (_root == nullptr){Node* newNode = new Node(kv);   //新节点_root = newNode;return true;}//找要插入节点的位置Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//插入节点Node* newNode = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = newNode;newNode->_parent = parent;}else{parent->_right = newNode;newNode->_parent = parent;}//调整平衡因子cur = newNode;  //新节点while (parent){//如果新插入的节点位于右子树，那么父亲节点平衡因子+1if (parent->_right == cur){++parent->_bf;}else if(parent->_left == cur){//如果新插入的节点位于左子树，那么父亲节点的平衡因子-1--parent->_bf;}else{//int a = 0;assert(false);}if (parent->_bf == 0){//如果插入节点后父亲节点的平衡因子变为0，那么父亲节点原来的平衡因子为1或-1//那么插入节点在较矮的一侧，树的高度没有发生变化break;}else if (parent->_bf == 1 || parent->_bf == -1){//说明原来父亲节点的平衡因子为0，插入后树的高度发生变化，要继续向上更改平衡因子parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//在较长的一边插入，此时结构已不满足AVL树的结构，要进行旋转//旋转要分4种情况讨论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 if(parent->_bf >= 3 || parent->_bf <= -3){assert(false);}}return true;}

四. AVL树的检验

要验证通过插入节点创建的AVL树是否正确，应当通过下面两重检验：

验证其为搜索二叉树。
验证其为平衡树。

验证搜索二叉树

搜索二叉树的检验，只需对二叉树进行中序遍历，如果得到的结果为升序排列的数据，那就说明该树为搜索二叉树。

代码4.1：（中序遍历）

	//中序遍历函数void InOrder(){_InOrder(_root);std::cout << std::endl;}//子函数void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}

验证平衡树

平衡树的验证也需要以下两重检验：

检验左右子树的高度差是否不超过1，如果任何一颗子树的左右子树高度差超过1，则不满足平衡树的结构要求。
检验平衡因子是否正确，算出右子树高度 - 左子树高度的值，与本节点的平衡因子比较，看是否相等，不等就不是平衡树。

代码4.2：（平衡树检验）

	bool isAVLTree()  //检查是否为AVL树（平衡树）{return _isAVLTree(_root);}bool _isAVLTree(Node* root){if (root == nullptr){return true;}int leftHigh = TreeHigh(root->_left);int rightHigh = TreeHigh(root->_right);   //调用TreeHigh函数求左右子树高度if (root->_bf != rightHigh - leftHigh){std::cout << "平衡因子异常" << " ";return false;}return abs(rightHigh - leftHigh) < 2 && _isAVLTree(root->_left) && _isAVLTree(root->_right);}

代码4.3：（求二叉树的高度）

	int TreeHigh(Node* root){if (nullptr == root){return 0;}int left = TreeHigh(root->_left);int right = TreeHigh(root->_right);return left > right ? left + 1 : right + 1;}

附录：AVL树的实现完整代码

AVL树定义代码 -- AVLTree.h

//AVLTree.h
#pragma once#include<iostream>
#include<utility>
#include<assert.h>
#include<math.h>template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;std::pair<K, V> _kv;int _bf;   //平衡因子AVLTreeNode(const std::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;public:bool insert(const std::pair<K, V>& kv)  //节点插入函数{if (_root == nullptr){Node* newNode = new Node(kv);   //新节点_root = newNode;return true;}//找要插入节点的位置Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}//插入节点Node* newNode = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = newNode;newNode->_parent = parent;}else{parent->_right = newNode;newNode->_parent = parent;}//调整平衡因子cur = newNode;  //新节点while (parent){//如果新插入的节点位于右子树，那么父亲节点平衡因子+1if (parent->_right == cur){++parent->_bf;}else if(parent->_left == cur){//如果新插入的节点位于左子树，那么父亲节点的平衡因子-1--parent->_bf;}else{//int a = 0;assert(false);}if (parent->_bf == 0){//如果插入节点后父亲节点的平衡因子变为0，那么父亲节点原来的平衡因子为1或-1//那么插入节点在较矮的一侧，树的高度没有发生变化break;}else if (parent->_bf == 1 || parent->_bf == -1){//说明原来父亲节点的平衡因子为0，插入后树的高度发生变化，要继续向上更改平衡因子parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){//在较长的一边插入，此时结构已不满足AVL树的结构，要进行旋转//旋转要分4种情况讨论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 if(parent->_bf >= 3 || parent->_bf <= -3){assert(false);}}return true;}//中序遍历函数void InOrder(){_InOrder(_root);std::cout << std::endl;}bool isAVLTree()  //检查是否为AVL树{return _isAVLTree(_root);}private:bool _isAVLTree(Node* root){if (root == nullptr){return true;}int leftHigh = TreeHigh(root->_left);int rightHigh = TreeHigh(root->_right);if (root->_bf != rightHigh - leftHigh){std::cout << "平衡因子异常" << " ";return false;}return abs(rightHigh - leftHigh) < 2 && _isAVLTree(root->_left) && _isAVLTree(root->_right);}int TreeHigh(Node* root){if (nullptr == root){return 0;}int left = TreeHigh(root->_left);int right = TreeHigh(root->_right);return left > right ? left + 1 : right + 1;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);std::cout << root->_kv.first << " ";_InOrder(root->_right);}void RotateL(Node* parent)   //左单旋函数{Node* ppNode = parent->_parent;Node* pR = parent->_right;Node* pRL = pR->_left;//右子节点的左子节点托管给父亲节点的右子节点parent->_right = pRL;if (pRL != nullptr){pRL->_parent = parent;}//父亲节点托管给右子节点的左子节点pR->_left = parent;parent->_parent = pR;if (_root == parent){_root = pR;pR->_parent = nullptr;}else{pR->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = pR;}else{ppNode->_right = pR;}}parent->_bf = 0;pR->_bf = 0;}void RotateR(Node* parent)    //右单旋函数{Node* ppNode = parent->_parent;Node* pL = parent->_left;Node* pLR = pL->_right;//将左子节点的右子节点托管给父亲节点的左子节点parent->_left = pLR;if (pLR != nullptr){pLR->_parent = parent;}//将父亲节点托管给左子节点的右子节点pL->_right = parent;parent->_parent = pL;if (_root == parent){_root = pL;pL->_parent = nullptr;}else{pL->_parent = ppNode;if (ppNode->_left == parent){ppNode->_left = pL;}else{ppNode->_right = pL;}}pL->_bf = 0;parent->_bf = 0;}void RotateRL(Node* parent)   //右左双旋函数{Node* pR = parent->_right;Node* pRL = pR->_left;int bf = pRL->_bf;    //右子节点的左子节点的平衡因子RotateR(pR);  //对右子节点进行右单旋RotateL(parent);  //对父亲节点进行左单旋//更新平衡因子if (bf == 1){pR->_bf = 0;parent->_bf = -1;pRL->_bf = 0;}else if (bf == -1){pR->_bf = 1;parent->_bf = 0;pRL->_bf = 0;}else if(bf == 0){pRL->_bf = 0;pR->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* pL = parent->_left;Node* pLR = pL->_right;int bf = pLR->_bf;RotateL(pL);RotateR(parent);   //前后执行左右单旋if (bf == 1){pL->_bf = -1;parent->_bf = 0;pLR->_bf = 0;}else if (bf == -1){pL->_bf = 0;parent->_bf = 1;pLR->_bf = 0;}else if(bf == 0){pL->_bf = 0;parent->_bf = 0;pLR->_bf = 0;}else{assert(false);}}private:Node* _root = nullptr;  //根节点
};

AVL树检验代码 -- test.cpp

//test.cpp
#include<iostream>
#include<stdlib.h>
#include<time.h>
#include "AVLTree.h"void TestAVLTree1()
{AVLTree<int, int> at;int arr[] = { 10, 9, 7 };for (auto& e : arr){at.insert(std::make_pair(e, 0));}int a = 0;
}void TestAVLTree2()
{AVLTree<int, int> at;//srand(time(nullptr));for (int i = 0; i < 1000; ++i){int e = rand();std::cout << e << " " << "num=" << i << std::endl;at.insert(std::make_pair(e, i));bool ret = at.isAVLTree();if (!ret){std::cout << "不是AVL树" << " ";}else{std::cout << "是AVL树" << " ";}std::cout << std::endl;}at.InOrder();
}int main()
{TestAVLTree2();return 0;
}