java數(shù)據(jù)結(jié)構(gòu)與算法之平衡二叉樹(AVL樹)的設(shè)計(jì)與實(shí)現(xiàn)

1、java數(shù)據(jù)結(jié)構(gòu)與算法之平衡二叉樹(AVL樹)的設(shè)計(jì)與實(shí)現(xiàn)普通二叉查找樹的問題在開篇，我們提到過，普通二叉樹（二叉查找樹）在操作的時(shí)間復(fù)雜度上不一定遵循O(n)，也有可能是O(n)，這是為什么呢？在上一篇中，我們明明插入都按照一定規(guī)則比較的呀，其實(shí)那是因?yàn)槲覀冊谏掀獪y試時(shí)執(zhí)行了隨機(jī)插入的操作，如果此時(shí)利用上篇實(shí)現(xiàn)的二叉搜索樹將一段已排序好的數(shù)據(jù)一個(gè)個(gè)插入后，就會發(fā)現(xiàn)如下情況了：從圖中我們可以發(fā)現(xiàn)，把已排序的1-9數(shù)據(jù)進(jìn)行正序和倒序插入后，樹的結(jié)構(gòu)已變成單向左子樹或者右子樹了，如果我們在往里插入已排序的數(shù)據(jù)，那么單向左子樹或者右子樹越來越長，此時(shí)已跟單鏈表沒有什么區(qū)別了，因此對此結(jié)構(gòu)的操作時(shí)間復(fù)

2、雜度自然就由O(n)變成O(n)了，這也就是普通二叉查找樹不是嚴(yán)格意義上O(n)的原因。那么該如何解決這個(gè)問題呢？事實(shí)上一種解決的辦法就是要有一個(gè)稱為平衡的附加結(jié)構(gòu)條件即：任何結(jié)點(diǎn)的深度不得過深，而這種數(shù)據(jù)結(jié)構(gòu)就是我們本篇要分析的平衡二叉樹（AVL），它本身也是一種二叉查找樹，只不過不會出現(xiàn)前面我們分析的情形罷了，接下來我們就來分析一下這棵平衡二叉樹。平衡二叉樹的定義通過上面的分析，我們明白的普通二叉查找樹的不足，也知道了如何去解決這個(gè)缺點(diǎn)，即構(gòu)建樹時(shí)要求任何結(jié)點(diǎn)的深度不得過深（子樹高度相差不超過1），而最終這棵樹就是平衡二叉樹（Balanced Binary Tree），它是G.M. Ade

3、lson-Velsky 和 E.M. Landis在1962年在論文中發(fā)表的，因此又叫AVL樹。這里我們還需要明確一個(gè)概念，AVL樹只是實(shí)現(xiàn)平衡二叉樹的一種方法，它還有很多的其他實(shí)現(xiàn)方法如紅黑樹、替罪羊樹、Treap、伸展樹等，后面我們還會分析其他樹的實(shí)現(xiàn)。ok，接著來了解一下AVL樹的特性：一棵AVL樹是其每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度最多相差1的二叉查找樹(空樹的高度為-1)，這個(gè)差值也稱為平衡因子（其取值可以是1，0，-1，平衡因子是某個(gè)結(jié)點(diǎn)左右子樹層數(shù)的差值，有的書上定義是左邊減去右邊，有的書上定義是右邊減去左邊，這樣可能會有正負(fù)的區(qū)別，但是這個(gè)并不影響我們對平衡二叉樹的討論）。如下圖

4、圖(1)顯然就是一棵平衡二叉樹，它每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度最多相差1，同時(shí)也是一棵二叉查找樹，而圖二雖然也是一棵二叉查找樹，但是它每個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度相差卻到達(dá)了2，因此不是平衡二叉樹。理解了平衡二叉樹的概念后，我們在思考一下，那些操作可能引起平衡發(fā)生變化呢？顯然只有那些引起結(jié)點(diǎn)數(shù)量變化的操作才可能導(dǎo)致平衡被改變，也就是刪除和插入操作了，如下圖，我們把6插入到圖a后，結(jié)構(gòu)變成了圖b，這時(shí)原本的平衡二叉樹就失去平衡了。顯然圖b已失去平衡，如果發(fā)生這樣的情況，我們就必須考慮插入元素后恢復(fù)二叉樹的平衡性質(zhì)，實(shí)際上也總是可以通過對樹進(jìn)行簡單的修復(fù)來讓其重新恢復(fù)到平衡，而這樣的簡單操作我

