溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
AVL樹是高度平衡的二叉搜索樹，較搜索樹而言降低了樹的高度；時(shí)間復(fù)雜度減少了使其搜索起來更方便；
1.性質(zhì)：
（1）左子樹和右子樹高度之差絕對值不超過1；
（2）樹中每個(gè)左子樹和右子樹都必須為AVL樹；
（3）每一個(gè)節(jié)點(diǎn)都有一個(gè)平衡因子（-1,0,1：右子樹-左子樹）
（4）遍歷一個(gè)二叉搜索樹可以得到一個(gè)遞增的有序序列
2.結(jié)構(gòu)：
平衡二叉樹是對二叉搜索樹(又稱為二叉排序樹)的一種改進(jìn)。二叉搜索樹有一個(gè)缺點(diǎn)就是，樹的結(jié)構(gòu)是無法預(yù)料的。任意性非常大。它僅僅與節(jié)點(diǎn)的值和插入的順序有關(guān)系。往往得到的是一個(gè)不平衡的二叉樹。在最壞的情況下?？赡艿玫降氖且粋€(gè)單支二叉樹，其高度和節(jié)點(diǎn)數(shù)同樣，相當(dāng)于一個(gè)單鏈表。對其正常的時(shí)間復(fù)雜度有O(lb n)變成了O(n)。從而喪失了二叉排序樹的一些應(yīng)該有的長處。
當(dāng)插入一個(gè)新的節(jié)點(diǎn)的時(shí)候。在普通的二叉樹中不用考慮樹的平衡因子，僅僅要將大于根節(jié)點(diǎn)的值插入到右子樹，小于節(jié)點(diǎn)的值插入到左子樹，遞歸就可以。
而在平衡二叉樹則不一樣，在插入節(jié)點(diǎn)的時(shí)候，假設(shè)插入節(jié)點(diǎn)之后有一個(gè)節(jié)點(diǎn)的平衡因子要大于2或者小于-2的時(shí)候，他須要對其進(jìn)行調(diào)整。如今僅僅考慮插入到節(jié)點(diǎn)的左子樹部分（右子樹與此同樣）。主要分為下面三種情況：
(1)若插入前一部分節(jié)點(diǎn)的左子樹高度和右子樹高度相等。即平衡因子為0。插入后平衡因子變?yōu)?。仍符合平衡的條件不用調(diào)整。
(2)若插入前左子樹高度小于右子樹高度。即平衡因子為-1，則插入后將使平衡因子變?yōu)?，平衡性反倒得到調(diào)整，所以不必調(diào)整。
(3)若插入前左子樹的高度大于右子樹高度。即平衡因子為1。則插入左子樹之后會(huì)使得平衡因子變?yōu)?，這種情況下就破壞了平衡二叉樹的結(jié)構(gòu)。所以必須對其進(jìn)行調(diào)整，使其加以改善。
調(diào)整二叉樹首先要明確一個(gè)定義。即最小不平衡子樹。最小不平衡子樹是指以離插入節(jié)點(diǎn)近期、且平衡因子絕對值大于1的節(jié)點(diǎn)做根的子樹。
在構(gòu)建AVL樹的時(shí)候使用三叉鏈：parent,left,right方便回溯，也可以用遞歸或者棧解決；
在插入一個(gè)新節(jié)點(diǎn)后，一個(gè)平衡二叉樹可能失衡，失衡情況下相應(yīng)的調(diào)整方法
（1）右旋
（2）左旋
（3）右左雙旋
（4）左右雙旋
#include<iostream>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K ,V>*_left;
AVLTreeNode<K ,V>*_right;
AVLTreeNode<K ,V>*_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 K,class V>
class AVLTree
{
typedef AVLTreeNode <K,V> 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<key)
{
parent=cur;
cur=cur->_right;
}
else
{
return false ;
}
}
//插入
cur= new Node (key,value);
if(parent->_key<key )
{
parent->_right=cur;
cur->_parent=parent;
}
else
{
parent->_left=cur;
cur->_parent=parent;
}
//檢查是否平衡
//1更新平衡因子，不滿足條件時(shí)進(jìn)行旋轉(zhuǎn)
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
{
//旋轉(zhuǎn)處理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);
//根據(jù)subLR的平衡因子修正其他節(jié)點(diǎn)的平衡因子
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<<endl;
}
void _Inorder(Node * root)
{
if(_root==NULL )
return;
_Inorder( root->_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é)點(diǎn)的平衡因子異常" <<endl;
cout<< root->_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ù)遍歷先求子書的高度的同時(shí)就可以
//判斷出子樹是否平衡，然后依次求根節(jié)點(diǎn)的高度
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<int , int> t;
for (size_t i = 0; i < sizeof(a)/ sizeof(a[0]); ++i)
{
t.Insert(a[i], i);
}
t.Inorder();
cout<< "是否平衡?" <<t.IsBalence()<<endl;
}免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