AVL树是平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

AVL树的性质

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

树中的每个左子树和右子树都是AVL树

节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

#include<iostream>usingnamespacestd;//平衡搜索二叉树template<classK,classV>structAVLTreeNode{AVLTreeNode(K&key,V&val):_key(key),_val(val),_left(NULL),_right(NULL),_parent(NULL),_bf(0){}K_key;V_val;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;//BalanceFactor};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree():_root(NULL){}boolInsert(K&key,V&val){if(_root==NULL){_root=newNode(key,val);returntrue;}else{Node*cur=_root;Node*parent=NULL;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}elsereturnfalse;}cur=newNode(key,val);if(parent->_key>key){parent->_left=cur;cur->_parent=parent;}else{parent->_right=cur;cur->_parent=parent;}//更新平衡因子，不平衡进行旋转while(parent!=NULL){if(cur==parent->_left)++parent->_bf;else--parent->_bf;//跳出条件if(parent->_bf==0)break;elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=cur->_parent;}else//-22旋转{if(parent->_bf==2){if(1==cur->_bf)//右旋{RotateR(parent);}else//左右旋{RotateLR(parent);}}else{if(1==cur->_bf)//左右旋{RotateRL(parent);}else//左旋{RotateL(parent);}}break;}}returntrue;}}Node*Find(K&key){if(_root==NULL)returnfalse;else{Node*cur=_root;while(cur){if(cur->_key>key)cur=cur->_left;elseif(cur->_key<key)cur=cur->_right;elsereturncur;}returnNULL;}}boolRemove(K&key){if(_root==NULL)returnfalse;Node*cur=_root;Node*parent=NULL;while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{Node*del=NULL;if(cur->_left==NULL){del=cur;if(cur==_root){_root=cur->_right;_root->_parent=NULL;}else{if(parent->_left==cur){parent->_left=cur->_right;cur->_parent=parent;}else{parent->_right=cur->_right;cur->_parent=parent;}}}elseif(cur->_right==NULL){del=cur;if(cur==_root){_root=cur->_left;_root->_parent=NULL;}else{if(parent->_left==cur){parent->_left=cur->_left;cur->_parent=parent;}else{parent->_right=cur->_left;cur->_parent=parent;}}}else//左右都不为空{Node*rightMin=root->_right;Node*parent=root;while(rightMin->_left){parent=rightMin;rightMin=rightMin->_left;}root->_key=rightMin->_key;root->_val=rightMin->_val;del=rightMin;if(parent->_left==rightMin)parent->_left=NULL;elseparent->_right=NULL;}deletedel;}}returnfalse;}voidInOrder(){_InOrder(_root);}boolIsBalance(){return_IsBalance(_root);}intHeight(){return_Height(_root);}protected:int_Height(Node*root){if(root==NULL)return0;intleft=_Height(root->_left);intright=_Height(root->_right);returnleft>right?left+1:right+1;}bool_IsBalance(Node*root){if(root==NULL)returntrue;intleft=_Height(root->_left);intright=_Height(root->_right);if(left-right!=root->_bf){cout<<"平衡因子错误，不平衡"<<root->_key<<endl;returnfalse;}returnabs(left-right)<2&&_IsBalance(root->_left)&&_IsBalance(root->_right);}void_InOrder(Node*root){if(root==NULL)return;_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL)subRL->_parent=parent;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;if(ppNode==NULL){_root=subR;subR->_parent=NULL;}else{if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;subR->_parent=ppNode;}subR->_bf=parent->_bf=0;}voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*ppNode=parent->_parent;subL->_right=parent;parent->_parent=subL;if(ppNode==NULL){_root=subL;subL->_parent=NULL;}else{if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;subL->_parent=ppNode;}subL->_bf=parent->_bf=0;}voidRotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;RotateL(parent->_left);RotateR(parent);if(bf==1){parent->_bf=-1;subL->_bf=0;}elseif(bf==-1){subL->_bf=1;parent->_bf=0;}elsesubL->_bf=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){parent->_bf=0;subR->_bf=-1;}elseif(bf==-1){subR->_bf=0;parent->_bf=1;}elsesubR->_bf=parent->_bf=0;}private:Node*_root;};voidTest1(){AVLTree<int,int>t;inta[]={16,3,7,11,9,26,18,14,15};for(inti=0;i<sizeof(a)/sizeof(a[0]);++i){t.Insert(a[i],i);}t.InOrder();t.IsBalance();}intmain(){Test1();system("pause");return0;}