平衡二叉树的调整(详解 LL、RR、LR、RL)

╰+哭是因爲堅強的太久メ 2022-01-29 11:23 478阅读 0赞

[浙江大学讲解视频][Link 1]

平衡二叉树(AVL)的**定义**：

*  任一结点的左右子树高度差的绝对值小于等于1，绝对值就是平衡因子
 *  任一结点的左右子树均为AVL树
 *  平衡二叉树也可以是一个空树

--------------------

**平均查找长度(ASL)**(查找效率) `（ASL=所有查找次数X*查找次数为X的结点数相加)/总结点数`  
例：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70][]

--------------------

##### 平衡二叉树的调整 #####

当向一棵AVL树中插入一个新的结点，有可能会破坏树的平衡，这时就需要调整这棵树，根据不同的插入位置，一共有四种调整方法，在调整的过程中要注意，一定要满足二叉搜索树的性质

<table> 
 <thead> 
  <tr> 
   <th>插入位置</th> 
   <th>如何调整</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>插入结点在发现者<code>右子树</code>的<code>右边</code></td> 
   <td>RR调整，右单旋</td> 
  </tr> 
  <tr> 
   <td>插入结点在发现者<code>左子树</code>的<code>左边</code></td> 
   <td>LL调整，左单旋</td> 
  </tr> 
  <tr> 
   <td>插入结点在发现者<code>左子树</code>的<code>右边</code></td> 
   <td>LR调整，左右双旋</td> 
  </tr> 
  <tr> 
   <td>插入结点在发现者<code>右子树</code>的<code>左边</code></td> 
   <td>RL调整，右左双旋</td> 
  </tr> 
 </tbody> 
</table>

注，发现者是第一个不满足这棵树是平衡二叉树的结点，**如果有多个结点同时不满足，就选最靠近下面的那个结点作为发现者**，

--------------------

###### 右单旋(RR调整) ######

插入结点在发现结点的`右子树的右边`

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1][]

插入13时发现5的平衡因子被破坏了，破坏者在发现结点右子树的右边，所以应该对这棵树进行右单旋(RR单旋)，让树向左边转，在旋转过程中让被破坏者的右子树作为调整后的跟结点.在调整过程中发现8这个结点会有冲突，那么就按照二叉搜索树的性质将8放在5的右边，调整结果如下  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 2][]

--------------------

###### 左单旋(LL调整) ######

插入结点在发现结点`左子树的左边`  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 3][]

插入2时发现4和5同时为发现者，这时就选择距离插入结点较近的点作为发现者。因为插入结点在发现者左子树的左边，所以应该对这棵树进行左单旋(LL单旋)，让树向右边转，调整结果如下  
![20190523162009324.PNG][]

--------------------

###### 左右双旋(LR双旋) ######

插入结点在发现结点左子树的右边  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 4][]  
一定要记得先右单旋，再左单旋,`以4这棵树`右单旋以后结果如下  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 5][]  
发现这棵平衡二叉树还不平衡，再`以5这棵树`左单旋，结果如下  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 6][]

--------------------

###### 右左双旋(RL双旋) ######

插入结点在发现结点右子树的左边  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 7][]  
一定要记得先左单旋，再右单旋,`以6这棵树`左单旋以后结果如下  
![20190524171701777.PNG][]  
发现这棵平衡二叉树还不平衡，再`以3这棵树`右单旋，结果如下  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 8][]

--------------------

> 注意：在双旋过程中，注意不要让双旋的名称误解了，名称仅仅是表示`插入结点`相对于`发现结点`的位置，`左右双旋`是先`右单旋`在`左单旋`，`右左双旋`是先`左单旋`再`右单旋`

如有错误之处，欢迎评论

[Link 1]: https://www.icourse163.org/learn/ZJU-93001#/learn/content?type=detail&id=1007588489&cid=1009165001
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: /images/20220129/f653fb50cd094cc8912f2188b4fbd435.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 1]: /images/20220129/188f5ce88087486896db4c35d7b9854e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 2]: /images/20220129/164ecb545dbb4cee97db9328458d44b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 3]: /images/20220129/ffe11888e6a84f9f937370193b1d6939.png
[20190523162009324.PNG]: /images/20220129/6d572fa52e314d30bbf0180d5927366f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 4]: /images/20220129/cf4c460654d54f76b04e37bab36cbe6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 5]: /images/20220129/c42d400ecd17466597294259fa1b9d2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 6]: /images/20220129/5ffbcfa4d20a4375b3ca548b337d45e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 7]: /images/20220129/894de632d4974d3a9370e5d528aeee38.png
[20190524171701777.PNG]: /images/20220129/f4439687dafb4a6fa74b646655972257.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70 8]: /images/20220129/d643cc0b30824d24a1d06efe3e0f8072.png