AVL树的性质

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

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

3. 每个节点都有一个平衡因子(balance factor--bf),任一节点的平衡因子是-1,0,1。(每个节点的平衡因子等于右子树的高度减去左子树的高度 )

#pragmaoncetemplate<classK,classV>structAVLTreeNode{K_key;V_value;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;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){}~AVLTree(){}public://空树//查找位置//插入节点//更新平衡因子//如果进行了旋转调整，则将parent进行重新连接boolInsert(constK&key,constV&value){//空树if(_root==NULL){_root=newNode(key,value);returntrue;}//查找位置Node*cur=_root;Node*parent=NULL;while(cur){if(key>cur->_key){parent=cur;cur=cur->_right;}elseif(key<cur->_key){parent=cur;cur=cur->_left;}else{returnfalse;}}//插入节点cur=newNode(key,value);if(key>parent->_key){parent->_right=cur;cur->_parent=parent;}else{parent->_left=cur;cur->_parent=parent;}//更新平衡因子(右树-左树)boolisRotate=false;//定义标志位，记录是否旋转while(parent){if(parent->_left==cur)//插在parent的左边，平衡因子减1{parent->_bf--;}else//插在parent的右边，平衡因子加1{parent->_bf++;}if(parent->_bf==0)break;elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=cur->_parent;}else//旋转，调整平衡因子2-2{isRotate=true;if(parent->_bf==2){if(cur->_bf==1){_RotateL(parent);}else//cur->_bf==-1{_RotateRL(parent);}}else//parent->_bf==-2{if(cur->_bf==-1){_RotateR(parent);}else{_RotateLR(parent);}}break;}}if(isRotate)//true则表示进行了调整{Node*GrandParent=parent->_parent;if(GrandParent==NULL){_root=parent;}else{if(parent->_key<GrandParent->_key){GrandParent->_left=parent;}else{GrandParent->_right=parent;}}}returntrue;}voidInOrder(){_InOrder(_root);cout<<endl;}boolIsBalanceTree(){return_IsBalanceTree(_root);}protected:bool_IsBalanceTree(Node*root){if(root==NULL){returntrue;}intleft=_Height(root->_left);intright=_Height(root->_right);intbf=abs(right-left);if(bf>1){returnfalse;}elseif(bf!=abs(root->_bf)){cout<<root->_bf<<"平衡因子有误！"<<endl;returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}//左单旋void_RotateL(Node*&parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL){subRL->_parent=parent;}subR->_left=parent;subR->_parent=parent->_parent;parent->_parent=subR;parent->_bf=subR->_bf=0;parent=subR;}void_RotateR(Node*&parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR){subLR->_parent=parent;}subL->_right=parent;subL->_parent=parent->_parent;parent->_parent=subL;parent->_bf=subL->_bf=0;parent=subL;}void_RotateLR(Node*&parent){Node*subL=parent->_left;Node*subLR=subL->_right;//左单旋subL->_right=subLR->_left;if(subLR->_left){subLR->_left->_parent=subL;}subLR->_left=subL;subLR->_parent=subL->_parent;subL->_parent=subLR;if(subLR->_bf==0||subLR->_bf==-1){subL->_bf=0;}else//subLR->_bf==1{subL->_bf=-1;}//右单旋parent->_left=subLR->_right;if(subLR->_right){subLR->_right->_parent=parent;}subLR->_right=parent;subLR->_parent=parent->_parent;parent->_parent=subLR;if(subLR->_bf==0||subLR->_bf==1){parent->_bf=0;}else//subLR->_bf==-1{parent->_bf=1;}subLR->_bf=0;parent=subLR;}void_RotateRL(Node*&parent){Node*subR=parent->_right;Node*subRL=subR->_left;subR->_left=subRL->_right;if(subRL->_right){subRL->_right->_parent=subR;}subRL->_right=subR;subR->_parent=subRL;if(subRL->_bf==0||subRL->_bf==1){subR->_bf=0;}else{subR->_bf=1;}parent->_right=subRL->_left;if(subRL->_left){subRL->_left->_parent=parent;}subRL->_left=parent;subRL->_parent=parent->_parent;parent->_parent=subRL;if(subRL->_bf==0||subRL->_bf==-1){parent->_bf=0;}else{parent->_bf=-1;}subRL->_bf=0;parent=subRL;}void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}int_Height(Node*root){if(root==NULL){return0;}intleft=_Height(root->_left)+1;intright=_Height(root->_right)+1;returnleft>right?left:right;}protected:Node*_root;};voidTestAVL1(){AVLTree<int,int>t;inta[]={16,3,7,11,9,26,18,14,15};for(inti=0;i<sizeof(a)/sizeof(int);++i){t.Insert(a[i],i);}t.InOrder();cout<<"IsBlance?"<<t.IsBalanceTree()<<endl;}voidTestAVL2(){AVLTree<int,int>t;inta[]={4,2,6,1,3,5,15,7,16,14};for(inti=0;i<sizeof(a)/sizeof(int);++i){t.Insert(a[i],i);t.InOrder();}cout<<"IsBlance?"<<t.IsBalanceTree()<<endl;}