溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下Java如何實現平衡二叉樹，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
為了避免極端情況下二叉搜索樹退化為鏈表，影響查找效率，我們引入了平衡二叉樹，即讓樹的結構看起來盡量“均勻”，左右子樹的節點數和層級盡量一樣多。要想學習平衡二叉樹并且掌握它，必須要先掌握二叉排序樹，如果對二叉搜索樹還不太明白的，包括為什么二叉排序樹可能退化為鏈表，可以看看這篇文章：數據結構—二叉排序樹的原理以及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開始以下的子樹為最小不平衡子樹。
平衡二叉樹實現原理的核心就是：由于在插入、刪除節點以后，只有那些從插入點到根節點的路徑上的節點的平衡可能被改變，因為只有這些節點的子樹可能發生變化。因此，我們需要沿著這條路徑上行到根并更新平衡信息，嘗試找出最小不平衡樹。在保持二叉排序樹特性的前提下，調整最小不平衡子樹中根節點和子結點之間的關系，進行相應的旋轉（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個問題的通用解決辦法和單旋轉和雙旋轉的概念。
首先是添加前兩個元素“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和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的通解。
左-右雙旋之后，重新形成了平衡二叉樹：
實際上，左-右雙旋，分開旋轉的過程模型如下：
節點添加完畢，最終形成了一顆平衡二叉樹：
插入節點的不平衡的情況只有四種：
在節點X的左孩子節點的左子樹中插入元素，簡稱LL
在節點X的左孩子節點的右子樹中插入元素，簡稱LR
在節點X的右孩子節點的左子樹中插入元素，簡稱RL
在節點X的右孩子節點的右子樹中插入元素，簡稱RR
其中1采用單右旋、4采用單左旋即可解決問題。2和3比較復雜，2需要采用左-右雙旋、3需要采用右-左雙旋。
1和4、2和3是對稱的情況，現在綜合起來看，所謂的旋轉似乎也不那么復雜，并且我們已經求出了這幾種問題的通解，該通解對于節點的刪除是同樣適用的，不必再考慮各種特殊情況，非常方便，下面來看看具體的代碼實現！
首先節點對象還是需要一個數據域和兩個引用域，相比于二叉排序樹，還要多一個節點高度的字段，這樣方便計算平衡因子，并且提供返回節點高度的方法。 另外還需要一個比較器的引用，因為需要對元素進行排序，自然需要比較元素的大小，如果外部傳遞了比較器，那么就使用用戶指定的比較器進行比較，否則，數據類型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;
}
}平衡二叉樹就是一顆二叉排序樹，其查找方法可以復用二叉排序樹的查找方法，很簡單：
若根節點的關鍵字值等于查找的關鍵字，成功，返回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;
}
}很簡單，只需要遞歸的查看所有節點，判斷是否存在的節點的左右子節點高度差絕對值是否大于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);
}平衡二叉樹和二叉排序樹的最大區別就是在插入和刪除的時候了。我們已經討論過插入之后的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的數據結構和在實現原理中最終的結構是一致的。
很簡單，最左邊的節點一定是最小的，最右邊的節點一定是最大的。因此查找最小的節點只需要向左遞歸查找，查找最大的節點只需要向右遞歸查找。
/**
* 查找最小的節點
*
* @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);
}平衡二叉樹節點的刪除同樣可能導致產生不平衡的狀態，因此同樣在二叉排序樹的刪除代碼的基礎上，刪除元素之后需要在刪除節點之上進行回溯直到根節點，嘗試找出最小不平衡樹來進行重平衡。其平衡的方法是和插入的時候是一樣的。
/**
* 刪除,開放給外部使用的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());在進行上面的一系列刪除之后，樹結構會變成如下形狀：
平衡二叉樹是基于二叉排序樹的，但是由于其必須保持平衡的特性，因此其編碼難度比二叉排序樹的編碼難度更高，不過如果我們搞懂了其旋轉的原理，那么實現起來還是比較簡單的。
如果我們需要查找的集合本身沒有順序，在頻繁查找的同時也需要經常的插入和刪除操作，顯然我們需要構建一棵二叉排序樹，但是不平衡的二叉排序樹，極端情況下可能退化為鏈表，查找效率是非常低的，因此我們需要在構建時，就讓這棵二叉排序樹是動態的轉換為平衡二叉樹，此時我們的查找時間復雜度就為O(logn)，而插入和刪除也為O(logn)。這顯然是比較理想的一種動態查找表算法。
以上是“Java如何實現平衡二叉樹”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