5、們就稱之為旋轉(zhuǎn)，當(dāng)然旋轉(zhuǎn)也有單旋轉(zhuǎn)和雙旋轉(zhuǎn)之分，下面我們將會一一分析，這里有點(diǎn)需要明白的是，無論是插入還是刪除，只有那些從插入或者刪除點(diǎn)到根結(jié)點(diǎn)的路徑上的結(jié)點(diǎn)的平衡才有可能被改變，因?yàn)橹挥羞@些結(jié)點(diǎn)的子樹才可能發(fā)生變化，所以最終也只需針對這些點(diǎn)進(jìn)行平衡修復(fù)操作即可。平衡二叉樹的設(shè)計(jì)與實(shí)現(xiàn)ok，有了旋轉(zhuǎn)的概念后，我們接著了解如何通過旋轉(zhuǎn)來修復(fù)一棵失衡的二叉樹，這里假設(shè)結(jié)點(diǎn)X是失衡點(diǎn)，它必須重新恢復(fù)平衡，由于任意結(jié)點(diǎn)的孩子結(jié)點(diǎn)最多有兩個(gè)，而且導(dǎo)致失衡的必要條件是X結(jié)點(diǎn)的兩棵子樹高度差為2(大于1)，因此一般只有以下4種情況可能導(dǎo)致X點(diǎn)失去平衡： 在結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)的左子樹中插入元素 在結(jié)點(diǎn)X的左孩

6、子結(jié)點(diǎn)的右子樹中插入元素 在結(jié)點(diǎn)X的右孩子結(jié)點(diǎn)的左子樹中插入元素 在結(jié)點(diǎn)X的右孩子結(jié)點(diǎn)的右子樹中插入元素 以上4種情況，其中第情況和第情況是對稱的，可以通過單旋轉(zhuǎn)來解決，而第種情況和第情況是對稱的，需要雙旋轉(zhuǎn)來解決。在分析這四種情況前，我們先看看AVL的結(jié)點(diǎn)該如何設(shè)計(jì)的，其聲明如下：package com.zejian.structures.Tree.AVLTree;/* * Created by zejian on 2016/12/25. * Blog : 原文地址,請尊重原創(chuàng) * 平衡二叉搜索樹(AVL樹)節(jié)點(diǎn) */public class AVLNode<T extends Com

7、parable> public AVLNode<T> left;/左結(jié)點(diǎn) public AVLNode<T> right;/右結(jié)點(diǎn) public T data; public int height;/當(dāng)前結(jié)點(diǎn)的高度 public AVLNode(T data) this(null,null,data); public AVLNode(AVLNode<T> left, AVLNode<T> right, T data) this(left,right,data,0); public AVLNode(AVLNode<T> left,

8、 AVLNode<T> right, T data, int height) this.left=left; this.right=right; this.data=data; this.height = height; 可以看出，為了滿足平衡二叉樹的特性，需要在原來的二叉搜索樹(BST)的結(jié)點(diǎn)中添加一個(gè)height的字段表示高度，方便我們計(jì)算，這里強(qiáng)調(diào)一下，高度和深度一組相反的概念，高度是指當(dāng)前結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長路徑，如所有葉子結(jié)點(diǎn)的高度都為0，而深度則是指從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的最大路徑，如根結(jié)點(diǎn)的深度為0。這里約定空結(jié)點(diǎn)（空子樹）的高度為-1，葉子結(jié)點(diǎn)的高度為0，非葉子節(jié)點(diǎn)的高

9、度則根據(jù)其子樹的高度而計(jì)算獲取，如下圖：ok，了解上述的內(nèi)容，下面就來分析4種可能失衡的情景。平衡二叉樹的單旋轉(zhuǎn)算法與實(shí)現(xiàn)左左單旋轉(zhuǎn)(LL)情景分析從下圖可以看出，結(jié)點(diǎn)X并不能滿足AVL樹的性質(zhì)，因?yàn)樗淖笞訕浔扔易訕渖?層，這種情況就是典型的LL情景，此時(shí)需要通過右向旋轉(zhuǎn)來修復(fù)失衡的樹，如圖1，X經(jīng)過右旋轉(zhuǎn)后變成圖2，W變?yōu)楦Y(jié)點(diǎn)，X變?yōu)閃的右子樹，同時(shí)W的右子樹變?yōu)閄的左子樹，樹又重新回到平衡，各個(gè)結(jié)點(diǎn)的子樹高度差都已在正常范圍。一般情況下，我們把X結(jié)點(diǎn)稱為失衡點(diǎn)，修復(fù)一棵被破壞的AVL樹時(shí)，找到失衡點(diǎn)是很重要的并把通過一次旋轉(zhuǎn)即可修復(fù)平衡的操作叫做單旋轉(zhuǎn)，從圖3和圖4可知，在原始AVL樹

