AVL树又称高度平衡的二叉搜索树，是1962年俄罗斯的数学家提出来的。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

AVL的性质：

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

（2）树中的每个左子树和右子树都是AVL树。

（3）每个节点都有一个平衡因子，任一节点的平衡因子是-1，0，1（每个节点的平衡因子等于右子树的高度减去左子树的高度）。

代码实现如下：

#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):_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;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->_left=cur;cur->_parent=parent;}else{parent->_right=cur;cur->_parent=parent;}//更新平衡因子//不平衡，则进行旋转while(parent){if(parent->_right==cur)parent->_bf++;elseparent->_bf--;//父节点平衡因子为0时，退出（说明父节点的两边高度一样，算路径长度的话都一样，没有影响）if(parent->_bf==0)break;//父节点平衡因子为1或-1的时候（说明是从0+1或0-1得来的），父节点两边高度不同，故需要继续更新平衡因子elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=cur->_parent;}//父节点平衡因子为2或-2时，旋转else//(parent->_bf==2||parent->_bf==-2)旋转{if(parent->_bf==-2){if(cur->_bf==-1)//右单旋{_RotateR(parent);}else//(cur->_bf==1)左右单旋{_RotateLR(parent);}}else//(parent->_bf==2){if(cur->_bf==1)//左单旋{_RotateL(parent);}else//(cur->_bf==-1)右左单旋{_RotateRL(parent);}}break;}}}Node*Find(constK&key){if(_root==NULL)returnfalse;Node*cur=_root;while(cur){if(cur->_key>key)cur=cur->_left;elseif(cur->_key<key)cur=cur->_right;elsereturncur;}returnfalse;}boolRemove(constK&key){if(_root==NULL)returnfalse;Node*parent=NULL;Node*cur=_root;while(cur){if(cur->_key>key){parent=cur;cur=cur->_left;}elseif(cur->_key<key){parent=cur;cur=cur->_right;}else{Node*del;if(cur->_right==NULL){del=cur;if(parent==NULL){_root=cur->_left;//_root->_bf=0;}else{if(parent->_left==cur){parent->_left=cur->_left;parent->_bf++;}else{parent->_right=cur->_left;parent->_bf--;}}deletedel;}elseif(cur->_left==NULL){del=cur;if(parent==NULL){_root=cur->_right;_root->_bf=0;}else{if(parent->_left==cur){parent->_left=cur->_right;parent->_bf++;}else{parent->_right=cur->_right;parent->_bf--;}}deletedel;}else{parent=cur;Node*left=cur->_right;while(left->_left){parent=left;left=left->_left;}del=left;cur->_key=left->_key;cur->_value=left->_value;if(parent->_left==left){parent->_left=left->_right;parent->_bf++;}else{parent->_right=left->_right;parent->_bf--;}deletedel;}break;}}if(cur==NULL){returnfalse;}while(parent){if(parent->_bf==0){break;}elseif(parent->_bf==1||parent->_bf==-1){break;}else//parent->_bf=2||parent->_bf=-2{if(parent->_bf==-2){if(cur->_bf==-1)_RotateR(parent);else//cur->_bf=1_RotateLR(parent);}else{if(cur->_bf==1)_RotateL(parent);else_RotateRL(parent);}break;}}returntrue;}voidInOrder(){_InOrder(_root);cout<<endl;}//判断这棵树是否是平衡搜索树boolIsBlance(){return_IsBlance(_root);}protected:void_RotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR!=NULL){subLR->_parent=parent;}subL->_right=parent;Node*ppNode=parent->_parent;parent->_parent=subL;if(ppNode==NULL){_root=subL;subL->_parent=NULL;}else{if(ppNode->_left==parent){ppNode->_left=subL;subL->_parent=ppNode;}else{ppNode->_right=subL;subL->_parent=ppNode;}}subL->_bf=parent->_bf=0;}void_RotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL!=NULL){subRL->_parent=parent;}subR->_left=parent;Node*ppNode=parent->_parent;parent->_parent=subR;if(ppNode==NULL){_root=subR;subR->_parent=NULL;}else{if(ppNode->_left==parent){ppNode->_left=subR;subR->_parent=ppNode;}else{ppNode->_right=subR;subR->_parent=ppNode;}}subR->_bf=parent->_bf=0;}void_RotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;_RotateR(parent->_right);_RotateL(parent);if(bf==1)//从subRL的右边插入{parent->_bf=-1;subR->_bf=0;}elseif(bf==-1)//从subRL的左边插入{parent->_bf=0;subR->_bf=1;}else//(bf=0){parent->_bf=0;subR->_bf=0;}subRL->_bf=0;}void_RotateLR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;intbf=subLR->_bf;_RotateL(parent->_left);_RotateR(parent);if(bf==1){parent->_bf=0;subL->_bf=-1;}elseif(bf==-1){parent->_bf=1;subL->_bf=0;}else//bf=0{parent->_bf=0;subL->_bf=0;}subLR->_bf=0;}bool_IsBlance(Node*root){if(root==NULL)returntrue;intright=_Height(root->_right);intleft=_Height(root->_left);if(right-left!=root->_bf||abs(right-left)>=2){cout<<"平衡因子异常"<<root->_key<<endl;}return_IsBlance(root->_left)&&_IsBlance(root->_right);}int_Height(Node*root){if(root==NULL)return0;intright=_Height(root->_right);intleft=_Height(root->_left);if(right>left)return(right+1);elsereturn(left+1);}void_InOrder(Node*root){if(root==NULL){return;}else{_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}}protected:Node*_root;};#include"AVLTree.h"voidTest1(){inta[9]={16,3,7,11,9,26,18,14,15};AVLTree<int,int>avl;for(inti=0;i<sizeof(a)/sizeof(a[0]);++i){avl.Insert(a[i],i);}avl.InOrder();cout<<avl.IsBlance()<<endl;AVLTreeNode<int,int>*ret1=avl.Find(18);if(ret1)cout<<ret1->_key<<":"<<ret1->_value<<endl;elsecout<<"不存在ret1"<<endl;AVLTreeNode<int,int>*ret2=avl.Find(1);if(ret2)cout<<ret2->_key<<":"<<ret2->_value<<endl;elsecout<<"不存在ret2"<<endl;avl.Remove(26);avl.Remove(18);avl.Remove(15);avl.InOrder();avl.Remove(3);cout<<avl.Remove(7)<<endl;avl.Remove(7);avl.Remove(9);avl.Remove(11);avl.Remove(14);avl.Remove(15);cout<<avl.Remove(100)<<endl;avl.Remove(16);avl.Remove(18);avl.Remove(26);avl.InOrder();}voidTest2(){inta[10]={4,2,6,1,3,5,15,7,16,14};AVLTree<int,int>avl;for(inti=0;i<sizeof(a)/sizeof(a[0]);++i){avl.Insert(a[i],i);}avl.InOrder();cout<<avl.IsBlance()<<endl;AVLTreeNode<int,int>*ret1=avl.Find(5);if(ret1)cout<<ret1->_key<<":"<<ret1->_value<<endl;elsecout<<"不存在ret1"<<endl;AVLTreeNode<int,int>*ret2=avl.Find(88);if(ret2)cout<<ret2->_key<<":"<<ret2->_value<<endl;elsecout<<"不存在ret2"<<endl;avl.Remove(14);avl.Remove(16);avl.Remove(7);avl.InOrder();avl.Remove(15);avl.Remove(6);avl.Remove(5);cout<<avl.Remove(4)<<endl;avl.Remove(4);avl.Remove(3);avl.Remove(2);avl.Remove(1);cout<<avl.Remove(100)<<endl;avl.Remove(7);avl.Remove(16);avl.InOrder();}intmain(){Test1();cout<<endl;cout<<endl;Test2();return0;}

实现结果：