自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

這個(gè)樹，怎么一下就平衡了？

作者： bigsai
開發(fā) 前端
在樹的種類中，通常分成二叉樹和多叉樹，我們熟悉的二叉樹種類有二叉搜索(排序、查找)樹、二叉平衡樹、伸展樹、紅黑樹等等。而熟悉的多叉樹像B樹、字典樹都是經(jīng)典多叉樹。

[[427844]]

本文轉(zhuǎn)載自微信公眾號(hào)「bigsai」，作者bigsai。轉(zhuǎn)載本文請(qǐng)聯(lián)系bigsai公眾號(hào)。

什么是AVL樹

大家好，我是bigsai，好久不見，甚是想念,今天給大家講講AVL樹。

對(duì)于樹這種數(shù)據(jù)結(jié)構(gòu)，想必大家也已經(jīng)不再陌生，我們簡(jiǎn)單回顧一下。

在樹的種類中，通常分成二叉樹和多叉樹，我們熟悉的二叉樹種類有二叉搜索(排序、查找)樹、二叉平衡樹、伸展樹、紅黑樹等等。而熟悉的多叉樹像B樹、字典樹都是經(jīng)典多叉樹。

普通的二叉樹，我們研究其遍歷方式，因?yàn)槠錄]啥規(guī)則約束查找和插入都很隨意所以很少有研究?jī)r(jià)值。

但是二叉樹結(jié)構(gòu)上很有特點(diǎn)：左孩子和右孩子，兩個(gè)不同方向的孩子對(duì)應(yīng)二進(jìn)制的01，判斷的對(duì)錯(cuò)，比較的大小 ，所以根據(jù)這個(gè)結(jié)構(gòu)所有樹左側(cè)節(jié)點(diǎn)比父節(jié)點(diǎn)小，右側(cè)節(jié)點(diǎn)比父節(jié)點(diǎn)大，這時(shí)候就誕生了二叉搜索(排序)樹。二叉搜索(排序)樹的一大特點(diǎn)就是查找效率提高了，因?yàn)椴檎乙粋€(gè)元素位置或者查看元素是否存在通過每遇到一個(gè)節(jié)點(diǎn)直接進(jìn)行比較就可以一步步逼近結(jié)果的位置。

但二叉搜索(排序樹)有個(gè)很大的問題就是當(dāng)插入節(jié)點(diǎn)很有序，很可能成為一棵斜樹或者深度很高，那么這樣的一個(gè)查找效率還是趨近于線性O(shè)(n)級(jí)別，所以這種情況二叉搜索(排序)樹的效率是比較低的。

所以，人們有個(gè)期望：對(duì)一棵樹來(lái)說插入節(jié)點(diǎn)，小的還在左面，大的還在右面方便查找，但是能不能不要出現(xiàn)那么斜的情況?

這不，平衡二叉搜索(AVL)樹就是這么干的，AVL在插入的時(shí)候每次都會(huì)旋轉(zhuǎn)自平衡，讓整個(gè)樹一直處于平衡狀態(tài)，讓整個(gè)樹的查詢更加穩(wěn)定(logN)。我們首先來(lái)看一下什么是AVL樹：

  • AVL樹是帶有平衡條件的二叉搜索樹，這個(gè)平衡條件必須要容易保持，而且要保證它的深度是O(logN)。
  • AVL的左右子樹的高度差(平衡因子)不大于1，并且它的每個(gè)子樹也都是平衡二叉樹。
  • 對(duì)于平衡二叉樹的最小個(gè)數(shù)，n0=0;n1=1;nk=n(k-1)+n(k-2)+1;(求法可以類比斐波那契)

難點(diǎn)：AVL是一顆二叉排序樹，用什么樣的規(guī)則或者規(guī)律讓它能夠在復(fù)雜度不太高的情況下實(shí)現(xiàn)動(dòng)態(tài)平衡呢?

不平衡情況

如果從簡(jiǎn)單情況模型看，其實(shí)四種不平衡情況很簡(jiǎn)單，分別是RR,LL,RL,LR四種不平衡情況。

然后將其平衡的結(jié)果也很容易(不考慮其附帶節(jié)點(diǎn)只看結(jié)果)，將中間大小數(shù)值移動(dòng)最上方，其他相對(duì)位置不變即可：

當(dāng)然，這個(gè)僅僅是針對(duì)三個(gè)節(jié)點(diǎn)情況太過于理想化了，很多時(shí)候讓你找不平衡的點(diǎn)，或者我們?cè)诮鉀Q不平衡的時(shí)候，我們需要的就是找到第一個(gè)不平衡(從底往上)的點(diǎn)將其平衡即可，下面列舉兩個(gè)不平衡的例子：

