什么是平衡二叉樹（中）

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

同學們可以點擊這里回顧之前的知識http://www.szjyscs.com/?mod=news_detail&id=94

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

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

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

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

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

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

然后我們再增加結(jié)點4，如圖9，平衡因子沒有超出限定范圍（-1，0，1）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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