一、平衡二叉树（ AVL树 ）

1、定义：AVL树又称为高度平衡的二叉搜索树，是1962年有俄罗斯的数学家G.M.Adel'son-Vel'skii和E.M.Landis提出来的。它能保持二叉树的高度平衡，尽量降低二叉树的高度，减少树的平均搜索长度。

2、出现原因：搜索二叉树若出现严重退化，查找或使用时会造成资源浪费。

3、特性：

AVL树是一个三叉链；

左、右子树的 | 高度之差| 不超过 1；

左右子树都是AVL树；

每个节点的平衡因子 = 右子树高度 - 左子树高度；（平衡因子：-1,1,0）

4、效率：

一棵AVL树有N个节点，其高度可以保持在log2N，插入/删除/查找的时间复杂度：log2N，即 O(lgN)。

二、AVL相关

1、右单旋

2、左单旋

3、右左单旋及左右单旋

根据左单旋、右单旋及树的情况进行选择，旋转后需要更新平衡因子，以防失误。

4、节点平衡因子的更新：

（1）插入节点的右孩子，及平衡因子bf++;左孩子，bf--;

（2）若插入节点后，计算得bf==0,则平衡，不需更新平衡因子；bf==1或-1，则需向上查看是否需要平衡因子；bf==2或-2,则根据情况进行旋转，并更新平衡因子。

5、判断AVL树：

（1）计算左、右子树高度，平衡因子；

（2）若平衡因子 < 2,即其子树为AVL树；

三、源代码

1、节点

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){}};

2、AVL树及相关实现

template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree():_root(NULL){}voidInOrder(){_InOrder(_root);cout<<endl;}intHeight(){return_Height(_root);cout<<endl;}voidRotateR(Node*parent)//右旋{Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR)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;elseppNode->_right=subL;subL->_parent=ppNode;}}voidRotateL(Node*parent)//左旋转{Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subR;if(subRL)subRL->_parent=parent;subRL->_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;elseppNode->_right=subR;subR->_parent=ppNode;}}voidRotateRL(Node*parent)//右左旋转{Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subR->_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//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//0{subL->_bf=parent->_bf=0;subLR=0;}}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;}elsereturnfalse;}cur=newNode(key,value);if(parent->_key<key)parent->_right=newNode(key,value);elseparent->_left=newNode(key,value);//更新平衡因子while(parent){if(cur==parent->_right)parent->_bf++;elseparent->_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)RotateR(parent);//右旋转else//-2RotateLR(parent);//左右旋转}else//2{if(cur->_bf==1)RotateL(parent);//左旋转elseRotateRL(parent);//右左旋转}break;}}returnfalse;}protected: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);intright=_Height(root->_right);returnleft>right?left+1:right+1;}protected:Node*_root;};

3、总结：

AVL树是对搜索二叉树的进一步优化，根据平衡因子使搜索二叉树高度平衡。其的插入、删除、查找都和搜索二叉树类似，只是需要注意平衡因子的问题。

AVL树解决了搜索二叉树的退化问题，需要注意树的旋转问题及平衡因子的更新问题。