上述四種不平衡條件情況，可能出現(xiàn)在底部，也可能出現(xiàn)在頭，也可能出現(xiàn)在某個(gè)中間節(jié)點(diǎn)導(dǎo)致不平衡， 而我們只需要研究其首次不平衡點(diǎn)，解決之后整棵樹即繼續(xù)平衡，在具體的處理上我們使用遞歸的方式解決問題。

四種不平衡情況處理

針對(duì)四種不平衡的情況，這里對(duì)每種情況進(jìn)行詳細(xì)的講解。

RR平衡旋轉(zhuǎn)(左單旋轉(zhuǎn))

這里的RR指的是節(jié)點(diǎn)模型的樣子，其含義是需要左單旋轉(zhuǎn)(記憶時(shí)候需要注意一下RR不是右旋轉(zhuǎn))!

出現(xiàn)這種情況的原因是節(jié)點(diǎn)的右側(cè)的右側(cè)較深這時(shí)候不平衡節(jié)點(diǎn)需要左旋，再細(xì)看過程。

  • 在左旋的過程中，root(oldroot)節(jié)點(diǎn)下沉，中間節(jié)點(diǎn)(newroot)上浮.而其中中間節(jié)點(diǎn)(newroot)的右側(cè)依然不變。
  • 它上浮左側(cè)所以需要指向根節(jié)點(diǎn)(oldroot)(畢竟一棵樹)。但是這樣newroot原來(lái)左側(cè)節(jié)點(diǎn)H空缺。而我們需要仍然讓整個(gè)樹完整并且滿足二叉排序樹的規(guī)則。
  • 而剛好本來(lái)oldroot右側(cè)指向newroot現(xiàn)在結(jié)構(gòu)改變oldroot右側(cè)空缺，剛好這個(gè)位置滿足在oldroot的右側(cè)，在newroot的左側(cè)，所以我們將H插入在這個(gè)位置。
  • 其中H可能為NULL，不過不影響操作!

其更詳細(xì)流程為：

而左旋的代碼可以表示為：

  1. private node getRRbanlance(node oldroot) {//右右深，需要左旋 
  2.     // TODO Auto-generated method stub 
  3.     node newroot=oldroot.right; 
  4.     oldroot.right=newroot.left; 
  5.     newroot.left=oldroot; 
  6.     oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  7.     newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新計(jì)算 
  8.     return newroot;      
  9. } 

LL平衡旋轉(zhuǎn)(右單旋轉(zhuǎn))

而右旋和左旋相反，但是思路相同，根據(jù)上述進(jìn)行替換即可!

代碼：

  1. private node getLLbanlance(node oldroot) {//LL小，需要右旋轉(zhuǎn) 
  2.     // TODO Auto-generated method stub 
  3.     node newroot=oldroot.left; 
  4.     oldroot.left=newroot.right; 
  5.     newroot.right=oldroot; 
  6.     oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  7.     newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新金酸   
  8.     return newroot;  
  9. } 

RL平衡旋轉(zhuǎn)(先右后左雙旋轉(zhuǎn))

這個(gè)RL你可能有點(diǎn)懵圈，為啥RR叫左旋，LL叫右旋，這個(gè)RL怎么就叫先右后左旋轉(zhuǎn)了?

別急別急，這個(gè)之所以先后后左，是因?yàn)榫唧w需要中間節(jié)點(diǎn)右旋一次，然后上面節(jié)點(diǎn)左旋一次才能平衡，具體可以下面慢慢看。

首先產(chǎn)生這種不平衡的條件原因是：ROOT節(jié)點(diǎn)右側(cè)左側(cè)節(jié)點(diǎn)的深度高些，使得與左側(cè)的差大于1，這個(gè)與我們前面看到的左旋右旋不同因?yàn)樾D(zhuǎn)一次無(wú)法達(dá)到平衡!

對(duì)于右左結(jié)構(gòu)，中間(R)的最大，兩側(cè)(ROOT,R.L)的最小，但是下面(R.L)的比上面(ROOT)大(R.L在ROOT右側(cè))所以如果平衡的話，那么R.L應(yīng)該在中間，而R應(yīng)該在右側(cè),原來(lái)的ROOT在左側(cè)。

這個(gè)過程節(jié)點(diǎn)的變化浮動(dòng)比較大，需要妥善處理各個(gè)子節(jié)點(diǎn)的移動(dòng)使其滿足二叉排序樹的性質(zhì)!

這種雙旋轉(zhuǎn)具體實(shí)現(xiàn)其實(shí)也不難，不要被外表唬住，這里面雙旋轉(zhuǎn)我提供兩種解答方法。

