RL 旋转

当新节点插入到关键节点 A 的右子树的左子树中时，需要执行 RL 旋转。我们考虑节点 B 是关键节点右子树的根，节点 C 是插入新节点的子树的根。

令 T1 为关键节点 A 的左子树，T2 和 T3 分别为节点 C 的左子树和右子树，子树 T4 为节点 B 的右子树。

由于 RL 旋转是 LR 旋转的镜像。在此旋转中，节点 C 成为树的根节点，A 和 B 分别作为其左子节点和右子节点。子树 T1 和 T2 成为 A 的左子树和右子树，而 T3 和 T4 成为 B 的左子树和右子树。

RL 旋转的过程如下图所示。

示例

将值为 92 的节点插入到下图所示的树中。

解决方案

插入 92 破坏了节点 92 的平衡因子，它成为关键节点 A，105 为节点 B，95 为

节点 C。在 RL 旋转中，C 成为树的根（如图所示），节点 A (90) 和 B (105) 分别作为其左子节点和右子节点。树将按图所示进行旋转。