当前位置：网站首页>AVL 平衡二叉搜索树

AVL 平衡二叉搜索树

2022-07-01 15:42:00 【颜然】

二叉搜索树（BST）虽能缩短查找效率，但如果数据有序或接近有序，BST将退化为单支树，此时查找元素就相当于在顺序表中搜索元素，效率低下。

那么此时如果能保证每个结点的左右子树高度差的绝对值不超过1，就可以降低树的高度，从而减少平均搜索长度。所以AVL带着这个使命诞生了。

一、AVL

在二叉树中，如果每个结点的子树的高度差距为0、1或-1，则称这棵树是平衡二叉树，即AVL。

二、平衡二叉树

执行插入或删除操作后如果导致了AVL的不平衡，那么我们需要执行旋转操作来重新平衡这棵树。旋转操作主要有LL、RR、LR、RL四种类型。

1、LL

向左子树中的左孩子插入新结点后导致不平衡，此时需要右旋操作：

旋转后平衡二叉树将B看作新root，将E结点与A.left相连，再将A与B.right相连，最后得到新的AVL。

    private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.left;
        if(A == root){
            root = B;
        }else{
            if(parentOfA.left == A){
                parentOfA.left = B;
            }else{
                parentOfA.right = B;
            }
        }

        A.left = B.right;
        B.right = A;
        updateHeight((AVLTreeNode<E>) A);

2、RR

和LL相反，向右子树中的右孩子插入新结点后导致的不平衡，此时需要左旋操作：

    private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B =A.right;

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

        A.right = B.left;
        B.left = A;
        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
    }

3、LR

左儿子左旋，根结点右旋：

    private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.left;
        TreeNode C = B.right;

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

        A.left = C.right;
        B.right = C.left;
        C.left = B;
        C.right = A;

        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
        updateHeight((AVLTreeNode<E>)C);
    }

4、RL

右儿子右旋，根结点左旋：

    private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.right;
        TreeNode<E> C = B.left;

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

        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
        updateHeight((AVLTreeNode<E>)C);
    }

三、Java实现AVLTree类

AVLTree类继承BST类。

public class AVLTree<E extends Comparable<E>> extends BST<E>{
    public AVLTree() {
    }

    public AVLTree(E[] objects) {
        super(objects);
    }

    // 插入方法和BST中的方法一样，只不过每次添加后需要检查平衡
    @Override
    public boolean insert(E e){
        boolean success = super.insert(e);
        if(!success){
            return false;
        }else{
            balancePath(e);  // 检查是否需要平衡操作
        }
        return true;
    }

    private void updateHeight(AVLTreeNode<E> node){
        if(node.left == null && node.right == null){
            node.height = 0;
        }else if(node.left == null){
            node.height = 1 + ((AVLTreeNode<E>)(node.right)).height;
        }else if(node.right == null){
            node.height = 1 + ((AVLTreeNode<E>)(node.left)).height;
        }else
            node.height = 1 + Math.max(((AVLTreeNode<E>)(node.right)).height,((AVLTreeNode<E>)(node.left)).height);
    }

    // 平衡一条路径上的结点
    private void balancePath(E e){
        java.util.ArrayList<TreeNode<E>> path = path(e);  // 获取包含e的结点到根结点的路径
        for(int i = path.size() - 1; i >= 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) <= 0){
                        balanceLL(A,parentOfA);
                    }else{
                        balanceLR(A,parentOfA);
                    }
                    break;
                case +2 :
                    if(balanceFactor((AVLTreeNode<E>)A.right) >= 0){
                        balanceRR(A, parentOfA);
                    }else{
                        balanceRL(A, parentOfA);
                    }
            }
        }
    }

    private int balanceFactor(AVLTreeNode<E> node){
        if(node.left == null){
            return -node.height;
        }else if(node.left == null){
            return +node.height;
        }else
            return ((AVLTreeNode<E>)node.right).height - ((AVLTreeNode<E>)node.left).height;
    }

    private void balanceLL(AVLTreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.left;
        if(A == root){
            root = B;
        }else{
            if(parentOfA.left == A){
                parentOfA.left = B;
            }else{
                parentOfA.right = B;
            }
        }

        A.left = B.right;
        B.right = A;
        updateHeight((AVLTreeNode<E>) A);
        updateHeight((AVLTreeNode<E>) B);
    }

    private void balanceLR(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.left;
        TreeNode C = B.right;

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

        A.left = C.right;
        B.right = C.left;
        C.left = B;
        C.right = A;

        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
        updateHeight((AVLTreeNode<E>)C);
    }

    private void balanceRR(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B =A.right;

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

        A.right = B.left;
        B.left = A;
        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
    }

    private void balanceRL(TreeNode<E> A, TreeNode<E> parentOfA){
        TreeNode<E> B = A.right;
        TreeNode<E> C = B.left;

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

        updateHeight((AVLTreeNode<E>)A);
        updateHeight((AVLTreeNode<E>)B);
        updateHeight((AVLTreeNode<E>)C);
    }

    // 和BST中的删除方法一样，只不过需要判断下是否平衡
    @Override
    public boolean delete(E element){
        if (root == null) {
            return false;
        }
        TreeNode<E> parent = null;
        TreeNode<E> 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;
        }
        if(current == null){
            return false;
        }

        if(current.left == null){
            if(parent == null){
                root = current.right;
            }else {
                if(element.compareTo(parent.element) < 0){
                    parent.left = current.right;
                }else{
                    parent.right = current.right;
                }
                balancePath(parent.element);
            }
        }else{
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;

            while(rightMost.right != null){
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }
            current.element = rightMost.element;

            if(parentOfRightMost.right == rightMost){
                parentOfRightMost.right = rightMost.left;
            }else{
                parentOfRightMost.left = rightMost.left;
            }
            balancePath(parentOfRightMost.element);
        }
        size--;
        return true;
    }

    protected static class AVLTreeNode<E> extends BST.TreeNode<E>{
        protected int height = 0;

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

四、测试AVLTree类

public class TestAVLTree {
    public static void main(String[] args){
        AVLTree<Integer> tree = new AVLTree<Integer>(new Integer[]{25, 20 ,5});
        System.out.print("After inserting 25,20,,5: ");
        printTree(tree);

        tree.insert(34);
        tree.insert(50);
        System.out.print("\nAfter inserting 34, 50 : ");
        printTree(tree);

        tree.insert(30);
        System.out.print("\nAfter inserting 30 : ");
        printTree(tree);

        tree.insert(10);
        System.out.print("\nAfter inserting 10 : ");
        printTree(tree);

        tree.delete(34);
        tree.delete(30);
        tree.delete(50);
        System.out.print("\nAfter removing 34, 30, 50: ");
        printTree(tree);

        tree.delete(5);
        System.out.print("\nAfter removing 5 : ");
        printTree(tree);

        System.out.print("\nTraverse the element in the tree: ");
        for(Object e : tree){
            System.out.print(e + " ");
        }
    }

    public static void printTree(BST tree){
        System.out.print("\nInorder (sorted) : ");
        tree.inorder();
        System.out.print("\nPostorder : ");
        tree.postorder();
        System.out.print("\nPreorder");
        tree.preorder();
        System.out.print("\nThe number of nodes is " + tree.getSize());
        System.out.println();
    }
}

程序插入图示：