0

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

在此处输入图像描述

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

4

1 回答 1

7

您不理解它，因为它不正确，如图所示。它甚至不是一个有效的二叉搜索树。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
于 2013-09-15T02:26:16.640 回答