AVLTree 类

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 createNewNode(E e) {
        return new AVLTreeNode(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 node) {
        if (node.left == null && node.right == null) // node is a leaf
            node.height = 0;
        else if (node.left == null) // node has no left subtree
            node.height = 1 + ((AVLTreeNode)(node.right)).height;
        else if (node.right == null) // node has no right subtree
            node.height = 1 + ((AVLTreeNode)(node.left)).height;
        else
            node.height = 1 + Math.max(((AVLTreeNode)(node.right)).height, ((AVLTreeNode)(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> path = path(e);
        for (int i = path.size() - 1; i >= 0; i--) {
            AVLTreeNode A = (AVLTreeNode)(path.get(i));
            updateHeight(A);
            AVLTreeNode parentOfA = (A == root) ? null : (AVLTreeNode)(path.get(i - 1));

            switch (balanceFactor(A)) {
            case -2:
                if (balanceFactor((AVLTreeNode)A.left) <= 0) {
                    balanceLL(A, parentOfA); // Perform LL rotation
                }
                else {
                    balanceLR(A, parentOfA); // Perform LR rotation
                }
                break;
                case +2:
                    if (balanceFactor((AVLTreeNode)A.right) >= 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 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)node.right).height - ((AVLTreeNode)node.left).height;
    }

    /** Balance LL (see Figure 26.2) */
    private void balanceLL(TreeNode A, TreeNode parentOfA) {
        TreeNode 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)A);
        updateHeight((AVLTreeNode)B);
    }

    /** Balance LR (see Figure 26.4) */
    private void balanceLR(TreeNode A, TreeNode parentOfA) {
        TreeNode B = A.left; // A is left-heavy
        TreeNode 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)A);
        updateHeight((AVLTreeNode)B);
        updateHeight((AVLTreeNode)C);
    }

    /** Balance RR (see Figure 26.3) */
    private void balanceRR(TreeNode A, TreeNode parentOfA) {
        TreeNode 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)A);
        updateHeight((AVLTreeNode)B);
    }

    /** Balance RL (see Figure 26.5) */
    private void balanceRL(TreeNode A, TreeNode parentOfA) {
        TreeNode B = A.right; // A is right-heavy
        TreeNode 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)A);
        updateHeight((AVLTreeNode)B);
        updateHeight((AVLTreeNode)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 parent = null;
        TreeNode current = root;
        while (current != null) {
            if (element.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            }
            else 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) < 0)
                    parent.left = current.right;
                else
                    parent.right = current.right;
                // Balance the tree if necessary
                balancePath(parent.element);
            }
        }
        else {
            // Case 2: The current node has a left child
            // Locate the rightmost node in the left subtree of
            // the current node and also its parent
            TreeNode parentOfRightMost = current;
            TreeNode 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> extends BST.TreeNode {
        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 行）。

Lateral App

整理归类论文

下载

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

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

treenode 参数（a 和 parentofa）进行调用，以在节点 a 处执行适当的旋转。帖子中的附图说明了如何执行每次旋转。旋转后，节点a、b和c的高度更新（第98、125、148、175行）。

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