二叉排序樹AVL如何實(shí)現(xiàn)動態(tài)平衡

什么是AVL樹

大家好，我是bigsai，好久不見，甚是想念,今天給大家講講AVL樹。

對于樹這種數(shù)據(jù)結(jié)構(gòu)，想必大家也已經(jīng)不再陌生，我們簡單回顧一下。

在樹的種類中，通常分成二叉樹和多叉樹，我們熟悉的二叉樹種類有二叉搜索(排序、查找)樹、二叉平衡樹、伸展樹、紅黑樹等等。而熟悉的多叉樹像B樹、字典樹都是經(jīng)典多叉樹。

普通的二叉樹，我們研究其遍歷方式，因?yàn)槠錄]啥規(guī)則約束查找和插入都很隨意所以很少有研究價(jià)值。

但是二叉樹結(jié)構(gòu)上很有特點(diǎn)：左孩子和右孩子，兩個(gè)不同方向的孩子對應(yīng)二進(jìn)制的01，判斷的對錯(cuò)，比較的大小，所以根據(jù)這個(gè)結(jié)構(gòu)所有樹左側(cè)節(jié)點(diǎn)比父節(jié)點(diǎn)小，右側(cè)節(jié)點(diǎn)比父節(jié)點(diǎn)大，這時(shí)候就誕生了二叉搜索(排序)樹。二叉搜索(排序)樹的一大特點(diǎn)就是查找效率提高了，因?yàn)椴檎乙粋€(gè)元素位置或者查看元素是否存在通過每遇到一個(gè)節(jié)點(diǎn)直接進(jìn)行比較就可以一步步逼近結(jié)果的位置。

但二叉搜索(排序樹)有個(gè)很大的問題就是當(dāng)插入節(jié)點(diǎn)很有序，很可能成為一棵斜樹或者深度很高，那么這樣的一個(gè)查找效率還是趨近于線性O(shè)(n)級別，所以這種情況二叉搜索(排序)樹的效率是比較低的。

所以，人們有個(gè)期望：對一棵樹來說插入節(jié)點(diǎn)，小的還在左面，大的還在右面方便查找，但是能不能不要出現(xiàn)那么斜的情況？

這不，平衡二叉搜索(AVL)樹就是這么干的，AVL在插入的時(shí)候每次都會旋轉(zhuǎn)自平衡，讓整個(gè)樹一直處于平衡狀態(tài)，讓整個(gè)樹的查詢更加穩(wěn)定(logN)。我們首先來看一下什么是AVL樹：

• AVL樹是帶有平衡條件的二叉搜索樹，這個(gè)平衡條件必須要容易保持，而且要保證它的深度是O(logN)。

• AVL的左右子樹的高度差（平衡因子）不大于1，并且它的每個(gè)子樹也都是平衡二叉樹。

• 對于平衡二叉樹的最小個(gè)數(shù)，n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以類比斐波那契)

難點(diǎn)：AVL是一顆二叉排序樹，用什么樣的規(guī)則或者規(guī)律讓它能夠在復(fù)雜度不太高的情況下實(shí)現(xiàn)動態(tài)平衡呢？

不平衡情況

如果從簡單情況模型看，其實(shí)四種不平衡情況很簡單，分別是RR,LL,RL,LR四種不平衡情況。

然后將其平衡的結(jié)果也很容易(不考慮其附帶節(jié)點(diǎn)只看結(jié)果)，將中間大小數(shù)值移動最上方，其他相對位置不變即可：

當(dāng)然，這個(gè)僅僅是針對三個(gè)節(jié)點(diǎn)情況太過于理想化了，很多時(shí)候讓你找不平衡的點(diǎn)，或者我們在解決不平衡的時(shí)候，我們需要的就是找到第一個(gè)不平衡(從底往上)的點(diǎn)將其平衡即可，下面列舉兩個(gè)不平衡的例子：

