AVL树的旋转 (左单旋)
在向上不断更新的过程中,如果parent平衡因子被更新为2或者-2,即parent的平衡因子违反了AVL树的性质,因此需要对以parent为根的二叉树进行旋转处理
左单旋:新节点插入较高右子树的右侧
右单旋:新节点插入较高左子树的左侧
左右双旋:新节点插入较高左子树的右侧
右左双旋:
左单旋
情况1:
1.在树中插入70,根据二叉搜索树的性质新节点应该插入在
2.由于树中插入了新的节点,可能会破坏树的平衡性,在检测平衡性发现平衡性被破环,需要向上更新平衡因子
3.这时发现某个节点的平衡因为不符合条件,需要对其进行旋转,具体:将较高的右子树往上提,提的比双亲好高,节点20转到40的左侧,
parent->right = subRL;
subR->parent;
情况2:
情况3:
在旋转时,需要更新部分节点的左右指针域的指向,还需要更新部分节点的平衡因子
parent和cur节点的平衡因子更新为0,其余全不变。双亲及其右孩子的平衡因子
对parent的分析:上面的3中情况都是在parent没有双亲的情况下,也就是parent是这颗二叉搜索树的根节点,而parent也可能会是树的左右孩子。
所以就要注意parent双亲指针域的指向
右单旋
和左单旋的思路相同,