data-structures - 平衡 AVL 树

Question

我无法平衡 AVL 树。我已经到处搜索了如何平衡它们的步骤，但我找不到任何有用的东西。

我知道有4种：

• 单向左旋转
• 单次右转
• 双左右旋转
• 双左右旋转

但我就是不知道如何选择其中一个以及应用它的节点！

任何帮助将不胜感激！

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;
}

4个旋转的单独方法在这里：

/**
 * 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;
}

Answer 2

AVL 树中的关键不变量是每个节点的平衡因子是 -1、0 或 +1。这里，“平衡因子”是左右子树之间的高度差。+1 表示左子树比右子树高 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 树的文章有一张很好的图片，总结了所有可能需要应用的旋转。

希望这可以帮助！