从零开始学数据结构系列之第三章《平衡二叉树的旋转类型图文详解》

---

简单回顾

2 种「旋转」方式：

1. 左旋
   • 旧根节点为新根节点的左子树
   • 新根节点的左子树（如果存在）为旧根节点的右子树
2. 右旋：
   • 旧根节点为新根节点的右子树
   • 新根节点的右子树（如果存在）为旧根节点的左子树

4 种「旋转」纠正类型

1. LL 型：插入左孩子的左子树，右旋
2. RR 型：插入右孩子的右子树，左旋
3. LR 型：插入左孩子的右子树，先左旋，再右旋
4. RL 型：插入右孩子的左子树，先右旋，再左旋

LL 型

• 旧根节点（节点 3）为新根节点（节点 2）的右子树
• 新根节点的 右子树（如果存在）为旧根节点的左子树
  
  简单来说：

​ 先找到失衡树的根节点（Root），我们把他根节点的左子树称作为（temp）

​ 那么temp 的父亲，变成他的右孩子

​ 以上动图是最简单的方式

接下来如下图所示（一般情况，上面可以理解为右孙是NULL）：



用代码来讲就是

/* 因为他是LL型，先获取原先根节点的左孩子， */
reeNode* temp = node -> lchild;
/* 爹的左子树现在变成 儿的右子树*/
node -> lchild = temp -> rchild; 
/* 儿的右子树变成爹*/
temp -> rchild = node;

​ 因为我们本身是二叉排序树，所以爹一定是比儿大的，右孙也比儿大的，但是一定比爹小

​ 所以爹的左子树从儿变成右孙，儿变爹，爹变儿，孙子永远还是孙子

​ 也可以简单记为右旋

RR 型

• 旧根节点（节点 1）为新根节点（节点 2）的左子树
• 新根节点的左子树（如果存在）为旧根节点的右子树

简单来说：

​ 先找到失衡树的根节点（Root），我们把他根节点的左子树称作为（temp）

​ 那么temp 的父亲，变成他的左孩子

​ 以上动图是最简单的方式

接下来如下图所示（一般情况，上面可以理解为左孙是NULL）：

用代码来讲就是

/* 因为他是RR型，先获取原先根节点的右孩子， */
reeNode* temp = node -> rchild;
/* 爹的右子树现在变成 儿的左子树*/
node -> rchild = temp -> lchild; 
/* 儿的左子树变成爹*/
temp -> lchild = node;

基本就是和LL型相反的，

​ 也可以简单记为左旋

我们可以通过下面的图直观的感受到

LR 型

• 旧根节点（节点 1）为新根节点（节点 2）的左子树
• 新根节点的左子树（如果存在）为旧根节点的右子树

• 根节点（节点 3）为新根节点（节点 2）的右子树
• 新根节点的 右子树（如果存在）为旧根节点的左子树
  
  接下来如下图所示（一般情况，上面可以理解为左右玄孙是NULL）：

孙子终于当爹了，太感动了~

简单来讲：

​   取最后一个节点，作为父节点，将它的父亲作为自己的左孩子，将它的父亲的父亲作为自己的右孩子，如果它有左孩子或者右孩子的话，它原先的左孩子，连接到父亲的右孩子上，它现在的右孩子，连接到父亲的父亲的左孩子上

这里先买个关子，我们后面在讲代码，先看RL型的

RL型

• 旧根节点（节点 3）为新根节点（节点 2）的右子树
• 新根节点的 右子树（如果存在）为旧根节点的左子树
  
• 旧根节点（节点 1）为新根节点（节点 2）的左子树
• 新根节点的左子树（如果存在）为旧根节点的右子树
  
    简单来说，取最后一个节点，作为父亲节点，将它原先的父亲作为自己的右孩子，将父亲的父亲作为自己的左孩子，如果自己有左孩子或者右孩子的话，自己原先的左孩子连接到父亲的父亲有孩子上，自己原先的右孩子连接到父亲的左孩子上

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解1》