Escolhendo uma Estrutura de Dados: Um Guia de Decisão

• Resumir, para cada uma das oito estruturas principais cobertas em Estruturas de Dados I e II, as operações que ela suporta bem e as garantias Big-O que de fato oferece.
• Distinguir uma garantia de caso médio (busca em hash table) de uma garantia de pior caso (operações de árvore AVL/rubro-negra, operações de heap) de uma garantia esperada (operações de skip list), e explicar por que essa distinção às vezes decide qual estrutura é correta para um dado problema.
• Combinar uma descrição de problema realista com a única estrutura mais apropriada entre hash table, BST simples, árvore AVL/rubro-negra, heap, union-find, trie, skip list e filtro de Bloom, citando a operação específica que o problema precisa.
• Identificar situações onde mais de uma estrutura é defensável, e articular a troca real entre os candidatos em vez de declarar uma única resposta "melhor".
• Explicar por que um filtro de Bloom pertence a esta lista mesmo respondendo um tipo de pergunta fundamentalmente diferente (pertencimento probabilístico) de toda outra estrutura aqui (respostas exatas).
• Usar a tabela comparativa deste conceito como referência de trabalho ao abordar um problema novo e desconhecido, reconhecendo a qual operação o requisito central do problema mapeia.

Todo conceito em Estruturas de Dados I e II fez uma versão do mesmo argumento: uma estrutura é rápida em algumas operações porque se comprometeu, estruturalmente, com uma forma particular de organizar dados, e esse mesmo compromisso é exatamente o que a torna lenta (ou simplesmente incapaz) em outras operações. Uma hash table se compromete a embaralhar chaves para busca exata O(1) em média, e abre mão de toda ordenação e toda relação de prefixo em troca. Uma árvore AVL ou rubro-negra se compromete com um invariante de balanceamento aplicado em toda inserção, comprando operações ordenadas O(log n) garantidas no pior caso ao custo de trabalho de inserção/remoção que uma BST simples ou hash table nunca precisa fazer. Um heap se compromete com um invariante muito mais fraco (pai ≤ ou ≥ filhos, não uma ordem total) em troca de acesso O(1) ao valor extremo atual e inserção/extração O(log n), mas abre mão inteiramente da capacidade de buscar um elemento arbitrário eficientemente. Union-find se compromete a responder apenas duas perguntas (estes estão conectados, mescle estes) mas responde ambas em tempo amortizado quase constante, mais rápido do que qualquer travessia de grafo de propósito geral conseguiria por consulta. Uma trie se compromete a soletrar chaves caractere por caractere, comprando operações de prefixo nativas que uma hash table não pode oferecer, ao custo de operações por chave que não são mais rápidas (e frequentemente mais lentas na prática) que as de uma hash table. Uma skip list se compromete com as mesmas garantias ordenadas dessas árvores, mas através de lançamentos de moeda independentes em vez de um invariante imposto, comprando mecânica de inserção/remoção radicalmente mais simples ao custo de um limite esperado (não de pior caso). Um filtro de Bloom se compromete a não armazenar chaves de forma alguma, apenas bits, comprando uso de memória independente do tamanho e da quantidade de chaves, ao custo de abrir mão da própria certeza: ele responde "possivelmente presente" ou "definitivamente ausente", nunca um "sim" garantido.

Nenhuma dessas oito estruturas é "a melhor" em qualquer sentido geral, e boa parte da competência genuína com estruturas de dados é exatamente a habilidade em torno da qual este conceito é construído: dado um problema, identificar corretamente qual operação específica é o gargalo, e então escolher a única estrutura cujo compromisso fundamental combina com aquela operação. Este é deliberadamente o ápice desta disciplina, todo outro conceito em Estruturas de Dados I e II construiu os detalhes internos de uma estrutura em profundidade; este pede que você mantenha todas elas na cabeça ao mesmo tempo e faça o julgamento comparativo que um engenheiro em atuação ou uma entrevista técnica de fato exige: não "explique como um heap funciona", mas "dado este problema, por que um heap e não uma BST?"

As oito estruturas em resumo

