Java數據結構之平衡二叉樹的原理與實現
平衡二叉樹(AVL樹)，顧名思義，是一顆很“平衡”的樹，它的平衡是相對於排序二叉樹來說的。為瞭避免極端情況下二叉搜索樹節點分佈不均勻，甚至退化為鏈表，影響查找效率，我們引入瞭平衡二叉樹，即讓樹的結構看起來盡量“均勻”，左右子樹的節點數和層級盡量一樣多。
本文詳細介紹瞭平衡二叉樹的概念和實現原理，並且提供瞭Java代碼的完全實現。
1 平衡二叉樹的概述
為瞭避免極端情況下二叉搜索樹退化為鏈表，影響查找效率，我們引入瞭平衡二叉樹，即讓樹的結構看起來盡量“均勻”，左右子樹的節點數和層級盡量一樣多。要想學習平衡二叉樹並且掌握它，必須要先掌握二叉排序樹，如果對二叉搜索樹還不太明白的，包括為什麼二叉排序樹可能退化為鏈表，可以看看這篇文章：數據結構—二叉排序樹的原理以及Java代碼的完全實現。
平衡二叉樹，又稱AVL樹，指的是左子樹上的所有節點的值都比根節點的值小，而右子樹上的所有節點的值都比根節點的值大，且左子樹與右子樹的高度差最大為1。因此，平衡二叉樹滿足所有二叉排序（搜索）樹的性質，是在二叉排序樹的基礎上發展而來的。至於AVL，則是取自兩個發明平衡二叉樹的俄羅斯科學傢的名字：G. M. Adelson-Velsky和E. M. Landis。
總的來說平衡二叉樹具有如下性質：
- 它一定是一棵二叉排序樹；
- 它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹，遞歸定義。
平衡因子BF（Balance Factor）： 我們將二叉樹上節點的左子樹深度減去右子樹深度的值稱為平衡因子，那麼平衡二叉樹上所有節點的平衡因子隻可能是-1、0和1。隻要二叉樹上有一個節點的平衡因子的絕對值大於1，則該二叉樹就是不平衡的。
上圖中，圖一是平衡二叉樹，圖二的59比58大，卻是58的左子樹，這是不符合二叉排序樹的定義的，圖二不是平衡二叉樹。圖3不是平衡二叉樹的原因就在於，節點58的左子樹高度為3，而右子樹為空，二者差大於瞭絕對值1，因此它也不是平衡的。而經過適當的調整後的圖4，它就符合瞭定義，因此它是平衡二叉樹。
最小不平衡子樹： 距離插入、刪除節點最近的，且平衡因子的絕對值大於1的節點為根的子樹，我們稱為最小不平衡子樹。下圖中當新插入節點37時，距離它最近的平衡因子絕對值超過1的節點是58（即它的左子樹高度3減去右子樹高度1），所以從58開始以下的子樹為最小不平衡子樹。
2 平衡二叉樹的實現原理
平衡二叉樹實現原理的核心就是：由於在插入、刪除節點以後，隻有那些從插入點到根節點的路徑上的節點的平衡可能被改變，因為隻有這些節點的子樹可能發生變化。因此，我們需要沿著這條路徑上行到根並更新平衡信息，嘗試找出最小不平衡樹。在保持二叉排序樹特性的前提下，調整最小不平衡子樹中根節點和子結點之間的關系，進行相應的旋轉（rotation），使之成為新的平衡子樹。
先來看看插入的重平衡，因為到後面我們會發現插入和刪除進行的重平衡操作基本是一致的。
我們把需要進行平衡（平衡因子絕對值大於1）的節點稱為x，由於任意節點最多有兩個兒子，因此出現高度不平衡就需要x點的兩棵子樹的高度差2，而這種不平衡隻可能出現在下面四種情況中：
- 在節點X的左孩子節點的左子樹中插入元素，簡稱LL
- 在節點X的左孩子節點的右子樹中插入元素，簡稱LR
- 在節點X的右孩子節點的左子樹中插入元素，簡稱RL
- 在節點X的右孩子節點的右子樹中插入元素，簡稱RR
其中第1種情況和第4種情況是對稱的，被稱為發生“外邊”的情況，可以通過單旋轉來解決，而第2種情況和第3種情況是對稱的，被稱為發生在“內邊”的情況，需要雙旋轉來解決。
案例：對數組中的元素{3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9}順序插入並建立一個平衡二叉樹。以這個案例為例，來講解上面4個問題的通用解決辦法和單旋轉和雙旋轉的概念。
2.1 單旋轉
首先是添加前兩個元素“3、2”的時候，可以正常的構建平衡二叉樹，到瞭第3個數“1”時，發現此時根節點“3”的平衡因子變成瞭2，此時整棵樹都成瞭最小不平衡子樹，因此需要調整結構。
上圖中的情況情況符合條件1——LL，因此所采用單旋轉來重平衡。此時，我們需要右旋（順時針旋轉）。旋轉的目的實際上就是為瞭降低深度，保持平衡。
節點3經過右旋後，節點2變成瞭根節點，節點3變成瞭2的右子樹，此時樹節點1的深度降低瞭一級，整顆樹重新回到瞭平衡。我們把通過一次旋轉即可修復平衡的操作叫做單旋轉。
平衡因子BF絕對值大於1的節點X稱為失衡點，修復一棵被破壞的AVL樹時，找到失衡點是很重要的，查找失衡點就是從新插入、刪除的節點的位置向上回溯至根節點的過程。
然後我們再增加節點4，平衡因子沒有超出限定范圍。增加節點5時，節點3的BF值為-2，說明又要旋轉瞭。
上圖中的情況情況符合條件4——RR，需要采用單旋轉來重平衡。此時，我們需要左旋（逆時針旋轉）。
左旋之後，如上圖右，樹的深度降低瞭一級，此時整棵樹又達到瞭平衡狀態。繼續，增加節點6時，發現根節點2的BF值變成瞭-2，所以我們對根節點進行瞭左旋。
左旋的結果使得節點2成為節點4的左孩子，原本處於2和4之間的節點3是4的左子樹，由於旋轉後需要滿足二叉排序樹特性，因此它成瞭節點2的右子樹，因為該子樹的每一個關鍵字都在2-4之間，因此這個變換是成立的。
現在我們來嘗試總結出發生情況1和4時的通用解法。
首先，情況1和4可以提煉出一個通用模型：
模型中，左邊如果要發生不平衡的情況1，那麼左子樹1的深度肯定比右子樹1的深度深2層；右邊如果要發生不平衡的情況4，那麼左子樹1的深度肯定比右子樹1的深度淺2層。
針對上面情況1和情況4，我們分別使用右旋和左旋，來降低或者升高這兩顆子樹的深度：
如上圖，情況1右旋之後，k2成為根節點，k1成為k2的右子節點，k2的右子樹2成為k1的左子樹；情況4左旋之後，k2成為根節點，k1成為k2的左子節點，k2的左子樹2成為k1的右子樹。樹重新達到瞭平衡狀態，這就是解決情況1和情況4的通解，並且我們可以發現它們是對稱的。
下面增加節點7，這導致節點5的BF變成瞭-2，且符合情況4，需要左旋，根據上面的通解，采用下面的左旋方法讓樹重新成為平衡二叉樹：
2.2 雙旋轉
上面的單旋轉對於情況2和3是沒有用的，因為此時樹結構太深，單旋轉並不會減低它的深度。此時需要使用雙旋轉。
當增加節點16時，結構無變化，再增加節點15，此時節點7的BF變成瞭-2。此時符合情況3：在節點X的右孩子節點的左子樹中插入元素，簡稱RL。如下圖：
此時簡單的左旋無法解決問題：節點15成瞭16的右孩子，這是不符合二叉排序樹的特性的，此時不能簡單的左旋。如下圖：
對於這種情況，我們對於關鍵節點7、16、15先建立一個更廣泛的模型：
其中7-k1、16-k2、15-k3，並且節點7完全還可以擁有左子樹，節點16可以擁有右子樹，而節點15則可以擁有左右子樹。
要想發生上面k1的BF為-2的情況，需要左子樹2或右子樹2其中一顆子樹的深度比左子樹1深兩層，或者他們都是空子樹，但是我們不知道是具體是什麼情況，不過這沒關系，在這裡我們要求出一個對這個問題通解！
此時為瞭平衡高度，我們不能將k1當作根節點瞭，但是左旋——把k2當作根節點也不能解決問題（上面已經證實瞭），唯一的選擇就是：將k3當作新的根節點，並且先使得k2右旋成為k3的右子樹，然後k1左旋成為k3的左子樹，並且左子樹2成為k1的右子樹，右子樹2成為k2的左子樹，這是完全成立的，這就是情況3的通解。 最終，右-左雙旋結果如下：
我們可以看到，無論是具體發生瞭什麼情況（左子樹2或右子樹2其中一顆子樹的深度比左子樹1深兩層，或者他們都是空子樹)，左-右雙旋轉換為上右圖的形狀之後，左子樹2或右子樹2都會被削減一層深度，而左子樹1會被增加一層深度，這棵樹始終都是一顆平衡二叉樹。
實際上，右-左雙旋，分開旋轉的過程模型如下：
回到案例，案例中左子樹2、右子樹2、左子樹1、右子樹1都是空樹，使用右-左雙旋之後，樹結構如下圖，該樹得以重新平衡：
接著插入14，情況與剛才類似，節點6的BF是-2，此時符合RL的情況（在節點6的右孩子節點15的左子樹7中插入元素），如下圖左，此時繼續右-左雙旋後，整棵樹又回到瞭平衡狀態，如下圖右：
繼續插入13，此時根節點4的BF變成瞭-2，符合情況4，此時使用一次單左旋即可解決問題：
繼續插入12之後，向上回溯到節點14時，發現節點14的BF為2，此時符合情況1，需要右旋恢復平衡：
繼續插入11之後，向上回溯到節點15時，發現節點15的BF為2，此時符合情況1，需要右旋恢復平衡：
繼續插入10之後，向上回溯到節點12時，發現節點12的BF為2，此時符合情況1，需要右旋恢復平衡：
插入8之後，向上回溯到根節點也沒有發現最小不平衡樹，因此不需要旋轉。最後插入9之後，我們發現出現瞭情況2，此時我們有情況1和情況4對稱的經驗，自然也知道需要右-左雙旋的的對稱操作——左-右雙旋來重新平衡。
先來看左-右雙旋模型：
它和右-左雙旋模型就是對稱操作，將k3當作新的根節點，並且先使得k2左旋成為k3的左子樹，然後k1右旋成為k3的右子樹，並且左子樹2成為k2的右子樹，右子樹2成為k1的左子樹，這是完全成立的，這就是情況2的通解。
左-右雙旋之後，重新形成瞭平衡二叉樹：
實際上，左-右雙旋，分開旋轉的過程模型如下：
節點添加完畢，最終形成瞭一顆平衡二叉樹：
2.3 總結
插入節點的不平衡的情況隻有四種：
- 在節點X的左孩子節點的左子樹中插入元素，簡稱LL
- 在節點X的左孩子節點的右子樹中插入元素，簡稱LR
- 在節點X的右孩子節點的左子樹中插入元素，簡稱RL
- 在節點X的右孩子節點的右子樹中插入元素，簡稱RR
其中1采用單右旋、4采用單左旋即可解決問題。2和3比較復雜，2需要采用左-右雙旋、3需要采用右-左雙旋。
1和4、2和3是對稱的情況，現在綜合起來看，所謂的旋轉似乎也不那麼復雜，並且我們已經求出瞭這幾種問題的通解，該通解對於節點的刪除是同樣適用的，不必再考慮各種特殊情況，非常方便，下面來看看具體的代碼實現！
3 平衡二叉樹的構建
3.1 類架構
首先節點對象還是需要一個數據域和兩個引用域，相比於二叉排序樹，還要多一個節點高度的字段，這樣方便計算平衡因子，並且提供返回節點高度的方法。 另外還需要一個比較器的引用，因為需要對元素進行排序，自然需要比較元素的大小，如果外部傳遞瞭比較器，那麼就使用用戶指定的比較器進行比較，否則，數據類型E必須是Comparable接口的子類，否則因為不能比較而報錯。
另外，還需要提供中序遍歷的方法，該遍歷方法對於二叉排序樹的結果將會順序展示。
public class AvlTree<E> {
/**
* 外部保存根節點的引用
*/
private BinaryTreeNode<E> root;
/**
* 自定義比較器
*/
private Comparator<? super E> cmp;
/**
* 樹節點的數量
*/
private int size;
/**
* 內部節點對象
*
* @param <E> 數據類型
*/
public static class BinaryTreeNode<E> {
//數據域
E data;
//左子節點
BinaryTreeNode<E> left;
//右子節點
BinaryTreeNode<E> right;
//節點高度 從0開始,從下往上;null節點高度返回-1
int height;
public BinaryTreeNode(E data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
/**
* 指定比較器
*
* @param cmp 比較器
*/
public AvlTree(Comparator<? super E> cmp) {
this.cmp = cmp;
}
/**
* 空構造器
*/
public AvlTree() {
}
/**
* 是否是空樹
*
* @return true 是 ;false 否
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 返回節點數
*
* @return 節點數
*/
public int size() {
return size;
}
/**
* 對元素進行比較大小的方法,如果傳遞瞭自定義比較器,則使用自定義比較器,否則則需要數據類型實現Comparable接口
*
* @param e1 被比較的第一個對象
* @param e2 被比較的第二個對象
* @return 0 相等 ;小於0 e1 < e2 ;大於0 e1 > e2
*/
private int compare(E e1, E e2) {
if (cmp != null) {
return cmp.compare(e1, e2);
} else {
return ((Comparable<E>) e1).compareTo(e2);
}
}
/**
* 保存遍歷出來的節點數據
*/
List<BinaryTreeNode<E>> str = new ArrayList<>();
/**
* 中序遍歷,提供給外部使用的api
*
* @return 遍歷的數據
*/
public String toInorderTraversalString() {
//如果是空樹,直接返回空
if (isEmpty()) {
return null;
}
//從根節點開始遞歸
inorderTraversal(root);
//獲取遍歷結果
String s = str.toString();
str.clear();
return s;
}
/**
* 中序遍歷 內部使用的遞歸遍歷方法,借用瞭棧的結構
*
* @param root 節點,從根節點開始
*/
private void inorderTraversal(BinaryTreeNode<E> root) {
BinaryTreeNode<E> left = getLeft(root);
if (left != null) {
//如果左子節點不為null,則繼續遞歸遍歷該左子節點
inorderTraversal(left);
}
//添加數據節點
str.add(root);
//獲取節點的右子節點
BinaryTreeNode<E> right = getRight(root);
if (right != null) {
//如果右子節點不為null,則繼續遞歸遍歷該右子節點
inorderTraversal(right);
}
}
/**
* 獲取左子節點
*
* @param parent 父節點引用
* @return 左子節點或者null--表示沒有左子節點
*/
public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.left;
}
/**
* 獲取右子節點
*
* @param parent 父節點引用
* @return 右子節點或者null--表示沒有右子節點
*/
public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.right;
}
/**
* 獲取根節點
*
* @return 根節點 ;或者null--表示空樹
*/
public BinaryTreeNode<E> getRoot() {
return root;
}
/**
* 獲取height
*
* @param node 節點
* @return 高度或者-1 表示節點為null
*/
private int getHeight(BinaryTreeNode<E> node) {
return node == null ? -1 : node.height;
}
}
3.2 查找的方法
平衡二叉樹就是一顆二叉排序樹，其查找方法可以復用二叉排序樹的查找方法，很簡單：
- 若根節點的關鍵字值等於查找的關鍵字，成功，返回true；
- 否則，若小於根節點的關鍵字值，遞歸查左子樹；
- 若大於根節點的關鍵字值，遞歸查右子樹；
- 最終查找到葉子節點還是沒有數據，那麼查找失敗，則返回false
/**
* 查找,開放給外部使用的api
* @param e 要查找的元素
* @return false 不存在 true 存在
*/
public boolean contains(E e) {
return contains(e, root);
}
/**
* 查找,內部調用的方法,從根節點開始查找
*
* @param e 要查找的元素
* @param root 節點
* @return false 不存在 true 存在
*/
private boolean contains(E e, BinaryTreeNode<E> root) {
/*null校驗*/
if (root == null) {
return false;
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
return contains(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
return contains(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即查詢成功*/
return true;
}
}
3.3 檢查是否平衡的方法
很簡單，隻需要遞歸的查看所有節點，判斷是否存在的節點的左右子節點高度差絕對值是否大於1的情況就能判斷瞭，如果存在，那麼返回false表示不是平衡二叉樹，不存在就返回true表示是平衡二叉樹。
/**
* 保存是否平衡的標志
*/
private boolean balance = true;
/**
* 檢查是否是平衡二叉樹的方法,當然也可以debug看,如果你不嫌麻煩……
*
* @return true 是 ；false 否
*/
public boolean checkBalance() {
checkBalance(root);
boolean balanceNow=balance;
balance=true;
return balanceNow;
}
/**
* 遞歸檢查是否平衡,實際上這裡采用瞭後序遍歷,即左子節點-右子節點-根節點的方法遞歸遍歷檢查
*
* @param root 根節點
* @return 節點的高度
*/
private int checkBalance(BinaryTreeNode<E> root) {
if (root == null) {
return -1;
}
//返回左子樹的高度
int hl = checkBalance(root.left);
//返回右子樹的高度
int hr = checkBalance(root.right);
//如果root的左右子樹高度差絕對值大於1,或者checkBalance和getHeight方法獲取的左/右子樹高度不一致,那麼算作不平衡
if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1 ||
getHeight(root.left) != hl || getHeight(root.right) != hr) {
balance = false;
}
return getHeight(root);
}
3.4 插入的方法
平衡二叉樹和二叉排序樹的最大區別就是在插入和刪除的時候瞭。我們已經討論過插入之後的4種出現平衡問題的特殊情況，這裡不再贅述，下面看代碼具體如何實現：
/**
* 插入,開放給外部使用的api
*
* @param e 要插入的元素
*/
public void insert(E e) {
//返回root,但此時新的節點可能已經被插入進去瞭
root = insert(e, root);
}
/**
* 插入,開放給外部使用的api
*
* @param es 要插入的元素的數組,註意,數組元素的順序存儲的位置將會影響二叉排序樹的生成
*/
public void insert(E[] es) {
//返回root,但此時新的節點可能已經被插入進去瞭
for (E e : es) {
root = insert(e, root);
}
}
/**
* 插入,內部調用的方法,先從根節點開始遞歸查找要插入的位置,然後插入
* 大部分代碼都和排序二叉樹的相似，區別就是在插入之後，會調用嘗試重平衡的方法rebalance
*
* @param e 要插入的數據
* @param root 節點
* @return 原節點重平衡之後的節點或者新插入的節點
*/
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
/*沒有查找到,那麼直接構建新的節點返回,將會在上一層方法中被賦值給其父節點的某個引用,這個插入的位置肯定是該遍歷路徑上的最後一點
* 即插入的元素節點肯定是屬於葉子節點*/
if (root == null) {
size++;
return new BinaryTreeNode<>(e);
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
//重新賦值
root.right = insert(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
//重新賦值
root.left = insert(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即存在節點 什麼都不做*/
}
/*insert遞歸插入之後,在返回時,會調用重新平衡並且設置高度的方法 嘗試重平衡root根節點 而不是像排序二叉樹一樣簡單的返回root
*從新插入節點的父節點一直向上回溯直到根節點,嘗試尋找最小不平衡樹,找到之後會進行平衡,返回返回平衡之後的樹,.*/
return rebalance(root);
}
/**
* 重平衡的方法
* 1) 在節點X的左孩子節點的左子樹中插入元素，簡稱LL 右旋
* 2) 在節點X的左孩子節點的右子樹中插入元素，簡稱LR 左-右雙旋
* 3) 在節點X的右孩子節點的左子樹中插入元素，簡稱RL 左旋
* 4) 在節點X的右孩子節點的右子樹中插入元素，簡稱RR 右-左雙旋
*
* @param root 樹的根節點,無論是否是最小不平衡樹,都是走這個方法
* @return 平衡之後的樹的根節點
*/
private BinaryTreeNode<E> rebalance(BinaryTreeNode<E> root) {
/*1、如果節點為null,直接返回null*/
if (root == null) {
return null;
}
/*2、開始旋轉*/
/*2.1、如果左子樹的高度減去右子樹的高度值大於1,說明左子樹的高度大於右子樹的高度至少2層,可能是情況1、2 繼續判斷*/
if (getHeight(root.left) - getHeight(root.right) > 1) {
/*如果左子節點的左子節點高度大於左子節點的右子節點高度,那說明是情況1,否則是情況2*/
if (getHeight(root.left.left) >= getHeight(root.left.right)) {
/*2.1.1、右旋*/
root = rotateRight(root);
} else {
/*2.1.2、左-右雙旋*/
root = rotateLeftAndRight(root);
}
/*2.2、如果右子樹的高度減去左子樹的高度值大於1,說明右子樹的高度大於左子樹的高度至少2層,可能是情況3、4 繼續判斷*/
} else if (getHeight(root.right) - getHeight(root.left) > 1) {
/*如果右子節點的右子節點高度大於右子節點的左子節點高度,那說明是情況4,否則是情況3*/
if (getHeight(root.right.right) >= getHeight(root.right.left)) {
/*2.2.1、左旋*/
root = rotateLeft(root);
} else {
/*2.2.2、右-左雙旋*/
root = rotateRightAndLeft(root);
}
}
/*3、到這一步,說明旋轉完畢,或者不需要旋轉,但是都需要重新計算高度,高度為左/右子樹高度最大值+1*/
root.height = Math.max(getHeight(root.left), getHeight(root.right)) + 1;
return root;
}
/**
* 右旋
* 通解:右旋之後，k2成為根節點，k1成為k2的右子節點，k2的右子樹2成為k1的左子樹
*
* @param k1 需要旋轉的最小不平衡樹根節點
* @return k2 旋轉後的最小不平衡樹根節點, 已經轉換為平衡二叉樹
*/
private BinaryTreeNode<E> rotateRight(BinaryTreeNode<E> k1) {
//獲取k2,k2是k1的左子節點
BinaryTreeNode<E> k2 = k1.left;
//k2的右子樹成為k1的左子樹
k1.left = k2.right;
//k1成為k2的右子節點
k2.right = k1;
//k1的高度等於k1的左或者右子樹的高度的最大值+1;
k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
//k2的高度等於k2的左子節點和k1的高度(此時k1就是k2的右子節點)的最大值+1
k2.height = Math.max(getHeight(k2.left), k1.height) + 1;
//返回k2,k2成為根節點
return k2;
}
/**
* 左旋 很簡單,實際上就是右旋的鏡像
* 通解:左旋之後，k2成為根節點，k1成為k2的左子節點，k2的左子樹2成為k1的右子樹
*
* @param k1 需要旋轉的最小不平衡樹根節點
* @return k2 旋轉後的最小不平衡樹根節點, 已經轉換為平衡二叉樹
*/
private BinaryTreeNode<E> rotateLeft(BinaryTreeNode<E> k1) {
//獲取k2,k2是k1的右子節點
BinaryTreeNode<E> k2 = k1.right;
//k2的左子樹成為k1的右子樹
k1.right = k2.left;
//k1成為k2的左子節點
k2.left = k1;
//k1的高度等於k1的左或者右子樹的高度的最大值+1;
k1.height = Math.max(getHeight(k1.left), getHeight(k1.right)) + 1;
//k2的高度等於k2的右子節點和k1的高度(此時k1就是k2的左子節點)的最大值+1
k2.height = Math.max(getHeight(k2.right), k1.height) + 1;
//返回k2,k2成為根節點
return k2;
}
/**
* 右-左雙旋
* 通解：將k3當作新的根節點，並且先使得k2右旋成為k3的右子樹，然後k1左旋成為k3的左子樹，並且左子樹2成為k1的右子樹，右子樹2成為k2的左子樹
*
* @param k1 需要旋轉的最小不平衡樹根節點
* @return 旋轉後的最小不平衡樹根節點, 已經轉換為平衡二叉樹
*/
private BinaryTreeNode<E> rotateRightAndLeft(BinaryTreeNode<E> k1) {
/*1、先對k1的右子節點k2進行右旋,返回右旋之後的根節點k3,然後使得成為k3成為的k1的左子樹*/
k1.right = rotateRight(k1.right);
/*2、然後對k1進行左旋,成為k3的左子樹,返回的根節點就是k3,即返回旋轉之後的根節點*/
return rotateLeft(k1);
}
/**
* 左-右雙旋 很簡單,實際上就是右-左雙旋的鏡像
* 通解: 將k3當作新的根節點，並且先使得k2左旋成為k3的左子樹，然後k1右旋成為k3的右子樹，並且左子樹2成為k2的右子樹，右子樹2成為k1的左子樹
*
* @param k1 需要旋轉的最小不平衡樹根節點
* @return 旋轉後的最小不平衡樹根節點, 已經轉換為平衡二叉樹
*/
private BinaryTreeNode<E> rotateLeftAndRight(BinaryTreeNode<E> k1) {
/*1、先對k1的左子節點k2進行左旋,返回左旋之後的根節點k3,然後使得成為k3成為的k1的左子樹*/
k1.left = rotateLeft(k1.left);
/*2、然後對k1進行右旋,成為k3的右子樹,返回的根節點就是k3,即返回旋轉之後的根節點*/
return rotateRight(k1);
}
3.4.1 測試
AvlTree<Integer> avlTree = new AvlTree<>();
Integer[] es = new Integer[]{3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
//批量插入
avlTree.insert(es);
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//數量
System.out.println(avlTree.size());
在insert之後打上斷點，Debug，可以看到avlTree的數據結構和在實現原理中最終的結構是一致的。
3.5 查找最大值和最小值
很簡單，最左邊的節點一定是最小的，最右邊的節點一定是最大的。因此查找最小的節點隻需要向左遞歸查找，查找最大的節點隻需要向右遞歸查找。
/**
* 查找最小的節點
*
* @param root 根節點
* @return 最小的節點
*/
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
if (root == null) {
return null;
/*如果該節點沒有左右子節點，那麼該節點就是最小的節點，返回*/
} else if (root.left == null) {
return root;
}
/*如果該節點存在左子節點，那麼繼續向左遞歸查找*/
return findMin(root.left);
}
/**
* 查找最大的節點
*
* @param root 根節點
* @return 最大的節點
*/
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
if (root == null) {
return null;
/*如果該節點沒有右子節點，那麼該節點就是最大的節點，返回*/
} else if (root.right == null) {
return root;
}
/*如果該節點存在右子節點，那麼繼續向右遞歸查找*/
return findMax(root.right);
}
3.6 刪除的方法
平衡二叉樹節點的刪除同樣可能導致產生不平衡的狀態，因此同樣在二叉排序樹的刪除代碼的基礎上，刪除元素之後需要在刪除節點之上進行回溯直到根節點，嘗試找出最小不平衡樹來進行重平衡。其平衡的方法是和插入的時候是一樣的。
/**
* 刪除,開放給外部使用的api
*
* @param e 要刪除的元素
*/
public void delete(E e) {
//返回root,但此時可能有一個節點已經被刪除瞭
root = delete(e, root);
}
/**
* 刪除,內部調用的方法,刪除分為三種情況: 1、該節點沒有子節點 2、該字節僅有一個子節點 3、該節點具有兩個子節點
*
* @param e 要刪除的數據
* @param root (子)樹根節點
* @return 該根節點重平衡之後的節點
*/
private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
/*沒有查找到,那麼什麼都不做*/
if (root == null) {
return null;
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
//重新賦值
root.right = delete(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
//重新賦值
root.left = delete(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即查詢成功 開始執行刪除*/
/*如果兩個子節點都不為null*/
if (root.left != null && root.right != null) {
/*遞歸查找最小的節點，然後遞歸刪除*/
root.data = findMin(root.right).data;
root.right = delete(root.data, root.right);
} else {
/*如果一個子節點不為null，則返回該子節點；或者兩個子節點都為null，則返回null
* 此時該root節點已經被"繞過瞭"*/
root = (root.left != null) ? root.left : root.right;
--size;
}
}
/*和二叉排序樹直接返回節點不同的是,刪除操作完成之後將會調用該方法,從被刪除節點回溯至根節點,對節點進行重平衡,然後才返回平衡後的節點*/
return rebalance(root);
}
3.6.1 測試
針對上面插入的平衡二叉樹進行刪除：
System.out.println("======>首先刪除5 此時沒有影響,不需要重平衡");
avlTree.delete(5);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
System.out.println("======>再次刪除6 此時節點4的BF為2 需要右旋重平衡");
avlTree.delete(6);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
System.out.println("======>再次刪除11 由於該節點擁有左右子樹,實際上刪除的是該節點的右子樹的最小節點12,然後將12的值賦值給11的節點,並導致節點12的原父節點11不平衡,需要重平衡");
avlTree.delete(11);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
System.out.println("======>再次刪除7 由於該節點擁有左右子樹,實際上刪除的是該節點的右子樹的最小節點8,然後將8的值賦值給7的節點,並導致節點8的原父節點9不平衡,需要重平衡");
avlTree.delete(7);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
System.out.println("======>再次刪除9、12 此時不需要重平衡");
avlTree.delete(9);
avlTree.delete(12);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.toInorderTraversalString());
System.out.println("======>最後刪除8 由於該節點擁有左右子樹,實際上刪除的是該節點的右子樹的最小節點10節點,然後將10的值賦值給8的節點,並導致節點10的原父節點13不平衡,需要重平衡");
avlTree.delete(8);
//檢查是否平衡
System.out.println(avlTree.checkBalance());
//中序遍歷輸出
System.out.println(avlTree.size());
System.out.println(avlTree.toInorderTraversalString());
在進行上面的一系列刪除之後，樹結構會變成如下形狀：
4 平衡二叉樹的總結
平衡二叉樹是基於二叉排序樹的，但是由於其必須保持平衡的特性，因此其編碼難度比二叉排序樹的編碼難度更高，不過如果我們搞懂瞭其旋轉的原理，那麼實現起來還是比較簡單的。
如果我們需要查找的集合本身沒有順序，在頻繁查找的同時也需要經常的插入和刪除操作，顯然我們需要構建一棵二叉排序樹，但是不平衡的二叉排序樹，極端情況下可能退化為鏈表，查找效率是非常低的，因此我們需要在構建時，就讓這棵二叉排序樹是動態的轉換為平衡二叉樹，此時我們的查找時間復雜度就為O(logn)，而插入和刪除也為O(logn)。這顯然是比較理想的一種動態查找表算法。
本文介紹瞭平衡二叉樹的原理以及Java代碼的完全實現，要想搞懂平衡二叉樹需要先搞懂二叉排序樹：二叉排序樹的詳解以及Java代碼的完全實現。而搞懂平衡二叉樹又是搞懂紅黑樹的基礎，後續文章我們將會介紹紅黑樹的概念以及Java代碼的完全實現！
以上就是Java數據結構之平衡二叉樹的原理與實現的詳細內容，更多關於Java平衡二叉樹的資料請關註WalkonNet其它相關文章！