AVL的调整_left-right double rotation

参考博客：https://blog.csdn.net/u013761665/article/details/50393548
https://blog.csdn.net/vesper305/article/details/13614403
（该博客用于理解AVL的旋转过程的前提下，用与记忆，理解见以上两博客）

我们知道之所以会出现不平衡是由于进行插入操作之后某些节点的深度过深导致不平衡。不平衡可能出现在下面四种情况中：

1.LL:对A的左儿子的左子树进行一次插入。
2.LR:对A的左儿子的右子树进行一次插入。
3.RL:对A的右儿子的左子树进行一次插入。
4.RR:对A的右儿子的右子树进行一次插入。

进行旋转处理的时候分成两种大类处理：单旋转和双旋转。

一、单旋转：

对于单旋转，由于问题节点C的插入使得A的平衡因子不再∈{-1,0,1}，在整个旋转的过程中变化的其实只有A,B两个节点。也就是说：当插入任一个节点C时，需要调整的只有他的父亲节点B与他的爷爷节点A（往上两个节点），A、B节点的子树的归属会发生变化，但子树本身不发生变化，而其他节点不发生任何变化。

1、LL：

问题节点插入C到A节点的左孩子的左子树上，使得A不平衡。只需要调整A，B两个节点（即问题节点C的父亲和爷爷）。

对于LL型，使用右旋（即让A成为B的右孩子）：
以B为轴，进行右旋，使得A成为B的右子树，B的左子树不动，B原来的右子树脱落，挂到A的左子树上，A的右子树不动。
原来是A的左子树比右子树大2，这样调整后相当于把A加到A的右子树中+1，让B成为根节点，相当于原来A的左子树-1，这样B的平衡因子就为0啦。

//右旋
AVLTree SingleRightRotation(AVLTree A)
{
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = GetHeight(A);
 B->Height = GetHeight(B);
 
 return B;
} 
1
2
3
4
5
6
7
8
9
10
11

2、RR：

问题节点C插入到A节点的右孩子的右子树上，使得A不平衡。只需要调整A，B两个节点（即问题节点C的父亲和爷爷）。

对于RR型，使用左旋（即让A成为B的左孩子）：
以B为轴，进行左旋，使得A成为B的左子树，B的右子树不动，B原来的左子树脱落，挂到A的右子树上，A的左子树不动。
原来是A的右子树比坐子树大2，这样调整后相当于把A加到A的左子树中+1，让B成为根节点，相当于原来A的右子树-1，这样B的平衡因子就为0啦。

//左旋 
AVLTree SingleLeftRotation(AVLTree A)
{
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = GetHeight(A);
 B->Height = GetHeight(B);
 
 return B;
}
1
2
3
4
5
6
7
8
9
10
11

二、双旋转：

对于这两种情况，由于较深的子树处于结构的中间，因此仅用单旋转并不能解决问题，这个时候，我们必须分别在两个节点之间使用两次单旋转，即一次双旋转使AVL树重新恢复平衡。

双旋相当于两次分别对两个不同的节点使用两次单旋转（左旋或右旋），对于LR型使用左-右单旋的组合，对于RL型使用右-左单旋的组合。

1、LR：

问题节点C插入到A节点的左孩子的右子树上，使得A不平衡。这时需要调整A，B，C三个节点（即问题节点C的父亲和爷爷以及其本身）。

B、C两节点相当于RR型，先对B、C两节点使用左旋，（以C为轴），使得B成为C的左孩子，恢复LL型，这时B是问题节点，A是发现问题节点，采用上所说的右旋策略，以C为轴右旋，使得A成为C的右孩子。子树归属的变化在单旋转过程中一致。

//左右双旋
AVLTree DoubleLeftRightRotation(AVLTree A) 
{
 A->Left = SingleLeftRotation(A->Left);
 return SingleRightRotation(A);
}
1
2
3
4
5
6

2、RL：

问题节点C插入到A节点的右孩子的左子树上，使得A不平衡。这时需要调整A，B，C三个节点（即问题节点C的父亲和爷爷以及其本身）。

