AVL树旋转顺序

Question

当AVL树中存在不平衡并且需要旋转时，如何选择首先旋转的节点。在示例中，有时我会看到根节点先旋转，有时我看到父节点先旋转；有时叶节点先旋转。

Answer 1

使用AVL树，当平衡因子沿着从叶到根的路径更新时，将检测到由插入或删除叶引起的不平衡。一旦发现一个节点(在向上遍历中(的平衡因子超出范围，该节点将发生单次或双次旋转。然而，双旋转分解为两个单旋转，这两个旋转中的第一个真正作用于给定节点的子节点。