平衡二叉樹(shù)
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-05-22 08:44:45 閱讀次數(shù)：3487次
平衡2叉樹(shù)又稱為AVL樹(shù)，
AVL樹(shù)是最早發(fā)明的自平衡2叉查找樹(shù)。在AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)兒子子樹(shù)的高度最大差別為1，所以它也被稱為高度平衡樹(shù)。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過(guò)1次或?qū)掖螛?shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。
保護(hù)平衡2叉樹(shù)需要有4種旋轉(zhuǎn)的情況
左左旋轉(zhuǎn)
右右旋轉(zhuǎn)
左右旋轉(zhuǎn)
右右旋轉(zhuǎn)
//********************************************************************************************
//***說(shuō)明：2叉排序樹(shù)遍歷是從小到大的順序，AVL樹(shù)也是bst，但是滿足所有的樹(shù)的左右高度相差不大于1
//***平衡2叉樹(shù)是1種特殊的2叉樹(shù)，滿足以上要求，主要是為了進(jìn)1步的優(yōu)化，提高操作的效力（O(log(n))）
//***針對(duì)下面情況進(jìn)行調(diào)劑
//***測(cè)試pat1066 http://www.patest.cn/contests/pat-a-practise/1066
//*********1*******************************1**********2***************************************
//**************************************************/***************************************
//***********2**************************************1***4*************************************
//*******************------>**************************/*************************************
//*************3**************************************3***5***********************************
//**************4*****************************************************************************
//*******************************************************************************************
//****************5***************************************************************************
// 其中主要的策略就是選擇，旋轉(zhuǎn)1共分為下面4種情況
//******** A ********** B ************** C ********************* D ***************************
//********************************************************************************************
//***** 6 **** 6 ************2***********************2****************************
//***** / **** / ***********/**********************/****************************
//***** 3 7 **** 2 7 **********1***5*******************1***4**************************
//***** / **** / *************/**********************/**************************
//*****1 4 **** 1 4 ************3***6*******************3***6************************
//***** **** / **************************************/*************************
//***** 2 **** 3 **************4***********************5**************************
//********************************************************************************************
//********************************************************************************************
//********************************************************************************************
//********************************************************************************************
//********************************************************************************************
/*********************************************************************************************
*A、6節(jié)點(diǎn)的左子樹(shù)3節(jié)點(diǎn)高度比右子樹(shù)7節(jié)點(diǎn)大2，左子樹(shù)3節(jié)點(diǎn)的左子樹(shù)1節(jié)點(diǎn)高度大于右子樹(shù)4節(jié)點(diǎn)，這類情況成為左左。
*B、6節(jié)點(diǎn)的左子樹(shù)2節(jié)點(diǎn)高度比右子樹(shù)7節(jié)點(diǎn)大2，左子樹(shù)2節(jié)點(diǎn)的左子樹(shù)1節(jié)點(diǎn)高度小于右子樹(shù)4節(jié)點(diǎn)，這類情況成為左右。
*C、2節(jié)點(diǎn)的左子樹(shù)1節(jié)點(diǎn)高度比右子樹(shù)5節(jié)點(diǎn)小2，右子樹(shù)5節(jié)點(diǎn)的左子樹(shù)3節(jié)點(diǎn)高度大于右子樹(shù)6節(jié)點(diǎn)，這類情況成為右左。
*D、2節(jié)點(diǎn)的左子樹(shù)1節(jié)點(diǎn)高度比右子樹(shù)4節(jié)點(diǎn)小2，右子樹(shù)4節(jié)點(diǎn)的左子樹(shù)3節(jié)點(diǎn)高度小于右子樹(shù)6節(jié)點(diǎn)，這類情況成為右右。
*
*說(shuō)明：2叉排序樹(shù)遍歷是從小到大的順序，AVL樹(shù)也是bst，但是滿足所有的樹(shù)的左右高度相差不大于1
*/
#ifndef AVL_H
#define AVL_H
#include <iostream>
using namespace std;
/*AVL樹(shù)節(jié)點(diǎn)信息*/
template <typename T>
class TreeNode
{
public :
TreeNode():lchild(NULL),rchild(NULL),freq(1),hgt(0){}
T data ;/*值*/
int hgt;/*以此節(jié)點(diǎn)為根的樹(shù)的高度*/
unsigned int freq;/*頻率*/
TreeNode * lchild,*rchild;/*左右孩子*/
};
/*AVL樹(shù)類的屬性和方法聲明*/
template <typename T>
class AVLTree
{
private :
TreeNode<T> *root; /*根節(jié)點(diǎn)*/
void InsertPri(TreeNode<T> * &node, T x); /*插入x*/
TreeNode <T>* FindPri(TreeNode<T> *node ,T x); /*查找x*/
void InSubTree(TreeNode<T> *node); /*中序遍歷*/
void DeletePri(TreeNode<T> * &node, T x); /*刪除*/
int height(TreeNode<T> *node); /*樹(shù)的高度*/
void SingRotateLeft(TreeNode<T> * &k2); /*左左情況下的旋轉(zhuǎn)*/
void SingRotateRight(TreeNode<T> * &k2); /*右右情況的旋轉(zhuǎn)*/
void DoubleRotateLR(TreeNode<T> * &k3); /*左右情況的旋轉(zhuǎn)*/
void DoubleRotateRL(TreeNode<T> * &k3); /*左右情況的旋轉(zhuǎn)*/
int Max(int cmpa,int cmpb); /*求最大值*/
public :
AVLTree():root(NULL){}
void insert(T x); /*插入接口*/
TreeNode<T> * Find(T x); /*查找接口*/
void Delete(T x); /*刪除接口*/
void Treversal(); /*遍歷接口*/
};
/*計(jì)算以節(jié)點(diǎn)為根的樹(shù)的高度*/
template <typename T>
int AVLTree <T>::height(TreeNode<T>* node)
{
return node!=NULL? node->hgt:⑴;
}
/*求最大值*/
template <typename T>
int AVLTree<T>::Max(int cmpa,int cmpb)
{
return cmpa>cmpb ? cmpa :cmpb;
}
/************************************************************************/
/* 單旋轉(zhuǎn) 單旋轉(zhuǎn)是針對(duì)左左和右右這兩種情況的解決方案，這兩種情況是
*對(duì)稱的，只要解決了左左這類情況，右右就很好辦了。圖3是左左情況的解決方案，
*節(jié)點(diǎn)k2不滿足平衡特性，由于它的左子樹(shù)k1比右子樹(shù)Z深2層，而且k1子樹(shù)中，更深
*的1層的是k1的左子樹(shù)X子樹(shù)，所以屬于左左情況 (左左情況下的選擇) */
/*為使樹(shù)恢復(fù)平衡，我們把k2變成這棵樹(shù)的根節(jié)點(diǎn)，由于k2大于k1，把k2置于k1的右
*子樹(shù)上，而本來(lái)在k1右子樹(shù)的Y大于k1，小于k2，就把Y置于k2的左子樹(shù)上，這樣既
*********************滿足了2叉查找樹(shù)的性質(zhì)，又滿足了平衡2叉樹(shù)的性質(zhì)。*/
/************************************************************************/
//****************k2******************************k1**********************
//***************/******************************/***********************
//**************k1**z****--------->*************x***k2********************
//*************/**********************************/*********************
//************x***y*******************************y***z*******************
/*這樣的操作只需要1部份指針改變，結(jié)果我們得到另外1顆2叉查找樹(shù)，它是1棵AVL樹(shù)，由于X向
*上1移動(dòng)了1層，Y還停留在原來(lái)的層面上，Z向下移動(dòng)了1層。整棵樹(shù)的新高度和之前沒(méi)有在左子
*樹(shù)上插入的高度相同，插入操作使得X高度長(zhǎng)高了。因此，由于這顆子樹(shù)高度沒(méi)有變化，所以通往根
*節(jié)點(diǎn)的路徑就不需要繼續(xù)旋轉(zhuǎn)了。***********************************************/
/*左左旋轉(zhuǎn)*/
template <typename T>
void AVLTree<T>::SingRotateLeft(TreeNode<T> * &k2)
{
TreeNode<T> *k1;
k1=k2->lchild;
k2->lchild=k1->rchild;
k1->rchild=k2;
k2->hgt=Max(height(k2->lchild),height(k2->rchild))+1;
k1->hgt=Max(height(k1->lchild),k2->hgt)+1;
k2=k1;/*最后1定要更新根節(jié)點(diǎn)*/
}
/*右右旋轉(zhuǎn)*/
template <typename T>
void AVLTree<T>::SingRotateRight(TreeNode<T> * &k2)
{
TreeNode<T> *k1;
k1=k2->rchild;
k2->rchild=k1->lchild;
k1->lchild=k2;
k2->hgt=Max(height(k2->lchild),height(k2->rchild))+1;
k1->hgt=Max(height(k1->rchild),k2->hgt)+1;
k2=k1;/*最后1定要更新根節(jié)點(diǎn)*/
}
/**************************雙旋轉(zhuǎn)(左右情況下的雙旋轉(zhuǎn))************************/
//************************************************************************
//*************k3******************k3**********************k2*************
//************/******************/**********************/**************
//**********k1***d*---->********k2***d*****---->********k1****k3**********
//*********/*******************/*********************/****/***********
//********a****k2*************k1***c******************a***b*c***d*********
//************/*************/*******************************************
//***********b***c**********a***b*****************************************
//************************************************************************
//************************************************************************
//************************************************************************
/************************************************************************/
/*
*左右旋轉(zhuǎn)
*為使樹(shù)恢復(fù)平衡，我們需要進(jìn)行兩步，第1步，把k1作為根，進(jìn)行1次右右旋轉(zhuǎn)，旋轉(zhuǎn)以后就變成
*了左左情況，所以第2步再進(jìn)行1次左左旋轉(zhuǎn)，最后得到了1棵以k2為根的平衡2叉樹(shù)樹(shù)。
*/
template <typename T>
void AVLTree<T>::DoubleRotateLR(TreeNode<T> * &k3)
{
SingRotateRight(k3->lchild);
SingRotateLeft(k3);
}
/*右左旋轉(zhuǎn)*/
template <typename T>
void AVLTree<T>::DoubleRotateRL(TreeNode<T> * &k3)
{
SingRotateLeft(k3->rchild);
SingRotateRight(k3);
}
/*************************************************************************
*插入的方法和2叉查找樹(shù)基本1樣，區(qū)分是，插入完成后需要從插入的節(jié)點(diǎn)開(kāi)始保護(hù)
*1個(gè)到根節(jié)點(diǎn)的路徑，每經(jīng)過(guò)1個(gè)節(jié)點(diǎn)都要保持樹(shù)的平衡。
*保持樹(shù)的平衡要根據(jù)高度差的特點(diǎn)選擇不同的旋轉(zhuǎn)算法。
*insert
*************************************************************************/
template <typename T>
void AVLTree<T>::InsertPri(TreeNode<T>* &node, T x)
{
if(node==NULL)/*如果節(jié)點(diǎn)為空,就在此節(jié)點(diǎn)處加入x信息*/
{
node =new TreeNode<T>();
node->data=x;
return ;
}
if (node->data>x)/*如果X小于節(jié)點(diǎn)的值，就繼續(xù)再節(jié)點(diǎn)的左子樹(shù)中插入*/
{
InsertPri(node->lchild,x);
if (2==height(node->lchild)-height(node->rchild))
{
if (x<node->lchild->data)
{
SingRotateLeft(node);
}
else
DoubleRotateLR(node);
}
}
else if (node->data<x)/*如果X大于節(jié)點(diǎn)的值，就繼續(xù)再節(jié)點(diǎn)的右子樹(shù)中插入*/
{
InsertPri(node->rchild,x);
if (2==height(node->rchild)-height(node->lchild))
{
if (x>node->rchild->data)
{
SingRotateRight(node);
}
else
DoubleRotateRL(node);
}
}
else
node->freq++;/*如果相等，頻率加1*/
node->hgt=Max(height(node->lchild),height(node->rchild))+1;
}
/************************************************************************/
/* 插入接口 */
/************************************************************************/
template <typename T>
void AVLTree<T>::insert(T x)
{
InsertPri(root,x);
}
/************************************************************************/
/* 查找 */
/*和2叉查找樹(shù)相比，查找方法沒(méi)有變法，不過(guò)根據(jù)存儲(chǔ)的特性，
*AVL樹(shù)能保持在1個(gè)O(logN)的穩(wěn)定的時(shí)間，而2叉查找樹(shù)則相當(dāng)不穩(wěn)定。
/************************************************************************/
template<typename T>
TreeNode<T>* AVLTree<T>::FindPri(TreeNode<T> *node ,T x)
{
if(node==NULL)/*如果節(jié)點(diǎn)為空說(shuō)明沒(méi)找到,返回NULL*/
return NULL;
if(node->data>x)/*如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中查找x*/
return FindPri(node->lchild,x);
if (node->data<x)/*如果x大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中查找x*/
return FindPri(node->rchild,x);
return node;/*如果相等,就找到了此節(jié)點(diǎn)*/
}
/*查找接口*/
template<typename T>
TreeNode<T>* AVLTree<T>::Find(T x)
{
return FindPri(root,x);
}
/************************************************************************/
/* 刪除 */
/*刪除的方法也和2叉查找樹(shù)的1致，區(qū)分是，刪除完成后，
*需要從刪除節(jié)點(diǎn)的父親開(kāi)始向上保護(hù)樹(shù)的平衡1直到根節(jié)點(diǎn)。
/************************************************************************/
template<typename T>
void AVLTree<T>::DeletePri(TreeNode<T> * &node, T x)
{
if(node==NULL)/*空*/
return ;
if(x<node->data)
{/*如果x小于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的左子樹(shù)中刪除x，刪除完成后，需要調(diào)劑樹(shù)，使之保持平衡*/
DeletePri(node->lchild,x);
if (2==height(node->rchild)-height(node->lchild))
{
if(node->rchild->lchild!=NULL &&
(height(node->rchild->lchild)>height(node->rchild->rchild))
)
DoubleRotateRL(node);
else
SingRotateRight(node);
}
}
else if (x>node->data)
{/*如果大于節(jié)點(diǎn)的值,就繼續(xù)在節(jié)點(diǎn)的右子樹(shù)中刪除x，刪除完成后，需要調(diào)劑樹(shù)，使之保持平衡*/
DeletePri(node->rchild,x);
if (2==height(node->lchild)-height(node->rchild))
{
if(node->rchild->lchild!=NULL &&
(height(node->lchild->rchild)>height(node->lchild->lchild))
)
DoubleRotateLR(node);
else
SingRotateLeft(node);
}
}
else/*相等，刪除，然后調(diào)劑，使之平衡*/
{
if (node->lchild && node->rchild)/*此節(jié)點(diǎn)有兩個(gè)兒子*/
{
TreeNode<T>* temp=node->rchild;/*temp指向節(jié)點(diǎn)的右兒子*/
while(temp->lchild!=NULL)
temp=temp->lchild;/*找到中序遍歷的后繼節(jié)點(diǎn)，一定在最左側(cè)那個(gè)*/
node->data=temp->data;/*調(diào)劑節(jié)點(diǎn)數(shù)據(jù)信息*/
node->freq=temp->freq;
DeletePri(node->rchild,temp->data);/*刪除邊沿節(jié)點(diǎn)*/
if (2==height(node->lchild)-height(node->rchild))
{
if (node->lchild->rchild!=NULL &&
(height(node->lchild->rchild)>height(node->lchild->lchild))
)
DoubleRotateLR(node);
else
SingRotateLeft(node);
}
}
else/*此節(jié)點(diǎn)有1個(gè)或0個(gè)兒子*/
{
TreeNode<T> *temp=node;
if(node->lchild==NULL)/*有右兒子或沒(méi)有兒子*/
node=node->rchild;
else if(node->rchild==NULL)/*有左兒子*/
node=node->lchild;
delete(temp);
temp=NULL;
}
}
if(node==NULL)
return ;
node->hgt=Max(height(node->lchild),height(node->rchild))+1;
return ;
}
/*刪除接口*/
template<typename T>
void AVLTree<T>::Delete(T x)
{
DeletePri(root,x);
}
/*中序遍歷函數(shù)*/
template<typename T>
void AVLTree<T>::InSubTree(TreeNode<T> *node)
{
if(node==NULL)
return ;
InSubTree(node->lchild);/*先遍歷左子樹(shù)*/
cout<<node->data<<" ";/*輸出根節(jié)點(diǎn)*/
InSubTree(node->rchild);/*再遍歷右子樹(shù)*/
}
/*中序遍歷接口*/
template<typename T>
void AVLTree<T>::Treversal()
{
//cout<<root->data;
InSubTree(root);
}
#endif//avl.h
測(cè)試用例：
#include "AVL.h"
int arrs[7]={88,70,61,96,120,90,65};
int main(int argc,char** argv)
{
AVLTree<int> te;
for (int i=0;i<7;i++)
{
te.insert(arrs[i]);
}
te.Treversal();
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