上述四種不平衡條件情況，可能出現(xiàn)在底部，也可能出現(xiàn)在頭，也可能出現(xiàn)在某個(gè)中間節(jié)點(diǎn)導(dǎo)致不平衡，而我們只需要研究其首次不平衡點(diǎn)，解決之后整棵樹即繼續(xù)平衡，在具體的處理上我們使用遞歸的方式解決問題。

四種不平衡情況處理

針對四種不平衡的情況，這里對每種情況進(jìn)行詳細(xì)的講解。

RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))

這里的RR指的是節(jié)點(diǎn)模型的樣子，其含義是需要左單旋轉(zhuǎn)(記憶時(shí)候需要注意一下RR不是右旋轉(zhuǎn))！

出現(xiàn)這種情況的原因是節(jié)點(diǎn)的右側(cè)的右側(cè)較深這時(shí)候不平衡節(jié)點(diǎn)需要左旋，再細(xì)看過程。

• 在左旋的過程中，root(oldroot)節(jié)點(diǎn)下沉，中間節(jié)點(diǎn)(newroot)上浮.而其中中間節(jié)點(diǎn)(newroot)的右側(cè)依然不變。

• 它上浮左側(cè)所以需要指向根節(jié)點(diǎn)(oldroot)(畢竟一棵樹)。但是這樣newroot原來左側(cè)節(jié)點(diǎn)H空缺。而我們需要仍然讓整個(gè)樹完整并且滿足二叉排序樹的規(guī)則。

• 而剛好本來oldroot右側(cè)指向newroot現(xiàn)在結(jié)構(gòu)改變oldroot右側(cè)空缺，剛好這個(gè)位置滿足在oldroot的右側(cè)，在newroot的左側(cè)，所以我們將H插入在這個(gè)位置。

• 其中H可能為NULL，不過不影響操作！

其更詳細(xì)流程為：

而左旋的代碼可以表示為：

privatenodegetRRbanlance(nodeoldroot){//右右深，需要左旋
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新計(jì)算
returnnewroot;
}

LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))

而右旋和左旋相反，但是思路相同，根據(jù)上述進(jìn)行替換即可！

代碼：

privatenodegetLLbanlance(nodeoldroot){//LL小，需要右旋轉(zhuǎn)
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
returnnewroot;
}

RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))

這個(gè)RL你可能有點(diǎn)懵圈，為啥RR叫左旋，LL叫右旋，這個(gè)RL怎么就叫先右后左旋轉(zhuǎn)了？

別急別急，這個(gè)之所以先后后左，是因?yàn)榫唧w需要中間節(jié)點(diǎn)右旋一次，然后上面節(jié)點(diǎn)左旋一次才能平衡，具體可以下面慢慢看。

首先產(chǎn)生這種不平衡的條件原因是：ROOT節(jié)點(diǎn)右側(cè)左側(cè)節(jié)點(diǎn)的深度高些，使得與左側(cè)的差大于1，這個(gè)與我們前面看到的左旋右旋不同因?yàn)樾D(zhuǎn)一次無法達(dá)到平衡！

對于右左結(jié)構(gòu)，中間(R)的最大，兩側(cè)(ROOT,R.L)的最小，但是下面(R.L)的比上面(ROOT)大(R.L在ROOT右側(cè))所以如果平衡的話，那么R.L應(yīng)該在中間，而R應(yīng)該在右側(cè),原來的ROOT在左側(cè)。

這個(gè)過程節(jié)點(diǎn)的變化浮動比較大，需要妥善處理各個(gè)子節(jié)點(diǎn)的移動使其滿足二叉排序樹的性質(zhì)！

這種雙旋轉(zhuǎn)具體實(shí)現(xiàn)其實(shí)也不難，不要被外表唬住，這里面雙旋轉(zhuǎn)我提供兩種解答方法。

思路(標(biāo)準(zhǔn)答案)1：兩次旋轉(zhuǎn)RR,LL

