AVL樹是高度平衡的二叉搜索樹，較搜索樹而言降低了樹的高度；時間復雜度減少了使其搜索起來更方便；
創(chuàng)新互聯(lián)成立與2013年，公司以成都網站設計、成都網站制作、
外貿網站建設、系統(tǒng)開發(fā)、網絡推廣、文化傳媒、企業(yè)宣傳、
平面廣告設計等為主要業(yè)務，適用行業(yè)近百種。服務企業(yè)客戶上千多家，涉及國內多個省份客戶。擁有多年網站建設開發(fā)經驗。為企業(yè)提供專業(yè)的網站建設、創(chuàng)意設計、宣傳推廣等服務。 通過專業(yè)的設計、獨特的風格，為不同客戶提供各種風格的特色服務。
1.性質：
（1）左子樹和右子樹高度之差絕對值不超過1；
（2）樹中每個左子樹和右子樹都必須為AVL樹；
（3）每一個節(jié)點都有一個平衡因子（-1,0,1：右子樹-左子樹）
（4）遍歷一個二叉搜索樹可以得到一個遞增的有序序列
2.結構：
平衡二叉樹是對二叉搜索樹(又稱為二叉排序樹)的一種改進。二叉搜索樹有一個缺點就是，樹的結構是無法預料的。任意性非常大。它僅僅與節(jié)點的值和插入的順序有關系。往往得到的是一個不平衡的二叉樹。在最壞的情況下。可能得到的是一個單支二叉樹，其高度和節(jié)點數同樣，相當于一個單鏈表。對其正常的時間復雜度有O(lb n)變成了O(n)。從而喪失了二叉排序樹的一些應該有的長處。
當插入一個新的節(jié)點的時候。在普通的二叉樹中不用考慮樹的平衡因子，僅僅要將大于根節(jié)點的值插入到右子樹，小于節(jié)點的值插入到左子樹，遞歸就可以。
而在平衡二叉樹則不一樣，在插入節(jié)點的時候，假設插入節(jié)點之后有一個節(jié)點的平衡因子要大于2或者小于-2的時候，他須要對其進行調整。如今僅僅考慮插入到節(jié)點的左子樹部分（右子樹與此同樣）。主要分為下面三種情況：
(1)若插入前一部分節(jié)點的左子樹高度和右子樹高度相等。即平衡因子為0。插入后平衡因子變?yōu)?。仍符合平衡的條件不用調整。
(2)若插入前左子樹高度小于右子樹高度。即平衡因子為-1，則插入后將使平衡因子變?yōu)?，平衡性反倒得到調整，所以不必調整。
(3)若插入前左子樹的高度大于右子樹高度。即平衡因子為1。則插入左子樹之后會使得平衡因子變?yōu)?，這種情況下就破壞了平衡二叉樹的結構。所以必須對其進行調整，使其加以改善。
調整二叉樹首先要明確一個定義。即最小不平衡子樹。最小不平衡子樹是指以離插入節(jié)點近期、且平衡因子絕對值大于1的節(jié)點做根的子樹。
在構建AVL樹的時候使用三叉鏈：parent,left,right方便回溯，也可以用遞歸或者棧解決；
在插入一個新節(jié)點后，一個平衡二叉樹可能失衡，失衡情況下相應的調整方法
（1）右旋
（2）左旋
（3）右左雙旋
（4）左右雙旋
#include
using namespace std;
template
struct AVLTreeNode
{
AVLTreeNode*_left;
AVLTreeNode*_right;
AVLTreeNode*_parent;
K _key;
V _value;
int _bf;//平衡因子
AVLTreeNode( const K & key,const V& value ):_bf(0)
,_left(NULL)
,_right( NULL)
,_parent( NULL)
,_key( key)
,_value( value)
{}
};
template
class AVLTree
{
typedef AVLTreeNode Node;
protected:
Node* _root;
public:
AVLTree():_root( NULL)
{}
bool Insert(const K& key,const V& value)
{
if(_root==NULL )
{
_root= new Node (key,value);
return true ;
}
Node* cur=_root;
Node* parent=NULL ;
while(cur)
{
if(cur->_key>key )
{
parent=cur;
cur=cur->_left;
}
else if (cur->_key_right;
}
else
{
return false ;
}
}
//插入
cur= new Node (key,value);
if(parent->_key_right=cur;
cur->_parent=parent;
}
else
{
parent->_left=cur;
cur->_parent=parent;
}
//檢查是否平衡
//1更新平衡因子，不滿足條件時進行旋轉
while(parent)
{
if(cur==parent->_left)
parent->_bf --;
else
parent->_bf ++;
if(parent->_bf ==0)
{
break;
}
// -1 1
else if (parent->_bf ==-1||parent->_bf ==1)
{
cur=parent;
parent=cur->_parent;
}
else
{
//旋轉處理2 -2
if(cur->_bf ==1)
{
if(parent->_bf==2)
RotateL(parent);
else//-2
RotateLR(parent);
}
else
{
if(parent->_bf ==-2)
RotateR(parent);
else//2
RotateRL(parent);
}
break;
}
}
return true ;
}
//左單旋
void RotateL(Node * parent)
{
Node* subR=parent ->_right;
Node* subRL=subR->_left;
if(subRL)
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;
}
else
{
ppNode->_right=subR;
}
}
parent->_bf=subR->_bf=0;
}
//右單旋
void RotateR(Node * parent)
{
Node* subL=parent ->_left;
Node* subLR=subL->_right;
if(subLR)
subLR->_parent = parent;
subL->_right = parent;
Node* ppNode=parent ->_parent;
if(ppNode==NULL )
{
_root=subL;
}
else
{
if(ppNode->_left==parent )
ppNode->_left=subL;
else
ppNode->_right=subL;
}
parent->_bf =subL->_bf =0;
}
//左右雙旋
void RotateLR(Node * parent)
{
Node* subL=parent ->_left;
Node* subLR=subL->_right ;
int bf=subLR->_bf ;
RotateL( parent->_left);
RotateR( parent);
//根據subLR的平衡因子修正其他節(jié)點的平衡因子
if(bf==-1)
{
subL->_bf =0;
parent->_bf =1;
}
else if (bf==1)
{
subL->_bf =-1;
parent->_bf=0;
}
}
//右左雙旋
void RotateRL(Node * parent)
{
Node* subR=parent ->_right ;
Node* subRL=subR->_left ;
int bf=subRL->_bf ;
RotateR( parent->_right);
RotateL( parent);
if(bf==1)
{
subR->_bf =0;
parent->_bf =-1;
}
else if (bf==-1)
{
subR->_bf = 1;
parent->_bf = 0;
}
}
//中序遍歷
void Inorder()
{
_Inorder(_root);
cout<_left);
cout<< root->_key <<" " ;
_Inorder( root->_right );
}
//判斷是否平衡
bool IsBalence()
{
return _IsBalence(_root);
}
bool _IsBalence(Node * root)
{
if(root ==NULL)
return true ;
int left=_Height(root ->_left );
int right= _Height(root ->_right );
if(right-left!=root ->_bf || abs(right-left)>1)
{
cout<< "節(jié)點的平衡因子異常" <_key ;
return false ;
}
return _IsBalence(root ->_left)&&_IsBalence(root->_left);
}
//求子樹的高度
int _Height(Node * root)
{
if(root ==NULL)
return 0;
int left=_Height(root ->_left );
int right= _Height(root ->_right );
return left>right?left+1:right+1;
}
//前邊方法的優(yōu)化
//后續(xù)遍歷先求子書的高度的同時就可以
//判斷出子樹是否平衡，然后依次求根節(jié)點的高度
bool _Isbalence(Node * root, int& height )
{
if(root ==NULL)
{
height=0;
return true ;
}
if(root ->_left ==NULL&& root->_right ==NULL )
{
height=1;
returnn true;
}
int leftheight=0;
if(_Isbalence(root ->_left ,leftheight)==false)
return false ;
int rightheight=0;
if(_Isbalence(root ->_right ,rightheight)==false)
return false ;
height=leftheight>rightheight?leftheight:rightheight;
}
};
void TestTree()
{
int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
AVLTree t;
for (size_t i = 0; i < sizeof(a)/ sizeof(a[0]); ++i)
{
t.Insert(a[i], i);
}
t.Inorder();
cout<< "是否平衡?" <另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
文章標題：數據結構--AVL樹-創(chuàng)新互聯(lián)
URL網址：http://weahome.cn/article/gcjio.html
重慶分公司
重慶分公司
