溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
AVL樹是高度平衡的二叉搜索樹，較搜索樹而言降低了樹的高度；時間復雜度減少了使其搜索起來更方便；
1.性質：
（1）左子樹和右子樹高度之差絕對值不超過1；
（2）樹中每個左子樹和右子樹都必須為AVL樹；
（3）每一個節點都有一個平衡因子（-1,0,1：右子樹-左子樹）
（4）遍歷一個二叉搜索樹可以得到一個遞增的有序序列
2.結構：
平衡二叉樹是對二叉搜索樹(又稱為二叉排序樹)的一種改進。二叉搜索樹有一個缺點就是，樹的結構是無法預料的。任意性非常大。它僅僅與節點的值和插入的順序有關系。往往得到的是一個不平衡的二叉樹。在最壞的情況下。可能得到的是一個單支二叉樹，其高度和節點數同樣，相當于一個單鏈表。對其正常的時間復雜度有O(lb n)變成了O(n)。從而喪失了二叉排序樹的一些應該有的長處。
當插入一個新的節點的時候。在普通的二叉樹中不用考慮樹的平衡因子，僅僅要將大于根節點的值插入到右子樹，小于節點的值插入到左子樹，遞歸就可以。
而在平衡二叉樹則不一樣，在插入節點的時候，假設插入節點之后有一個節點的平衡因子要大于2或者小于-2的時候，他須要對其進行調整。如今僅僅考慮插入到節點的左子樹部分（右子樹與此同樣）。主要分為下面三種情況：
(1)若插入前一部分節點的左子樹高度和右子樹高度相等。即平衡因子為0。插入后平衡因子變為1。仍符合平衡的條件不用調整。
(2)若插入前左子樹高度小于右子樹高度。即平衡因子為-1，則插入后將使平衡因子變為0，平衡性反倒得到調整，所以不必調整。
(3)若插入前左子樹的高度大于右子樹高度。即平衡因子為1。則插入左子樹之后會使得平衡因子變為2，這種情況下就破壞了平衡二叉樹的結構。所以必須對其進行調整，使其加以改善。
調整二叉樹首先要明確一個定義。即最小不平衡子樹。最小不平衡子樹是指以離插入節點近期、且平衡因子絕對值大于1的節點做根的子樹。
在構建AVL樹的時候使用三叉鏈：parent,left,right方便回溯，也可以用遞歸或者棧解決；
在插入一個新節點后，一個平衡二叉樹可能失衡，失衡情況下相應的調整方法
（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更新平衡因子，不滿足條件時進行旋轉
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的平衡因子修正其他節點的平衡因子
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<< "節點的平衡因子異常" <<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;
}
//前邊方法的優化
//后續遍歷先求子書的高度的同時就可以
//判斷出子樹是否平衡，然后依次求根節點的高度
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;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
