Java中平衡二叉樹的原理是什么

Java中平衡二叉樹的原理是什么？很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

一、平衡二叉樹的定義

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

這里舉個栗子：

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

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

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

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

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

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

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é)點左邊的深度增加，右子樹的深度減小，以達(dá)到滿足二叉平衡樹的性質(zhì)。

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

三、最終結(jié)果

Java是什么

Java是一門面向?qū)ο缶幊陶Z言，可以編寫桌面應(yīng)用程序、Web應(yīng)用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應(yīng)用程序。

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。