转载自：https://zhuanlan.zhihu.com/p/488480370

二叉树平衡遵循原则

平衡的原则公式：|左子树高度-右子树高度| < 2

也就是说，如果一棵二叉树中，只要有任何子树，它的左子树高度减去右子树高度（绝对值）只要大于或者等于2，那么这棵二叉树就不是平衡的。就需要进行旋转操作使之变成平衡。

非平衡二叉树的种类

非平衡二叉树主要分为四种：LL类、RR类、LR类、RL类。

下面画图分别说明其特点：（Lleft表示左子树高度，Lright表示右子树高度）

第1类—LL型：

特点：根节点的左孩子的左孩子引起的树不平衡。可能是左孩子的左孩子加进来。或者左孩子的左孩子又加了一个孩子进来，导致左子树的高度过高，违反了|Lleft-Lright|<2的原则。这种就是LL型。

第2类—RR型：

特点：根节点的右孩子的右孩子引起的树不平衡。可能是右孩子的右孩子加进来；或者右孩子的右孩子又加了一个孩子进来，导致右子树的高度过高，违反了|Lleft-Lright|<2的原则。这种就是RR型。

第3类—LR型：

特点：根节点的左孩子的右孩子引起的树不平衡。可能是左孩子的右孩子加进来；或者左孩子的右孩子又加了一个孩子进来，导致左子树的高度过高，违反了|Lleft-Lright|<2的原则。这种就是LR型。

第4类—RL型：

特点：根节点的右孩子的左孩子引起的树不平衡。可能是右孩子的左孩子加进来；或者右孩子的左孩子又加了一个孩子进来，导致右子树的高度过高，违反了|Lleft-Lright|<2的原则。这种就是RL型。

非平衡二叉树的旋转法

LL型：根节点右旋；

RR型：根节点左旋；

LR型：先左旋再右旋；（1、根节点不动，让左节点去解决；2、小弟左旋到其右孩子的左边，这时树演化成了LL型；3、LL型则将根节点右旋）

RL型：先右旋再左旋；（1、根节点不动，让右节点去解决；2、小弟右旋到其左孩子的右边，这时树演化成了RR型；3、RR型则将根节点左旋）

下面以画图方式对四种非平衡树的旋转解法详细剖析：

1、LL型

示例1：

示例2：

示例3：

2、RR型

示例1：

示例2：

示例3：

3、LR型

示例1：

示例2：

日本蓬松去油控油修复毛糙分叉防脱洗发水

¥268.00

已失效 

示例3：

4、RL型

示例1：

示例2：

示例3：

非平衡到平衡的秘籍大法

综合上述案例分析，总结出4类非平衡树如何旋转成平衡树的以下秘笈（敲黑板划重点！！！）：

• LL型：右旋无阻碍则直接右旋；右旋有阻碍则鸠占鹊巢，然后鹊归位；

• RR型：左旋无阻碍则直接左旋；左旋有阻碍则鸠占鹊巢，然后鹊归位；

• LR型：先左旋（小弟）再右旋（根节点），若旋转有阻碍则鸠占鹊巢然后鹊归位；

• RL型：先右旋（小弟）再左旋（根节点），若旋转有阻碍则鸠占鹊巢然后鹊归位；