AVL树调整平衡的方法

AVL树调整平衡的方法

LL型 #

插入新节点x后,从该节点向上找到最近的不平衡节点A,如果最近不平衡节点到新节点的路径前两个都是左子树L,就是LL型。需要进行LL旋转(顺时针)。

RR型 #

插入新节点x后,从该节点向上找到最近不平衡节点A,如果最近不平衡节点到新节点的路径前两个都是右子树R,就是RR型。需要进行RR旋转(逆时针)。

LR型 #

插入新节点x后,从该节点向上找到最近不平衡节点A,如果最近不平衡节点到新节点的路径前两个依次是左子树L、右子树R,就是LR型。 实际上,也可以看作C固定不动,B进行RR旋转,然后进行LL旋转。

RL型 #

插入新节点x后,从该节点向上找到最近不平衡节点A,如果最近不平衡节点到新节点的路径前两个依次是右子树R、左子树L,就是RL型。 实际上,也可以看作C固定不动,B进行LL旋转,然后进行RR旋转。