10、插入7結(jié)點(diǎn)后，結(jié)點(diǎn)9變?yōu)槭Ш恻c(diǎn)，樹再滿足AVL性質(zhì)，因此需要對9結(jié)點(diǎn)進(jìn)行左左單旋轉(zhuǎn)(即向右旋轉(zhuǎn))后，得到圖4，我們發(fā)現(xiàn)此時(shí)并沒有操作樹的根結(jié)點(diǎn)(6)，實(shí)際上這是因?yàn)檎Ｇ闆r下，不必從樹的根結(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，而是從插入結(jié)點(diǎn)處開始，向上遍歷樹，并更新和修復(fù)在這個(gè)路徑上的每個(gè)結(jié)點(diǎn)的平衡及其平衡信息(高度)即可。其代碼實(shí)現(xiàn)如下，比較簡單：/* * 左左單旋轉(zhuǎn)(LL旋轉(zhuǎn)) w變?yōu)閤的根結(jié)點(diǎn), x變?yōu)閣的右子樹 * param x * return */private AVLNode<T> singleRotateLeft(AVLNode<T> x) /把w結(jié)點(diǎn)旋轉(zhuǎn)為根結(jié)點(diǎn) AVLNo

11、de<T> w= x.left; /同時(shí)w的右子樹變?yōu)閤的左子樹 x.left=w.right; /x變?yōu)閣的右子樹 w.right=x; /重新計(jì)算x/w的高度 x.height=Math.max(height(x.left),height(x.right)+1; w.height=Math.max(height(w.left),x.height)+1; return w;/返回新的根結(jié)點(diǎn)右右單旋轉(zhuǎn)(RR)情景分析接著再來看看右右單旋轉(zhuǎn)(RR)的情景，如下圖，可以發(fā)現(xiàn)與左左單旋轉(zhuǎn)的情況恰好是一種鏡像關(guān)系，同樣結(jié)點(diǎn)X并不能滿足AVL樹的性質(zhì)，在這樣的情景下，需要對X結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)來

