日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
這個樹，怎么一下就平衡了？

[[427844]]

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

網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計的關(guān)注點不是能為您做些什么網(wǎng)站，而是怎么做網(wǎng)站，有沒有做好網(wǎng)站，給成都創(chuàng)新互聯(lián)公司一個展示的機會來證明自己，這并不會花費您太多時間，或許會給您帶來新的靈感和驚喜。面向用戶友好，注重用戶體驗，一切以用戶為中心。

什么是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ù)平衡，在具體的處理上我們使用遞歸的方式解決問題。

四種不平衡情況處理

針對四種不平衡的情況，這里對每種情況進行詳細的講解。

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

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

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

  • 在左旋的過程中，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，不過不影響操作!

其更詳細流程為：

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

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

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

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

代碼：

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

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)

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

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

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

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

這部分代碼為

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

代碼實現(xiàn)

首先對于節(jié)點多個height屬性。用于計算高度(平衡因子)

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

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

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

測試情況：

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

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


網(wǎng)頁標(biāo)題：這個樹，怎么一下就平衡了？
分享路徑：http://www.5511xx.com/article/dhdgogd.html