AVL是平衡搜索二叉树，它的主要特点在于：（1）左子树和右子树的高度差绝对值<1,（2）树中的每个子树都是AVL树，（3）每个节点都有一个平衡因子（-1、0、1），平衡因子的大小等于右子树的高度减左子树的高度

下面就是一个AVL树：

其中，这个树满足左子树和右子树的高度差绝对值小于1，每个节点的平衡因子都满足条件。

下面是AVLTree中节点的结构：

template<classK,classV>structAVLTreeNode{K_key;V_value;int_bf;//节点的平衡因子AVLTreeNode<K,V>*_parent;//指向节点的父节点AVLTreeNode<K,V>*_left;//指向节点的左孩子AVLTreeNode<K,V>*_right;//指向节点的右孩子AVLTreeNode(constK&key=K(),constV&value=V())//构造节点:_key(key),_value(value),_parent(NULL),_left(NULL),_right(NULL),_bf(0){}};

下面讨论一下AVLTree中插入节点的情况：

当插入一个节点时，如果这个节点的父节点的平衡因子不满足AVLTree的特点，这时就需要对AVLTree进行调整，直到满足AVLTree的条件。

（1）左单旋

（2）右单旋

（3）左右双旋

（4）右左双旋

针对上面的情况，下面是具体的程序实现：

#pragmaonce#include<assert.h>#include<math.h>//实现平衡搜索二叉树//构造AVL树的节点（使用三叉链表）template<classK,classV>structAVLTreeNode{K_key;V_value;int_bf;AVLTreeNode<K,V>*_parent;AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode(constK&key=K(),constV&value=V())//构造节点:_key(key),_value(value),_parent(NULL),_left(NULL),_right(NULL),_bf(0){}};template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;public:AVLTree()//初始化根节点:_root(NULL){}boolInsert(constK&key,constV&value)//插入{//根节点判空if(_root==NULL){_root=newNode(key,value);returntrue;}//将数据先插入到树中Node*cur=_root;Node*parent=NULL;Node*tmp=newNode(key,value);while(cur){if(cur->_key<key){parent=cur;cur=cur->_right;}elseif(cur->_key>key){parent=cur;cur=cur->_left;}else{returnfalse;}}if(parent->_key>key){parent->_left=tmp;tmp->_parent=parent;}if(parent->_key<key){parent->_right=tmp;tmp->_parent=parent;}//对树进行调整cur=tmp;parent=cur->_parent;boolisRotate=false;while(parent){if(parent->_left==cur)//插入左节点，父亲节点的平衡因子-1{parent->_bf--;}if(parent->_right==cur)//插入右节点，父亲节点的平衡因子+1{parent->_bf++;}if(parent->_bf==0)//调整过程中，若碰到平衡因子为0的节点，就不用在继续调整{break;}elseif(parent->_bf==-1||parent->_bf==1)//更新平衡因子{cur=parent;parent=cur->_parent;}else{if(parent->_bf==2){if(cur->_bf==1)//左单旋{_RotateL(parent);}else//右左单旋{_RotateRL(parent);}}else//=-2{if(cur->_bf==-1)//右单旋{_RotateR(parent);}else//左右单旋{_RotateLR(parent);}}isRotate=true;}break;}if(isRotate){if(parent->_parent==NULL){_root=parent;returntrue;}}returntrue;}voidInOrder()//后序遍历{_InOrder(_root);cout<<endl;}boolIsBalance(){if(_root==NULL){cout<<"rootisnull!"<<endl;returnfalse;}return_IsBalance(_root);}intHeigth(){intheigthTree=0;Node*cur=_root;while(cur){if(cur!=NULL){heigthTree++;}cur=cur->_left;}return_Heigth(_root,heigthTree,0);}protected:int_Heigth(Node*root,intheigthTree,intcountNum){if(root==NULL){if(countNum>heigthTree){heigthTree=countNum;}returnheigthTree;}_Heigth(root->_left,heigthTree,countNum++);_Heigth(root->_right,heigthTree,countNum++);}bool_IsBalance(Node*root){intbf=root->_right->_bf-root->_right->_bf;if(bf==0||bf==1||bf==-1){returntrue;}else{returnfalse;}_IsBalance(root->_left);_IsBalance(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_RotateRL(Node*&parent)//右左单旋{Node*pNode=parent;Node*subRNode=parent->_right;Node*subRLNode=subRNode->_left;intbf=subRLNode->_bf;_RotateR(parent->_right);_RotateL(parent);if(bf==-1){subRNode->_bf=0;pNode->_bf=-1;}elseif(bf==1){subRNode->_bf=1;pNode->_bf=0;}else{subRNode->_bf=0;pNode->_bf=0;}subRNode->_bf=0;}void_RotateLR(Node*&parent)//左右单旋{Node*pNode=parent;Node*subLNode=parent->_left;Node*subLRNode=subLNode->_right;intbf=subLRNode->_bf;_RotateL(parent->_left);_RotateR(parent);if(bf==-1){subLNode->_bf=0;pNode->_bf=1;}elseif(bf==1){subLNode->_bf=-1;pNode->_bf=0;}else{subLNode->_bf=0;pNode->_bf=0;}subLNode->_bf=0;}void_InOrder(Node*root){if(root==NULL){return;}_InOrder(root->_left);cout<<root->_key<<"";_InOrder(root->_right);}protected:Node*_root;};voidTest(){AVLTree<int,int>ht;/*ht.Insert(16,1);ht.Insert(3,1);ht.Insert(7,1);ht.Insert(11,1);ht.Insert(9,1);ht.Insert(26,1);ht.Insert(18,1);ht.Insert(14,1);ht.Insert(15,1);*/ht.Insert(4,1);ht.Insert(2,1);ht.Insert(6,1);ht.Insert(1,1);ht.Insert(3,1);ht.Insert(5,1);ht.Insert(15,1);ht.Insert(7,1);ht.Insert(16,1);ht.Insert(14,1);ht.InOrder();cout<<ht.IsBalance()<<endl;cout<<ht.Heigth()<<endl;}