這個樹，怎么一下就平衡了？
本文轉(zhuǎn)載自微信公眾號「bigsai」，作者bigsai。轉(zhuǎn)載本文請聯(lián)系bigsai公眾號。
什么是AVL樹
大家好，我是bigsai，好久不見，甚是想念,今天給大家講講AVL樹。
對于樹這種數(shù)據(jù)結(jié)構(gòu)，想必大家也已經(jīng)不再陌生，我們簡單回顧一下。
在樹的種類中，通常分成二叉樹和多叉樹，我們熟悉的二叉樹種類有二叉搜索(排序、查找)樹、二叉平衡樹、伸展樹、紅黑樹等等。而熟悉的多叉樹像B樹、字典樹都是經(jīng)典多叉樹。
普通的二叉樹，我們研究其遍歷方式，因為其沒啥規(guī)則約束查找和插入都很隨意所以很少有研究價值。
但是二叉樹結(jié)構(gòu)上很有特點：左孩子和右孩子，兩個不同方向的孩子對應(yīng)二進制的01，判斷的對錯，比較的大小 ，所以根據(jù)這個結(jié)構(gòu)所有樹左側(cè)節(jié)點比父節(jié)點小，右側(cè)節(jié)點比父節(jié)點大，這時候就誕生了二叉搜索(排序)樹。二叉搜索(排序)樹的一大特點就是查找效率提高了，因為查找一個元素位置或者查看元素是否存在通過每遇到一個節(jié)點直接進行比較就可以一步步逼近結(jié)果的位置。
但二叉搜索(排序樹)有個很大的問題就是當(dāng)插入節(jié)點很有序，很可能成為一棵斜樹或者深度很高，那么這樣的一個查找效率還是趨近于線性O(shè)(n)級別，所以這種情況二叉搜索(排序)樹的效率是比較低的。
所以，人們有個期望：對一棵樹來說插入節(jié)點，小的還在左面，大的還在右面方便查找，但是能不能不要出現(xiàn)那么斜的情況?
這不，平衡二叉搜索(AVL)樹就是這么干的，AVL在插入的時候每次都會旋轉(zhuǎn)自平衡，讓整個樹一直處于平衡狀態(tài)，讓整個樹的查詢更加穩(wěn)定(logN)。我們首先來看一下什么是AVL樹：
- AVL樹是帶有平衡條件的二叉搜索樹，這個平衡條件必須要容易保持，而且要保證它的深度是O(logN)。
- AVL的左右子樹的高度差(平衡因子)不大于1，并且它的每個子樹也都是平衡二叉樹。
- 對于平衡二叉樹的最小個數(shù)，n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以類比斐波那契)
難點：AVL是一顆二叉排序樹，用什么樣的規(guī)則或者規(guī)律讓它能夠在復(fù)雜度不太高的情況下實現(xiàn)動態(tài)平衡呢?
不平衡情況
如果從簡單情況模型看，其實四種不平衡情況很簡單，分別是RR,LL,RL,LR四種不平衡情況。
然后將其平衡的結(jié)果也很容易(不考慮其附帶節(jié)點只看結(jié)果)，將中間大小數(shù)值移動最上方，其他相對位置不變即可：
當(dāng)然，這個僅僅是針對三個節(jié)點情況太過于理想化了，很多時候讓你找不平衡的點，或者我們在解決不平衡的時候，我們需要的就是找到第一個不平衡(從底往上)的點將其平衡即可，下面列舉兩個不平衡的例子：
上述四種不平衡條件情況，可能出現(xiàn)在底部，也可能出現(xiàn)在頭，也可能出現(xiàn)在某個中間節(jié)點導(dǎo)致不平衡， 而我們只需要研究其首次不平衡點，解決之后整棵樹即繼續(xù)平衡，在具體的處理上我們使用遞歸的方式解決問題。
四種不平衡情況處理
針對四種不平衡的情況，這里對每種情況進行詳細(xì)的講解。
RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))
這里的RR指的是節(jié)點模型的樣子，其含義是需要左單旋轉(zhuǎn)(記憶時候需要注意一下RR不是右旋轉(zhuǎn))!
出現(xiàn)這種情況的原因是節(jié)點的右側(cè)的右側(cè)較深這時候不平衡節(jié)點需要左旋，再細(xì)看過程。
- 在左旋的過程中，root(oldroot)節(jié)點下沉，中間節(jié)點(newroot)上浮.而其中中間節(jié)點(newroot)的右側(cè)依然不變。
- 它上浮左側(cè)所以需要指向根節(jié)點(oldroot)(畢竟一棵樹)。但是這樣newroot原來左側(cè)節(jié)點H空缺。而我們需要仍然讓整個樹完整并且滿足二叉排序樹的規(guī)則。
- 而剛好本來oldroot右側(cè)指向newroot現(xiàn)在結(jié)構(gòu)改變oldroot右側(cè)空缺，剛好這個位置滿足在oldroot的右側(cè)，在newroot的左側(cè)，所以我們將H插入在這個位置。
- 其中H可能為NULL，不過不影響操作!
其更詳細(xì)流程為：
而左旋的代碼可以表示為：
- 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平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))
而右旋和左旋相反，但是思路相同，根據(jù)上述進行替換即可!
代碼：
- private node getLLbanlance(node oldroot) {//LL小，需要右旋轉(zhuǎn)
- // 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平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))
這個RL你可能有點懵圈，為啥RR叫左旋，LL叫右旋，這個RL怎么就叫先右后左旋轉(zhuǎn)了?
別急別急，這個之所以先后后左，是因為具體需要中間節(jié)點右旋一次，然后上面節(jié)點左旋一次才能平衡，具體可以下面慢慢看。
首先產(chǎn)生這種不平衡的條件原因是：ROOT節(jié)點右側(cè)左側(cè)節(jié)點的深度高些，使得與左側(cè)的差大于1，這個與我們前面看到的左旋右旋不同因為旋轉(zhuǎn)一次無法達到平衡!
對于右左結(jié)構(gòu)，中間(R)的最大，兩側(cè)(ROOT,R.L)的最小，但是下面(R.L)的比上面(ROOT)大(R.L在ROOT右側(cè))所以如果平衡的話，那么R.L應(yīng)該在中間，而R應(yīng)該在右側(cè),原來的ROOT在左側(cè)。
這個過程節(jié)點的變化浮動比較大，需要妥善處理各個子節(jié)點的移動使其滿足二叉排序樹的性質(zhì)!
這種雙旋轉(zhuǎn)具體實現(xiàn)其實也不難，不要被外表唬住，這里面雙旋轉(zhuǎn)我提供兩種解答方法。
思路(標(biāo)準(zhǔn)答案)1：兩次旋轉(zhuǎn)RR,LL
這個處理起來非常容易，因為前面已經(jīng)解決RR(左旋),LL(右旋)的問題，所以這里面在上面基礎(chǔ)上可以直接解決，首先對R節(jié)點進行一次LL右旋，旋轉(zhuǎn)一次之后R在最右側(cè)，這就轉(zhuǎn)化成RR不平衡旋轉(zhuǎn)的問題了，所以這個時候以ROOT開始一次RR左旋即可完成平衡，具體流程可以參考下面這張圖。
思路(個人方法)2：直接分析
根據(jù)初始和結(jié)果的狀態(tài)，然后分析各個節(jié)點變化順序=，手動操作這些節(jié)點即可。其實不管你怎么操作，只要能滿足最后結(jié)構(gòu)一致就行啦!
首先根據(jù)ROOT,R,R.L三個節(jié)點變化，R.L肯定要在最頂層，左右分別指向ROOT和R，那么這其中R.left，ROOT.right發(fā)生變化(原來分別是R.L和R)暫時為空。而剛好根據(jù)左右大小關(guān)系可以補上R.L原來的孩子節(jié)點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平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))
這個情況和RL情況相似，采取相同操作即可。
根據(jù)上述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);
- }
代碼實現(xiàn)
首先對于節(jié)點多個height屬性。用于計算高度(平衡因子)
插入是遞歸插入，遞歸是一個來回的過程，去的過程進行插入，回的過程進行高度更新，和檢查是否平衡。推薦不要寫全局遞歸計算高度，效率太低下，事實上高度變化只和插入和平衡有關(guān)，仔細(xì)考慮即不會有疏漏!
代碼寫的比較早，如有命名不規(guī)范的情況，還請勿噴，如果有疏漏還請指出!
- 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;
- } // 在里面判斷如果超直接返回
- }
- // 如果在這個位置判斷是否為空會導(dǎo)致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)//中序遍歷 中序遍歷：左子樹---> 根結(jié)點 ---> 右子樹
- {//為了測試改成中后都行
- if(t!=null)
- {
- zhongxu(t.left);
- System.out.print(t.value+" ");//訪問完左節(jié)點訪問當(dāng)前節(jié)點
- zhongxu(t.right);
- //System.out.print(t.value+" ");//訪問完左節(jié)點訪問當(dāng)前節(jié)點
- }
- }
- public void qianxu(node t)//前序遞歸 前序遍歷：根結(jié)點 ---> 左子樹 ---> 右子樹
- {
- if(t!=null) {
- System.out.print(t.value+" ");//當(dāng)前節(jié)點
- 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;}
- //插入操作。遞歸實現(xiàn)
- else if(t!=null)
- {
- if(x<t.value)
- { t.left=insert(x,t.left);}
- else
- { t.right= insert(x,t.right);}
- }
- /*
- * 更新當(dāng)前節(jié)點的高度，因為整個插入只有被插入的一方有影響，
- * 所以遞歸會更新好最底層的，上層可直接調(diào)用
- */
- 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)//右側(cè)大
- {
- 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小，需要右旋轉(zhuǎn)
- // 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);
- }
- /* (不平衡出現(xiàn)在右左節(jié)點)
- * 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的理解需要時間，當(dāng)然筆者的AVL自己寫的可能有些疏漏，如果有問題還請各位一起探討!
當(dāng)然，除了插入，AVL還有刪除等其他操作，(原理相似。刪除后平衡)有興趣可以一起研究。
