O que é uma Binary Search Tree
Uma binary search tree é uma binary tree com uma regra adicionada: para todo node, tudo na sua subtree esquerda é menor, e tudo na sua subtree direita é maior.
Essa é a diferença inteira em relação ao artigo anterior, e é a diferença entre uma forma e uma estrutura de busca. A regra transforma os dois children de "o da esquerda" e "o da direita" numa instrução: compare, e vá para um lado. Toda comparação descarta uma subtree inteira.
Procurando uma palavra num dicionário de papel, ninguém começa na página um. Você abre em algum lugar perto do meio, lê a palavra do topo, e aquela única palavra te diz qual metade jogar fora. Depois faz de novo na metade que sobrou.
Você nunca precisou de índice, e nunca teve que olhar as palavras que pulou. Tudo que você precisou foi que as páginas estivessem em ordem, mais a capacidade de olhar uma e comparar. Uma binary search tree é esse arranjo construído com nodes: uma comparação por node, metade dos dados restantes descartada a cada vez.
todo valor sob a esquerda de 50 está abaixo de 50, todo valor sob a direita está acima
O problema que uma Binary Tree não resolvia
O artigo anterior terminou numa reclamação específica. Uma binary tree restringe onde os nodes podem estar — full, complete, perfect — mas não diz nada sobre qual valor vai onde. Então achar um valor significava verificar todo node, O(n), na melhor forma e na pior. A forma era previsível e o conteúdo não.
Compare os dois direto. Numa binary tree comum, chegar num node que não é o valor que você quer não te diz nada: o valor pode estar em qualquer uma das subtrees, então você tem que tentar as duas. Numa search tree, a mesma comparação falha te diz exatamente qual subtree não pode conter o valor, e você nunca olha lá.
Esse único bit de informação por node é o que transforma O(n) em . E como o artigo anterior estabeleceu que uma binary tree arrumada tem height log₂ n, isso é O(log n) — 20 comparações num milhão de nodes.
A invariante
A regra vale ser dita com cuidado, porque a versão descuidada é sutilmente errada e o erro é extremamente comum.
Para todo node: todo valor na subtree esquerda é menor que o node, e todo valor na subtree direita é maior que ele.
A palavra que carrega o peso é todo.
Ela é recursiva, não local
O atalho tentador é verificar cada node contra seus dois children — child da esquerda menor, da direita maior — e considerar resolvido. Essa verificação aceita trees que não são search trees de jeito nenhum.
60 é o child direito de 30, então é maior que seu parent — e está na subtree esquerda de 50 sendo maior que 50
Olhe o 60. Contra seu parent ele é perfeitamente legal: é o child direito de 30 e 60 > 30. Mas ele vive na subtree esquerda de 50, e 60 > 50, o que quebra a regra. Busque 60 nessa tree e você vai para a direita na root, para dentro da subtree que não o contém, e reporta que não existe.
A verificação correta carrega limites tree abaixo: um node na subtree esquerda de 50 tem que ser menor que 50, e se ele também está na subtree direita de 30 tem que ser maior que 30. Cada passo estreita a janela.
Lida da esquerda para a direita dá ordem crescente
Uma consequência da invariante vale ser nomeada porque é o que faz uma BST ser mais que uma tabela de lookup. Pegue a subtree esquerda de um node, depois o node, depois sua subtree direita — e os valores saem em ordem crescente. Toda vez, para qualquer BST.
Isso decorre direto da regra: tudo à esquerda de um node é menor e tudo à direita é maior, então visitar nessa ordem visita menor antes de maior, até o fim. O nome para ler uma tree assim é in-order, e este artigo não precisa de nada mais dele além do fato.
Essa é a promessa que o artigo de hash tables deixou aberta. Uma hash table implementa o Map ADT e é mais rápida em média, mas ela espalha keys de propósito e por isso não consegue responder "me dê estes em ordem" ou "me dê tudo entre dois valores" de forma alguma. Uma BST responde as duas, e essa propriedade é o porquê. Ela também está visível no playground abaixo, que imprime os valores da tree lidos desse jeito.
Buscando, e por que isso divide pela metade
Busca é a operação para a qual a estrutura existe, e é quatro linhas de lógica: compare, e recurse para um lado.
40 < 50 então vai para a esquerda · 40 > 30 então vai para a direita · achou — 60, 70, 80 e 20 nunca foram olhados
Quatro dos sete nodes nunca foram examinados, e isso numa tree minúscula. A proporção é o que importa: cada comparação elimina uma subtree, então o número de nodes que você examina é o número de levels, não o número de nodes.
Uma busca que falha é igualmente informativa. Caminhar para baixo e cair do fundo significa que o valor não está lá — e, de forma útil, o lugar de onde você caiu é exatamente onde o valor teria que ir. Insert é construído sobre isso.
Inserindo
Para inserir, busque o valor. Se você achar, não há nada a fazer. Se você cair do fundo, prenda um leaf novo onde caiu.
É o algoritmo inteiro, e explica por que a forma de uma BST depende da ordem de inserção: cada valor novo ocupa o único slot que suas comparações permitem, e nada nunca move um node existente. A tree lembra a ordem em que foi construída, o que é a semente do problema no fim deste artigo.
O playground abaixo mostra o slot antes de você se comprometer com ele — digite um valor e o círculo tracejado é onde as comparações o colocam.
Deletando — os três casos
Delete é a única operação com análise de casos de verdade, porque remover um node pode deixar um buraco que seus children têm que preencher de forma legal.
O node é um leaf
Nada depende dele. Desconecte e acabou.
30 mantém seu child direito e a invariante fica intocada
O node tem um child
Promova o child. Todo valor na subtree daquele child já estava do lado correto do parent do node deletado, então subi-lo um level não pode quebrar nada.
20 já era menor que 50, então é legal como child esquerdo de 50
O node tem dois children
Nenhum dos children pode ser simplesmente promovido — o node tem um slot e existem duas subtrees para manter. Então, em vez de remover o node, sobrescreva o valor dele com o próximo valor em ordem crescente, e depois delete aquele valor de onde ele estava.
O próximo valor em ordem crescente é o in-order successor: o menor valor na subtree direita, que você acha indo para a direita uma vez e depois para a esquerda o máximo possível. É a escolha certa porque ele é maior que tudo na subtree esquerda e menor que todo o resto na direita — exatamente as duas propriedades que o slot exige.
40 era o menor valor maior que 30, então satisfaz o slot que 30 deixou
E a recursão termina: o successor é o node mais à esquerda de uma subtree, então não tem child esquerdo, o que significa que deletar ele cai no caso um ou no caso dois e nunca no caso três de novo.
As operações em Go
Teste você mesmo
Digite um valor e veja o slot tracejado se mover conforme as comparações o colocam. Depois insira, busque e delete — e note a contagem de comparações que a linha de status reporta contra a height da tree.
insira, busque ou delete — o caminho acende conforme ele caminha
Quando pegar o jeito, aperte Inserir em ordem crescente e olhe o que acontece. Essa é a próxima seção.
Operações comuns e seus custos
Toda operação aqui custa a height da tree, o que é o ponto — e a razão de a forma importar tanto:
| Operação | Tree balanced | Tree degenerate |
|---|---|---|
| Search | ||
| Insert | ||
| Delete | ||
| Mínimo, máximo | ||
| Todos os valores em ordem |
Note que não existe O(1) em lugar nenhum, e nenhuma operação se importa com n diretamente — todas se importam com h. Tudo nesta tabela é o mesmo algoritmo nas duas colunas; só a forma da tree difere. O que significa que a performance inteira de uma BST se apoia numa propriedade que a estrutura não garante.
Binary Search Trees no mundo real
Ordered maps e sets em bibliotecas padrão
std::map e std::set em C++, TreeMap e TreeSet em Java. Esses são os equivalentes ordenados dos containers baseados em hash, e existem exatamente pela propriedade que este artigo descreveu: iteração em ordem de key, mais range queries. Todos são variantes auto-balanceadas em vez de BSTs comuns, pela razão que a próxima seção dá.
Índices de banco de dados
Qualquer índice que suporta WHERE created_at BETWEEN ... AND ... ou ORDER BY sem um sort é um índice de tree, porque um índice hash não responde nenhum dos dois. Bancos usam B-trees em vez de binárias — uma forma afinada para páginas de disco — mas a propriedade de ordenação sendo explorada é esta.
Scheduling e problemas de intervalo
"Qual é o próximo evento depois deste timestamp" é uma query de BST: busque o timestamp e pegue o successor. Qualquer coisa que precise de mais próximo em vez de exato — match mais próximo, próximo maior, faixa de autocomplete — quer estrutura ordenada, o que descarta hash table imediatamente.
Tabelas de símbolos onde a ordem importa
Compiladores e interpretadores que precisam de iteração determinística sobre declarações usam ordered maps, já que ordem de iteração de hash é arbitrária e, no caso do Go, deliberadamente randomizada.
Quando Binary Search Trees deixam a desejar
Entrada ordenada destrói ela. Este é o grande. Insira 10, 20, 30, 40 em ordem crescente e todo valor vai para a direita, porque todo valor é maior que tudo que já está lá. O resultado tem height n − 1.
uma linked list com um pointer Left sem uso em todo node
E entrada ordenada não é um caso patológico que alguém tem que construir — é a coisa mais banal do mundo. Dados chegam de um ORDER BY, de um arquivo ordenado, de um id auto-incremental, de um timestamp. A entrada mais natural que existe produz a pior tree possível, e todo O(log n) da tabela acima silenciosamente vira O(n).
Uma hash table é mais rápida quando você não precisa de ordem. O(1) médio bate O(log n), e por uma margem maior do que a notação sugere quando comportamento de cache entra na conta. Use uma BST quando você precisa de iteração ordenada, range queries ou match mais próximo. Se você só busca valores por key exata, a hash table ganha.
Pointer chasing custa mais do que a contagem de comparações implica. Vinte comparações numa tree de um milhão de nodes soa barato, mas cada uma é um dereference de pointer para um node que pode estar em qualquer lugar do heap — potencialmente vinte cache misses. É por isso que as estruturas apoiadas em array desta série frequentemente batem as em forma de tree na prática, em tamanhos pequenos.
Sem duplicatas, sem maquinário extra. A invariante usa desigualdades estritas, então valores iguais não têm casa legal. Implementações reais guardam uma contagem por node ou empurram duplicatas consistentemente para um lado, e as duas complicam o delete.
Resumo
Uma binary search tree adiciona uma regra de ordenação a uma binary tree e obtém uma estrutura de busca:
- Subtree esquerda menor, direita maior — para todo node — e a regra é recursiva, não uma verificação contra o parent
- Uma comparação descarta uma subtree inteira — que é por que o custo é
O(h), o número de levels, nãoO(n) - Insert é uma busca que falha mais um leaf — então a forma da tree é um registro da ordem em que ela foi construída
- Delete tem três casos — um leaf se desconecta, um child é promovido, e dois children significam sobrescrever com o in-order successor
- Lida da esquerda para a direita dá ordem crescente — a propriedade que uma hash table não oferece, e a razão de ordered maps serem apoiados em tree
- Todo custo depende da height, que nada aqui garante — entrada ordenada dá
n − 1
O insight central é que a performance de uma BST é uma propriedade da história dela, não da definição. Nada na estrutura resiste a uma ordem ruim de inserção, e a pior ordem — ordenada — é também a mais comum na prática. Isso é uma estrutura com excelente comportamento médio e nenhum piso sob o pior caso, o que para qualquer coisa guardando dados reais não é um trade que você pode aceitar.
O próximo artigo põe um piso embaixo. Se o problema é que inserts podem fazer a tree pender, a correção é notar o pendor e desfazê-lo — um rearranjo local que preserva a invariante enquanto encurta a tree. Essa operação se chama rotação, e um punhado delas por insert é suficiente para garantir O(log n) para sempre.