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 回答