4

给定下面的 AVL 树：

        23
       /    \     
   19        35
  /  \      /  \     
 8   20   27    40
               /
             38
             /
            36

可以在 40 度时进行单次旋转吗？使它像这样：

        23
      /    \     
   19        35
  /  \      /  \     
 8   20   27    38
               /  \
             36    40

与左子树相比，它仍然符合具有 -+1 高度的 AVL 属性。

在答案中，它进行了两次旋转，因此上面 35 处的子树在之后看起来像这样：

        23
      /    \     
   19        38
  /  \      /  \     
 8   20   35    40
         /  \
        27  36

如果它们都没有违反 height 属性，我不明白何时进行双重旋转以及何时进行单次旋转。

4

3 回答 3

1

双重旋转可能是由于使用了特定的 AVL 算法。对我来说，这两个答案都像是有效的 AVL 树。

于 2011-06-14T14:21:11.110 回答
1

如果最初的问题只给出了不平衡的 AVL 树（而不是在添加或删除节点之前的平衡树），那么单次旋转是一个有效的答案。

如果问题提供了添加或删除节点之前和之后的 AVL 树，则重新平衡算法可能会导致发生双重旋转。

于 2011-06-14T14:24:43.513 回答
0

尽管根据我使用的文献，这两个答案都是正确的：

有四种类型的旋转 LL、RR、LR 和 RL。这些旋转的特征是插入节点 N 的最近祖先 A，其平衡因子变为 2。

获得以下旋转类型的特征：

  1. LL：N被插入到A的左子树的左子树中
  2. LR：将N插入A的左子树的右子树
  3. RR：N被插入到A的右子树的右子树中
  4. RL：将N插入A的右子树的左子树

根据这些规则，平衡因子变为 2 的最近祖先40在您的示例中，并且插入是在左子树的左子树中进行的，40因此您必须执行 LL 旋转。遵循这些规则，您的第一个答案将是所选操作。

尽管如此，这两个答案都是正确的，并且取决于您使用的算法及其遵循的规则。

于 2012-07-21T18:38:51.250 回答