什么是平衡二叉樹（中）

在上一次跟大家介紹平衡二叉樹的時(shí)候我們介紹了平衡二叉樹的定義，以及如何去辨別什么是平衡二叉樹，今天繼續(xù)跟大家介紹平衡二叉樹的實(shí)現(xiàn)原理。

同學(xué)們可以點(diǎn)擊這里回顧之前的知識(shí)http://sadw.com.cn/?mod=news_detail&id=94

平衡二叉樹構(gòu)建的基本思想就是在構(gòu)建二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。

為了能在講解算法時(shí)輕松一些，我們先講一個(gè)平衡二叉樹構(gòu)建過程的例子。假設(shè)我們現(xiàn)在有一個(gè)數(shù)組a[10]={3,2,1,4,5,6,7,10,9,8}需要構(gòu)建二叉排序樹。在沒有學(xué)習(xí)平衡二叉樹之前，根據(jù)二叉排序樹的特性，我們通常會(huì)將它構(gòu)建成如圖5所示的樣子。

雖然它完全符合二叉排序樹的定義，但是對(duì)這樣深度達(dá)到8的二叉樹來說，查找是非常不利的。我們更期望能構(gòu)建成如圖6所示的樣子，深度為4的二叉排序樹才可以提供高效的查找效率。

那么現(xiàn)在我們就來研究如何將一個(gè)數(shù)組構(gòu)建出圖6的樹結(jié)構(gòu)。

(在以下圖中，結(jié)點(diǎn)左上角數(shù)字為該結(jié)點(diǎn)的平衡因子BF值)

對(duì)于數(shù)組a[10]={3,2,1,4,5,6,7,10,9,8}的前兩位3和2，我們很正常的構(gòu)建。到了第3個(gè)數(shù)“1” 時(shí)，發(fā)現(xiàn)此時(shí)根結(jié)點(diǎn)”3“的平衡因子變成了2，此時(shí)整棵樹都成了最小不平衡子樹，因此需要調(diào)整，如下圖7。因?yàn)锽F值為正，因此我們將整個(gè)樹進(jìn)行右旋(順時(shí)針旋轉(zhuǎn))，此時(shí)結(jié)點(diǎn)2成了根結(jié)點(diǎn)，3成了2的右孩子，這樣三個(gè)結(jié)點(diǎn)的BF值均為0，非常的平衡，如下圖8所示。

然后我們?cè)僭黾咏Y(jié)點(diǎn)4，如圖9，平衡因子沒有超出限定范圍（-1，0，1）。

接下來增加結(jié)點(diǎn)5，如下圖（圖10），此時(shí)結(jié)點(diǎn)3的BF值為-2，說明要旋轉(zhuǎn)了。由于BF是負(fù)值，所以我們對(duì)這顆最小平衡子樹進(jìn)行左旋（逆時(shí)針旋轉(zhuǎn)），如圖11，此時(shí)整個(gè)樹又達(dá)到了平衡。

繼續(xù)增加結(jié)點(diǎn)6，此時(shí)根結(jié)點(diǎn)2的BF值變成-2，如下圖（圖12）。所以我們對(duì)根結(jié)點(diǎn)進(jìn)行左旋操作，注意此時(shí)原本結(jié)點(diǎn)3是結(jié)點(diǎn)4的左孩子，由于旋轉(zhuǎn)后需要滿足二叉排序樹特性，因此它成了結(jié)點(diǎn)2的右孩子，如圖13。

再增加結(jié)點(diǎn)7，同樣進(jìn)行左旋操作，使整棵樹達(dá)到平衡，如圖14和圖15。

增加結(jié)點(diǎn)10，仍然平衡，如下（圖16）。

再接下來增加結(jié)點(diǎn)9，此時(shí)結(jié)點(diǎn)7的BF變成-2，理論上來說我們只需要旋轉(zhuǎn)最小平衡子樹7，9，10即可，但是如果左旋轉(zhuǎn)后，就會(huì)初選如下圖（圖17）虛線框出來的部分，這不符合二叉排序樹的特性，此時(shí)就不能簡單的左旋。

仔細(xì)觀察圖17，發(fā)現(xiàn)根本原因在于結(jié)點(diǎn)7的BF是-2，而結(jié)點(diǎn)10的BF是1，也就是說，它們符號(hào)不統(tǒng)一，而前面的幾次旋轉(zhuǎn)，無論是左旋還是右旋，最小不平衡子樹的根結(jié)點(diǎn)與子節(jié)點(diǎn)的符號(hào)都是相同的。這就是不能直接旋轉(zhuǎn)的原因。

不統(tǒng)一的話就把它們的符號(hào)先轉(zhuǎn)統(tǒng)一，于是就如圖17所示，先將結(jié)點(diǎn)9和結(jié)點(diǎn)10進(jìn)行右旋，使結(jié)點(diǎn)10成為結(jié)點(diǎn)9的右子樹，此時(shí)就與結(jié)點(diǎn)7的BF值符號(hào)統(tǒng)一了，如（圖18）所示。

然后再以結(jié)點(diǎn)7為最小不平衡子樹進(jìn)行左旋，得到如下圖（圖19）。

接著插入8，情況與剛才類似，結(jié)點(diǎn)6的BF值為-2，而它的右孩子9的BF是1，如（圖20），因此先以9為根結(jié)點(diǎn)，進(jìn)行右旋，得到（圖21）。

此時(shí)結(jié)點(diǎn)6和結(jié)點(diǎn)7的符號(hào)都是負(fù)，再以結(jié)點(diǎn)6為根結(jié)點(diǎn)左旋，最終得到最后的平衡二叉樹，如下圖（圖22）所示。

根據(jù)以上的講述，我們構(gòu)建二叉排序樹的過程中，每當(dāng)插入一個(gè)節(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。

在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各個(gè)節(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行對(duì)應(yīng)的旋轉(zhuǎn)，尤其注意當(dāng)最小不平衡子樹的BF值與它的子樹的BF值符號(hào)相反時(shí)，就需要對(duì)結(jié)點(diǎn)先進(jìn)行一次旋轉(zhuǎn)使符號(hào)相同后，再反向旋轉(zhuǎn)才能夠完成平衡操作，使之成為新的平衡子樹。

下一章將繼續(xù)跟大家分享平衡二叉樹實(shí)現(xiàn)算法。

文章參考《大話數(shù)據(jù)結(jié)構(gòu)》