右右(RR)旋转

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

在旋转时,节点B成为树的根节点。 关键节点A将向左移动并成为B的左子节点。

子树T3成为A的右子树,T1T2成为节点A的左右子树。

示例
90插入到图中所示的AVL树中。

解决方案:
90插入右子树的右侧。 在这种情况下,关键节点A将是85,这是新节点的最接近的祖先,其平衡因子受到干扰。 因此,需要通过对其应用RR旋转来重新平衡树。

节点B将是节点90,它将成为子树的根节点。 关键节点85将成为其左子节点,以便产生现在是AVL树的重新平衡树。


上一篇: 平衡搜索树(AVL树) 下一篇: B树