思路(標(biāo)準(zhǔn)答案)1：兩次旋轉(zhuǎn)RR,LL

這個(gè)處理起來(lái)非常容易，因?yàn)榍懊嬉呀?jīng)解決RR(左旋),LL(右旋)的問題，所以這里面在上面基礎(chǔ)上可以直接解決，首先對(duì)R節(jié)點(diǎn)進(jìn)行一次LL右旋，旋轉(zhuǎn)一次之后R在最右側(cè)，這就轉(zhuǎn)化成RR不平衡旋轉(zhuǎn)的問題了，所以這個(gè)時(shí)候以ROOT開始一次RR左旋即可完成平衡，具體流程可以參考下面這張圖。

思路(個(gè)人方法)2：直接分析

根據(jù)初始和結(jié)果的狀態(tài)，然后分析各個(gè)節(jié)點(diǎn)變化順序=，手動(dòng)操作這些節(jié)點(diǎn)即可。其實(shí)不管你怎么操作，只要能滿足最后結(jié)構(gòu)一致就行啦!

首先根據(jù)ROOT,R,R.L三個(gè)節(jié)點(diǎn)變化，R.L肯定要在最頂層，左右分別指向ROOT和R，那么這其中R.left，ROOT.right發(fā)生變化(原來(lái)分別是R.L和R)暫時(shí)為空。而剛好根據(jù)左右大小關(guān)系可以補(bǔ)上R.L原來(lái)的孩子節(jié)點(diǎn)A，B。

代碼為：(注釋部分為方案1)

  1. private node getRLbanlance(node oldroot) {//右左深     
  2. //        node newroot=oldroot.right.left; 
  3. //        oldroot.right.left=newroot.right; 
  4. //        newroot.right=oldroot.right; 
  5. //        oldroot.right=newroot.left;  
  6. //        newroot.left=oldroot; 
  7. //        oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  8. //        newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1; 
  9. //        newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新金酸   
  10.     oldroot.right =getLLbanlance(oldroot.right); 
  11.     oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1; 
  12.     return getRRbanlance(oldroot); 
  13.  
  14.     } 

LR平衡旋轉(zhuǎn)(先左后右雙旋轉(zhuǎn))

這個(gè)情況和RL情況相似，采取相同操作即可。

根據(jù)上述RL修改即可

這部分代碼為

  1. private node getLRbanlance(node oldroot) { 
  2.     oldroot.left =getRRbanlance(oldroot.left); 
  3.     oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1; 
  4.     return getLLbanlance(oldroot); 
  5.  
  6.     } 

代碼實(shí)現(xiàn)

首先對(duì)于節(jié)點(diǎn)多個(gè)height屬性。用于計(jì)算高度(平衡因子)

插入是遞歸插入，遞歸是一個(gè)來(lái)回的過程，去的過程進(jìn)行插入，回的過程進(jìn)行高度更新，和檢查是否平衡。推薦不要寫全局遞歸計(jì)算高度，效率太低下，事實(shí)上高度變化只和插入和平衡有關(guān)，仔細(xì)考慮即不會(huì)有疏漏!

