Java源碼解析之平衡二叉樹
一、平衡二叉樹的定義
平衡二叉樹是一種二叉排序樹，其中每一個節點的左子樹和右子樹的高度差至多等於1 。它是一種高度平衡的二叉排序樹。意思是說，要麼它是一棵空樹，要麼它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1 。我們將二叉樹上結點的左子樹深度減去右子樹深度的值稱為平衡因子BF (Balance Factor)，那麼平衡二叉樹上所有結點的平衡因子隻可能是-1 、0 和1。
這裡舉個栗子：
仔細看圖中值為18的節點，18的節點的深度為2 。而它的右子樹的深度為0，其差值的絕對值大於1瞭，所以這不是一科平衡二叉樹。
二、平衡二叉樹的實現原理
平衡二叉樹構建的基本思想就是在構建二叉排序樹的過程中，每當插入一個節點時，先檢查是否因插入而破壞瞭樹的平衡性，如果是，則找出最小不平衡二叉樹。在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各節點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。最小不平衡子樹是指距離插入節點最近，且平衡因子的絕對值大於1的節點為根的子樹。
下面就讓我們通過一個栗子來看看平衡二叉樹是怎麼構建的呢
首先我們將{3, 2, 1, 4, 5, 6, 7, 10, 9, 8}這樣的數組構建成一個二叉排序樹，按照二叉排序樹的性質，我們將得到下圖這樣的樹：
從圖中可以看出，樹的高度達到瞭8，對於查找和插入效率肯定是不夠理想的。
接下裡我們來看看怎麼將這顆二叉排序樹一步步構建成平衡二叉樹的：
1.按數組順序將2和3插入，此時沒有什麼影響，3的平衡因子為1， 2的平衡因子為0，到這裡還沒什麼問題
2.此時我們再來插入1，根據二叉排序樹，1隻能是2的左子樹，然而此時3的平衡因子為2，已經不符合平衡二叉樹的規則，這個時候，這棵樹就是最小不平衡子樹
3.我們將其右旋：三個元素的平衡因子都為0，沒什麼毛病，我們繼續
4.在插入4，根據二叉排序樹的規則，4隻能放在3的右子樹，此時沒什麼大毛病，我們繼續
5.在插入元素5，同理，5隻能放在4的右子樹，此時元素2的平衡因子為2大於1，
6.將其左旋：沒什麼大毛病，我們繼續
7.在插入元素6，此時為最小不平衡子樹
8.再將其左旋，這裡具體怎麼左旋，就這麼想，就是在滿足二叉排序樹性質的同時，讓根節點左邊的深度增加，右子樹的深度減小，以達到滿足二叉平衡樹的性質。
接下來的過程大傢可以自行去嘗試做出來
三、最終結果
可以看到，最後樹的高度僅為4，比之前的8對比來說，效率就高瞭近一半。
平衡二叉樹的刪除操作與插入類似，這裡將不再介紹。大傢可以自己思考如何最高效地刪除元素，可以分葉結點、僅有一個子結點和有兩個子結點三種情況考慮，這裡還用到瞭遞歸的思想。
到此這篇關於Java源碼解析之平衡二叉樹的文章就介紹到這瞭,更多相關Java平衡二叉樹內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！