请帮我理解 AVL 树中的 LR 旋转

Question

今天我正在研究数据结构中的 AVL 树，但在理解 LR 和 RL 旋转方面陷入了困境。LL 和 RR 轮换非常直观且容易记住，但在我看来 LR 和 RL 轮换不符合常识，所以我很难记住它们。这些旋转是否应该被塞满或者有什么方法可以理解它们？我正在阅读的书（Seymoure Lipschutz 的《数据结构》）说 LR 旋转是 RR 旋转和 LL 旋转的组合。但我无法连接它。这是那本书中描绘的图片：

在第二张图片和最后一张图片之间发生了什么，如果可能，请用这张图片解释一下。我想如果我理解 LR，那么就会自动理解 RL，因为两者都是彼此的镜像。

Answer 1

你不理解它，因为它不正确，如图。它甚至不是一个有效的二叉搜索树。37 不能是 76 的正确（较大）孩子，因为它较小。

初始插入

??? 44
    ??? (L) 30
    ?   ??? (L) 16
    ?   ??? (R) 39
    ?       ??? (L) 37
    ??? (R) 76

在 (30) 上左旋转后： (39) 旋转到它的父节点 [30] 位置，(39) 的子节点 [37] 变成 30 的子节点。

??? 44
    ??? (L) 39
    ?   ??? (L) 30
    ?       ??? (L) 16
    ?       ??? (R) 37
    ??? (R) 76

在 (39) 上向右旋转后： (39) 在树的顶部， (44) 成为他的右孩子。

??? 39
    ??? (L) 30
    ?   ??? (L) 16
    ?   ??? (R) 37
    ??? (R) 44
        ??? (R) 76