一、平衡二叉樹的定義

平衡二叉樹是一種二叉排序樹，其中每一個節(jié)點的左子樹和右子樹的高度差至多等于1 。它是一種高度平衡的二叉排序樹。意思是說，要么它是一棵空樹，要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1 。我們將二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF (Balance Factor)，那么平衡二叉樹上所有結點的平衡因子只可能是-1 、0 和1。

這里舉個栗子：

仔細看圖中值為18的節(jié)點，18的節(jié)點的深度為2 。而它的右子樹的深度為0，其差值的絕對值大于1了，所以這不是一科平衡二叉樹。

二、平衡二叉樹的實現(xiàn)原理

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

下面就讓我們通過一個栗子來看看平衡二叉樹是怎么構建的呢

首先我們將{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}這樣的數(shù)組構建成一個二叉排序樹，按照二叉排序樹的性質(zhì)，我們將得到下圖這樣的樹：

從圖中可以看出，樹的高度達到了8，對于查找和插入效率肯定是不夠理想的。
接下里我們來看看怎么將這顆二叉排序樹一步步構建成平衡二叉樹的：

1.按數(shù)組順序?qū)?和3插入，此時沒有什么影響，3的平衡因子為1， 2的平衡因子為0，到這里還沒什么問題

2.此時我們再來插入1，根據(jù)二叉排序樹，1只能是2的左子樹，然而此時3的平衡因子為2，已經(jīng)不符合平衡二叉樹的規(guī)則，這個時候，這棵樹就是最小不平衡子樹

3.我們將其右旋：三個元素的平衡因子都為0，沒什么毛病，我們繼續(xù)

4.在插入4，根據(jù)二叉排序樹的規(guī)則，4只能放在3的右子樹，此時沒什么大毛病，我們繼續(xù)

5.在插入元素5，同理，5只能放在4的右子樹，此時元素2的平衡因子為2大于1，

6.將其左旋：沒什么大毛病，我們繼續(xù)

7.在插入元素6，此時為最小不平衡子樹

8.再將其左旋，這里具體怎么左旋，就這么想，就是在滿足二叉排序樹性質(zhì)的同時，讓根節(jié)點左邊的深度增加，右子樹的深度減小，以達到滿足二叉平衡樹的性質(zhì)。

接下來的過程大家可以自行去嘗試做出來

三、最終結果

可以看到，最后樹的高度僅為4，比之前的8對比來說，效率就高了近一半。

平衡二叉樹的刪除操作與插入類似，這里將不再介紹。大家可以自己思考如何最高效地刪除元素，可以分葉結點、僅有一個子結點和有兩個子結點三種情況考慮，這里還用到了遞歸的思想。

到此這篇關于Java源碼解析之平衡二叉樹的文章就介紹到這了,更多相關Java平衡二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論