RR 旋转

如果一个节点被插入到节点 A 的右子树的右侧，并且树变得不平衡，那么在这种情况下，将执行 RR 旋转，如下图所示。

旋转时，节点 B 成为树的根节点。关键节点 A 将移到 B 的左侧，并成为 B 的左子节点。

子树 T3 成为 A 的右子树。T1 和 T2 成为节点 A 的左子树和右子树。

示例

将 90 插入到图示的 AVL 树中。

解决方案

90 被插入到右子树的右侧。在这种情况下，关键节点 A 将是 85，它是新节点最近的祖先，其平衡因子已受到干扰。因此，我们需要通过对节点 85 应用 RR 旋转来重新平衡树。

节点 B 将是节点 90，它将成为这个子树的根节点。关键节点 85 将成为它的左子节点，以生成重新平衡的树，现在它是一棵 AVL 树。