LR 旋转

当新节点插入到节点 A 的左子树的右侧时，需要执行 LR 旋转。

在 LR 旋转中，节点 C（如图所示）成为树的根节点，而节点 B 和 A 分别成为它的左子节点和右子节点。

T1 和 T2 分别成为节点 B 的左子树和右子树，而 T3 和 T4 分别成为节点 A 的左子树和右子树。

示例

将值为 70 的节点插入到下面数据结构所示的树中。

解决方案

根据二叉搜索树的性质，值为 70 的节点被插入到树根节点的左子树的右侧。

如图所示，插入 70 后，根节点的平衡因子发生失衡，根节点成为关键节点 A。

为了重新平衡树，需要执行 LR 旋转。节点 C，即 75，将成为新的树根节点，B 和 A 分别作为它的左子节点和右子节点。

子树 T1、T2 成为 B 的左子树和右子树，而子树 T3、T4 成为 A 的左子树和右子树。