AVL Tree — The Data Structures Atlas

Category: Trees

The problem

Binary Search Tree already proved the problem here: a plain BST's height depends entirely on insertion order. Random order tends toward O(log n); sorted (or adversarial) order degenerates it into a straight chain, O(n) height, no better than a linked list. A caller can't always control insertion order — and shouldn't have to, just to keep lookups fast.

The solution

After every insert, walk back up toward the root restoring one invariant at every node: |height(left) - height(right)| <= 1. Insert only ever grows one subtree by exactly one level, so a node can only ever fall out of balance by exactly 2 — which means a single rotation (one of four cases: left-left, right-right, left-right, right-left) is always enough to fix it before continuing back up. That single guarantee is what makes height provably O(log n) regardless of insertion order — sorted, reverse-sorted, adversarial, it doesn't matter.

flowchart TD
    subgraph "Before: right-heavy at 10"
        A1["10"] --> A2["null"]
        A1 --> A3["20"]
        A3 --> A4["null"]
        A3 --> A5["30"]
    end
    subgraph "After: rotateLeft(10)"
        B1["20"] --> B2["10"]
        B1 --> B3["30"]
    end

Operation	Cost	Why
`insert`	O(log n) guaranteed	height is provably bounded; each insert does at most one rotation
`get` / `contains`	O(log n) guaranteed	same height bound, plain BST-style descent
`height()`	O(1)	cached per node, updated during rotations instead of recomputed

Classic example

classic/AvlTree implements insert, get, contains, and height() from scratch, with all four rotation cases. Delete is deliberately out of scope — real AVL deletion needs the same four rotations plus the two-children splice bookkeeping Binary Search Tree already covers, for no new teaching value. AvlTreeTest hand-traces a dedicated insertion sequence for each of the four rotation cases, and — the module's real point — inserts the exact same 100-key sorted sequence that degenerates the plain BinarySearchTree's height to 100, and asserts the AVL tree's height stays at 7.

Applied example: fraud-detection platform's rule index

applied/FraudRuleIndex indexes fraud-detection rules by the risk-score threshold each one fires at. Compliance teams tend to register rules in ascending threshold order as new tiers roll out ("add one at 700, then 750, then 800...") — precisely the sorted-insertion pattern that degrades a plain BST. Since rule lookup sits on the hot path of every scored transaction, a guaranteed O(log n) regardless of registration order is the actual requirement, not just the common case. FraudRuleIndexTest covers exact-threshold lookup and the missing-threshold case.

Benchmark

./gradlew :trees:avl-tree:jmh

Real run (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork) — get() cost on this repo's own BinarySearchTree (via a real project(":trees:binary-search-tree") dependency) versus this module's AvlTree, each built from both a random-shuffled and a sorted key sequence:

`get` cost (ns/op)	size=100	size=1,000	size=10,000
BST, random insert order	20.8	44.1	31.2
BST, sorted insert order	128.0	1,253.7	21,514.5
AVL, random insert order	18.5	20.9	36.0
AVL, sorted insert order	24.1	29.5	27.8

The plain BST explodes on sorted input — ~168x slower at size=10,000 than its own random-order run. The AVL tree barely notices which order the same keys arrived in: its sorted-order and random-order numbers sit in the same narrow band at every size. That's the guarantee, made measurable rather than just asserted.

When not to use it

Delete isn't implemented here. If a real workload needs balanced deletion, that's real additional complexity this module deliberately didn't take on — see the classic example note.
Read-heavy, write-rarely, and insertion order is already effectively random? A plain Binary Search Tree is simpler and just as fast in that specific case — the AVL guarantee is insurance against an insertion-order risk that may not exist.
Need average-case performance closer to Red-Black trees under heavy interleaved insert/delete (fewer rotations per delete, at the cost of a slightly looser balance guarantee)? That's a different, related structure this repo doesn't (yet) implement.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :trees:avl-tree:jacocoTestReport

Report at trees/avl-tree/build/reports/jacoco/test/html/index.html.

Unit tests

src/test/java/com/datastructures/trees/avltree/classic/AvlTreeTest.java

package com.datastructures.trees.avltree.classic;

