AVL树：又称高度平衡的二叉搜索树，它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

AVL树的性质

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

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

#pragmaonce#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):_left(NULL),_right(NULL),_parent(NULL),_key(key),_value(value),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree():_root(NULL){}~AVLTree(){}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->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{cout<<"该节点已经存在"<<endl;returnfalse;}}cur=newNode(key,value);if(parent->_key<key){parent->_right=cur;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}//更新平衡因子while(parent){if(cur==parent->_right)++parent->_bf;elseif(cur==parent->_left)--parent->_bf;if(parent->_bf==0)break;elseif(parent->_bf==-1||parent->_bf==1){cur=parent;parent=cur->_parent;}else//平衡因子为2或-2时的情况{if(parent->_bf==2){if(cur->_bf==1){//左旋转RotateL(parent);}elseif(cur->_bf==-1){RotateRL(parent);}}else{if(cur->_bf==-1){//右旋转RotateR(parent);}elseif(cur->_bf==1){RotateLR(parent);}}break;}}returntrue;}Node*Find(constK&key){if(_root==NULL)returnNULL;Node*cur=_root;while(cur){if(cur->_key<key){cur=cur->_right;}elseif(cur->_key>key){cur=cur->_left;}else{cout<<"找到该数"<<endl;returncur;}}returnNULL;}boolRemove(constK&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{if(cur->_left==NULL&&cur->_right==NULL){//1.左右都为空if(parent==NULL)_root=NULL;//若只有一个节点else{if(parent->_left==cur)parent->_bf++;elseparent->_bf--;}deletecur;cur=NULL;}elseif(cur->_left&&cur->_right){//2.左右都不为空Node*RightMin=cur->_right;while(RightMin->_left){parent=RightMin;RightMin=RightMin->_left;}cur->_key=RightMin->_key;//采用替换法删除cur->_value=RightMin->_value;if(parent->_left==RightMin){parent->_bf++;parent->_left=RightMin->_right;}else{parent->_bf--;parent->_right=RightMin->_right;}deleteRightMin;RightMin=NULL;}else{//3.左为空或右为空if(cur->_left){//1).右为空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--;}}}else{//2).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--;}}}deletecur;cur=NULL;}break;}}while(parent){//平衡因子为0或1、-1对这个树的高度不会产生影响if(parent->_parent->_left==parent)parent->_parent->_bf++;elseparent->_parent->_bf--;if(parent->_parent->_bf==0)returntrue;elseif(parent->_parent->_bf==1||parent->_parent->_bf==-1){cur=parent;parent=cur->_parent;}else{if(parent->_bf==-2){if(cur->_bf==-1){RotateR(parent);}else{RotateLR(parent);}}else{if(cur->_bf==1){RotateL(parent);}else{RotateRL(parent);}}cout<<"删除成功"<<endl;returntrue;}}returnfalse;}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(parent==ppNode->_left){ppNode->_left=subL;}else{ppNode->_right=subL;}subL->_parent=ppNode;}subL->_bf=parent->_bf=0;}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(parent==ppNode->_left){ppNode->_left=subR;}else{ppNode->_right=subR;}subR->_parent=ppNode;}subR->_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=-1;subR->_bf=0;}elseif(bf==-1){parent->_bf=0;subR->_bf=1;}else//bf=0;{subR->_bf=parent->_bf=0;}//subRL->_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){parent->_bf=0;subL->_bf=-1;}else//bf=0;{subL->_bf=parent->_bf=0;}//subLR->_bf=0;}voidInOrder(){_InOrder(_root);cout<<endl;}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((right-left)!=root->_bf){cout<<root->_key<<"平衡因子异常"<<endl;returnfalse;}returnabs(right-left)<2&&_IsBalance(root->_left)&&_IsBalance(root->_right);}void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}protected:Node*_root;};voidTest(){AVLTree<int,int>avl;intarr[]={4,2,6,1,3,5,15,7,16,14};//intarr[]={16,3,7,11,9,26,18,14,15};intsize=sizeof(arr)/sizeof(arr[0]);for(inti=0;i<size;++i){avl.Insert(arr[i],i);avl.IsBalance();}avl.InOrder();avl.Remove(4);avl.InOrder();avl.IsBalance();//avl.Remove(7);//avl.InOrder();//avl.IsBalance();//avl.Remove(16);//avl.InOrder();//avl.IsBalance();}