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树,而且该旋转只需要一次即可完成。
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的旋转
图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。
RR的旋转代码: