AVL Tree — The Data Structures Atlas

Categoría: Trees

El problema

El Binary Search Tree ya demostró el problema aquí: la altura de un BST simple depende enteramente del orden de inserción. Un orden aleatorio tiende a O(log n); un orden ordenado (o adversarial) lo degenera en una cadena recta, altura O(n), no mejor que una lista enlazada. Quien lo invoca no siempre puede controlar el orden de inserción — y no debería tener que hacerlo solo para mantener las búsquedas rápidas.

La solución

Después de cada inserción, sube de vuelta hacia la raíz restaurando un invariante en cada nodo: |height(left) - height(right)| <= 1. La inserción siempre hace crecer un solo subárbol en exactamente un nivel, así que un nodo solo puede desbalancearse en exactamente 2 — lo que significa que una sola rotación (uno de cuatro casos: left-left, right-right, left-right, right-left) siempre es suficiente para corregirlo antes de continuar subiendo. Esa única garantía es lo que hace que la altura sea demostrablemente O(log n) sin importar el orden de inserción — ordenado, ordenado en reversa, adversarial, no 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

Operación	Costo	Por qué
`insert`	O(log n) garantizado	la altura está demostrablemente acotada; cada inserción hace como máximo una rotación
`get` / `contains`	O(log n) garantizado	mismo límite de altura, descenso al estilo BST simple
`height()`	O(1)	almacenado en caché por nodo, actualizado durante las rotaciones en lugar de recalculado

Ejemplo clásico

classic/AvlTree implementa insert, get, contains y height() desde cero, con los cuatro casos de rotación. La eliminación queda deliberadamente fuera de alcance — la eliminación real en AVL necesita las mismas cuatro rotaciones más el control de empalme de dos hijos que el Binary Search Tree ya cubre, sin ningún valor didáctico nuevo. AvlTreeTest traza a mano una secuencia de inserción dedicada para cada uno de los cuatro casos de rotación y — el punto real del módulo — inserta exactamente la misma secuencia ordenada de 100 claves que degenera la altura del BinarySearchTree simple a 100, y verifica que la altura del árbol AVL se mantiene en 7.

Ejemplo aplicado: índice de reglas de una plataforma de detección de fraude

applied/FraudRuleIndex indexa reglas de detección de fraude por el umbral de score de riesgo en el que cada una se dispara. Los equipos de compliance tienden a registrar reglas en orden ascendente de umbral a medida que se lanzan nuevos niveles ("agregar una en 700, luego 750, luego 800...") — precisamente el patrón de inserción ordenada que degrada un BST simple. Como la búsqueda de reglas está en el camino crítico de cada transacción puntuada, un O(log n) garantizado sin importar el orden de registro es el requisito real, no solo el caso común. FraudRuleIndexTest cubre la búsqueda por umbral exacto y el caso de umbral inexistente.

Benchmark

./gradlew :trees:avl-tree:jmh

Ejecución real (JMH 1.37, JDK 26.0.2, 2 iteraciones de calentamiento + 3 de medición, 1 fork) — costo de get() en el propio BinarySearchTree de este repositorio (vía una dependencia real de project(":trees:binary-search-tree")) frente al AvlTree de este módulo, cada uno construido tanto a partir de una secuencia de claves mezclada aleatoriamente como de una secuencia ordenada:

Costo de `get` (ns/op)	size=100	size=1,000	size=10,000
BST, orden de inserción aleatorio	20.8	44.1	31.2
BST, orden de inserción ordenado	128.0	1,253.7	21,514.5
AVL, orden de inserción aleatorio	18.5	20.9	36.0
AVL, orden de inserción ordenado	24.1	29.5	27.8

El BST simple explota con entrada ordenada — ~168x más lento en size=10,000 que su propia ejecución en orden aleatorio. El árbol AVL casi no nota en qué orden llegaron las mismas claves: sus números en orden ordenado y en orden aleatorio se mantienen en la misma banda estrecha en todos los tamaños. Esa es la garantía, hecha medible en lugar de simplemente afirmada.

Cuándo no usarlo

La eliminación no está implementada aquí. Si una carga de trabajo real necesita eliminación balanceada, esa es una complejidad adicional real que este módulo deliberadamente no asumió — ver la nota del ejemplo clásico.
¿Lectura intensiva, escritura poco frecuente, y el orden de inserción ya es efectivamente aleatorio? Un Binary Search Tree simple es más simple e igual de rápido en ese caso específico — la garantía del AVL es un seguro contra un riesgo de orden de inserción que tal vez ni siquiera exista.
¿Necesitas un rendimiento promedio más cercano al de los árboles Red-Black bajo inserción/eliminación intercaladas intensas (menos rotaciones por eliminación, a costa de una garantía de balanceo un poco más laxa)? Esa es una estructura diferente, relacionada, que este repositorio (todavía) no implementa.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de ramas (JaCoCo). Reprodúcelo tú mismo:

./gradlew :trees:avl-tree:jacocoTestReport

Informe en trees/avl-tree/build/reports/jacoco/test/html/index.html.

Pruebas unitarias

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 informe completo de cobertura JaCoCo →