12、修復(fù)樹的平衡，如圖1經(jīng)左旋轉(zhuǎn)后變了圖2，此時(shí)X變?yōu)榱烁Y(jié)點(diǎn)，W變?yōu)閄的左孩子，X的左子樹變?yōu)閃的右子樹，而樹又重新恢復(fù)了平衡。如圖3和圖4的實(shí)例情景，原始的AVL樹在12處插入結(jié)點(diǎn)18后，結(jié)點(diǎn)10就變成了失衡點(diǎn)，因?yàn)?0的左子樹和右子樹的高度相差2，顯然不符合AVL樹性質(zhì)，需要對結(jié)點(diǎn)10進(jìn)行右右單旋轉(zhuǎn)修復(fù)(向左旋轉(zhuǎn))，然后得到圖4，此時(shí)樹重新回到了平衡，這便是右右單旋轉(zhuǎn)(RR)的修復(fù)情景。代碼實(shí)現(xiàn)如下：/* * 右右單旋轉(zhuǎn)(RR旋轉(zhuǎn)) x變?yōu)閣的根結(jié)點(diǎn), w變?yōu)閤的左子樹 * return */private AVLNode<T> singleRotateRight(AVLNode

13、<T> w) AVLNode<T> x=w.right; w.right=x.left; x.left=w; /重新計(jì)算x/w的高度 x.height=Math.max(height(x.left),w.height)+1; w.height=Math.max(height(w.left),height(w.right)+1; /返回新的根結(jié)點(diǎn) return x;平衡二叉樹的雙旋轉(zhuǎn)算法與實(shí)現(xiàn)前面兩種情景都已分析完，它們都是基于單旋轉(zhuǎn)的算法，但這種算法存在一個(gè)問題，那就是對情景無法生效，根本問題在于子樹Y太深了，如下圖所示：顯然經(jīng)過一次單旋轉(zhuǎn)的修復(fù)后無論是X或者W作為根結(jié)

14、點(diǎn)都無法符合AVL樹的性質(zhì)，此時(shí)就需要用雙旋轉(zhuǎn)算法來實(shí)現(xiàn)了。由于子樹Y是在插入某個(gè)結(jié)點(diǎn)后導(dǎo)致X結(jié)點(diǎn)的左右子樹失去平衡，那么就說明子樹Y肯定是非空的，因此為了易于理解，我們可以把子樹Y看作一個(gè)根結(jié)點(diǎn)和兩棵子樹，如下圖所示：ok，明白了單旋轉(zhuǎn)對于情景的窘境，下面我們就通過雙旋轉(zhuǎn)算法來解開這個(gè)窘境。左右雙旋轉(zhuǎn)(LR)情景分析為了重新平衡，通過上述的分析顯然不能把X根結(jié)點(diǎn)，而X與W間的旋轉(zhuǎn)也解決不了問題，那唯一的旋轉(zhuǎn)就是把Y作為新根。這樣的話，X、W就不得不成為Y的孩子結(jié)點(diǎn)，其中W作為Y的左孩子結(jié)點(diǎn)，而X成為Y的右孩子結(jié)點(diǎn)。這里我們以下圖為例來分析，為了達(dá)到以上結(jié)果，需要W、Y進(jìn)行單旋轉(zhuǎn)（圖1），這里

15、我們可把WY組成的子樹看成前面的右右旋轉(zhuǎn)情景，然后進(jìn)行左向旋轉(zhuǎn)，得到圖2，W變?yōu)閅的左子樹同時(shí)Y的左子樹B變成W的右子樹，其他不變，到此第一次旋轉(zhuǎn)完成，進(jìn)行第二次旋轉(zhuǎn)，以X結(jié)點(diǎn)向右進(jìn)行旋轉(zhuǎn)(同樣可看作左左情景)，由圖2得到圖3，X變成Y的右孩子結(jié)點(diǎn)并且Y的右子樹C變成X的左子樹，第二次旋轉(zhuǎn)完成，樹也重新恢復(fù)到平衡。在左右雙旋轉(zhuǎn)實(shí)例圖123中，在原AVL樹種插入結(jié)點(diǎn)7后，結(jié)點(diǎn)8變成了失衡點(diǎn)，此時(shí)需要把6結(jié)點(diǎn)變?yōu)楦Y(jié)點(diǎn)才能重新恢復(fù)平衡。因此先進(jìn)行左向旋轉(zhuǎn)再進(jìn)行右向旋轉(zhuǎn)，最后樹恢復(fù)平衡。算法代碼實(shí)現(xiàn)如下：/* * 左右旋轉(zhuǎn)(LR旋轉(zhuǎn)) x(根) w y 結(jié)點(diǎn) 把y變成根結(jié)點(diǎn) * return */p

16、rivate AVLNode<T> doubleRotateWithLeft(AVLNode<T> x) /w先進(jìn)行RR旋轉(zhuǎn) x.left=singleRotateRight(x.left); /再進(jìn)行x的LL旋轉(zhuǎn) return singleRotateLeft(x);右左雙旋轉(zhuǎn)(RL)情景分析對于右左雙旋轉(zhuǎn)(RL)情景和左右雙旋轉(zhuǎn)(LR)情景是一對鏡像，旋轉(zhuǎn)的原理上一樣的，這里就不廢話了，給出下圖協(xié)助理解即可(已很清晰了)：實(shí)現(xiàn)代碼如下：/* * 右左旋轉(zhuǎn)(RL旋轉(zhuǎn)) * param w * return */private AVLNode<T> doub

17、leRotateWithRight(AVLNode<T> w) /先進(jìn)行LL旋轉(zhuǎn) w.right=singleRotateLeft(w.right); /再進(jìn)行RR旋轉(zhuǎn) return singleRotateRight(w);好，到此4種情況都已分析完畢，接著我們就利用這種四種情況來重寫AVL樹的插入操作過程。平衡二叉樹插入操作的實(shí)現(xiàn)實(shí)際上，有了上述四種情況后，編寫插入操作的編碼細(xì)節(jié)并不會太困難，這里我們給出主要思路和代碼實(shí)現(xiàn)即可（很清晰的注釋），與BST（二叉查找樹）的插入實(shí)現(xiàn)原理一樣，使用遞歸算法，根據(jù)值大小查找到插入位置，然后進(jìn)行插入操作，插入完成后，我們需要進(jìn)行平衡判斷，評

