avltree类扩展了bst类以重写insert和delete方法以在必要时重新平衡树。下面的代码给出了 avltree 类的完整源代码。

package demo;

public class AVLTree> extends BST {
/* Create an empty AVL tree /
public AVLTree() {}

/** Create an AVL tree from an array of objects */
public AVLTree(E[] objects) {
    super(objects);
}

@Override /** Override createNewNode to create an AVLTreeNode */
protected AVLTreeNode<e> createNewNode(E e) {
    return new AVLTreeNode<e>(e);
}

@Override /** Insert an element and rebalance if necessary */
public boolean insert(E e) {
    boolean successful = super.insert(e);
    if (!successful)
        return false; // e is already in the tree
    else {
        balancePath(e); // Balance from e to the root if necessary
    }

    return true; // e is inserted
}

/** Update the height of a specified node */
private void updateHeight(AVLTreeNode<e> node) {
    if (node.left == null &amp;&amp; node.right == null) // node is a leaf
        node.height = 0;
    else if (node.left == null) // node has no left subtree
        node.height = 1 + ((AVLTreeNode<e>)(node.right)).height;
    else if (node.right == null) // node has no right subtree
        node.height = 1 + ((AVLTreeNode<e>)(node.left)).height;
    else
        node.height = 1 + Math.max(((AVLTreeNode<e>)(node.right)).height, ((AVLTreeNode<e>)(node.left)).height);
}

/** Balance the nodes in the path from the specified
* node to the root if necessary
*/
private void balancePath(E e) {
    java.util.ArrayList<treenode>&gt; path = path(e);
    for (int i = path.size() - 1; i &gt;= 0; i--) {
        AVLTreeNode<e> A = (AVLTreeNode<e>)(path.get(i));
        updateHeight(A);
        AVLTreeNode<e> parentOfA = (A == root) ? null : (AVLTreeNode<e>)(path.get(i - 1));

        switch (balanceFactor(A)) {
        case -2:
            if (balanceFactor((AVLTreeNode<e>)A.left) )A.right) &gt;= 0) {
                    balanceRR(A, parentOfA); // Perform RR rotation
                }
            else {
                balanceRL(A, parentOfA); // Perform RL rotation
            }
        }
    }
}

/** Return the balance factor of the node */
private int balanceFactor(AVLTreeNode<e> node) {
    if (node.right == null) // node has no right subtree
        return -node.height;
    else if (node.left == null) // node has no left subtree
        return +node.height;
    else
        return ((AVLTreeNode<e>)node.right).height - ((AVLTreeNode<e>)node.left).height;
}

/** Balance LL (see Figure 26.2) */
private void balanceLL(TreeNode<e> A, TreeNode<e> parentOfA) {
    TreeNode<e> B = A.left; // A is left-heavy and B is left-heavy
    if (A == root) {
        root = B;
    }
    else {
        if (parentOfA.left == A) {
            parentOfA.left = B;
        }
        else {
            parentOfA.right = B;
        }
    }

    A.left = B.right; // Make T2 the left subtree of A
    B.right = A; // Make A the left child of B
    updateHeight((AVLTreeNode<e>)A);
    updateHeight((AVLTreeNode<e>)B);
}

/** Balance LR (see Figure 26.4) */
private void balanceLR(TreeNode<e> A, TreeNode<e> parentOfA) {
    TreeNode<e> B = A.left; // A is left-heavy
    TreeNode<e> C = B.right; // B is right-heavy

    if (A == root) {
        root = C;
    }
    else {
        if (parentOfA.left == A) {
            parentOfA.left = C;
        }
        else {
            parentOfA.right = C;
        }
    }

    A.left = C.right; // Make T3 the left subtree of A
    B.right = C.left; // Make T2 the right subtree of B
    C.left = B;
    C.right = A;

    // Adjust heights
    updateHeight((AVLTreeNode<e>)A);
    updateHeight((AVLTreeNode<e>)B);
    updateHeight((AVLTreeNode<e>)C);
}