Esta tabela é o artefato mais útil deste conceito, o resto de Teoria Central existe para justificar por que cada linha diz o que diz, e os Exemplos Resolvidos existem para praticar a leitura de um problema e encontrar a linha correta.

Lendo a tabela corretamente: o tipo de garantia importa tanto quanto o expoente

A distinção mais consequente nesta tabela não é entre O(1) e O(log n), é entre garantias de caso médio e pior caso, e entre garantias amortizadas e por operação, porque essas determinam o que uma estrutura de fato promete que você pode confiar:

• Hash table, O(1) em média, O(n) no pior caso. Uma sequência patológica de chaves que todas colidem (ou uma carga de trabalho adversarial deliberadamente construída) pode degradar uma hash table para operações de tempo linear. Para a maioria das aplicações esse risco é negligenciável, mas é real, e é precisamente por isso que sistemas com entradas adversariais (por exemplo, servidores web aceitando chaves não confiáveis) às vezes precisam de funções de hash randomizadas ou recorrem a árvores balanceadas para proteção de pior caso.
• BST simples, O(log n) em média, O(n) no pior caso. Uma BST construída a partir de entrada já ordenada degenera em uma lista ligada, com toda operação custando O(n). Este não é um caso de borda raro a ser descartado, entrada ordenada ou quase ordenada é comum na prática (arquivos de log, registros com timestamp, IDs atribuídos em ordem), o que é exatamente a motivação para árvores autobalanceadas.
• Árvores AVL e rubro-negra, O(log n), garantido, sempre. O propósito inteiro do invariante de balanceamento aplicado em toda inserção é eliminar completamente o pior caso da BST simples. Essa garantia é o que torna árvores AVL/rubro-negra a escolha certa sempre que uma carga de trabalho não pode tolerar uma operação lenta ocasional, não meramente uma rápida em média.
• Heap, O(log n) inserir/extrair, pior caso, mas apenas para o elemento extremo. A garantia de um heap tem escopo mais estreito que o de uma árvore balanceada: não diz nada sobre encontrar um elemento arbitrário (isso é O(n), uma varredura completa, já que a propriedade de heap só ordena pai contra filho, não irmãos entre si), a garantia se aplica apenas a acessar e remover o mínimo ou máximo atual.
• Union-find, O(α(n)) amortizado, com compressão de caminho e união por rank/tamanho. α é a função inversa de Ackermann, que cresce tão lentamente que é efetivamente uma constante (abaixo de 5) para qualquer n que já pudesse ser representado em um computador real, "amortizado" aqui significa que o limite vale sobre uma sequência inteira de operações, não necessariamente em qualquer operação isolada, embora na prática se comporte tão perto de O(1) quanto qualquer estrutura nesta tabela consegue.
• Trie, O(L) por operação de chave, independente de n (o número de chaves armazenadas). Este é um formato genuinamente diferente de garantia dos demais: custos de trie escalam com o comprimento da chave, não com quantas chaves estão armazenadas, o que é por que o desempenho de uma trie não degrada conforme mais chaves são adicionadas, diferente de uma BST ou hash table onde n aparece diretamente na fórmula de custo (dentro de um logaritmo, ou como um termo de pior caso).
• Skip list, O(log n) esperado, sobre os próprios lançamentos de moeda internos da estrutura, não sobre a entrada. Este é um terceiro formato distinto de garantia, nem o caso médio "geralmente bom, raramente ruim" da hash table nem o pior caso "sempre bom" da árvore AVL/rubro-negra: nenhuma entrada, por mais adversarial que seja, consegue forçar uma skip list ao seu pior caso O(n) (teoricamente possível, mas exponencialmente improvável), porque esse pior caso exigiria que a própria aleatorização da skip list conspirasse contra ela.
• Filtro de Bloom, O(k) por operação, mas a própria resposta carrega incerteza que nenhuma outra estrutura nesta tabela tem. Toda outra estrutura aqui retorna uma resposta certa a algum custo; um filtro de Bloom retorna "definitivamente ausente" com certeza mas "possivelmente presente" com uma pequena probabilidade de falso positivo precisamente calculável, trocando a própria exatidão, não apenas velocidade, por espaço.