18、估子樹是否需要進(jìn)行平衡修復(fù)，需要則利用上述的四種情景套入代碼即可，最后要記得重新計(jì)算插入結(jié)點(diǎn)路徑上的高度。代碼實(shí)現(xiàn)如下：/* 插入方法* param data*/Overridepublic void insert(T data) if (data=null) throw new RuntimeException("data can't not be null "); this.root=insert(data,root);private AVLNode<T> insert(T data , AVLNode<T> p) /說明已沒有孩子結(jié)點(diǎn),

19、可以創(chuàng)建新結(jié)點(diǎn)插入了. if(p=ull) p=new AVLNode<T>(data); else if(pareTo(p.data)<0)/向左子樹尋找插入位置 p.left=insert(data,p.left); /插入后計(jì)算子樹的高度,等于2則需要重新恢復(fù)平衡,由于是左邊插入,左子樹的高度肯定大于等于右子樹的高度 if(height(p.left)-height(p.right)=2) /判斷data是插入點(diǎn)的左孩子還是右孩子 if(pareTo(p.left.data)<0) /進(jìn)行LL旋轉(zhuǎn) p=singleRotateLeft(p); else /進(jìn)行左右

20、旋轉(zhuǎn) p=doubleRotateWithLeft(p); else if (pareTo(p.data)>0)/向右子樹尋找插入位置 p.right=insert(data,p.right); if(height(p.right)-height(p.left)=2) if (pareTo(p.right.data)<0) /進(jìn)行右左旋轉(zhuǎn) p=doubleRotateWithRight(p); else p=singleRotateRight(p); else ;/if exist do nothing /重新計(jì)算各個(gè)結(jié)點(diǎn)的高度 p.height = Math.max( heigh

21、t( p.left ), height( p.right ) ) + 1; return p;/返回根結(jié)點(diǎn)平衡二叉樹刪除操作的實(shí)現(xiàn)關(guān)于平衡二叉樹的刪除，我們這里給出一種遞歸的實(shí)現(xiàn)方案，和二叉查找樹中刪除方法的實(shí)現(xiàn)類似，但是在移除結(jié)點(diǎn)后需要進(jìn)行平衡檢測，以便判斷是否需要進(jìn)行平衡修復(fù)，主要明白的是，這種實(shí)現(xiàn)方式在刪除時(shí)效率并不高，不過我們并不打算過多討論它，更復(fù)雜的刪除操作過程將放在紅黑樹中進(jìn)行討論。下面給出實(shí)現(xiàn)代碼：/* * 刪除方法 * param data */Overridepublic void move(T data) if (data=null) throw new RuntimeE

22、xception("data can't not be null "); this.root=remove(data,root);/* * 刪除操作 * param data * param p * return */private AVLNode<T> remove(T data,AVLNode<T> p) if(p =null) return null; int result=pareTo(p.data); /從左子樹查找需要刪除的元素 if(result<0) p.left=remove(data,p.left); /檢測是否平衡

23、 if(height(p.right)-height(p.left)=2) AVLNode<T> currentNode=p.right; /判斷需要那種旋轉(zhuǎn) if(height(currentNode.left)>height(currentNode.right) /LL p=singleRotateLeft(p); else /LR p=doubleRotateWithLeft(p); /從右子樹查找需要刪除的元素 else if(result>0) p.right=remove(data,p.right); /檢測是否平衡 if(height(p.left)-he

24、ight(p.right)=2) AVLNode<T> currentNode=p.left; /判斷需要那種旋轉(zhuǎn) if(height(currentNode.right)>height(currentNode.left) /RR p=singleRotateRight(p); else /RL p=doubleRotateWithRight(p); /已找到需要刪除的元素,并且要刪除的結(jié)點(diǎn)擁有兩個(gè)子節(jié)點(diǎn) else if(p.right!=null&&p.left!=null) /尋找替換結(jié)點(diǎn) p.data=findMin(p.right).data; /移除用于替換的結(jié)點(diǎn) p.right = remove( p.data, p.right ); else /只有一個(gè)孩子結(jié)點(diǎn)或者只是葉子結(jié)點(diǎn)的情況 p=(p.left!=null)? p.left:p.right; /更新高度值 if(p!