這個(gè)處理起來非常容易，因?yàn)榍懊嬉呀?jīng)解決RR(左旋),LL(右旋)的問題，所以這里面在上面基礎(chǔ)上可以直接解決，首先對R節(jié)點(diǎn)進(jìn)行一次LL右旋，旋轉(zhuǎn)一次之后R在最右側(cè)，這就轉(zhuǎn)化成RR不平衡旋轉(zhuǎn)的問題了，所以這個(gè)時(shí)候以ROOT開始一次RR左旋即可完成平衡，具體流程可以參考下面這張圖。

思路(個(gè)人方法)2：直接分析

根據(jù)初始和結(jié)果的狀態(tài)，然后分析各個(gè)節(jié)點(diǎn)變化順序=，手動操作這些節(jié)點(diǎn)即可。其實(shí)不管你怎么操作，只要能滿足最后結(jié)構(gòu)一致就行啦！

首先根據(jù)ROOT,R,R.L三個(gè)節(jié)點(diǎn)變化，R.L肯定要在最頂層，左右分別指向ROOT和R，那么這其中R.left，ROOT.right發(fā)生變化(原來分別是R.L和R)暫時(shí)為空。而剛好根據(jù)左右大小關(guān)系可以補(bǔ)上R.L原來的孩子節(jié)點(diǎn)A，B。

代碼為：(注釋部分為方案1)

privatenodegetRLbanlance(nodeoldroot){//右左深
//nodenewroot=oldroot.right.left;
//oldroot.right.left=newroot.right;
//newroot.right=oldroot.right;
//oldroot.right=newroot.left;
//newroot.left=oldroot;
//oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
//newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
//newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
oldroot.right=getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetRRbanlance(oldroot);

}

LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))

這個(gè)情況和RL情況相似，采取相同操作即可。

根據(jù)上述RL修改即可

privatenodegetLRbanlance(nodeoldroot){
oldroot.left=getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetLLbanlance(oldroot);

}

代碼實(shí)現(xiàn)

首先對于節(jié)點(diǎn)多個(gè)height屬性。用于計(jì)算高度(平衡因子)

插入是遞歸插入，遞歸是一個(gè)來回的過程，去的過程進(jìn)行插入，回的過程進(jìn)行高度更新，和檢查是否平衡。推薦不要寫全局遞歸計(jì)算高度，效率太低下，事實(shí)上高度變化只和插入和平衡有關(guān)，仔細(xì)考慮即不會有疏漏！

代碼寫的比較早，如有命名不規(guī)范的情況，還請勿噴，如果有疏漏還請指出！

importjava.util.ArrayDeque;
importjava.util.Queue;