A operação única que cada estrutura habilita exclusivamente

Além da velocidade bruta, cada estrutura é frequentemente a escolha certa não porque é mais rápida mas porque é a única nesta lista que suporta a operação necessária de forma alguma, eficientemente:

• Só uma trie responde eficientemente "me dê toda chave que começa com este prefixo".
• Só um heap responde eficientemente "qual é o mínimo/máximo atual, e deixe-me removê-lo, repetidamente, conforme o conjunto muda".
• Só union-find responde eficientemente "estes dois elementos já foram mesclados no mesmo grupo?" através de um fluxo longo de operações de mesclagem e consulta.
• Só uma estrutura ordenada (BST, AVL, ou rubro-negra) responde eficientemente "me dê todos os elementos entre X e Y, em ordem" (consultas de intervalo e travessia em ordem), uma hash table e uma trie (para consultas apenas de prefixo) não conseguem fazer isso de forma alguma, e um heap só consegue alcançar barato o único extremo, não um intervalo arbitrário.
• Só uma hash table (entre essas oito) alcança O(1) em média para uma consulta pura de "esta chave exata está presente" sem nenhum requisito de ordenação, toda estrutura ordenada paga pelo menos O(log n) pelo privilégio de manter ordenação junto com a busca.
• Só um filtro de Bloom responde a uma consulta de pertencimento usando memória que não cresce com o tamanho ou a quantidade das próprias chaves, toda outra estrutura aqui precisa armazenar algo proporcional a n (ou, para uma trie, ao comprimento total das chaves); esse é o nicho específico que justifica aceitar seu risco de falso positivo.
• Uma skip list oferece exclusivamente tudo que uma árvore AVL ou rubro-negra oferece (ordenação completa, operações O(log n)) sem nenhuma lógica de rotação ou contabilidade de balanceamento por nó, ela não habilita uma operação nova que as árvores já não pudessem fazer, mas é frequentemente a escolha certa puramente por simplicidade de implementação e concorrência (um fato por trás de seu uso em sistemas como o Redis).

Exemplo 1: combinando oito cenários realistas com uma estrutura

Problema: Para cada cenário abaixo, nomeie a estrutura correta e a operação específica que a torna correta.

