AVL树是高度平衡的二叉搜索树，较搜索树而言降低了树的高度；时间复杂度减少了使其搜索起来更方便；

1.性质：

（1）左子树和右子树高度之差绝对值不超过1；

（2）树中每个左子树和右子树都必须为AVL树；

（3）每一个节点都有一个平衡因子（-1,0,1：右子树-左子树）

（4）遍历一个二叉搜索树可以得到一个递增的有序序列

2.结构：

平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的。任意性非常大。它仅仅与节点的值和插入的顺序有关系。往往得到的是一个不平衡的二叉树。在最坏的情况下。可能得到的是一个单支二叉树，其高度和节点数同样，相当于一个单链表。对其正常的时间复杂度有O(lb n)变成了O(n)。从而丧失了二叉排序树的一些应该有的长处。

当插入一个新的节点的时候。在普通的二叉树中不用考虑树的平衡因子，仅仅要将大于根节点的值插入到右子树，小于节点的值插入到左子树，递归就可以。

而在平衡二叉树则不一样，在插入节点的时候，假设插入节点之后有一个节点的平衡因子要大于2或者小于-2的时候，他须要对其进行调整。如今仅仅考虑插入到节点的左子树部分（右子树与此同样）。主要分为下面三种情况：

(1)若插入前一部分节点的左子树高度和右子树高度相等。即平衡因子为0。插入后平衡因子变为1。仍符合平衡的条件不用调整。

(2)若插入前左子树高度小于右子树高度。即平衡因子为-1，则插入后将使平衡因子变为0，平衡性反倒得到调整，所以不必调整。

(3)若插入前左子树的高度大于右子树高度。即平衡因子为1。则插入左子树之后会使得平衡因子变为2，这种情况下就破坏了平衡二叉树的结构。所以必须对其进行调整，使其加以改善。

调整二叉树首先要明确一个定义。即最小不平衡子树。最小不平衡子树是指以离插入节点近期、且平衡因子绝对值大于1的节点做根的子树。

在构建AVL树的时候使用三叉链：parent,left,right方便回溯，也可以用递归或者栈解决；

在插入一个新节点后，一个平衡二叉树可能失衡，失衡情况下相应的调整方法

（1）右旋

（2）左旋

（3）右左双旋

（4）左右双旋

#include<iostream>usingnamespacestd;template<classK,classV>structAVLTreeNode{AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;K_key;V_value;int_bf;//平衡因子AVLTreeNode(constK&key,constV&value):_bf(0),_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;protected:Node*_root;public:AVLTree():_root(NULL){}boolInsert(constK&key,constV&value){if(_root==NULL){_root=newNode(key,value);returntrue;}Node*cur=_root;Node*parent=NULL;while(cur){if(cur->_key>key){parent=cur;cur=cur->_left;}elseif(cur->_key<key){parent=cur;cur=cur->_right;}else{returnfalse;}}//插入cur=newNode(key,value);if(parent->_key<key){parent->_right=cur;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}//检查是否平衡//1更新平衡因子，不满足条件时进行旋转while(parent){if(cur==parent->_left)parent->_bf--;elseparent->_bf++;if(parent->_bf==0){break;}//-11elseif(parent->_bf==-1||parent->_bf==1){cur=parent;parent=cur->_parent;}else{//旋转处理2-2if(cur->_bf==1){if(parent->_bf==2)RotateL(parent);else//-2RotateLR(parent);}else{if(parent->_bf==-2)RotateR(parent);else//2RotateRL(parent);}break;}}returntrue;}//左单旋voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;if(subRL)subRL->_parent=parent;subR->_left=parent;Node*ppNode=parent->_parent;parent->_parent=subR;if(ppNode==NULL){_root=subR;}else{if(ppNode->_left=parent){ppNode->_left=subR;}else{ppNode->_right=subR;}}parent->_bf=subR->_bf=0;}//右单旋voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;if(subLR)subLR->_parent=parent;subL->_right=parent;Node*ppNode=parent->_parent;if(ppNode==NULL){_root=subL;}else{if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;}parent->_bf=subL->_bf=0;}//左右双旋voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);//根据subLR的平衡因子修正其他节点的平衡因子if(bf==-1){subL->_bf=0;parent->_bf=1;}elseif(bf==1){subL->_bf=-1;parent->_bf=0;}}//右左双旋voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(parent->_right);RotateL(parent);if(bf==1){subR->_bf=0;parent->_bf=-1;}elseif(bf==-1){subR->_bf=1;parent->_bf=0;}}//中序遍历voidInorder(){_Inorder(_root);cout<<endl;}void_Inorder(Node*root){if(_root==NULL)return;_Inorder(root->_left);cout<<root->_key<<"";_Inorder(root->_right);}//判断是否平衡boolIsBalence(){return_IsBalence(_root);}bool_IsBalence(Node*root){if(root==NULL)returntrue;intleft=_Height(root->_left);intright=_Height(root->_right);if(right-left!=root->_bf||abs(right-left)>1){cout<<"节点的平衡因子异常"<<endl;cout<<root->_key;returnfalse;}return_IsBalence(root->_left)&&_IsBalence(root->_left);}//求子树的高度int_Height(Node*root){if(root==NULL)return0;intleft=_Height(root->_left);intright=_Height(root->_right);returnleft>right?left+1:right+1;}//前边方法的优化//后续遍历先求子书的高度的同时就可以//判断出子树是否平衡，然后依次求根节点的高度bool_Isbalence(Node*root,int&height){if(root==NULL){height=0;returntrue;}if(root->_left==NULL&&root->_right==NULL){height=1;returnntrue;}intleftheight=0;if(_Isbalence(root->_left,leftheight)==false)returnfalse;intrightheight=0;if(_Isbalence(root->_right,rightheight)==false)returnfalse;height=leftheight>rightheight?leftheight:rightheight;}};voidTestTree(){inta[]={16,3,7,11,9,26,18,14,15};AVLTree<int,int>t;for(size_ti=0;i<sizeof(a)/sizeof(a[0]);++i){t.Insert(a[i],i);}t.Inorder();cout<<"是否平衡?"<<t.IsBalence()<<endl;}