Binary Search Tree — The Data Structures Atlas

Categoría: Trees

El problema

Un array ordenado ofrece búsqueda O(log n) mediante búsqueda binaria, pero insertar en el medio cuesta O(n) porque hay que desplazar todo lo que viene después. Una lista enlazada ofrece inserción O(1), pero búsqueda O(n). Ninguna de las dos ofrece búsqueda rápida e inserción rápida al mismo tiempo — y ninguna puede responder "cuál es la clave más cercana a X" sin un recorrido completo.

La solución

Mantén la clave de cada nodo mayor que todo lo que hay en su subárbol izquierdo y menor que todo lo que hay en su subárbol derecho. Ese único invariante es lo que permite que las búsquedas, inserciones y consultas de "clave más cercana" descarten la mitad del árbol restante en cada paso, de la misma manera que lo hace la búsqueda binaria — salvo que aquí es la propia estructura la que está ordenada, no un array subyacente, así que la inserción no necesita desplazar nada.

flowchart TD
    N50(("50")) --> N20(("20"))
    N50 --> N80(("80"))
    N20 --> N10(("10"))
    N20 --> N30(("30"))
    N80 --> N70(("70"))
    N80 --> N90(("90"))

Nada aquí se rebalancea. Esa es la trampa: el orden de inserción controla la forma del árbol. Un orden de inserción aleatorio tiende a una altura de aproximadamente O(log n). Un orden de inserción ordenado (o en orden inverso) degenera el árbol en una cadena recta — altura O(n), búsquedas O(n), nada mejor que una lista enlazada. El benchmark de abajo mide exactamente esa brecha; un futuro módulo AVL/Red-Black en este repositorio existe específicamente para cerrarla, rebalanceando en cada inserción.

Operación	Promedio (orden de inserción aleatorio)	Peor caso (orden de inserción ordenado)
`get` / `insert` / `delete`	O(log n)	O(n)
`floorEntry` (clave más cercana `<=` X)	O(log n)	O(n)
`inOrderKeys` (recorrido ordenado)	O(n)	O(n)

Ejemplo clásico

classic/BinarySearchTree implementa insert, get, delete, floorEntry y el recorrido en orden (in-order) desde cero. El delete maneja los tres casos clásicos — hoja, un hijo, dos hijos (empalmando el sucesor en orden, la clave más pequeña del subárbol derecho) — sin dejar rota la propiedad del BST. BinarySearchTreeTest cubre los tres casos de delete, más el caso degenerado directamente: insertar 100 claves en orden ascendente y verificar que la altura resultante sea exactamente 100.

Ejemplo aplicado: búsqueda de nivel de límite de transacción del BACEN

applied/TransactionLimitTierIndex resuelve qué nivel de límite de transacción PIX definido por el BACEN se aplica a un monto dado — los niveles se definen por umbral ("desde R$1.000 se aplica hasta que se cruza un umbral mayor"), así que responder "¿qué nivel cubre R$1.347,50?" requiere una búsqueda ordenada de piso (floor), no una de coincidencia exacta. Esta es la operación que una hash table estructuralmente no puede ofrecer mejor que un recorrido completo; un BST la resuelve en O(altura) por construcción. TransactionLimitTierIndexTest cubre un monto exactamente en un límite, un monto entre dos niveles y un monto por debajo de todos los umbrales registrados.

Benchmark

./gradlew :trees:binary-search-tree:jmh

Ejecución real (JMH 1.37, JDK 26.0.2, 2 iteraciones de calentamiento + 3 de medición, 1 fork). Mismo conjunto de claves, misma operación de búsqueda — la única variable es si el árbol se construyó a partir de un orden de inserción mezclado (shuffled) u ordenado.

Costo de `get`	size=100	size=1,000	size=10,000
orden de inserción aleatorio	18.9 ns	38.7 ns	32.3 ns
orden de inserción ordenado (degenerado)	115.7 ns	1,079.1 ns	22,575.8 ns

El costo de búsqueda del árbol con orden aleatorio se mantiene prácticamente plano a lo largo de un aumento de 100x en el tamaño — la forma que predice O(log n). El costo del árbol con orden ordenado, en cambio, crece casi linealmente con el tamaño — pasar de 1,000 a 10,000 claves (10x más datos) hace que las búsquedas sean ~21x más lentas, consistente con que el árbol se haya degenerado en una cadena de 10,000 nodos. Mismo código, mismos datos, solo cambió el orden de inserción — y por eso, precisamente, nada aquí se rebalancea solo, y por eso importa.

Cuándo no usarlo

Si el orden de inserción no se puede controlar o no es confiable (entrada ordenada o adversarial), un BST no balanceado degrada a una lista enlazada — ver el benchmark de arriba. Una variante autobalanceada (AVL, Red-Black) es la solución; este repositorio agregará una justamente para contrastarla con este módulo.
¿Solo necesitas búsqueda por coincidencia exacta, nunca orden ni consultas de rango/piso? Una hash table (ver el módulo Hash Table de este repositorio) da O(1) promedio en lugar de O(log n) para esa necesidad más acotada.
¿Necesitas una altura garantizada en el peor caso (no solo en el caso promedio)? Misma respuesta: un árbol balanceado.

Cobertura de pruebas

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

./gradlew :trees:binary-search-tree:jacocoTestReport

Reporte en trees/binary-search-tree/build/reports/jacoco/test/html/index.html.

Pruebas unitarias