/** Balance RR (see Figure 26.3) */
private void balanceRR(TreeNode<e> A, TreeNode<e> parentOfA) {
    TreeNode<e> B = A.right; // A is right-heavy and B is right-heavy

    if (A == root) {
        root = B;
    }
    else {
        if (parentOfA.left == A) {
            parentOfA.left = B;
        }
        else {
            parentOfA.right = B;
        }
    }

    A.right = B.left; // Make T2 the right subtree of A
    B.left = A;
    updateHeight((AVLTreeNode<e>)A);
    updateHeight((AVLTreeNode<e>)B);
}

/** Balance RL (see Figure 26.5) */
private void balanceRL(TreeNode<e> A, TreeNode<e> parentOfA) {
    TreeNode<e> B = A.right; // A is right-heavy
    TreeNode<e> C = B.left; // B is left-heavy

    if (A == root) {
        root = C;
    }
    else {
        if (parentOfA.left == A) {
            parentOfA.left = C;
        }
        else {
            parentOfA.right = C;
        }
    }

    A.right = C.left; // Make T2 the right subtree of A
    B.left = C.right; // Make T3 the left subtree of B
    C.left = A;
    C.right = B;

    // Adjust heights
    updateHeight((AVLTreeNode<e>)A);
    updateHeight((AVLTreeNode<e>)B);
    updateHeight((AVLTreeNode<e>)C);
}

@Override /** Delete an element from the AVL tree.
* Return true if the element is deleted successfully
* Return false if the element is not in the tree */
public boolean delete(E element) {
    if (root == null)
        return false; // Element is not in the tree

    // Locate the node to be deleted and also locate its parent node
    TreeNode<e> parent = null;
    TreeNode<e> current = root;
    while (current != null) {
        if (element.compareTo(current.element)  0) {
            parent = current;
            current = current.right;
        }
        else
            break; // Element is in the tree pointed by current
    }

    if (current == null)
        return false; // Element is not in the tree

    // Case 1: current has no left children (See Figure 25.10)
    if (current.left == null) {
        // Connect the parent with the right child of the current node
        if (parent == null) {
            root = current.right;
        }
        else {
            if (element.compareTo(parent.element)  parentOfRightMost = current;
        TreeNode<e> rightMost = current.left;

        while (rightMost.right != null) {
            parentOfRightMost = rightMost;
            rightMost = rightMost.right; // Keep going to the right
        }

        // Replace the element in current by the element in rightMost
        current.element = rightMost.element;

        // Eliminate rightmost node
        if (parentOfRightMost.right == rightMost)
            parentOfRightMost.right = rightMost.left;
        else
            // Special case: parentOfRightMost is current
            parentOfRightMost.left = rightMost.left;
        // Balance the tree if necessary
        balancePath(parentOfRightMost.element);
    }

    size--;
    return true; // Element inserted
}

/** AVLTreeNode is TreeNode plus height */
protected static class AVLTreeNode<e extends comparable>&gt; extends BST.TreeNode<e> {
    protected int height = 0; // New data field

    public AVLTreeNode(E e) {
        super(e);
    }
}

}

登录后复制

avltree 类扩展了bst。与 bst 类一样，avltree 类有一个无参构造函数，用于构造一个空的 avltree（第 5 行），以及一个从元素数组创建初始 avltree 的构造函数（第 8-10 行） .

bst类中定义的createnewnode()方法创建一个treenode。重写此方法以返回 avltreenode（第 13-15 行）。

avltree中的insert方法在第18-27行被覆盖。该方法首先调用bst中的insert方法，然后调用balancepath(e)（第23行）来确保树是平衡的。

balancepath方法首先获取从包含元素e的节点到根节点的路径上的节点（第45行）。对于路径中的每个节点，更新其高度（第 48 行），检查其平衡系数（第 51 行），并在必要时执行适当的旋转（第 51-67 行）。

第 82-178 行定义了四种执行旋转的方法。每个方法都使用两个 treenode 参数（a 和 parentofa）进行调用，以在节点 a 处执行适当的旋转。帖子中的附图说明了如何执行每次旋转。旋转后，节点a、b和c的高度更新（第98、125、148、175行）。

avltree中的delete方法在第183-248行被重写。该方法与bst类中实现的方法相同，只是在两种情况下需要在删除后重新平衡节点（第218、243行）。

    以上就是AVLTree 类的详细内容，更多请关注php中文网其它相关文章！