我个人是通过b站学习的懂得
b站视频连接：
旋转原则：
下面看一张图：
PS: 以下 p 是A q是B
LL型：
1) 定义一个结构体指针指向A的左子树 ，tree *q = p->l
2) 让A左子树连上B的右子树 p->l = q->r (因为B是A的左子树， 所以B上所有子节点的data 都小于A 的data) ，
3) 由于A的data大于B的data ,再将B的右子树连上A q->r = p
3) 计算q的(B)右子树p深度 p->height = max(height(p->l), height(p->r)) + 1; // +1 是加上p本身
4) 计算q的深度 q->height = max(height(q->l), p->height) + 1; // +1 是加上q本身
RR型:
1) 定义一个结构体指针指向A的右子树 ，tree *q = p->r
2) 让A右子树连上B的左子树 p->l = q->r (因为B是A的右子树， 所以B上所有子节点的data 都大于A 的data) ，
3) 由于A的data小于B的data ,再将B的左子树连上A q->l = p
3) 计算q的(B)左子树p深度 p->height = max(height(p->l), height(p->r)) + 1; // +1 是加上p本身
4) 计算q的深度 q->height = max(height(q->l), p->height) + 1; // +1 是加上q本身
LR型：
一次RR 一次LL
RL型：
一次LL 一次RR
下面是一个例题：
数据结构实验之查找二：平衡二叉树
Time Limit: 400 ms Memory Limit: 65536 KiB
Problem Description
根据给定的输入序列建立一棵平衡二叉树，求出建立的平衡二叉树的树根。
Input
输入一组测试数据。数据的第1行给出一个正整数N(n <= 20)，N表示输入序列的元素个数；第2行给出N个正整数，按数据给定顺序建立平衡二叉树。
Output
输出平衡二叉树的树根。
Sample Input
588 70 61 96 120
Sample Output
70
Hint
Source
xam
ACcode：
#includeusing namespace std;struct tree{ int data; //记录关键字数值 tree *l, *r; int height; //平衡因子};int height(tree *p) //求树的深度{ if (p == NULL) return -1; return p->height;}tree *LL(tree *p) //对LL型直接在不平衡结点进行左旋转{ tree *q; q = p->l; // q是p的左子树 p->l = q->r; // q的左子树一定小于p->data 所以p->l连上q->r q->r = p; // q->r连上p p->height = max(height(p->l), height(p->r)) + 1; // 结点的位置变了，要更新结点的高度值 q->height = max(height(q->l), p->height) + 1; return q;}tree *RR(tree *p) //对RR型直接在不平衡结点进行右旋转{ tree *q; // 连接原理与LL相同 q = p->r; p->r = q->l; q->l = p; p->height = max(height(p->l), height(p->r)) + 1; q->height = max(height(q->r), p->height) + 1; return q;}tree *LR(tree *p){ p->l = RR(p->l); //在不平衡结点p的左儿子处进行右旋转 return LL(p); //在不平衡结点p处进行左旋转并返回新的根}tree *RL(tree *p){ p->r = LL(p->r); //在不平衡结点p的右儿子处进行左旋转 return RR(p); //在不平衡结点p处进行左旋转并返回新的根}tree *insert(tree *p, int k){ if (p == NULL) //待插入的值赋给新开辟的结点 { p = new tree; p->data = k; p->height = 0; p->l = p->r = NULL; } else if (k < p->data) //若待插入的值小于p的关键字数值，则插入到左子树中 { p->l = insert(p->l, k); if (height(p->l) - height(p->r) == 2) //该树出现不平衡 { if (k < p->l->data) //若待插入的值插到了左儿子的左子树上则单旋转 p = LL(p); else //反之，双旋转 p = LR(p); } } else if (k > p->data) //道理同上 { p->r = insert(p->r, k); if (height(p->l) - height(p->r) == -2) { if (k > p->r->data) p = RR(p); else p = RL(p); } } p->height = max(height(p->l), height(p->r)) + 1; return p;}int main(){ int n, k; while (cin >> n) { tree *head = NULL; for (int i = 0; i < n; i++) { cin >> k; head = insert(head, k); } cout << head->data << endl; } return 0;}/***************************************************User name: QXQZXResult: AcceptedTake time: 0msTake Memory: 236KBSubmit time: 2018-12-19 14:58:13****************************************************/