如果节点插入节点A的右子树的右侧并且树变得不平衡,那么在这种情况下,将执行RR 旋转,如下图所示。
在旋转时,节点B
成为树的根节点。 关键节点A
将向左移动并成为B
的左子节点。
子树T3
成为A
的右子树,T1和T2成为节点A
的左右子树。
示例
将90
插入到图中所示的AVL树中。
解决方案:
将90
插入右子树的右侧。 在这种情况下,关键节点A
将是85
,这是新节点的最接近的祖先,其平衡因子受到干扰。 因此,需要通过对其应用RR
旋转来重新平衡树。
节点B
将是节点90
,它将成为子树的根节点。 关键节点85
将成为其左子节点,以便产生现在是AVL
树的重新平衡树。