AVL树的旋转 (左单旋)

在向上不断更新的过程中,如果parent平衡因子被更新为2或者-2,即parent的平衡因子违反了AVL树的性质,因此需要对以parent为根的二叉树进行旋转处理

左单旋:新节点插入较高右子树的右侧

右单旋:新节点插入较高左子树的左侧

左右双旋:新节点插入较高左子树的右侧

右左双旋:

左单旋

AVL树的旋转 (左单旋)

情况1:

1.在树中插入70,根据二叉搜索树的性质新节点应该插入在

AVL树的旋转 (左单旋)

2.由于树中插入了新的节点,可能会破坏树的平衡性,在检测平衡性发现平衡性被破环,需要向上更新平衡因子

AVL树的旋转 (左单旋)

3.这时发现某个节点的平衡因为不符合条件,需要对其进行旋转,具体:将较高的右子树往上提,提的比双亲好高,节点20转到40的左侧,

AVL树的旋转 (左单旋)

parent->right = subRL;

subR->parent;

情况2:

AVL树的旋转 (左单旋)
 

情况3:

AVL树的旋转 (左单旋)

在旋转时,需要更新部分节点的左右指针域的指向,还需要更新部分节点的平衡因子

parent和cur节点的平衡因子更新为0,其余全不变。双亲及其右孩子的平衡因子

 

对parent的分析:上面的3中情况都是在parent没有双亲的情况下,也就是parent是这颗二叉搜索树的根节点,而parent也可能会是树的左右孩子。

AVL树的旋转 (左单旋)

所以就要注意parent双亲指针域的指向

右单旋

和左单旋的思路相同,