AVL树平衡

| 给定下面的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属性）。     
2020-02-05 4 条评论
分享

没有找到相关结果

    已邀请:

    挂帘妈乡

            两次旋转可能是由于使用了特定的AVL算法造成的。这两个答案对我来说都像是有效的AVL树。     
    2020-02-05 0 0
    分享

    闲窍

            如果仅使用不平衡的AVL树（而不是添加或删除节点之前的平衡树）给出原始问题，则单次旋转是有效的答案。 如果问题在添加或删除节点之前和之后提供了AVL树，则重新平衡的算法可能会导致发生两次旋转。     
    2020-02-05 0 0
    分享

    蓄荣糖些

            尽管根据我使用的文献，这两个答案都是正确的：   旋转LL，RR，LR和RL有四种旋转类型。这些旋转是   其特征在于所插入节点N的最近祖先A，其节点   平衡系数变为2。      获得以下旋转类型的特征：         LL：在A的左子树的左子树中插入N   LR：将N插入A的左子树的右子树中   RR：将N插入到A的右子树的右子树中   RL：N插入到A的右子树的左子树中    根据这些规则，在您的示例中，平衡因子变为2的最近祖先是
    40
    ，并且插入是在
    40
    的左子树的左子树中进行的，因此您必须执行LL旋转。遵循这些规则，您的第一个答案将是选择的操作。 尽管如此，两个答案都是正确的，并且取决于您使用的算法及其遵循的规则。     
    2020-02-05 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.035120010375977