一、平衡二叉樹的定義

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

這里舉個(gè)栗子：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

三、最終結(jié)果

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

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

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

最新評(píng)論