平衡二叉树的四种旋转类型详解
平衡二叉树的四种旋转类型详解
平衡二叉树是一种特殊的二叉树，它要求任意节点的左右子树的高度差不超过1。当向平衡二叉树中插入或删除节点时，可能会破坏这种平衡性，此时需要通过旋转操作来恢复平衡。平衡二叉树主要有四种旋转类型：LL型、LR型、RR型和RL型。
旋转类型的判断与进行
如何判断旋转类型？从不平衡的节点（先找离造成不平衡的节点最近的），朝着造成不平衡的节点走两步，看每一步是Left还是Right以判断。
LL型旋转
旋转类型的判断
假设有一个节点 5，在它的左边有一个节点 4，当节点 3 插入会导致 5 的不平衡，此时不平衡节点是 5 ，造成不平衡的节点是 3 ，走两步进行判断，第一步是走一个Left，第二步也是走一个Left，因此这是一个LL型旋转。
旋转的进行
中间节点成为新的父节点，原父节点向下变成右子树，其余子树按位置重新排列。
→
示例
下面的这个平衡二叉树在插入了节点 0 之后变得不平衡了，分析如何进行旋转。
分析：0 的插入导致 5 的不平衡，从 5 向 0 走两步判断为LL型旋转，0 和 1 作为一个整体，此时中间节点就是 2 ，2 成为新的父节点，而原来的父节点 5 向下变成右子树，其余的再重新排序，0和1和6不发生改变，仍然在原来的位置，3大于2小于5，因此排在5的左边。
旋转结果
RR型旋转
旋转类型的判断
假设有一个节点 A，在它的左边有一个节点 B，当节点 C 插入 B 的右边会导致 A 的不平衡，此时不平衡节点是 A，造成不平衡的节点是 C，走两步进行判断，第一步是走一个Right，第二步也是走一个Right，因此这是一个RR型旋转。
旋转的进行
中间节点成为新的父节点，原父节点向下变成左子树，其余子树按位置重新排列。
LR型旋转
旋转的进行
首先让后两个节点进行旋转，变成LL型旋转，随后再按照LL型旋转规则进行旋转。
示例
下面的这个平衡二叉树在插入了节点 3 之后变得不平衡了，分析如何进行旋转。
分析：3 的插入导致 6 的不平衡，从 6 到 3 是LR型旋转，因此将 4 与 2 进行旋转，变成一个 6 4 2 的LL型旋转，再以 4 为新父节点，6 变为 4 的右子树，3 变成 2 的右子树，剩下的数保持不变。
旋转结果
RL型旋转
旋转的进行
首先让后两个节点进行旋转，变成RR型旋转，随后再按照RR型旋转规则进行旋转。
示例
下面的这个平衡二叉树在插入了节点 4 之后变得不平衡了，分析如何进行旋转。
分析：4 的插入造成 3 的不平衡，3 到 4 是RL型旋转，因此将 5 6 先进行旋转，形成 3 5 6 的RR型旋转，再以中间数 5 作为新的父节点，3 变成 5 的左子树，4接在3的右边，其余保持不变。
旋转结果