Java AVL deletion: rebalance every surviving ancestor

Last updated: 29 Sept 20264 min read

tutorial

AVL deletion removes a search-tree key and repairs subtree heights on the path back to the root, including rotations caused by the reduced subtree.

Download Java source kit

Java 8+. The program uses JDK classes and requires no preview flags.

Insertion cases are not enough

A shipment index can stay balanced during insertion and become skewed after deletion. Removing a leaf changes the height seen by its parent. That parent may rotate, and the height change can continue upward. Stopping after the first repaired node can leave another ancestor outside the balance rule.

For a node with two children, this implementation copies its successor key and removes that successor from the right subtree. Key copying is acceptable for this integer-set model. An index storing node identities or mutable payloads needs a separate decision about identity and ownership.

The child balance chooses the rotation. After deletion, a heavy child can have balance zero; that case still permits a single rotation. Reusing insertion’s newly inserted-key tests would make the deletion decision depend on a key that no longer describes the surviving subtree.

Treat absent keys as a normal result

Deleting an absent shipment leaves membership unchanged. The recursive path still returns the existing subtree roots, and cached heights are recomputed before they are used. The property suite compares repeated deletions with TreeSet and checks ordering, cached height and balance at every node.

Working program

public class DeletableShipmentAvl {
    static class Node {int key,height=1;Node left,right;Node(int key){this.key=key;}}
    Node root;
    static int height(Node n){return n==null?0:n.height;}
    static int balance(Node n){return n==null?0:height(n.left)-height(n.right);}
    static void update(Node n){n.height=1+Math.max(height(n.left),height(n.right));}
    static Node right(Node n){Node next=n.left;n.left=next.right;next.right=n;update(n);update(next);return next;}
    static Node left(Node n){Node next=n.right;n.right=next.left;next.left=n;update(n);update(next);return next;}
    static Node repair(Node n){
        if(n==null)return null;update(n);
        if(balance(n)>1){if(balance(n.left)<0)n.left=left(n.left);return right(n);}
        if(balance(n)<-1){if(balance(n.right)>0)n.right=right(n.right);return left(n);}
        return n;
    }
    static Node add(Node n,int key){
        if(n==null)return new Node(key);
        if(key<n.key)n.left=add(n.left,key);else if(key>n.key)n.right=add(n.right,key);else return n;
        return repair(n);
    }
    static Node remove(Node n,int key){
        if(n==null)return null;
        if(key<n.key)n.left=remove(n.left,key);else if(key>n.key)n.right=remove(n.right,key);
        else {
            if(n.left==null)return n.right;if(n.right==null)return n.left;
            Node successor=n.right;while(successor.left!=null)successor=successor.left;
            n.key=successor.key;n.right=remove(n.right,successor.key);
        }return repair(n);
    }
    static void ordered(Node n,java.util.List<Integer> values){if(n!=null){ordered(n.left,values);values.add(n.key);ordered(n.right,values);}}
    public static void main(String[] args){
        DeletableShipmentAvl index=new DeletableShipmentAvl();
        for(int key:new int[]{40,20,60,10,30,50,70,5})index.root=add(index.root,key);
        index.root=remove(index.root,40);index.root=remove(index.root,5);index.root=remove(index.root,999);
        java.util.List<Integer> values=new java.util.ArrayList<>();ordered(index.root,values);System.out.println(values);
    }
}

Output

[10, 20, 30, 50, 60, 70]

Costs and boundaries

A maintained AVL height makes lookup, insertion and deletion O(log n). Recursive stack storage is O(log n). Exporting the ordered list is O(n) and allocates n result positions. This set model does not preserve the identity of a two-child node’s former key.

Common Mistakes

Repair every surviving ancestor on the return path.
Deletion must handle a heavy child with zero balance.
Key copying can be wrong for an identity-sensitive payload model.