1. "Preciso processar um fluxo enorme de chamadas union(a, b) e connected(a, b) o mais rápido possível, e nunca preciso listar os membros de um grupo ou desfazer uma mesclagem." → Union-find. As operações nomeadas são exatamente as duas operações suportadas por union-find, e nada mais na lista combina com "mesclar" e "consulta de conectividade" como primitivas, uma BST ou hash table poderia simular isso com uma travessia de grafo por consulta, mas a um custo muito pior que O(α(n)) amortizado por operação.
2. "Preciso de uma fila de prioridade para um agendador de tarefas, sempre processar a tarefa de maior prioridade em seguida, e novas tarefas chegam continuamente." → Heap. "Sempre o maior atual, com inserções contínuas" é precisamente o contrato de espiar O(1) / inserir-extrair O(log n) de um heap; uma árvore balanceada também poderia suportar isso (seu mínimo/máximo é alcançável em O(log n)) mas a um custo de espiar estritamente pior e nenhum benefício, já que nada aqui precisa de ordenação entre os elementos não extremos.
3. "Preciso armazenar registros de usuário chaveados por ID de usuário e suportar buscas exatas rápidas; nunca preciso deles em nenhuma ordem particular." → Hash table. Nenhum requisito de ordenação é declarado, então pagar O(log n) pela garantia de ordenação de uma árvore balanceada não compra nada útil aqui, a busca O(1) em média da hash table é estritamente o melhor ajuste quando ordenação é genuinamente irrelevante.
4. "Preciso suportar uma caixa de busca que sugere completações enquanto o usuário digita." → Trie. Isso é autocomplete, coberto no conceito anterior, keysWithPrefix é a operação, e é a operação que só uma trie (ou TST, para um alfabeto grande) oferece nativamente.
5. "Preciso de um índice em memória que suporte consultas de intervalo rápidas ('me dê todo pedido entre estes dois timestamps') e não posso tolerar uma operação lenta ocasional, mesmo que rara, porque isso roda em um sistema de negociação sensível a latência." → Árvore AVL ou rubro-negra, não uma BST simples. A necessidade de consulta de intervalo aponta para uma estrutura ordenada; o requisito "não pode tolerar nem mesmo uma operação lenta rara" elimina uma BST simples (O(n) no pior caso) e aponta especificamente para a variante com garantia de pior caso.
6. "Preciso deduplicar uma lista de objetos arbitrários, verificando 'já vi isso antes' repetidamente, sem nunca precisar iterá-los em ordem." → Hash table. Mesmo raciocínio do cenário 3, nenhuma necessidade de ordenação, então a verificação simples de pertencimento exato O(1) em média é a ferramenta certa e mais simples; recorrer a uma trie ou árvore aqui só se justificaria se os objetos fossem strings e relações de prefixo importassem, o que este cenário não menciona.
7. "Preciso de um índice ordenado em memória suportando consultas de intervalo concorrentes entre várias threads, e prefiro evitar implementar e testar lógica de rotação sob modificação concorrente." → Skip list. O requisito de ordenação sozinho apontaria para qualquer uma entre BST, árvore AVL/rubro-negra, ou skip list, mas "evitar lógica de rotação sob modificação concorrente" é especificamente a vantagem de uma skip list: sua inserção e remoção são atualizações locais de ponteiro sem nenhuma passada de rebalanceamento de árvore inteira para sincronizar, que é exatamente por que skip lists são uma escolha comum para estruturas ordenadas concorrentes na prática.
8. "Preciso verificar, antes de uma leitura de disco cara, se uma chave pode existir em disco, entre bilhões de chaves, usando o mínimo de memória possível, e uma leitura de disco desnecessária ocasional é um custo aceitável." → Filtro de Bloom. "Bilhões de chaves, o mínimo de memória possível, resposta errada ocasional aceitável" é precisamente o contrato de um filtro de Bloom, nenhuma outra estrutura nesta tabela oferece uso de memória independente do tamanho e da quantidade de chaves, e a tolerância declarada para falsos positivos ocasionais (uma leitura de disco desnecessária) é exatamente o custo que essa estrutura é construída para trocar por essa economia de memória.

Exemplo 2: um caso onde duas estruturas são ambas defensáveis, e escolhendo corretamente

Problema: Um sistema precisa manter um placar dos 10 melhores escores entre milhões de submissões, atualizado continuamente, com consultas frequentes para "qual é o atual 10º maior escore" (o corte para entrar no placar). Compare uma abordagem baseada em heap contra uma abordagem baseada em árvore balanceada e determine qual é preferível.

Solução. Um min-heap de tamanho 10 é o ajuste natural: mantenha apenas os 10 líderes atuais no heap, com o menor dos 10 na raiz; a cada nova submissão, compare-a contra a raiz, e se for maior, remova a raiz e insira o novo escore, uma operação O(log 10) = O(1)-ish (log de uma constante é uma constante). O corte atual (10º lugar) é sempre a espiada O(1) na raiz. Essa abordagem usa O(1) de espaço adicional além dos 10 escores rastreados e não toca em nada fora do minúsculo heap a cada atualização.

Uma árvore balanceada (AVL/rubro-negra) contendo todos os escores também poderia responder "qual é o 10º maior" caminhando a partir do máximo, mas isso exige que a árvore de fato armazene todas as submissões (não só o top 10), custando O(log n) por inserção onde n é o número total de submissões (potencialmente milhões), e encontrar o 10º maior exige uma travessia em ordem limitada a partir do máximo, o que é mais maquinário do que a pergunta precisa.

O heap vence decisivamente aqui, e a razão mapeia diretamente para "a operação única que cada estrutura habilita exclusivamente" da Teoria Central: a necessidade real é acesso repetido a um conjunto extremo limitado, que é a especialidade de um heap, não uma necessidade geral de intervalo ordenado ou pertencimento completo, que é para o que uma árvore balanceada é construída. Recorrer à estrutura mais poderosa e mais geral (a árvore balanceada) quando uma mais estreita e mais barata (o heap pequeno de tamanho fixo) responde exatamente a pergunta feita é um erro comum de over-engineering que esta comparação pretende evitar.

