AVL树

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

AVL树的性质

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

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

下面实现一棵AVL树，主要实现其插入部分：

#pragmaoncetemplate<classK,classV>structAVLTreeNode{K_key;V_val;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;int_bf;//平衡因子AVLTreeNode(constK&key,constK&val):_key(key),_val(val),_left(NULL),_right(NULL),_parent(NULL),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree():_root(NULL){}~AVLTree(){_Clear(_root);}boolInsert(constK&key,constV&val){if(_root==NULL)//如果根结点为NULL，则创建一个结点，返回真{_root=newNode(key,val);returntrue;}Node*cur=_root;Node*prev=NULL;while(cur!=NULL)//查找合适的位置插入{if(cur->_key==key)//如果结点已存在，则返回假returnfalse;elseif(cur->_key>key)//如果要插入值小于当前结点，则去左子树查找{prev=cur;cur=cur->_left;}else//如果插入值大于当前结点，则去右子树查找{prev=cur;cur=cur->_right;}}//循环结束，则表明找到了合适的位置，判断应插入左边还是右边Node*tmp=newNode(key,val);if(key<prev->_key)prev->_left=tmp;elseprev->_right=tmp;tmp->_parent=prev;//插入结点之后，需要判断当前树是否满足AVL树的规则，若不满足，进行相应的调整while(prev!=NULL){//平衡因子为右边高度减去左边高度if(prev->_left==tmp)--(prev->_bf);else++(prev->_bf);if(prev->_bf==0)//如果平衡因子为0，则一定平衡，因为可以看做是在同一层插入了一个结点，对高度并无影响break;elseif(prev->_bf==1||prev->_bf==-1)//如果平衡因子为1/-1，则表明高度有所变化，需要继续向上调整{tmp=prev;prev=prev->_parent;}else//说明平衡因子的绝对值大于1，则这个时候不满足AVL树的性质，需要进行调整{if(prev->_bf==2){if(tmp->_bf==1)_RotateL(prev);else{_RotateR(tmp);_RotateL(prev);}}else{if(tmp->_bf==-1)_RotateR(prev);else{_RotateL(tmp);_RotateR(prev);}}break;}}returntrue;}voidInOrder(){_InOrder(_root);cout<<endl;}protected:void_Clear(Node*root){if(root!=NULL){_Clear(root->_left);_Clear(root->_right);deleteroot;root=NULL;}}//左单旋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;else{if(ppNode->_left==parent)ppNode->_left=subR;elseppNode->_right=subR;}subR->_parent=ppNode;parent->_bf=subR->_bf=0;}//右单旋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;else{if(ppNode->_left==parent)ppNode->_left=subL;elseppNode->_right=subL;}subL->_parent=ppNode;parent->_bf=subL->_bf=0;}void_InOrder(Node*root){if(root!=NULL){_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}}protected:Node*_root;};voidTest(){intarr[]={4,2,6,1,3,5,15,7,16,14};//intarr[]={16,3,7,11,9,26,18,14,15};AVLTree<int,int>t;for(inti=0;i<sizeof(arr)/sizeof(arr[0]);++i)t.Insert(arr[i],i);t.InOrder();}

其中的左右单旋如下图所示：

运行程序：

《完》