AVL Tree — The Data Structures Atlas

Categoria: Trees

O problema

O Binary Search Tree já demonstrou o problema aqui: a altura de uma BST simples depende inteiramente da ordem de inserção. Ordem aleatória tende a O(log n); ordem ordenada (ou adversarial) a degenera em uma cadeia reta, altura O(n), não melhor que uma lista ligada. Quem chama nem sempre pode controlar a ordem de inserção — e não deveria precisar, só para manter as buscas rápidas.

A solução

Depois de cada inserção, suba de volta em direção à raiz restaurando um invariante em cada nó: |height(left) - height(right)| <= 1. A inserção sempre cresce apenas uma subárvore em exatamente um nível, então um nó só pode sair de balanço em exatamente 2 — o que significa que uma única rotação (um dos quatro casos: left-left, right-right, left-right, right-left) sempre é suficiente para corrigi-lo antes de continuar subindo. Essa única garantia é o que torna a altura comprovadamente O(log n) independentemente da ordem de inserção — ordenada, ordenada ao contrário, adversarial, não importa.

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

Operação	Custo	Por quê
`insert`	O(log n) garantido	a altura é comprovadamente limitada; cada inserção faz no máximo uma rotação
`get` / `contains`	O(log n) garantido	mesmo limite de altura, descida no estilo BST simples
`height()`	O(1)	armazenado em cache por nó, atualizado durante as rotações em vez de recalculado

Exemplo clássico

classic/AvlTree implementa insert, get, contains e height() do zero, com os quatro casos de rotação. A remoção é deliberadamente deixada de fora do escopo — a remoção real em AVL precisa das mesmas quatro rotações mais o controle de emenda de dois filhos que o Binary Search Tree já cobre, sem nenhum valor didático novo. AvlTreeTest traça manualmente uma sequência de inserção dedicada para cada um dos quatro casos de rotação e — o ponto real do módulo — insere exatamente a mesma sequência ordenada de 100 chaves que degenera a altura da BinarySearchTree simples para 100, e verifica que a altura da árvore AVL permanece em 7.

Exemplo aplicado: índice de regras de uma plataforma de detecção de fraude

applied/FraudRuleIndex indexa regras de detecção de fraude pelo limiar de score de risco em que cada uma dispara. Equipes de compliance tendem a registrar regras em ordem crescente de limiar conforme novos níveis entram em vigor ("adicionar uma em 700, depois 750, depois 800...") — exatamente o padrão de inserção ordenada que degrada uma BST simples. Como a busca de regras fica no caminho crítico de cada transação pontuada, um O(log n) garantido independentemente da ordem de registro é o requisito real, não apenas o caso comum. FraudRuleIndexTest cobre a busca por limiar exato e o caso de limiar inexistente.

Benchmark

./gradlew :trees:avl-tree:jmh

Execução real (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 de medição, 1 fork) — custo de get() no próprio BinarySearchTree deste repositório (via uma dependência real de project(":trees:binary-search-tree")) contra o AvlTree deste módulo, cada um construído tanto a partir de uma sequência de chaves embaralhada aleatoriamente quanto de uma sequência ordenada:

Custo de `get` (ns/op)	size=100	size=1,000	size=10,000
BST, ordem de inserção aleatória	20.8	44.1	31.2
BST, ordem de inserção ordenada	128.0	1,253.7	21,514.5
AVL, ordem de inserção aleatória	18.5	20.9	36.0
AVL, ordem de inserção ordenada	24.1	29.5	27.8

A BST simples explode com entrada ordenada — ~168x mais lenta em size=10,000 do que sua própria execução em ordem aleatória. A árvore AVL quase não percebe em que ordem as mesmas chaves chegaram: seus números em ordem ordenada e em ordem aleatória ficam na mesma faixa estreita em todos os tamanhos. Essa é a garantia, tornada mensurável em vez de apenas afirmada.

Quando não usar

A remoção não está implementada aqui. Se uma carga de trabalho real precisar de remoção balanceada, essa é uma complexidade adicional real que este módulo deliberadamente não assumiu — veja a nota do exemplo clássico.
Leitura intensa, escrita rara, e a ordem de inserção já é efetivamente aleatória? Um Binary Search Tree simples é mais simples e igualmente rápido nesse caso específico — a garantia da AVL é um seguro contra um risco de ordem de inserção que talvez nem exista.
Precisa de desempenho médio mais próximo do de árvores Red-Black sob inserção/remoção intercaladas intensas (menos rotações por remoção, ao custo de uma garantia de balanceamento um pouco mais frouxa)? Essa é uma estrutura diferente, relacionada, que este repositório ainda não implementa.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :trees:avl-tree:jacocoTestReport

Relatório em trees/avl-tree/build/reports/jacoco/test/html/index.html.

Testes unitários

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

Ver relatório completo de cobertura JaCoCo →