Exemplo 3: trabalhando de trás para frente de uma operação até a estrutura, sem que o domínio seja informado

Problema: É necessária uma estrutura que suporte: inserir uma chave de string, e mais tarde, dados apenas alguns caracteres iniciais de uma chave, recuperar toda chave armazenada que comece com aqueles caracteres, rapidamente, mesmo quando milhões de chaves estão armazenadas e apenas um punhado casa. Nenhuma outra operação (nenhuma remoção neste cenário, nenhuma prioridade numérica, nenhuma conectividade) é necessária. Identifique a estrutura, independentemente de qualquer aplicação do mundo real declarada.

Solução. O requisito descrito, "inserir chaves de string, recuperar por prefixo, custo proporcional aos casamentos encontrados e ao comprimento do prefixo, não ao total de chaves armazenadas", é, palavra por palavra, a garantia definidora de uma trie (uma TST se o alfabeto de chaves for grande ou esparso, conforme a troca de memória daquele conceito). Nenhuma outra estrutura nesta lista oferece uma operação de coleta de prefixo nativa de forma alguma: uma hash table exigiria varrer toda chave; uma BST ou árvore balanceada poderia localizar um intervalo de chaves lexicograficamente próximas do prefixo mas não tem noção embutida de "prefixo" como distinto de "intervalo de valor", tornando-a um ajuste estranho e não nativo; um heap e union-find não suportam recuperação baseada em chave desse tipo de forma alguma. Este exemplo é incluído especificamente para demonstrar o processo de decisão independente de um domínio nomeado (autocomplete, roteamento), a operação descrita é o sinal, não a aplicação a que ela por acaso pertence.

• "Uma estrutura é objetivamente a melhor em geral, então devo usá-la por padrão." Nenhuma estrutura nesta tabela domina as outras em toda operação, a velocidade de cada uma em sua especialidade é comprada por uma fraqueza específica e nomeada em outro lugar (a falta de ordenação de uma hash table, a falta de busca arbitrária de um heap, a falta de qualquer vantagem de uma trie para busca exata sem prefixo). Usar uma única estrutura "favorita" por padrão independentemente do problema é precisamente o hábito que este conceito de ápice pretende corrigir.
• "Se ordenação não é explicitamente exigida, uma hash table sempre serve, não preciso pensar se vou precisar de consultas de intervalo depois." Isso frequentemente é verdade no momento mas é uma fonte comum de reescritas custosas: um sistema que começa com "só busca exata" frequentemente cresce uma necessidade de consultas de intervalo, iteração ordenada, ou buscas de vizinho mais próximo conforme requisitos evoluem, momento em que uma hash table não oferece nenhum crédito parcial (não pode ser adaptada para ordenação; os dados subjacentes devem ser reindexados em uma estrutura ordenada do zero). Antecipar uma necessidade de ordenação futura genuinamente provável é uma razão legítima para escolher uma árvore balanceada em vez de uma hash table mesmo quando só busca exata é exigida hoje.
• "Árvores AVL e rubro-negra são estritamente melhores que uma BST simples, então uma BST simples nunca é a escolha certa." Uma BST simples é mais simples de implementar e tem uma sobrecarga por operação ligeiramente menor (sem rotações, sem contabilidade de balanceamento) que uma variante autobalanceada, e permanece inteiramente adequada sempre que a ordem de inserção é conhecida como suficientemente aleatória ou de outra forma não adversarial, uma BST simples construída a partir de entrada genuinamente randomizada tem desempenho próximo de O(log n) em média na prática. A garantia de autobalanceamento importa especificamente quando a ordem de entrada não é confiável, é adversarial, ou já está ordenada; não é um upgrade gratuito sem custo em toda situação.
• "Union-find pode ser usado para verificar adjacência ou listar os membros de um grupo, já que rastreia quais elementos estão conectados." Union-find responde exatamente duas perguntas, "mescle estes dois grupos" e "estes dois elementos estão no mesmo grupo", e não suporta eficientemente listar todos os membros de um grupo, encontrar um caminho entre dois elementos conectados, ou responder "conectados por quantos saltos"; essas exigem uma estrutura real de travessia de grafo. A velocidade de union-find vem especificamente de não manter essa informação extra, e recorrer a ele para responder uma pergunta para a qual não foi construído ou falha completamente ou exige acoplar uma estrutura separada junto com ele.
• "Uma trie é a escolha certa sempre que as chaves por acaso são strings." As chaves serem strings é necessário mas não suficiente, uma trie ganha seu lugar especificamente quando consultas baseadas em prefixo importam. Um sistema que só precisa de busca por string exata (nenhuma consulta de prefixo, nenhum autocomplete, nenhum casamento mais longo estilo roteamento) não ganha nada de uma trie sobre uma hash table e tipicamente paga mais sobrecarga por chave por uma capacidade (busca de prefixo) que nunca de fato usa.
• "A garantia de caso esperado de uma skip list é mais fraca que a de uma árvore AVL ou rubro-negra, então uma árvore balanceada é sempre a escolha mais segura." O cenário 7 do Exemplo 1 mostra que a razão real para preferir uma skip list raramente é sobre a garantia Big-O em si (ambas são da classe O(log n)) e quase sempre é sobre simplicidade de implementação e concorrência, nenhum adversário consegue forçar o pior caso improvável de uma skip list mais do que se consegue forçar uma moeda honesta a sempre dar cara, então na prática a garantia "mais fraca" não é uma desvantagem prática para a maioria das cargas de trabalho.
• "Um filtro de Bloom é só uma hash table com um array menor, então deve ser menos confiável para o mesmo trabalho." Um filtro de Bloom não faz o mesmo trabalho que uma hash table de forma alguma, ele não consegue recuperar um valor associado a uma chave, não consegue enumerar suas chaves, e não consegue responder "definitivamente presente", só "definitivamente ausente" ou "possivelmente presente". Ele resolve um problema mais estreito (pertencimento aproximado de conjunto) que uma hash table resolve em excesso a um custo de memória muito maior; escolher entre eles é uma questão de qual problema de fato está sendo perguntado, não qual é "mais confiável" para um trabalho compartilhado.

