AVL小树转转转转转，我的考试挂挂挂挂挂

AVL 树的意义：是二分查找树 BST 。二分查找树查找某个值时，时间复杂度是 O(h) ，因此，我们让树的尽可能平衡，即最大高度尽可能的小。因此有了 AVL 。

创新互联长期为上千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为北关企业提供专业的网站建设、网站制作，北关网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

参考例题：

  • AcWing：AVL树的根[1]

百度百科[2]：在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

BST 本质上是维护一个有序序列，AVL 树中的左旋右旋操作，并不会改变树的中序遍历结果。

上图中把 A 右旋是怎么做的呢?把 B 旋转到根节点，然后把 A 变成 B 的右孩子，把 E 补偿给 A 作为 A 的左孩子。

左旋和右旋

对节点 u 右旋：

  • 根 u 的左儿子变成新的根 p
  • 根的左儿子变成新的根 p 原本的右儿子
  • 新的根 p 的右儿子变成了原本的根 u
  • u 和 p 的高度都需要更新
 
 
 
 
    
  
  
  
  
  1. void R(int& u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     int p = l[u]; 
    4.   
  
  
  
  4.     l[u] = r[p], r[p] = u; 
    5.   
  
  
  
  5.     update(u), update(p); 
    6.   
  
  
  
  6.     u = p; 
    7.   
  
  
  
  7. } 
    8.

对节点 u 右旋：

  • 根 u 的右儿子变成新的根 p
  • 根的右儿子变成新的根 p 原本的左儿子
  • 新的根 p 的左儿子变成了原本的根 u
  • u 和 p 的高度都需要更新
 
 
 
 
    
  
  
  
  
  1. void L(int& u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     int p = r[u]; 
    4.   
  
  
  
  4.     r[u] = l[p], l[p] = u; 
    5.   
  
  
  
  5.     update(u), update(p); 
    6.   
  
  
  
  6.     u = p; 
    7.   
  
  
  
  7. } 
    8.

高度更新由左右儿子决定，因为求高度时，默认其两个儿子已经更新完高度了：

 
 
 
 
    
  
  
  
  
  1. void update(int u) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     h[u] = max(h[l[u]], h[r[u]]) + 1; 
    4.   
  
  
  
  4. } 
    5.

插入的四种情况

四种情况

(一)新数字插到了左子树，导致左子树比右子树高2;左孩子的左子树比其右子树高1

对于四种情况中的①。应该右旋 A 。

实例如上图，右旋 88 即可。

(二)新数字插到了左子树，导致左子树比右子树高2;左孩子的右子树比其左子树高1

对于四种情况中的③。应该左旋 B 再右旋 A 。

对应的情况如如下：

 
 
 
 
    
  
  
  
  
  1.   70 
    2.   
  
  
  
  2. 61 
    3.   
  
  
  
  3.   65 
    4.   
  
  
  
  4. // 左旋 61 
    5.   
  
  
  
  5.     70 
    6.   
  
  
  
  6.   65 
    7.   
  
  
  
  7. 61 
    8.   
  
  
  
  8. // 右旋 70 
    9.   
  
  
  
  9.   65 
    10.   
  
  
  
  10. 61  70 
    11.

(三)新数字插到了右子树，导致右子树比左子树高2;右孩子的右子树比其左子树高1

对于四种情况中的②。应该左旋 A 。

对应的情况如 88 96 120 ，左旋 88 即可。

(四)新数字插到了右子树，导致右子树比左子树高2;右孩子的左子树比其右子树高1

对于四种情况中的④。应该右旋 B 再左旋 A 。

对应的情况如如下：

 
 
 
 
    
  
  
  
  
  1.   70 
    2.   
  
  
  
  2. 96 
    3.   
  
  
  
  3.   88 
    4.   
  
  
  
  4. // 右旋 96 
    5.   
  
  
  
  5. 70 
    6.   
  
  
  
  6.   88 
    7.   
  
  
  
  7.     96 
    8.   
  
  
  
  8. // 左旋 70 
    9.   
  
  
  
  9.   96 
    10.   
  
  
  
  10. 70  88 
    11.

插入的代码

 
 
 
 
    
  
  
  
  
  1. void insert(int& u, int w) 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     if (!u) u = ++ idx, v[u] = w; 
    4.   
  
  
  
  4.     else if (w < v[u]) 
    5.   
  
  
  
  5.     { 
    6.   
  
  
  
  6.         insert(l[u], w); 
    7.   
  
  
  
  7.         if (get_balance(u) == 2) 
    8.   
  
  
  
  8.         { 
    9.   
  
  
  
  9.             if (get_balance(l[u]) == 1) R(u); 
    10.   
  
  
  
  10.             else L(l[u]), R(u); 
    11.   
  
  
  
  11.         } 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.     else 
    14.   
  
  
  
  14.     { 
    15.   
  
  
  
  15.         insert(r[u], w); 
    16.   
  
  
  
  16.         if (get_balance(u) == -2) 
    17.   
  
  
  
  17.         { 
    18.   
  
  
  
  18.             if (get_balance(r[u]) == -1) L(u); 
    19.   
  
  
  
  19.             else R(r[u]), L(u); 
    20.   
  
  
  
  20.         } 
    21.   
  
  
  
  21.     } 
    22.   
  
  
  
  22.  
    23.   
  
  
  
  23.     update(u); 
    24.   
  
  
  
  24. } 
    25.

参考资料

[1]AVL树的根: https://www.acwing.com/problem/content/description/1554/

[2]百度百科: https://baike.baidu.com/item/AVL%E6%A0%91/10986648

新闻标题：AVL小树转转转转转，我的考试挂挂挂挂挂
分享地址：http://www.mswzjz.cn/qtweb/news17/59367.html

攀枝花网站建设、攀枝花网站运维推广公司-贝锐智能，是专注品牌与效果的网络营销公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 贝锐智能

贝锐智能技术为您推荐以下文章

网站排名知识

同城分类信息

德阳网站建设　　 　成都网站推广　　 　平山县网站建设　　 　内江服务器托管　　 　免备案空间　　 　成都广告公司　　 　企业网站改版　　 　seo优化　　 　卖友情链接　　 　成都网站营销推广　　 　赛亚人环保　　 　网站制作价格　　 　企业网站建设　　 　中国电信成都枢纽中心　　 　重庆app软件开发　　 　亚克力背部发光字　　 　深圳惠宜防蚊纱窗　　 　艾瑞格衣柜　　 　梓潼做网站　　 　品牌网站建设公司