這個樹，怎麼一下就平衡了？
什麼是 AVL 樹
對於樹這種數據結構，想必大家也已經不再陌生，我們簡單回顧一下。
在樹的種類中，通常分成二叉樹和多叉樹，我們熟悉的二叉樹種類有二叉搜索 (排序、查找) 樹、二叉平衡樹、伸展樹、紅黑樹等等。而熟悉的多叉樹像 B 樹、字典樹都是經典多叉樹。
但二叉搜索 (排序樹) 有個很大的問題就是當插入節點很有序，很可能成爲一棵斜樹或者深度很高，那麼這樣的一個查找效率還是趨近於線性 O(n)級別，所以這種情況二叉搜索 (排序) 樹的效率是比較低的。
所以，人們有個期望：對一棵樹來說插入節點，小的還在左面，大的還在右面方便查找，但是能不能不要出現那麼斜的情況？
這不，平衡二叉搜索 (AVL) 樹就是這麼幹的，AVL 在插入的時候每次都會旋轉自平衡，讓整個樹一直處於平衡狀態，讓整個樹的查詢更加穩定(logN)。我們首先來看一下什麼是 AVL 樹：
-
AVL 樹是帶有平衡條件的二叉搜索樹，這個平衡條件必須要容易保持，而且要保證它的深度是 O(logN)。
-
AVL 的左右子樹的高度差（平衡因子）不大於 1，並且它的每個子樹也都是平衡二叉樹。
-
對於平衡二叉樹的最小個數，
n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以類比斐波那契)
難點：AVL 是一顆二叉排序樹，用什麼樣的規則或者規律讓它能夠在複雜度不太高的情況下實現動態平衡呢？
不平衡情況
如果從簡單情況模型看，其實四種不平衡情況很簡單，分別是 RR,LL,RL,LR 四種不平衡情況。
然後將其平衡的結果也很容易 (不考慮其附帶節點只看結果)，將中間大小數值移動最上方，其他相對位置不變即可：
當然，這個僅僅是針對三個節點情況太過於理想化了，很多時候讓你找不平衡的點，或者我們在解決不平衡的時候，我們需要的就是找到第一個不平衡 (從底往上) 的點將其平衡即可，下面列舉兩個不平衡的例子：
上述四種不平衡條件情況，可能出現在底部，也可能出現在頭，也可能出現在某個中間節點導致不平衡， 而我們只需要研究其首次不平衡點，解決之後整棵樹即繼續平衡，在具體的處理上我們使用遞歸的方式解決問題。
四種不平衡情況處理
針對四種不平衡的情況，這裏對每種情況進行詳細的講解。
RR 平衡旋轉 (左單旋轉)
這裏的 RR 指的是節點模型的樣子，其含義是需要左單旋轉 (記憶時候需要注意一下 RR 不是右旋轉)！
出現這種情況的原因是節點的右側的右側較深這時候不平衡節點需要左旋，再細看過程。
-
在左旋的過程中，
root(oldroot)節點下沉，中間節點(newroot)上浮. 而其中中間節點(newroot)的右側依然不變。 -
它上浮左側所以需要指向
根節點(oldroot)(畢竟一棵樹)。但是這樣newroot原來左側節點H空缺。而我們需要仍然讓整個樹完整並且滿足二叉排序樹的規則。 -
而剛好本來 oldroot 右側指向 newroot 現在結構改變 oldroot 右側空缺，剛好這個位置滿足**在 oldroot 的右側，在 newroot 的左側，**所以我們將 H 插入在這個位置。
-
其中 H 可能爲
NULL，不過不影響操作！
其更詳細流程爲：
而左旋的代碼可以表示爲：
private node getRRbanlance(node oldroot) {//右右深，需要左旋
// TODO Auto-generated method stub
node newroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新計算
return newroot;
}LL 平衡旋轉 (右單旋轉)
而右旋和左旋相反，但是思路相同，根據上述進行替換即可！
代碼：
private node getLLbanlance(node oldroot) {//LL小，需要右旋轉
// TODO Auto-generated method stub
node newroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
return newroot;
}RL 平衡旋轉 (先右後左雙旋轉)
這個 RL 你可能有點懵圈，爲啥 RR 叫左旋，LL 叫右旋，這個 RL 怎麼就叫先右後左旋轉了？
別急別急，這個之所以先後後左，是因爲具體需要中間節點右旋一次，然後上面節點左旋一次才能平衡，具體可以下面慢慢看。
首先產生這種不平衡的條件原因是：ROOT 節點右側左側節點的深度高些，使得與左側的差大於 1，這個與我們前面看到的左旋右旋不同因爲旋轉一次無法達到平衡！
對於右左結構，中間 (R) 的最大，兩側 (ROOT,R.L) 的最小，但是下面 (R.L) 的比上面 (ROOT) 大 (R.L在ROOT右側) 所以如果平衡的話，那麼R.L應該在中間，而R應該在右側, 原來的ROOT在左側。
這個過程節點的變化浮動比較大，需要妥善處理各個子節點的移動使其滿足二叉排序樹的性質！
這種雙旋轉具體實現其實也不難，不要被外表唬住，這裏面雙旋轉我提供兩種解答方法。
思路 (標準答案)1：兩次旋轉 RR,LL
這個處理起來非常容易，因爲前面已經解決 RR(左旋),LL(右旋) 的問題，所以這裏面在上面基礎上可以直接解決，首先對 R 節點進行一次 LL 右旋，旋轉一次之後 R 在最右側，這就轉化成 RR 不平衡旋轉的問題了，所以這個時候以 ROOT 開始一次 RR 左旋即可完成平衡，具體流程可以參考下面這張圖。
思路 (個人方法)2：直接分析
根據初始和結果的狀態，然後分析各個節點變化順序 =，手動操作這些節點即可。其實不管你怎麼操作，只要能滿足最後結構一致就行啦！
首先根據ROOT,R,R.L三個節點變化，R.L肯定要在最頂層，左右分別指向 ROOT 和 R，那麼這其中R.left，ROOT.right發生變化 (原來分別是 R.L 和 R) 暫時爲空。而剛好根據左右大小關係可以補上R.L原來的孩子節點A，B。
代碼爲：(註釋部分爲方案 1)
private node getRLbanlance(node oldroot) {//右左深
// node newroot=oldroot.right.left;
// oldroot.right.left=newroot.right;
// newroot.right=oldroot.right;
// oldroot.right=newroot.left;
// newroot.left=oldroot;
// oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
// newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
// newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
oldroot.right =getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1;
return getRRbanlance(oldroot);
}LR 平衡旋轉 (先左後右雙旋轉)
這個情況和 RL 情況相似，採取相同操作即可。
根據上述 RL 修改即可
這部分代碼爲
private node getLRbanlance(node oldroot) {
oldroot.left =getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1;
return getLLbanlance(oldroot);
}代碼實現
首先對於節點多個height屬性。用於計算高度 (平衡因子)
插入是遞歸插入，遞歸是一個來回的過程，去的過程進行插入，**回的過程進行高度更新，和檢查是否平衡。**推薦不要寫全局遞歸計算高度，效率太低下，事實上高度變化只和插入和平衡有關，仔細考慮即不會有疏漏！
代碼寫的比較早，如有命名不規範的情況，還請勿噴，如果有疏漏還請指出！
import java.util.ArrayDeque;
import java.util.Queue;
public class AVLTree {
class node
{
int value;
node left;
node right;
int height;
public node() {
}
public node(int value)
{
this.value=value;
this.height=0;
}
public node(int value,node left,node right)
{
this.value=value;
this.left=left;this.right=right;
this.height=0;
}
}
node root;// 根
public AVLTree() {
this.root = null;
}
public boolean isContains(int x)// 是否存在
{
node current = root;
if (root == null) {
return false;
}
while (current.value != x && current != null) {
if (x < current.value) {
current = current.left;
}
if (x > current.value) {
current = current.right;
}
if (current == null) {
return false;
} // 在裏面判斷如果超直接返回
}
// 如果在這個位置判斷是否爲空會導致current.value不存在報錯
if (current.value == x) {
return true;
}
return false;
}
public int getHeight(node t)
{
if(t==null) {return -1;}//
return t.height;
//return 1+Math.max(getHeight(t.left), getHeight(t.right));這種效率太低
}
public void cengxu(node t) {//層序遍歷
Queue<node> q1 = new ArrayDeque<node>();
if (t == null)
return;
if (t != null) {
q1.add(t);
}
while (!q1.isEmpty()) {
node t1 = q1.poll();
if (t1.left != null)
q1.add(t1.left);
if (t1.right != null)
q1.add(t1.right);
System.out.print(t1.value + " ");
}
System.out.println();
}
public void zhongxu(node t)//中序遍歷 中序遍歷：左子樹---> 根結點 ---> 右子樹
{//爲了測試改成中後都行
if(t!=null)
{
zhongxu(t.left);
System.out.print(t.value+" ");//訪問完左節點訪問當前節點
zhongxu(t.right);
//System.out.print(t.value+" ");//訪問完左節點訪問當前節點
}
}
public void qianxu(node t)//前序遞歸 前序遍歷：根結點 ---> 左子樹 ---> 右子樹
{
if(t!=null) {
System.out.print(t.value+" ");//當前節點
qianxu(t.left );
qianxu(t.right);}
}
public void insert(int value) {
root=insert(value, root);
}
public node insert(int x,node t)//插入 t是root的引用
{
node a1=new node(x);
//if(root==null) {root=a1;return root;}
if(t==null) {return a1;}
//插入操作。遞歸實現
else if(t!=null)
{
if(x<t.value)
{ t.left=insert(x,t.left);}
else
{ t.right= insert(x,t.right);}
}
/*
* 更新當前節點的高度，因爲整個插入只有被插入的一方有影響，
* 所以遞歸會更新好最底層的，上層可直接調用
*/
t.height=Math.max(getHeight(t.left),getHeight(t.right))+1;//不要寫成遞歸， 遞歸效率低
return banlance(t);//因爲java對象傳參機制，需要克隆，不可直接t=xx 否則變換
}
private node banlance(node t) {
// TODO Auto-generated method stub
//if(t==null)return null;
int lefthigh=getHeight(t.left);
int righthigh=getHeight(t.right);
if(Math.abs(lefthigh-righthigh)<=1)//不需要平衡滴
{ return t;}
else if(lefthigh<righthigh)//右側大
{
if(getHeight(t.right.left)<getHeight(t.right.right))//RR需要左旋
{
return getRRbanlance(t);
}
else {
return getRLbanlance(t);
}
}
else {
if(getHeight(t.left.left)>getHeight(t.left.right))//ll 左左
{
return getLLbanlance(t);
}
else {
return getLRbanlance(t);
}
}
}
/*
* oldroot(平衡因子爲2,不平衡) ==> newroot
* / \ / \
* B newroot(平衡因子爲1) oldroot D
* / \ / \ \
* C D B C E
* \
* E
*/
private node getRRbanlance(node oldroot) {//右右深，需要左旋
// TODO Auto-generated method stub
node newroot=oldroot.right;
oldroot.right=newroot.left;
newroot.left=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新計算
return newroot;
}
/*
* 右旋同理
*/
private node getLLbanlance(node oldroot) {//LL小，需要右旋轉
// TODO Auto-generated method stub
node newroot=oldroot.left;
oldroot.left=newroot.right;
newroot.right=oldroot;
oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
return newroot;
}
private node getLRbanlance(node oldroot) {
oldroot.left =getRRbanlance(oldroot.left);
oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1;
return getLLbanlance(oldroot);
}
/* (不平衡出現在右左節點)
* oldroot ==> newroot
* / \ / \
* A B oldroot B
* / \ / \ / \
* newroot D A E F D
* / \
* E F
*/
private node getRLbanlance(node oldroot) {//右左深
// node newroot=oldroot.right.left;
// oldroot.right.left=newroot.right;
// newroot.right=oldroot.right;
// oldroot.right=newroot.left;
// newroot.left=oldroot;
// oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1;
// newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1;
// newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來的root的高度需要從新金酸
oldroot.right =getLLbanlance(oldroot.right);
oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1;
return getRRbanlance(oldroot);
}
}測試情況：
AVL 的理解需要時間，當然筆者的 AVL 自己寫的可能有些疏漏，如果有問題還請各位一起探討！
當然，除了插入，AVL 還有刪除等其他操作，(原理相似。刪除後平衡) 有興趣可以一起研究。
結語
原創不易，如果本文對你有幫助，還請動動小手，幫忙點個贊和在看，分享給好友或者朋友圈，謝謝啦！
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/jackutRD9YXTMl-wZQ8BeQ