B、C两节点相当于LL型，先对B、C两节点使用右旋，（以C为轴），使得B成为C的右孩子，恢复RR型，这时B是问题节点，A是发现问题节点，采用上所说的左旋策略，以C为轴左旋，使得A成为C的左孩子。子树归属的变化在单旋转过程中一致。

//右左双旋
AVLTree DoubleRightLeftRotation(AVLTree A) 
{
 A->Right = SingleLeftRotation(A->Right);
 return SingleLeftRotation(A);
}
1
2
3
4
5
6

【总结】：对于LL型使用右旋，对于RR型使用左旋，对于LR型使用左-右双旋，对于RL型使用右-左双旋。
若右旋则轴节点的父亲节点变为其右孩子，若左旋则轴节点的父亲节点变为其右左孩子。

#include<cstdio>
#include<iostream>
using namespace std;
typedef int ElementType ;
typedef struct AVLNode *Position;
typedef Position AVLTree;

struct AVLNode{
 ElementType Data;
 AVLTree Left;
 AVLTree Right;
 int Height;
}; 

int Max(int a,int b)
{
 return a>b?a:b;
}

int GetHeight(AVLTree A)//递归求树的高度
{
 int HL,HR,MaxH;
 if(A){
  HL = GetHeight(A->Left);
  HR = GetHeight(A->Right);
  MaxH = Max(HL,HR)+1;
  return MaxH;
 }
 else return 0;
}

//左旋 
AVLTree SingleLeftRotation(AVLTree A)
{
 AVLTree B = A->Right;
 A->Right = B->Left;
 B->Left = A;
 A->Height = GetHeight(A);
 B->Height = GetHeight(B);
 
 return B;
}

//右旋
AVLTree SingleRightRotation(AVLTree A)
{
 AVLTree B = A->Left;
 A->Left = B->Right;
 B->Right = A;
 A->Height = GetHeight(A);
 B->Height = GetHeight(B);
 
 return B;
} 

//左右双旋
AVLTree DoubleLeftRightRotation(AVLTree A) 
{
 A->Left = SingleLeftRotation(A->Left);
 return SingleRightRotation(A);
}

//右左双旋
AVLTree DoubleRightLeftRotation(AVLTree A) 
{
 A->Right = SingleLeftRotation(A->Right);
 return SingleLeftRotation(A);
}

AVLTree Insert(AVLTree T,ElementType X)
{
 if(!T){
  T = (AVLTree)malloc(sizeof(struct AVLNode));
  T->Data = X;
  T->Left = T->Right = NULL;
  T->Height = 1;
 }
 else if(X < T->Data){
  T->Left = Insert(T->Left,X);
  if(GetHeight(T->Left) - GetHeight(T->Right) == 2)//只有递归到C的爷爷节点A时这个if才会有可能成立，在其爷爷节点之前的节点由之前的步骤完成了
   if(X<T->Left->Data)//插入到T（C的爷爷节点A）左子树（C的父亲节点B）的左孩子上
    T = SingleRightRotation(T);
   else
    T = DoubleLeftRightRotation(T);//插入到T（C的爷爷节点A）左子树（C的父亲节点B）的右孩子上
 }
 else if(X>T->Data){
  T->Right = Insert(T->Right,X);
  if(GetHeight(T->Right) - GetHeight(T->Left) == 2)
   if(X>T->Right->Data)//插入到T（C的爷爷节点A）右子树（C的父亲节点B）的右孩子上
    T = SingleLeftRotation(T);
   else
    T = DoubleRightLeftRotation(T); //插入到T（C的爷爷节点A）右子树（C的父亲节点B）的左孩子上
 }
 /*else X==T->Data ,无需插入 */
 
 //别忘了更新树高
 T->Height = Max(GetHeight(T->Left), GetHeight(T->Right))+1;
 return T;
}

int main()
{
 int data;
 AVLTree AVL =NULL;
 AVL = Insert(AVL,1);
 while(scanf("%d",&data)!=EOF){
  AVL = Insert(AVL,data);
 }
 printf("树的高度为：%d\n",GetHeight(AVL));
 return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111