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

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

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

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

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

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

6、子結(jié)點(diǎn)的右子樹(shù)中插入元素 在結(jié)點(diǎn)X的右孩子結(jié)點(diǎn)的左子樹(shù)中插入元素 在結(jié)點(diǎn)X的右孩子結(jié)點(diǎn)的右子樹(shù)中插入元素 以上4種情況，其中第情況和第情況是對(duì)稱(chēng)的，可以通過(guò)單旋轉(zhuǎn)來(lái)解決，而第種情況和第情況是對(duì)稱(chēng)的，需要雙旋轉(zhuǎn)來(lái)解決。在分析這四種情況前，我們先看看AVL的結(jié)點(diǎn)該如何設(shè)計(jì)的，其聲明如下：package com.zejian.structures.Tree.AVLTree;/* * Created by zejian on 2016/12/25. * Blog : 原文地址,請(qǐng)尊重原創(chuàng) * 平衡二叉搜索樹(shù)(AVL樹(shù))節(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; 可以看出，為了滿(mǎn)足平衡二叉樹(shù)的特性，需要在原來(lái)的二叉搜索樹(shù)(BST)的結(jié)點(diǎn)中添加一個(gè)height的字段表示高度，方便我們計(jì)算，這里強(qiáng)調(diào)一下，高度和深度一組相反的概念，高度是指當(dāng)前結(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長(zhǎng)路徑，如所有葉子結(jié)點(diǎn)的高度都為0，而深度則是指從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的最大路徑，如根結(jié)點(diǎn)的深度為0。這里約定空結(jié)點(diǎn)（空子樹(shù)）的高度為-1，葉子結(jié)點(diǎn)的高度為0，非葉子節(jié)點(diǎn)的高

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

10、插入7結(jié)點(diǎn)后，結(jié)點(diǎn)9變?yōu)槭Ш恻c(diǎn)，樹(shù)再滿(mǎn)足AVL性質(zhì)，因此需要對(duì)9結(jié)點(diǎn)進(jìn)行左左單旋轉(zhuǎn)(即向右旋轉(zhuǎn))后，得到圖4，我們發(fā)現(xiàn)此時(shí)并沒(méi)有操作樹(shù)的根結(jié)點(diǎn)(6)，實(shí)際上這是因?yàn)檎Ｇ闆r下，不必從樹(shù)的根結(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)，而是從插入結(jié)點(diǎn)處開(kāi)始，向上遍歷樹(shù)，并更新和修復(fù)在這個(gè)路徑上的每個(gè)結(jié)點(diǎn)的平衡及其平衡信息(高度)即可。其代碼實(shí)現(xiàn)如下，比較簡(jiǎn)單：/* * 左左單旋轉(zhuǎn)(LL旋轉(zhuǎn)) w變?yōu)閤的根結(jié)點(diǎn), x變?yōu)閣的右子樹(shù) * 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的右子樹(shù)變?yōu)閤的左子樹(shù) x.left=w.right; /x變?yōu)閣的右子樹(shù) 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)情景分析接著再來(lái)看看右右單旋轉(zhuǎn)(RR)的情景，如下圖，可以發(fā)現(xiàn)與左左單旋轉(zhuǎn)的情況恰好是一種鏡像關(guān)系，同樣結(jié)點(diǎn)X并不能滿(mǎn)足AVL樹(shù)的性質(zhì)，在這樣的情景下，需要對(duì)X結(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)來(lái)

12、修復(fù)樹(shù)的平衡，如圖1經(jīng)左旋轉(zhuǎn)后變了圖2，此時(shí)X變?yōu)榱烁Y(jié)點(diǎn)，W變?yōu)閄的左孩子，X的左子樹(shù)變?yōu)閃的右子樹(shù)，而樹(shù)又重新恢復(fù)了平衡。如圖3和圖4的實(shí)例情景，原始的AVL樹(shù)在12處插入結(jié)點(diǎn)18后，結(jié)點(diǎn)10就變成了失衡點(diǎn)，因?yàn)?0的左子樹(shù)和右子樹(shù)的高度相差2，顯然不符合AVL樹(shù)性質(zhì)，需要對(duì)結(jié)點(diǎn)10進(jìn)行右右單旋轉(zhuǎn)修復(fù)(向左旋轉(zhuǎn))，然后得到圖4，此時(shí)樹(shù)重新回到了平衡，這便是右右單旋轉(zhuǎn)(RR)的修復(fù)情景。代碼實(shí)現(xiàn)如下：/* * 右右單旋轉(zhuǎn)(RR旋轉(zhuǎn)) x變?yōu)閣的根結(jié)點(diǎn), w變?yōu)閤的左子樹(shù) * 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;平衡二叉樹(shù)的雙旋轉(zhuǎn)算法與實(shí)現(xiàn)前面兩種情景都已分析完，它們都是基于單旋轉(zhuǎn)的算法，但這種算法存在一個(gè)問(wèn)題，那就是對(duì)情景無(wú)法生效，根本問(wèn)題在于子樹(shù)Y太深了，如下圖所示：顯然經(jīng)過(guò)一次單旋轉(zhuǎn)的修復(fù)后無(wú)論是X或者W作為根結(jié)

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

15、我們可把WY組成的子樹(shù)看成前面的右右旋轉(zhuǎn)情景，然后進(jìn)行左向旋轉(zhuǎn)，得到圖2，W變?yōu)閅的左子樹(shù)同時(shí)Y的左子樹(shù)B變成W的右子樹(shù)，其他不變，到此第一次旋轉(zhuǎn)完成，進(jìn)行第二次旋轉(zhuǎn)，以X結(jié)點(diǎn)向右進(jìn)行旋轉(zhuǎn)(同樣可看作左左情景)，由圖2得到圖3，X變成Y的右孩子結(jié)點(diǎn)并且Y的右子樹(shù)C變成X的左子樹(shù)，第二次旋轉(zhuǎn)完成，樹(shù)也重新恢復(fù)到平衡。在左右雙旋轉(zhuǎn)實(shí)例圖123中，在原AVL樹(shù)種插入結(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)，最后樹(shù)恢復(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)情景分析對(duì)于右左雙旋轉(zhuǎn)(RL)情景和左右雙旋轉(zhuǎn)(LR)情景是一對(duì)鏡像，旋轉(zhuǎn)的原理上一樣的，這里就不廢話(huà)了，給出下圖協(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種情況都已分析完畢，接著我們就利用這種四種情況來(lái)重寫(xiě)AVL樹(shù)的插入操作過(guò)程。平衡二叉樹(shù)插入操作的實(shí)現(xiàn)實(shí)際上，有了上述四種情況后，編寫(xiě)插入操作的編碼細(xì)節(jié)并不會(huì)太困難，這里我們給出主要思路和代碼實(shí)現(xiàn)即可（很清晰的注釋?zhuān)?，與BST（二叉查找樹(shù)）的插入實(shí)現(xiàn)原理一樣，使用遞歸算法，根據(jù)值大小查找到插入位置，然后進(jìn)行插入操作，插入完成后，我們需要進(jìn)行平衡判斷，評(píng)

18、估子樹(shù)是否需要進(jìn)行平衡修復(fù)，需要?jiǎng)t利用上述的四種情景套入代碼即可，最后要記得重新計(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) /說(shuō)明已沒(méi)有孩子結(jié)點(diǎn),

19、可以創(chuàng)建新結(jié)點(diǎn)插入了. if(p=ull) p=new AVLNode<T>(data); else if(pareTo(p.data)<0)/向左子樹(shù)尋找插入位置 p.left=insert(data,p.left); /插入后計(jì)算子樹(shù)的高度,等于2則需要重新恢復(fù)平衡,由于是左邊插入,左子樹(shù)的高度肯定大于等于右子樹(shù)的高度 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)/向右子樹(shù)尋找插入位置 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ù)刪除操作的實(shí)現(xiàn)關(guān)于平衡二叉樹(shù)的刪除，我們這里給出一種遞歸的實(shí)現(xiàn)方案，和二叉查找樹(shù)中刪除方法的實(shí)現(xiàn)類(lèi)似，但是在移除結(jié)點(diǎn)后需要進(jìn)行平衡檢測(cè)，以便判斷是否需要進(jìn)行平衡修復(fù)，主要明白的是，這種實(shí)現(xiàn)方式在刪除時(shí)效率并不高，不過(guò)我們并不打算過(guò)多討論它，更復(fù)雜的刪除操作過(guò)程將放在紅黑樹(shù)中進(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); /從左子樹(shù)查找需要?jiǎng)h除的元素 if(result<0) p.left=remove(data,p.left); /檢測(cè)是否平衡

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); /從右子樹(shù)查找需要?jiǎng)h除的元素 else if(result>0) p.right=remove(data,p.right); /檢測(cè)是否平衡 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ǎng)h除的元素,并且要?jiǎng)h除的結(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!