平衡AVL树

Question

我在平衡AVL树方面遇到了困难。我已经搜寻了很多关于如何平衡AVL树的步骤，但是没有找到有用的信息。

我知道有以下四种方法：

- 单左旋转 - 单右旋转 - 双左右旋转 - 双右左旋转

但我无法确定选择哪一种方法以及在哪个节点上应用它！

非常感谢您提供任何帮助！

- user1910524

Answer 1

这是Java实现，您可以在其中了解算法的思路：

private Node<T> rotate(Node<T> n) {
    if(n.getBf() < -1){
            if(n.getRight().getBf() <= 0){
                return left(n);         
            }
            if(n.getRight().getBf() > 0){
                return rightLeft(n);
            }
    }   
    if(n.getBf() > 1){
            if(n.getLeft().getBf() >= 0){
                return right(n);
            }
            if(n.getLeft().getBf() <  0){
                return leftRight(n);
            }
    }
    return n;
}

四种旋转的单独方法如下：

/**
 * Performs a left rotation on a node
 * 
 * @param n The node to have the left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> left(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getRight();
        n.setRight(temp.getLeft());
        temp.setLeft(n);
        return temp;
    }
    return n;   
}

/**
 * Performs a right rotation on a node
 * 
 * @param n The node to have the right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> right(Node<T> n) {
    if(n != null){
        Node<T> temp = n.getLeft();
        n.setLeft(temp.getRight());
        temp.setRight(n);
        return temp;
    }
    return n;
}

/**
 * Performs a left right rotation on a node
 * 
 * @param n The node to have the left right rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> leftRight(Node<T> n) {
    n.setLeft(left(n.getLeft()));
    Node<T> temp = right(n);
    return temp;
}

/**
 * Performs a right left rotation on a node
 * 
 * @param n The node to have the right left rotation performed on
 * @return The new root of the subtree that is now balanced due to the rotation
 */
private Node<T> rightLeft(Node<T> n) {
    n.setRight(right(n.getRight()));
    Node<T> temp = left(n);
    return temp;
}

- gtboy

Answer 2

AVL树中的关键不变量是每个节点的平衡因子为-1、0或+1。这里的“平衡因子”是左右子树高度之差。+1表示左子树比右子树高一个，-1表示左子树比右子树短一个，0表示子树大小相同。这些信息通常缓存在每个节点中。

当您得到一个平衡因子为-2或+2的节点时，您需要进行旋转。以下是旋转必要时的一种可能设置：

          u (-2)
         / \
        A   v (-1)
           / \
          B   C

如果我们填入这些树的高度，我们会得到：

          u h + 2
         / \
    h-1 A   v h + 1
           / \
      h-1 B   C h

如果发生这种情况，进行一次单右旋即可。

         v h+1
        / \ 
     h u   C h
      / \
 h-1 A   B h-1

嘿！树是平衡的。这棵树的镜像也可以通过单个左旋转进行修复。

所有AVL树的旋转都可以通过在一个小范围内列举可能的平衡因子，然后确定每一步应该应用哪些旋转来确定。我会把这个留给读者作为练习。:-) 如果你只想查找答案，维基百科关于AVL树有一张很好的图片总结了可能需要应用的所有旋转。

希望这对你有所帮助！

- templatetypedef

---

这棵树已经平衡了，为什么要旋转呢？ u+A =2 , u+v+c=3 , 2-3 = -1, 所以这是平衡的。 我们为什么要在这里进行旋转呢？ - user1910524

@user1910524- 不，这棵树不是平衡的。请注意，它的左子树和右子树的高度差为2 - 左子树的高度为h-1，右子树的高度为h+1。请记住，平衡因子表示两棵树之间的高度差异，因此说“u + A = 2”并没有实际意义。这样说您明白了吗？ - templatetypedef

@templatetypedef，我不明白。如果我们看“u”的左子树，我们发现层数=2。如果我们看“u”的右子树，我们发现层数=3。所以2-3=-1。 如果我们看“v”的左子树，我们发现层数=2。如果我们看“v”的右子树，我们发现层数=s。所以2-2=0。 所以这棵树是平衡的！ - user1910524

@user1910524- 哦，我明白了。A、B和C表示某个特定高度的任意子树，而不是单个节点。u和v指的是单个节点，而不是子树。我在符号表示上应该更加清晰明了。这样说你明白了吗？ - templatetypedef