如果将新节点插入关键节点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
。
在RL
旋转中,C
成为树的根(如图所示),其中节点A(90)
和B(105)
分别作为其左和右子节点。树旋转如图所示。