publicclassAVLTree{

classnode
{
intvalue;
nodeleft;
noderight;
intheight;
publicnode(){

}
publicnode(intvalue)
{
this.value=value;
this.height=0;
}
publicnode(intvalue,nodeleft,noderight)
{
this.value=value;
this.left=left;this.right=right;
this.height=0;
}
}
noderoot;//根

publicAVLTree(){
this.root=null;
}

publicbooleanisContains(intx)//是否存在
{
nodecurrent=root;
if(root==null){
returnfalse;
}
while(current.value!=x&¤t!=null){
if(xif(x>current.value){
current=current.right;
}
if(current==null){
returnfalse;
}//在里面判斷如果超直接返回
}
//如果在這個(gè)位置判斷是否為空會導(dǎo)致current.value不存在報(bào)錯(cuò)
if(current.value==x){
returntrue;
}
returnfalse;
}

publicintgetHeight(nodet)
{
if(t==null){return-1;}//
returnt.height;
//return1+Math.max(getHeight(t.left),getHeight(t.right));這種效率太低
}
publicvoidcengxu(nodet){//層序遍歷
Queueq1=newArrayDeque();
if(t==null)
return;
if(t!=null){
q1.add(t);
}
while(!q1.isEmpty()){
nodet1=q1.poll();
if(t1.left!=null)
q1.add(t1.left);
if(t1.right!=null)
q1.add(t1.right);
System.out.print(t1.value+"");
}
System.out.println();
}
publicvoidzhongxu(nodet)//中序遍歷中序遍歷：左子樹--->根結(jié)點(diǎn)--->右子樹
{//為了測試改成中后都行
if(t!=null)
{
zhongxu(t.left);
System.out.print(t.value+"");//訪問完左節(jié)點(diǎn)訪問當(dāng)前節(jié)點(diǎn)
zhongxu(t.right);
//System.out.print(t.value+"");//訪問完左節(jié)點(diǎn)訪問當(dāng)前節(jié)點(diǎn)
}
}
publicvoidqianxu(nodet)//前序遞歸前序遍歷：根結(jié)點(diǎn)--->左子樹--->右子樹
{
if(t!=null){
System.out.print(t.value+"");//當(dāng)前節(jié)點(diǎn)
qianxu(t.left);
qianxu(t.right);}
}
publicvoidinsert(intvalue){
root=insert(value,root);
}
publicnodeinsert(intx,nodet)//插入t是root的引用
{
nodea1=newnode(x);
//if(root==null){root=a1;returnroot;}
if(t==null){returna1;}
//插入操作。遞歸實(shí)現(xiàn)
elseif(t!=null)
{
if(xelse
{t.right=insert(x,t.right);}
}
/*
*更新當(dāng)前節(jié)點(diǎn)的高度，因?yàn)檎麄€(gè)插入只有被插入的一方有影響，
*所以遞歸會更新好最底層的，上層可直接調(diào)用
*/
t.height=Math.max(getHeight(t.left),getHeight(t.right))+1;//不要寫成遞歸，遞歸效率低
returnbanlance(t);//因?yàn)閖ava對象傳參機(jī)制，需要克隆，不可直接t=xx否則變換
}

privatenodebanlance(nodet){
//TODOAuto-generatedmethodstub
//if(t==null)returnnull;
intlefthigh=getHeight(t.left);
intrighthigh=getHeight(t.right);
if(Math.abs(lefthigh-righthigh)<=1)//不需要平衡滴
{returnt;}
elseif(lefthigh//右側(cè)大
{
if(getHeight(t.right.left)//RR需要左旋
{
returngetRRbanlance(t);
}
else{
returngetRLbanlance(t);
}
}
else{
if(getHeight(t.left.left)>getHeight(t.left.right))//ll左左
{
returngetLLbanlance(t);
}
else{
returngetLRbanlance(t);
}
}
}
/*
*oldroot(平衡因子為2,不平衡)==>newroot
*//
*Bnewroot(平衡因子為1)oldrootD
*//
*CDBCE
*
*E
*/

privatenodegetRRbanlance(nodeoldroot){//右右深，需要左旋
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新計(jì)算
returnnewroot;
}
/*
*右旋同理
*/
privatenodegetLLbanlance(nodeoldroot){//LL小，需要右旋轉(zhuǎn)
//TODOAuto-generatedmethodstub
nodenewroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
returnnewroot;
}

privatenodegetLRbanlance(nodeoldroot){
oldroot.left=getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetLLbanlance(oldroot);

}

/*(不平衡出現(xiàn)在右左節(jié)點(diǎn))
*oldroot==>newroot
*//
*ABoldrootB
*///
*newrootDAEFD
*/
*EF
*/

privatenodegetRLbanlance(nodeoldroot){//右左深
//nodenewroot=oldroot.right.left;
//oldroot.right.left=newroot.right;
//newroot.right=oldroot.right;
//oldroot.right=newroot.left;
//newroot.left=oldroot;
//oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
//newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
//newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
oldroot.right=getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
returngetRRbanlance(oldroot);

}
}

測試情況：

AVL的理解需要時(shí)間，當(dāng)然筆者的AVL自己寫的可能有些疏漏，如果有問題還請各位一起探討！

當(dāng)然，除了插入，AVL還有刪除等其他操作，(原理相似。刪除后平衡)有興趣可以一起研究。