代碼寫的比較早，如有命名不規(guī)范的情況，還請(qǐng)勿噴，如果有疏漏還請(qǐng)指出!

  1. import java.util.ArrayDeque; 
  2. import java.util.Queue; 
  3.  
  4. public class AVLTree { 
  5.  
  6.     class node 
  7.     { 
  8.         int value; 
  9.         node left; 
  10.         node right; 
  11.         int height; 
  12.         public node() { 
  13.  
  14.         } 
  15.         public node(int value) 
  16.         { 
  17.             this.value=value; 
  18.             this.height=0; 
  19.         } 
  20.         public node(int value,node left,node right) 
  21.         { 
  22.             this.value=value; 
  23.             this.left=left;this.right=right; 
  24.             this.height=0; 
  25.         } 
  26.     } 
  27.     node root;// 根 
  28.  
  29.     public AVLTree() { 
  30.         this.root = null; 
  31.     } 
  32.  
  33.     public boolean isContains(int x)// 是否存在 
  34.     { 
  35.         node current = root; 
  36.         if (root == null) { 
  37.             return false; 
  38.         } 
  39.         while (current.value != x && current != null) { 
  40.             if (x < current.value) { 
  41.                 current = current.left; 
  42.             } 
  43.             if (x > current.value) { 
  44.                 current = current.right; 
  45.             } 
  46.             if (current == null) { 
  47.                 return false; 
  48.             } // 在里面判斷如果超直接返回 
  49.         } 
  50.         // 如果在這個(gè)位置判斷是否為空會(huì)導(dǎo)致current.value不存在報(bào)錯(cuò) 
  51.         if (current.value == x) { 
  52.             return true; 
  53.         } 
  54.         return false; 
  55.     } 
  56.  
  57.     public int getHeight(node t) 
  58.     { 
  59.         if(t==null) {return -1;}// 
  60.         return t.height; 
  61.         //return 1+Math.max(getHeight(t.left), getHeight(t.right));這種效率太低 
  62.     } 
  63.     public void cengxu(node t) {//層序遍歷 
  64.         Queue<node> q1 = new ArrayDeque<node>(); 
  65.         if (t == null) 
  66.             return; 
  67.         if (t != null) { 
  68.             q1.add(t); 
  69.         } 
  70.         while (!q1.isEmpty()) { 
  71.             node t1 = q1.poll(); 
  72.             if (t1.left != null) 
  73.                 q1.add(t1.left); 
  74.             if (t1.right != null) 
  75.                 q1.add(t1.right); 
  76.             System.out.print(t1.value + " "); 
  77.         } 
  78.         System.out.println(); 
  79.     } 
  80.     public void zhongxu(node t)//中序遍歷 中序遍歷：左子樹---> 根結(jié)點(diǎn) ---> 右子樹 
  81.     {//為了測(cè)試改成中后都行 
  82.         if(t!=null) 
  83.         { 
  84.             zhongxu(t.left); 
  85.             System.out.print(t.value+" ");//訪問完左節(jié)點(diǎn)訪問當(dāng)前節(jié)點(diǎn) 
  86.             zhongxu(t.right); 
  87.             //System.out.print(t.value+" ");//訪問完左節(jié)點(diǎn)訪問當(dāng)前節(jié)點(diǎn) 
  88.         } 
  89.     } 
  90.     public void qianxu(node t)//前序遞歸 前序遍歷：根結(jié)點(diǎn) ---> 左子樹 ---> 右子樹 
  91.     { 
  92.         if(t!=null) { 
  93.             System.out.print(t.value+" ");//當(dāng)前節(jié)點(diǎn) 
  94.             qianxu(t.left ); 
  95.             qianxu(t.right);} 
  96.     } 
  97.     public void insert(int value) { 
  98.         root=insert(value, root); 
  99.     } 
  100.     public node insert(int x,node t)//插入   t是root的引用 
  101.     { 
  102.         node a1=new node(x); 
  103.         //if(root==null) {root=a1;return root;}         
  104.         if(t==null)    {return a1;} 
  105.         //插入操作。遞歸實(shí)現(xiàn) 
  106.         else if(t!=null) 
  107.         { 
  108.             if(x<t.value) 
  109.             { t.left=insert(x,t.left);} 
  110.             else 
  111.             { t.right= insert(x,t.right);} 
  112.         } 
  113.         /* 
  114.          * 更新當(dāng)前節(jié)點(diǎn)的高度，因?yàn)檎麄€(gè)插入只有被插入的一方有影響， 
  115.          * 所以遞歸會(huì)更新好最底層的，上層可直接調(diào)用 
  116.          */ 
  117.         t.height=Math.max(getHeight(t.left),getHeight(t.right))+1;//不要寫成遞歸， 遞歸效率低 
  118.         return banlance(t);//因?yàn)閖ava對(duì)象傳參機(jī)制，需要克隆，不可直接t=xx 否則變換       
  119.     } 
  120.  
  121.     private node banlance(node t) { 
  122.         // TODO Auto-generated method stub 
  123.         //if(t==null)return null; 
  124.         int lefthigh=getHeight(t.left); 
  125.         int righthigh=getHeight(t.right); 
  126.         if(Math.abs(lefthigh-righthigh)<=1)//不需要平衡滴 
  127.         {    return t;} 
  128.         else if(lefthigh<righthigh)//右側(cè)大 
  129.         { 
  130.             if(getHeight(t.right.left)<getHeight(t.right.right))//RR需要左旋 
  131.             { 
  132.                 return  getRRbanlance(t); 
  133.             } 
  134.             else { 
  135.                 return getRLbanlance(t); 
  136.             } 
  137.         } 
  138.         else { 
  139.             if(getHeight(t.left.left)>getHeight(t.left.right))//ll 左左 
  140.             { 
  141.                 return getLLbanlance(t); 
  142.             } 
  143.             else { 
  144.                 return getLRbanlance(t); 
  145.             } 
  146.         } 
  147.     } 
  148.     /* 
  149.      *        oldroot(平衡因子為2,不平衡)    ==>   newroot 
  150.      *       /    \                              /    \ 
  151.      *      B     newroot(平衡因子為1)        oldroot   D 
  152.      *             /    \                      / \      \ 
  153.      *            C      D                    B   C      E 
  154.      *                    \ 
  155.      *                     E 
  156.      */ 
  157.  
  158.     private node getRRbanlance(node oldroot) {//右右深，需要左旋 
  159.         // TODO Auto-generated method stub 
  160.         node newroot=oldroot.right; 
  161.         oldroot.right=newroot.left; 
  162.         newroot.left=oldroot; 
  163.         oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  164.         newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新計(jì)算 
  165.         return newroot; 
  166.     } 
  167.     /* 
  168.      * 右旋同理 
  169.      */ 
  170.     private node getLLbanlance(node oldroot) {//LL小，需要右旋轉(zhuǎn) 
  171.         // TODO Auto-generated method stub 
  172.         node newroot=oldroot.left; 
  173.         oldroot.left=newroot.right; 
  174.         newroot.right=oldroot; 
  175.         oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  176.         newroot.height=Math.max(getHeight(newroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新金酸     
  177.         return newroot; 
  178.     } 
  179.  
  180.     private node getLRbanlance(node oldroot) { 
  181.         oldroot.left =getRRbanlance(oldroot.left); 
  182.         oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1; 
  183.         return getLLbanlance(oldroot); 
  184.  
  185.     } 
  186.  
  187.     /*          (不平衡出現(xiàn)在右左節(jié)點(diǎn)) 
  188.      *         oldroot       ==>          newroot 
  189.      *        /        \                 /       \ 
  190.      *       A          B             oldroot     B 
  191.      *                /   \           /    \     /  \ 
  192.      *           newroot   D         A      E    F   D 
  193.      *            /   \ 
  194.      *           E     F 
  195.      */ 
  196.  
  197.     private node getRLbanlance(node oldroot) {//右左深     
  198. //        node newroot=oldroot.right.left; 
  199. //        oldroot.right.left=newroot.right; 
  200. //        newroot.right=oldroot.right; 
  201. //        oldroot.right=newroot.left;  
  202. //        newroot.left=oldroot; 
  203. //        oldroot.height=Math.max(getHeight(oldroot.left),getHeight(oldroot.right))+1; 
  204. //        newroot.right.height=Math.max(getHeight(newroot.right.left),getHeight(newroot.right.right))+1; 
  205. //        newroot.height=Math.max(getHeight(oldroot.left),getHeight(newroot.right))+1;//原來(lái)的root的高度需要從新金酸   
  206.         oldroot.right =getLLbanlance(oldroot.right); 
  207.         oldroot.height=Math.max(getHeight(oldroot.left), getHeight(oldroot.right))+1; 
  208.         return getRRbanlance(oldroot); 
  209.  
  210.     } 
  211. } 

測(cè)試情況：

AVL的理解需要時(shí)間，當(dāng)然筆者的AVL自己寫的可能有些疏漏，如果有問題還請(qǐng)各位一起探討!

當(dāng)然，除了插入，AVL還有刪除等其他操作，(原理相似。刪除后平衡)有興趣可以一起研究。

 

責(zé)任編輯：武曉燕 來(lái)源： bigsai
二叉樹多叉樹搜索
相關(guān)推薦

2021-04-21 21:06:11

棧數(shù)據(jù)結(jié)構(gòu)

2021-07-06 07:21:16

Spring 安全平臺(tái)

2022-06-29 10:04:01

PiniaVuex

2020-08-06 14:03:48

戴爾

2020-12-16 10:28:05

Double浮點(diǎn)數(shù)計(jì)算

2019-06-17 05:00:53

預(yù)測(cè)性維護(hù)物聯(lián)網(wǎng)IOT

2020-10-20 14:12:54

B站開源彈幕

2016-04-15 17:45:59

HPE存儲(chǔ)閃存

2020-05-06 16:41:36

紅黑樹二叉查找樹

2019-04-15 14:17:28

iTunes蘋果macOS

2020-06-11 18:06:03

電腦電路板元件

2021-02-26 22:34:28

Webpack 前端項(xiàng)目

2019-07-03 15:01:30

戴爾

2021-05-18 11:40:11

開源腳本工具

2019-12-24 09:49:02

微軟英語(yǔ)瀏覽器

2018-12-20 11:20:47

物聯(lián)網(wǎng)設(shè)備物聯(lián)網(wǎng)

2024-10-12 12:30:18

2012-04-09 16:22:43

C#

2021-07-17 22:32:29

Windows 11Windows微軟

2017-09-25 09:17:52

美工程序員互聯(lián)網(wǎng)
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)