Java源碼解析之平衡二叉樹(shù)

目錄

一、平衡二叉樹(shù)的定義

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

這里舉個(gè)栗子：

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

二、平衡二叉樹(shù)的實(shí)現原理

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

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

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

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

1.按數組順序將2和3插入，此時(shí)沒(méi)有什么影響，3的平衡因子為1， 2的平衡因子為0，到這里還沒(méi)什么問(wèn)題

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

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

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

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

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

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

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

接下來(lái)的過(guò)程大家可以自行去嘗試做出來(lái)

三、最終結果

可以看到，最后樹(shù)的高度僅為4，比之前的8對比來(lái)說(shuō)，效率就高了近一半。

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

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