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