#pragmaonce#include<iostream>usingnamespacestd;#defineNEG-1#defineZERO0#definePOS1template<classK,classV>structAVLTreeNode//树的节点{K_key;V_value;AVLTreeNode*_left;AVLTreeNode*_right;AVLTreeNode*_parent;int_bf;AVLTreeNode(constK&key,constV&value):_key(key),_value(value),_left(NULL),_right(NULL),_parent(NULL),_bf(0)//平衡因子取值-101（左高1相等右高1）{}};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,*prev=NULL;//当前与之前节点指针while(cur){if(cur->_key<key)//插入key比当前节点key大跳到右{if(cur->_right){//右不为空继续prev=cur;cur=cur->_right;if(cur->_bf==ZERO)//如果节点的bf为0，说明插入（如果成功），会改变prev->bf的值prev->_bf++;}else{//如果右为空到达插入节点位置，插入cur->bf++cur->_right=newNode(key,value);cur->_right->_parent=cur;cur->_bf++;break;}}elseif(cur->_key>key)//同理向左插入{if(cur->_left){prev=cur;cur=cur->_left;if(cur->_bf==ZERO)prev->_bf--;}else{cur->_left=newNode(key,value);cur->_left->_parent=cur;cur->_bf--;break;}}else//key相等，插入失败，依次将改变的平衡因子改回来{while(prev&&cur->_bf==ZERO){if(prev->_left==cur)prev->_bf++;elseprev->_bf--;cur=prev;prev=prev->_parent;}returnfalse;}}//插入结束对整棵树进行调节使其继续平衡//高度不变if(cur->_bf==ZERO)returntrue;else//高度改变{//找高度变为-2或2的节点旋转while(prev){if(prev->_bf<-1)//左高2{if(cur->_bf<=-1)//右旋{_RotateR(prev);cout<<"右旋"<<endl;break;}else//左右旋{_RotateL(cur);_RotateR(prev);cout<<"左右旋"<<endl;break;}}elseif(prev->_bf>1)//右高2{if(cur->_bf>=1)//左旋{_RotateL(prev);cout<<"左旋"<<endl;break;}else//右左旋{_RotateR(cur);_RotateL(prev);cout<<"右左旋"<<endl;break;}}cur=prev;prev=prev->_parent;}}returntrue;}boolIsBalance(){if(_root==NULL)returntrue;return_Isbalance(_root);}Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_key>key)cur=cur->_left;elseif(cur->_key<key)cur=cur->_right;elsereturncur;}returnNULL;}boolRemove(constK&key){if(_root==NULL){returnfalse;//空树删除失败}Node*cur=_root,*prev=NULL;while(cur){if(cur->_key<key)//删除位置在cur右{if(cur->_right){//右非空，继续找prev=cur;cur=cur->_right;}else//右空，未找到删除节点返回returnfalse;}elseif(cur->_key>key)//删除位置在左{if(cur->_left){prev=cur;cur=cur->_left;}elsereturnfalse;}else{Node*parent=cur->_parent;//记录删除节点的父if(cur->_left==NULL)//删除节点左空，直接使其右与prev相连{if(prev==NULL){//prev为空，删除根节点，根节点改变_root=cur->_right;deletecur;returntrue;}if(prev->_right==cur){//prev右为cur，cur的右连到prev右prev->_bf--;//平衡因子减少prev->_right=cur->_right;if(cur->_right)cur->_right->_parent=prev;}if(prev->_left==cur){//prev左为curprev->_left=cur->_right;prev->_bf++;if(cur->_right)cur->_right->_parent=prev;}deletecur;//释放节点cur=prev;//将curprev指向有效节点prev=cur->_parent;}elseif(cur->_right==NULL)//同上cur右为空{if(prev==NULL){_root=cur->_left;deletecur;returntrue;}if(prev->_right==cur){prev->_bf--;prev->_right=cur->_left;if(cur->_left)cur->_left->_parent=prev;}if(prev->_left==cur){prev->_left=cur->_left;prev->_bf++;if(cur->_left)cur->_left->_parent=prev;}deletecur;cur=prev;prev=cur->_parent;}else{//cur左右都非空，为了避免换当前root的复杂操作，替换为删除cur左孩子最右节点，或者cur右孩子的最左节点，将其内容拷贝给curNode*tmp=cur;prev=cur;cur=cur->_right;while(cur->_left)//找右树最左{prev=cur;cur=cur->_left;}tmp->_key=cur->_key;tmp->_value=cur->_value;//拷贝值if(cur==prev->_left)//调节prevbf并将cur右树连接到prevprev->_bf++;prev->_left=cur->_right;}if(cur==prev->_right)//同上{prev->_bf--;prev->_right=cur->_right;}tmp=cur;//记录删除位置cur=prev;parent=cur;//curprev指向有效节点prev=cur->_parent;deletetmp;//删除tmp}while(prev&&cur->_bf==ZERO)//删除节点父树高度可能改变，依次确认并修改bf（curbf为0说明是-1或1变来高度发生改变需修改父节点bf）{if(cur==prev->_left){prev->_bf++;}if(cur==prev->_right){prev->_bf--;}cur=prev;prev=prev->_parent;}prev=parent;//prev指向实际删除节点的父节点if(prev->_bf<ZERO)cur=prev->_left;if(prev->_bf>ZERO)cur=prev->_right;if(prev->_bf==ZERO){cur=prev;prev=prev->_parent;}break;}}//找高度变为-2或2的节点旋转while(prev){if(prev->_bf<-1)//左高2{cur=prev->_left;//因为删除一侧节点可能需要另一侧旋转，因此需要对cur重新赋值if(cur&&(cur->_bf<=-1||cur->_bf==ZERO))//右旋{_RotateR(prev);if(prev->_left&&prev->_right==NULL)//判断旋转后prev的bfprev->_bf--;cout<<"右旋"<<endl;}else//左右旋{_RotateL(cur);_RotateR(prev);cout<<"左右旋"<<endl;}cur=prev->_parent;prev=cur->_parent;while(prev&&cur->_bf==ZERO)//依次修改旋转完毕的prev的bf{if(cur==prev->_left)prev->_bf++;elseprev->_bf--;cur=prev;prev=prev->_parent;}}elseif(prev->_bf>1)//右高2{cur=prev->_right;if(cur&&(cur->_bf>=1||cur->_bf==ZERO))//左旋{_RotateL(prev);cout<<"左旋"<<endl;if(prev->_right&&prev->_left==NULL)prev->_bf++;}else//右左旋{_RotateR(cur);_RotateL(prev);cout<<"右左旋"<<endl;}cur=prev->_parent;prev=cur->_parent;while(prev&&cur->_bf==ZERO){if(cur==prev->_left)prev->_bf++;elseprev->_bf--;cur=prev;prev=prev->_parent;}}cur=prev;if(prev)prev=prev->_parent;}returntrue;}private:Node*_root;int_height(Node*root){if(root==NULL)return0;intleft=1,right=1;left+=_height(root->_left);right+=_height(root->_right);returnleft>right?left:right;}bool_Isbalance(Node*root)//判断数是否平衡bf是否匹配{if(root==NULL)returntrue;/*if(root->_left==NULL&&root->_right==NULL)returntrue;*/boolleft=_Isbalance(root->_left);boolright=_Isbalance(root->_right);intnum1=1;num1+=_height(root->_left);intnum2=1;num2+=_height(root->_right);if(left==false||right==false){cout<<"notbalace!"<<"key:"<<root->_key<<"bf:"<<root->_bf<<endl;returnfalse;}if(num2-num1!=root->_bf){cout<<"bferror!"<<"key:"<<root->_key<<"bf:"<<root->_bf<<"a-b:"<<num1-num2<<endl;returnfalse;}if(abs(num1-num2)<=1)returntrue;returnfalse;}//旋转后bf调节总结：左旋bf减小右旋bf增加；sub=2，parent变化3，sub变化2；sub=1，parent变化2，sub变化1；void_RotateR(Node*parent)//右旋{Node*subL=parent->_left;Node*subLR=subL->_right;Node*ppNode=parent->_parent;subL->_right=parent;parent->_parent=subL;parent->_left=subLR;if(subLR)subLR->_parent=parent;if(ppNode){if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;}else_root=subL;subL->_parent=ppNode;//旋转//修改bfif(subL->_bf==-2){parent->_bf=1;subL->_bf=0;}else{subL->_bf++;parent->_bf=0;}}void_RotateL(Node*parent)//左旋{Node*subR=parent->_right;Node*subRL=subR->_left;Node*ppNode=parent->_parent;subR->_left=parent;parent->_parent=subR;parent->_right=subRL;if(subRL)subRL->_parent=parent;if(ppNode){if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;}else_root=subR;subR->_parent=ppNode;//以上为左旋转//以下下修改bf值if(subR->_bf==2)//右孩子的高度为2说明旋转前高度差在右孩子的下方，旋转后parent右支没有可以连接的，高度会降3从2变为-1{parent->_bf=-1;subR->_bf=0;}else{//右孩子高度为1，旋转后高度将2buf为0，而右孩子高度将1；parent->_bf=0;subR->_bf--;}}};