平衡二叉树所有类型（不平衡二叉树的旋转）

在按照二叉查找树（二叉查找树（BST：Binary Search Tree） ）的方式插入元素构建一个平衡二叉树（平衡二叉树 ）时，可能会出现不平衡的现象。可以根据新插入节点与最低不平衡节点之间的位置关系进行相应的调整。

我们先把需要调整的类型分为四种情况：LL型、RR型、LR型、RL型。使用图形示例与实际代码结合的方式对不平衡二叉树进行旋转。

定义一个树节点：

平衡二叉树节点定义

LL型调整

由于在y_6的左孩子(L)的左子树(L)上插入新结点2，使原来平衡二叉树变得不平衡，此时y_6的平衡因子由1增至2。显然，按照大小关系，结点x_3应作为新的根结点，1和y_6两个节点分别作为左右孩子节点才能平衡，y_6结点就好像是绕结点x_3顺时针旋转一样。

LL型调整

总结一下LL型调整的一般步骤：

1. 将y_6（新的不平衡节点）的左孩子x_3提升为新的根节点；
2. 将原来的根节点y_6降为x_3的右孩子
3. 各子树按照大小关系连接（y_6的右孩子，x_3的左孩子不变，x_3的右孩子调整为y_6的左孩子）

LL型旋转代码实现

RR型调整

由于在y_2的右孩子(R)的右子树(L)上插入新结点5，使原来平衡二叉树变得不平衡，此时y_2的平衡因子由1增至2。显然，按照大小关系，结点x_4应作为新的根结点，y_2和6两个节点分别作为左右孩子节点才能平衡，y_2结点就好像是绕结点x_4逆时针旋转一样。

RR型调整

总结一下RR型调整的一般步骤：

1. 将y_2（新的不平衡节点）的右孩子x_4提升为新的根节点；
2. 将原来的根节点y_2降为x_4的左孩子
3. 各子树按照大小关系连接（y_6的左孩子，x_4的右孩子不变，x_4的左孩子调整为y_2的右孩子）

RR型旋转代码实现

LR型调整

由于在6的左孩子(L)的右子树(R)上插入新结点3，使原来平衡二叉树变得不平衡，此时6的平衡因子由1增至2。显然，按照大小关系，结点x_4应作为新的根结点，y_2和6两个节点分别作为左右孩子节点才能平衡。

LR型调整

总结一下LR型调整的一般步骤：

1. 将y_2假设为新的根节点；
2. 将以y_2为根的二叉树进行RR型旋转；
3. 再对以y_6为根的二叉树进行LL型旋转；

LR型旋转代码实现

RL型调整

由于在2的右孩子(R)的左子树(L)上插入新结点4，使原来平衡二叉树变得不平衡，此时2的平衡因子由1增至2。显然，按照大小关系，结点3应作为新的根结点，2和5两个节点分别作为左右孩子节点才能平衡。

RL型调整

总结一下RL型调整的一般步骤：

1. 将x_5假设为新的根节点；
2. 将以x_5为根的二叉树进行LL型旋转；
3. 再对以y_2为根的二叉树进行RR型旋转；

RL型旋转代码实现

理解好平衡二叉树的旋转，对后边学习红黑树有非常大的帮助。下一篇文章学习，如何在构建和删除平衡二叉树的过程中维持二叉树一直平衡。

平衡二叉树

如何优雅地画好二叉树

二叉树遍历的思维导图

二叉树的层序遍历及应用

二叉查找树（BST：Binary Search Tree）

,