import com.datastructures.trees.binarysearchtree.classic.BinarySearchTree;
import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class AvlTreeTest {

    @Test
    void startsEmpty() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        assertThat(tree.isEmpty()).isTrue();
        assertThat(tree.size()).isZero();
        assertThat(tree.height()).isZero();
    }

    @Test
    void insertThenGetReturnsTheStoredValue() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        tree.insert(50, "root");

        assertThat(tree.get(50)).isEqualTo("root");
        assertThat(tree.contains(50)).isTrue();
        assertThat(tree.isEmpty()).isFalse();
        assertThat(tree.height()).isEqualTo(1);
    }

    @Test
    void getOnAMissingKeyReturnsNull() {
        AvlTree<Integer, String> tree = new AvlTree<>();
        tree.insert(50, "root");

        assertThat(tree.get(99)).isNull();
        assertThat(tree.contains(99)).isFalse();
    }

    @Test
    void insertingAnExistingKeyOverwritesItsValueWithoutChangingShapeOrSize() {
        AvlTree<Integer, String> tree = new AvlTree<>();
        tree.insert(50, "original");
        tree.insert(20, "20");
        int heightBefore = tree.height();

        tree.insert(50, "replaced");

        assertThat(tree.get(50)).isEqualTo("replaced");
        assertThat(tree.size()).isEqualTo(2);
        assertThat(tree.height()).isEqualTo(heightBefore);
    }

    // --- The four rotation cases. Each sequence is hand-picked so the third insert is the one
    // that pushes the tree's root out of balance, and the resulting height (2, not 3) is what
    // proves a rotation actually happened rather than the tree just being left lopsided.

    @Test
    void leftLeftInsertionOrderTriggersASingleRightRotation() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        tree.insert(30, "30");
        tree.insert(20, "20");
        tree.insert(10, "10"); // 30 becomes unbalanced left-left; single right rotation at 30

        assertThat(tree.height()).isEqualTo(2);
        assertThat(tree.get(30)).isEqualTo("30");
        assertThat(tree.get(20)).isEqualTo("20");
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.size()).isEqualTo(3);
    }

    @Test
    void rightRightInsertionOrderTriggersASingleLeftRotation() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        tree.insert(10, "10");
        tree.insert(20, "20");
        tree.insert(30, "30"); // 10 becomes unbalanced right-right; single left rotation at 10

        assertThat(tree.height()).isEqualTo(2);
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.get(20)).isEqualTo("20");
        assertThat(tree.get(30)).isEqualTo("30");
        assertThat(tree.size()).isEqualTo(3);
    }

    @Test
    void leftRightInsertionOrderTriggersALeftRotationThenARightRotation() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        tree.insert(30, "30");
        tree.insert(10, "10");
        tree.insert(20, "20"); // 30 becomes left-heavy with a right-leaning left child

        assertThat(tree.height()).isEqualTo(2);
        assertThat(tree.get(30)).isEqualTo("30");
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.get(20)).isEqualTo("20");
        assertThat(tree.size()).isEqualTo(3);
    }

    @Test
    void rightLeftInsertionOrderTriggersARightRotationThenALeftRotation() {
        AvlTree<Integer, String> tree = new AvlTree<>();

        tree.insert(10, "10");
        tree.insert(30, "30");
        tree.insert(20, "20"); // 10 becomes right-heavy with a left-leaning right child

        assertThat(tree.height()).isEqualTo(2);
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.get(30)).isEqualTo("30");
        assertThat(tree.get(20)).isEqualTo("20");
        assertThat(tree.size()).isEqualTo(3);
    }

    @Test
    void sortedInsertionOrderThatDegeneratesAPlainBstStaysBalancedInAnAvlTree() {
        AvlTree<Integer, String> avlTree = new AvlTree<>();
        BinarySearchTree<Integer, String> plainBst = new BinarySearchTree<>();
        for (int key = 0; key < 100; key++) {
            avlTree.insert(key, "v" + key);
            plainBst.insert(key, "v" + key);
        }

        // Same 100-key sorted sequence that this repo's BinarySearchTreeTest proves degenerates
        // the plain BST's height to exactly 100 (a straight chain). The AVL tree rebalances on
        // every insert, so its height stays at exactly 7 instead — right in line with the
        // theoretical log2(100) ≈ 6.64.
        assertThat(plainBst.height()).isEqualTo(100);
        assertThat(avlTree.height()).isEqualTo(7);
        assertThat(avlTree.size()).isEqualTo(100);
        for (int key = 0; key < 100; key++) {
            assertThat(avlTree.get(key)).isEqualTo("v" + key);
        }
    }

    @Test
    void randomishInsertionOrderStaysWellBelowTheDegenerateHeight() {
        AvlTree<Integer, String> tree = new AvlTree<>();
        int[] order = {50, 25, 75, 12, 37, 62, 87, 6, 18, 31, 43, 56, 68, 81, 93};
        for (int key : order) {
            tree.insert(key, "v" + key);
        }

        assertThat(tree.height()).isLessThanOrEqualTo(4);
        assertThat(tree.size()).isEqualTo(order.length);
    }
}

src/test/java/com/datastructures/trees/avltree/applied/FraudRuleIndexTest.java

package com.datastructures.trees.avltree.applied;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.Optional;

import static org.assertj.core.api.Assertions.assertThat;

class FraudRuleIndexTest {

    private final FraudRuleIndex index = new FraudRuleIndex();

    @BeforeEach
    void registerRulesInAscendingThresholdOrder() {
        // Ascending registration order is deliberate: it's the realistic ops workflow (tiers
        // rolled out low-to-high) and exactly the order that would degenerate a plain BST.
        index.registerRule(new FraudRule(300, "low-risk-flag", "LOG_ONLY"));
        index.registerRule(new FraudRule(700, "elevated-risk-review", "FLAG_FOR_REVIEW"));
        index.registerRule(new FraudRule(900, "high-risk-block", "BLOCK"));
    }

    @Test
    void ruleAtARegisteredThresholdIsFound() {
        Optional<FraudRule> rule = index.ruleAt(700);

        assertThat(rule).isPresent();
        assertThat(rule.get().action()).isEqualTo("FLAG_FOR_REVIEW");
        assertThat(index.hasRuleAt(700)).isTrue();
    }

    @Test
    void thereIsNoRuleAtAnUnregisteredThreshold() {
        Optional<FraudRule> rule = index.ruleAt(750);

        assertThat(rule).isEmpty();
        assertThat(index.hasRuleAt(750)).isFalse();
    }

    @Test
    void registeringAtAnExistingThresholdReplacesTheRule() {
        index.registerRule(new FraudRule(700, "elevated-risk-review-v2", "STEP_UP_AUTH"));

        Optional<FraudRule> rule = index.ruleAt(700);

        assertThat(rule).isPresent();
        assertThat(rule.get().ruleId()).isEqualTo("elevated-risk-review-v2");
        assertThat(index.size()).isEqualTo(3);
    }

    @Test
    void sizeReflectsTheNumberOfDistinctRegisteredThresholds() {
        assertThat(index.size()).isEqualTo(3);
    }
}

View full JaCoCo coverage report →