AVL balanced binary search tree

Binary search tree （BST） Although it can shorten the search efficiency , but If the data is in order or close to order ,BST take Degenerate into a single tree , At this point, searching for elements is equivalent to The order sheet Search elements in , inefficiency .

At this time, if we can ensure that the absolute value of the height difference between the left and right subtrees of each node does not exceed 1, You can reduce the height of the tree , This reduces the average search length . therefore AVL With this mission was born .

One 、AVL 

In a binary tree , If the height difference of the subtree of each node is 0、1 or -1, Call this tree a balanced binary tree , namely AVL.

Two 、 Balanced binary trees

If the insert or delete operation results in AVL The imbalance of , Then we need to perform a rotation operation to rebalance the tree . Rotation operations mainly include LL、RR、LR、RL Four types .

1、LL

towards The left child in the left subtree inserts New nodes lead to imbalance , At this time need Right hand operation ：

After rotation, the balanced binary tree will B As new root,  take E Node and A.left Connected to a , then A And B.right Connected to a , Finally get a new 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

and LL contrary , towards The right child in the right subtree inserts Imbalance caused by new nodes , At this time need left-handed operation ： 

    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 

Left son left rotation , Root node dextral ：

    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

Right son right rotation , Left rotation of root node ：

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

  3、 ... and 、Java Realization AVLTree class

AVLTree Class inheritance BST class .

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

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

    //  Insertion method and BST In the same way , Just check the balance after each addition 
    @Override
    public boolean insert(E e){
        boolean success = super.insert(e);
        if(!success){
            return false;
        }else{
            balancePath(e);  //  Check whether balancing operation is required 
        }
        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);
    }

    //  Balance the nodes on a path 
    private void balancePath(E e){
        java.util.ArrayList<TreeNode<E>> path = path(e);  //  Get contains e The path from the node of to the root node 
        for(int i = path.size() - 1; i >= 0; i--){
            AVLTreeNode<E> A = (AVLTreeNode<E>)(path.get(i));
            updateHeight(A);  //  Update height 
            AVLTreeNode<E> parentOfA = (A == root) ? null : (AVLTreeNode<E>)(path.get(i - 1));

            switch(balanceFactor(A)){  //  Check the balance factor , Check if rotation is required 
                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);
    }

    //  and BST The deletion method in is the same , Just need to judge whether it is balanced 
    @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);
        }
    }
}

Four 、 test AVLTree class

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

Program insertion diagram ： 

  Program delete icon ：