src/test/java/com/datastructures/trees/binarysearchtree/classic/BinarySearchTreeTest.java

package com.datastructures.trees.binarysearchtree.classic;

import org.junit.jupiter.api.Test;

import java.util.Map;

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

class BinarySearchTreeTest {

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

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

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

        tree.insert(50, "root");

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

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

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

    @Test
    void insertingAnExistingKeyOverwritesItsValue() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "original");

        tree.insert(50, "replaced");

        assertThat(tree.get(50)).isEqualTo("replaced");
        assertThat(tree.size()).isEqualTo(1);
    }

    @Test
    void inOrderKeysAreAlwaysSortedRegardlessOfInsertionOrder() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 50, 70, 80, 90);
    }

    @Test
    void deletingALeafRemovesItAndNothingElse() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "50");
        tree.insert(20, "20");
        tree.insert(80, "80");

        tree.delete(20);

        assertThat(tree.contains(20)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(50, 80);
        assertThat(tree.size()).isEqualTo(2);
    }

    @Test
    void deletingANodeWithOneChildSplicesTheChildIntoItsPlace() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(50, "50");
        tree.insert(20, "20");
        tree.insert(10, "10");

        tree.delete(20);

        assertThat(tree.contains(20)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 50);
        assertThat(tree.get(10)).isEqualTo("10");
        assertThat(tree.size()).isEqualTo(2);
    }

    @Test
    void deletingANodeWithTwoChildrenSplicesInTheInOrderSuccessor() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        tree.delete(50);

        assertThat(tree.contains(50)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 70, 80, 90);
        assertThat(tree.size()).isEqualTo(6);
        // The successor (70) must have been spliced up, not just copied and left duplicated.
        assertThat(tree.get(70)).isEqualTo("v70");
    }

    @Test
    void deletingAKeyGreaterThanTheRootDescendsRightBeforeMatching() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        int[] insertionOrder = {50, 20, 80, 10, 30, 70, 90};
        for (int key : insertionOrder) {
            tree.insert(key, "v" + key);
        }

        tree.delete(90);

        assertThat(tree.contains(90)).isFalse();
        assertThat(tree.inOrderKeys()).containsExactly(10, 20, 30, 50, 70, 80);
        assertThat(tree.size()).isEqualTo(6);
    }

    @Test
    void deletingFromAnEmptyTreeIsANoOp() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();

        tree.delete(1);

        assertThat(tree.isEmpty()).isTrue();
    }

    @Test
    void floorEntryReturnsTheExactMatchWhenPresent() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");
        tree.insert(500, "tier-500");

        Map.Entry<Integer, String> floor = tree.floorEntry(500);

        assertThat(floor.getKey()).isEqualTo(500);
        assertThat(floor.getValue()).isEqualTo("tier-500");
    }

    @Test
    void floorEntryReturnsTheLargestKeyNotGreaterThanTheQuery() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");
        tree.insert(500, "tier-500");
        tree.insert(1000, "tier-1000");

        Map.Entry<Integer, String> floor = tree.floorEntry(750);

        assertThat(floor.getKey()).isEqualTo(500);
    }

    @Test
    void floorEntryReturnsNullWhenTheQueryIsBelowEveryStoredKey() {
        BinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
        tree.insert(100, "tier-100");

        assertThat(tree.floorEntry(50)).isNull();
    }

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

        assertThat(tree.height()).isEqualTo(100);
    }

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

        assertThat(tree.height()).isEqualTo(4);
    }
}

src/test/java/com/datastructures/trees/binarysearchtree/applied/TransactionLimitTierIndexTest.java

package com.datastructures.trees.binarysearchtree.applied;

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

import java.math.BigDecimal;
import java.util.Optional;

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

class TransactionLimitTierIndexTest {

    private final TransactionLimitTierIndex index = new TransactionLimitTierIndex();

    @BeforeEach
    void registerBacenTiers() {
        index.registerTier(new TransactionLimitTier(BigDecimal.ZERO, "daytime-standard", BigDecimal.ZERO));
        index.registerTier(new TransactionLimitTier(BigDecimal.valueOf(1000), "daytime-elevated", BigDecimal.valueOf(24)));
        index.registerTier(new TransactionLimitTier(BigDecimal.valueOf(10000), "daytime-high-value", BigDecimal.valueOf(72)));
    }

    @Test
    void amountExactlyOnABoundaryResolvesToThatTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(1000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-elevated");
    }

    @Test
    void amountBetweenTwoBoundariesResolvesToTheLowerTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(5000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-elevated");
    }

    @Test
    void amountAboveTheHighestBoundaryResolvesToTheHighestTier() {
        Optional<TransactionLimitTier> tier = index.tierFor(BigDecimal.valueOf(50000));

        assertThat(tier).isPresent();
        assertThat(tier.get().tierName()).isEqualTo("daytime-high-value");
    }

    @Test
    void amountBelowEveryRegisteredThresholdIsAbsentWhenNoZeroFloorTierExists() {
        TransactionLimitTierIndex indexWithoutZeroFloor = new TransactionLimitTierIndex();
        indexWithoutZeroFloor.registerTier(new TransactionLimitTier(BigDecimal.valueOf(1000), "daytime-elevated", BigDecimal.valueOf(24)));

        Optional<TransactionLimitTier> tier = indexWithoutZeroFloor.tierFor(BigDecimal.valueOf(500));

        assertThat(tier).isEmpty();
    }
}

Ver informe completo de cobertura JaCoCo →