AVL树的旋转操作详解(2)

case2)为什么经过右右单旋转就可以修正成为 AVL 树;因为 new point = 13 不在 4 和 7 之间, 所以一次单旋转就可以了,无需双旋转; 
(也就是说,new point 介于不满足AVL条件的树根和其孩子之间的话,那么就需要双旋转, 否则, 只需要 单旋转就可以了) 

这里写图片描述

Conclusion of single rotation)单旋转有两个属性: 轴 和 旋转方向

C1)单旋转的轴: 相信你也看到了, 单旋转的轴显然是不符合AVL条件的树根的直接孩子;

C1.1)左左单旋转的轴:是不符合AVL条件的树根的左孩子;

C1.2)右右单旋转的轴:是不符合AVL条件的树根的右孩子;

C2)旋转方向:

C2.1)左左单旋转方向:顺时针方向;

C2.2)右右单旋转方向:逆时针方向;

【3】双旋转

3.1)左右双旋转: (先左左单旋转,再右右单旋转; 即先顺时针旋转,后逆时针旋转)

case1)因为47 介于 40 和 50 之间, 所以肯定需要双旋转; 

这里写图片描述

 

这里写图片描述

3.2)右左双旋转:先将节点15向上提,还是不满足AVL树的条件,再把节点7向上提;(先右右单旋转,再左左单旋转; 即先逆时针旋转,后顺时针旋转) 

这里写图片描述

 

这里写图片描述

Conclusion of double rotations) 双旋转有两个属性: 轴 和 旋转方向

C1)双旋转的轴:相信你也看到了, 双旋转的轴显然是插入点的直接父节点;(除了两个特例) (干货——双旋转的轴显然是插入点的直接父节点(除了两个特例, 而两个特例的轴是插入点本身))

C1.1)左右单旋转的轴:插入点的父节点;

C1.2)右左单旋转的轴:插入点的父节点;

C2)旋转方向:

C2.1)左右单旋转方向:先右右单旋转,再左左单旋转;即先逆时针旋转,再顺时针旋转;

C2.2)右左单旋转方向:先左左单旋转,再右右单旋转;即先顺时针旋转,再逆时针旋转; 

这里写图片描述

 

  【4】示例图与代码参考

4.1)LL的旋转

AVL树的旋转操作详解

  图中左边是旋转之前的树,右边是旋转之后的树。从中可以发现,旋转之后的树又变成了AVL树,而且该旋转只需要一次即可完成。 

  LL的旋转代码:

/*
* LL:左左对应的情况(左单旋转)。
*
* 返回值:旋转后的根节点
*/
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
    AVLTreeNode
<T> k1;

    k1
= k2.left;
    k2.left
= k1.right;
    k1.right
= k2;

    k2.height
= max( height(k2.left), height(k2.right)) + 1;
    k1.height
= max( height(k1.left), k2.height) + 1;

   
return k1;
}

  4.2)RR的旋转

AVL树的旋转操作详解

  图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。

  RR的旋转代码:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/d36e1eaa9fe39c12f09ec4a1b9243113.html