什么是平衡二叉樹（中）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

文章參考《大話數(shù)據(jù)結構》