Através de Estruturas de Dados I e II, oito estruturas respondem cada uma, mais rápido, a uma pergunta genuinamente diferente: uma hash table responde "esta chave exata está presente?" em O(1) em média descartando ordenação completamente; uma BST simples responde consultas ordenadas em O(log n) em média mas degrada para O(n) com entrada adversarial ou ordenada; uma árvore AVL ou rubro-negra fecha essa lacuna com uma garantia O(log n) no pior caso, ao custo de sobrecarga de balanceamento em toda inserção; uma skip list combina essa mesma garantia ordenada em expectativa, através de lançamentos de moeda em vez de um invariante imposto, ao custo de um pior caso que é apenas improvável em vez de eliminado; um heap responde "qual é o extremo atual, e deixe-me removê-lo" em espiar O(1) / atualizar O(log n), sem suportar busca arbitrária de forma alguma; union-find responde "mescle estes" e "estes estão conectados?" em tempo amortizado quase constante deliberadamente não rastreando nada além de pertencimento a grupo; uma trie responde "quais chaves compartilham este prefixo?" em tempo proporcional ao prefixo e à contagem de casamentos, independente de quantas outras chaves existem, soletrando chaves caractere por caractere; e um filtro de Bloom responde "eu possivelmente já vi isso?" usando memória independente do tamanho ou da quantidade de chaves, abrindo mão da própria exatidão, aceitando falsos positivos ocasionais em troca de eliminar falsos negativos completamente. Escolher corretamente entre elas significa identificar a operação de gargalo real que um problema precisa, busca exata, intervalo ordenado, acesso a valor extremo, conectividade, busca de prefixo, ou pertencimento aproximado restrito por espaço, e combiná-la com a única estrutura construída em torno exatamente daquela operação, em vez de recorrer a uma favorita familiar ou assumir que uma estrutura mais genérica é automaticamente a escolha mais segura.