Binary Search Tree — The Data Structures Atlas

Categoria: Trees

O problema

Um array ordenado oferece busca O(log n) via busca binária, mas inserir no meio custa O(n) para deslocar tudo que vem depois. Uma lista encadeada oferece inserção O(1), mas busca O(n). Nenhum dos dois oferece busca rápida e inserção rápida ao mesmo tempo — e nenhum consegue responder "qual a chave mais próxima de X" sem uma varredura.

A solução

Mantenha a chave de cada nó maior do que tudo em sua subárvore esquerda e menor do que tudo em sua subárvore direita. Esse único invariante é o que permite que buscas, inserções e consultas de "chave mais próxima" descartem metade da árvore restante a cada passo, da mesma forma que a busca binária faz — exceto que é a própria estrutura que está ordenada, não um array subjacente, então a inserção não precisa deslocar nada.

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

Nada aqui se rebalanceia. Essa é a pegadinha: a ordem de inserção controla o formato da árvore. Uma ordem de inserção aleatória tende a uma altura de aproximadamente O(log n). Uma ordem de inserção ordenada (ou em ordem reversa) degenera a árvore em uma cadeia reta — altura O(n), buscas O(n), nada melhor do que uma lista encadeada. O benchmark abaixo mede exatamente essa diferença; um futuro módulo AVL/Red-Black neste repositório existe justamente para eliminá-la, rebalanceando a cada inserção.

Operação	Média (ordem de inserção aleatória)	Pior caso (ordem de inserção ordenada)
`get` / `insert` / `delete`	O(log n)	O(n)
`floorEntry` (chave mais próxima `<=` X)	O(log n)	O(n)
`inOrderKeys` (percurso ordenado)	O(n)	O(n)

Exemplo clássico

classic/BinarySearchTree implementa insert, get, delete, floorEntry e o percurso em ordem (in-order) do zero. O delete trata os três casos clássicos — folha, um filho, dois filhos (encaixando o sucessor em ordem, a menor chave da subárvore direita) — sem deixar a propriedade da BST quebrada. BinarySearchTreeTest cobre os três casos de delete, além do caso degenerado diretamente: inserir 100 chaves em ordem crescente e verificar que a altura resultante é exatamente 100.

Exemplo aplicado: consulta de faixa de limite de transação do BACEN

applied/TransactionLimitTierIndex resolve qual faixa de limite de transação PIX definida pelo BACEN se aplica a um determinado valor — as faixas são definidas por limiar ("a partir de R$1.000 aplica-se até que um limiar maior seja ultrapassado"), então responder "qual faixa cobre R$1.347,50?" exige uma busca ordenada por piso (floor), não uma busca por correspondência exata. Essa é a operação que uma hash table estruturalmente não consegue oferecer melhor do que uma varredura completa; uma BST responde isso em O(altura) por construção. TransactionLimitTierIndexTest cobre um valor exatamente em uma fronteira, um valor entre duas faixas e um valor abaixo de todos os limiares cadastrados.

Benchmark

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

Execução real (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 de medição, 1 fork). Mesmo conjunto de chaves, mesma operação de busca — a única variável é se a árvore foi construída a partir de uma ordem de inserção embaralhada ou ordenada.

Custo de `get`	size=100	size=1,000	size=10,000
ordem de inserção aleatória	18.9 ns	38.7 ns	32.3 ns
ordem de inserção ordenada (degenerada)	115.7 ns	1,079.1 ns	22,575.8 ns

O custo de busca da árvore com ordem aleatória permanece praticamente estável ao longo de um aumento de 100x no tamanho — o formato que O(log n) prevê. Já o custo da árvore com ordem ordenada cresce quase linearmente com o tamanho — passar de 1,000 para 10,000 chaves (10x mais dados) torna as buscas ~21x mais lentas, consistente com a árvore ter degenerado em uma cadeia de 10,000 nós. Mesmo código, mesmos dados, apenas a ordem de inserção mudou — e é exatamente por isso que nada aqui se rebalanceia sozinho, e por que isso importa.

Quando não usar

Se a ordem de inserção não pode ser controlada ou não é confiável (entrada ordenada ou adversarial), uma BST não balanceada degrada para uma lista encadeada — veja o benchmark acima. Uma variante autobalanceada (AVL, Red-Black) é a correção; este repositório vai adicionar uma justamente para contrastar com este módulo.
Só precisa de busca por correspondência exata, nunca de ordenação ou consultas de intervalo/piso? Uma hash table (veja o módulo Hash Table deste repositório) oferece O(1) médio em vez de O(log n) para essa necessidade mais restrita.
Precisa de uma garantia de altura no pior caso (não só no caso médio)? Mesma resposta: uma árvore balanceada.

Cobertura de testes

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

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

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

Testes unitários

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 relatório completo de cobertura JaCoCo →