Imagine que você está construindo um mecanismo de autocompletar — como o campo de busca do Google ou a barra de endereços do navegador. O usuário digita "pre" e em milissegundos você precisa retornar todas as palavras do seu dicionário de 100.000 entradas que começam com "pre": "prefixo", "preto", "preço", "preguiça", "presidência", ...

Quão rápido as estruturas que você conhece resolvem isso?

• ABP (árvore binária de busca): cada nó guarda uma palavra inteira e dois ponteiros (subárvore esquerda e direita). A árvore é organizada em ordem lexicográfica (a do dicionário): uma palavra menor que a do nó vai para a esquerda, uma maior vai para a direita. Por exemplo, inserindo "mesa", "casa", "preto", "prefixo" e "zebra": "mesa" é a raiz; "casa" < "mesa" vai à esquerda; "preto" > "mesa" vai à direita; "prefixo" > "mesa" e < "preto" fica à esquerda de "preto"; "zebra" fica à direita de "preto". Em cada nó visitado, comparar duas palavras exige ler os caracteres desde o início até achar o primeiro que difere: custo O(m), onde m é o comprimento da palavra. Como todas as palavras com prefixo "pre" ocupam uma faixa contínua da ordem lexicográfica, dá para descer até a primeira delas e coletar as demais em ordem, mas descer custa O(m) por nível (O(m·h), com h a altura da árvore — que chega a n se ela estiver desbalanceada) e o prefixo "pre" é relido, caractere por caractere, em cada comparação. A árvore não sabe que "prefixo", "preto" e "preço" compartilham o início: cada uma guarda e compara a palavra toda de novo.
• Tabela hash: O(1) para busca exata — mas completamente incapaz de busca por prefixo. O hash de "pre" não tem nenhuma relação com os hashes de "prefixo", "preto" ou "preço". Não há como pular de um para o outro.
• Vetor ordenado com busca binária: O(m log n) para busca exata; busca por prefixo é possível mas exige O(m log n) para localizar o ponto de início mais O(k) para coletar os k resultados — e ainda precisa manter o vetor ordenado a custo O(mn) nas inserções.

A raiz do problema: essas estruturas tratam cada palavra como um bloco opaco. Elas não exploram a estrutura interna dos caracteres. Para strings, existem estruturas especializadas que são dramaticamente mais eficientes. Nesta aula: Trie, Patrícia (Trie Comprimida) e TST.

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

1. Trie (Árvore de Prefixos)

1.1 Estrutura

Uma Trie (do inglês retrieval) é uma árvore em que cada nó representa um caractere — não uma palavra inteira. O caminho da raiz até um nó marcado como "fim de palavra" representa uma chave armazenada.

• Cada nó tem um vetor de filhos com uma entrada por caractere do alfabeto (26 para letras minúsculas).
• Cada entrada pode ser NULL (nenhuma palavra passa por aqui) ou apontar para o próximo nó.
• Cada nó tem um booleano fim que indica se uma palavra termina naquele nó.
• A raiz não representa nenhum caractere — ela é o ponto de partida.

Exemplo usado em toda a seção: as palavras "ar", "arco", "arte" e "as". Círculo duplo = fim de palavra (fim = true).

1.2 Inserção

Seguimos a chave letra por letra a partir da raiz. Para cada letra, usamos o filho correspondente se ele existir e o criamos se não existir. Ao acabar as letras, marcamos fim = true no último nó. Os casos:

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

Caso 1 — Algum nó do caminho não existe

Criam-se os nós que faltam e marca-se o fim no último.

Caso 2 — O caminho já existe, mas o último nó não marca fim

A palavra era apenas prefixo de outra. Não se cria nó algum: só se marca o fim.

Caso 3 — O caminho existe e o último nó já marca fim

A palavra já está na árvore: nada muda.

1.3 Busca

Seguimos a chave letra por letra a partir da raiz. O resultado depende de onde o caminho termina; a palavra só é encontrada no caso 1.

Caso 1 — Encontrada

Todos os nós do caminho existem e o último marca fim.

Caso 2 — O caminho se interrompe

Algum nó não tem o filho da próxima letra: a palavra não existe.

Caso 3 — O caminho existe, mas o último nó não marca fim

A chave é só um prefixo de outras palavras.

1.4 Remoção

Busca-se a palavra e desmarca-se o fim. Depois, subindo pelo caminho, apagam-se os nós que ficaram sem filhos e sem marca de fim; a subida pára no primeiro nó que ainda é necessário. Os casos:

Caso 1 — A palavra não existe

A busca falha e a árvore não muda.

Caso 2 — A palavra é prefixo de outras (o nó tem filhos)

Nenhum nó pode ser apagado, porque outras palavras passam por ele: só se desmarca o fim.

Caso 3 — O nó é folha (a palavra termina no fim de um ramo)

Apaga-se o nó e sobe-se, apagando cada nó que ficar sem filhos e sem fim, até encontrar um nó ainda necessário. Duas formas de a subida parar:

3a — Para num nó que ainda tem outro ramo:

3b — Para num nó que marca fim:

1.5 Exemplo completo: todos os casos em sequência

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

Uma sequência de operações sobre uma única árvore, partindo da árvore vazia. Cada passo indica qual caso (das seções de inserção, busca e remoção acima) ele exemplifica; no conjunto, os passos cobrem todos os casos das três operações, como mostra a tabela. Nos desenhos, cada passo mostra a árvore após a operação (nas remoções, antes e depois).

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

1.6 Complexidade

m = comprimento da chave (número de letras); n = número de chaves (palavras) armazenadas; |Σ| = tamanho do alfabeto (26 para a-z), tratado como constante; p = comprimento do prefixo buscado; t = nós visitados abaixo do prefixo (pelo menos o número de palavras encontradas e, no máximo, o total de letras delas).

Pior caso = o maior custo que pode acontecer, para o pior conjunto de palavras e a pior ordem de inserção. Caso médio = o custo típico, com palavras em ordem aleatória. Quando as duas colunas coincidem, o custo não depende de azar nos dados.

Por que busca, inserção e remoção custam O(m)?

Intuição: a Trie "lê" a chave letra por letra. Para cada letra ela dá um único passo: usa a letra como índice no vetor de filhos do nó atual (acesso direto, sem comparar com nada) e desce. Uma chave de m letras exige, no máximo, m passos. Disso decorrem duas coisas:

• O custo não depende de n. Buscar "arco" custa 4 passos com 10 mil palavras e os mesmos 4 passos com 10 milhões. Numa ABP balanceada com 1 milhão de palavras, seriam cerca de 20 comparações de palavras inteiras (log₂ 10⁶ ≈ 20).
• O custo não depende da forma da árvore: para uma dada chave, o caminho sempre tem no máximo m nós. Não existe "entrada azarada"; por isso o pior caso e o caso médio são ambos O(m).

• Busca: o pior caso é quando a palavra existe (exatamente m passos) ou quando a falta só aparece na última letra. Se faltar uma letra no meio, a busca para antes (ex.: "xyz" para no 1.º passo, custo O(1)), mas o limite O(m) vale para todas.
• Inserção: desce pelos nós que já existem e cria os que faltam: no máximo m nós novos. Criar um nó = alocar e zerar |Σ| ponteiros, o que é constante para alfabeto fixo (se contarmos o zeramento, o custo é O(m × |Σ|)).
• Remoção: desce m passos até o nó da palavra e sobe, no máximo m passos, apagando os nós que ficaram sem filhos e sem fim. Saber se um nó ficou "sem filhos" exige olhar seus |Σ| ponteiros (constante para alfabeto fixo).

Busca por prefixo: O(p + t)

Descemos p passos até o nó do prefixo e depois percorremos toda a subárvore abaixo dele para coletar as palavras. O custo é proporcional ao tamanho da resposta: t é pelo menos o número de palavras encontradas (cada uma termina num nó) e, no máximo, o total das letras delas (nós compartilhados são visitados uma só vez). Um prefixo curto como "a" pode devolver metade do dicionário e t ser enorme, mas aí o trabalho extra é justamente gerar a resposta. A fórmula é a mesma no pior caso e no caso médio.

Espaço

• Pior caso: palavras sem prefixo em comum. Cada palavra cria m nós próprios: n × m nós, cada um com |Σ| ponteiros → O(n × m × |Σ|). Ex.: 1.000 palavras de 7 letras → até 7.000 nós × 26 ponteiros × 8 bytes ≈ 1,5 MB.
• Caso típico: bem menor, porque palavras que começam igual compartilham os nós do início. "ar", "arco", "arte" e "as" têm 12 letras no total, mas a Trie tem apenas 7 nós (a, r, c, o, t, e, s) além da raiz.
• O gargalo é o vetor de |Σ| ponteiros por nó: quase todas as posições ficam NULL.

1.7 Estrutura e funções em C

#define ALPHA 26

typedef struct NodoTrie {
    struct NodoTrie *filhos[ALPHA];
    int fim;  /* 1 se este nó termina uma palavra */
} NodoTrie;

NodoTrie *novoNodo(void);                              /* cria um nó vazio (usado também como raiz) */
void      inserir(NodoTrie *raiz, const char *s);       /* insere a palavra s */
int       buscar(NodoTrie *raiz, const char *s);        /* 1 se s está armazenada, 0 caso contrário */

main de demonstração:

int main(void) {
    NodoTrie *raiz = novoNodo();

    inserir(raiz, "ar");
    inserir(raiz, "arco");
    inserir(raiz, "arte");

    printf("buscar(arco) = %d\n", buscar(raiz, "arco"));   /* 1 */
    printf("buscar(arca) = %d\n", buscar(raiz, "arca"));   /* 0 */
    printf("buscar(arc)  = %d\n", buscar(raiz, "arc"));    /* 0: é só um prefixo */
    return 0;
}

1.8 O problema

Cada nó da Trie guarda 26 ponteiros, mesmo que quase todos fiquem NULL. Para 1.000 palavras com média de 7 letras são cerca de 7.000 nós × 26 ponteiros × 8 bytes ≈ 1,5 MB só em ponteiros, e muitos desses nós têm um único filho. A próxima estrutura, a Patrícia, ataca exatamente esse desperdício.

2. Patrícia (Trie Comprimida / Radix Tree)

2.1 Estrutura

Em uma Trie com vocabulário esparso, muitos nós têm exatamente um único filho: são nós de passagem, que só prolongam um caminho sem nenhuma bifurcação. Isso desperdiça memória e indireções.

A solução da Patrícia (Trie Comprimida): comprimir cadeias de nós com filho único em uma única aresta rotulada com a substring inteira.

Regra de fusão. Um nó da Trie pode ser fundido com o seu único filho quando (1) ele tem exatamente um filho e (2) não marca fim de palavra. No exemplo, 'c' e 't' cumprem as duas condições e viram parte das arestas "co" e "te". Já o nó 'a' tem dois filhos ('r' e 's') e o 'r' marca o fim de "ar": ambos permanecem.

O que cada nó guarda:

• o rótulo da aresta que chega nele (uma string, não um caractere);
• a marca de fim de palavra;
• os filhos, numa lista. A primeira letra do rótulo identifica a aresta: dois irmãos nunca começam com a mesma letra.

2.2 Inserção

Descemos a partir da raiz com o resto da chave: a primeira letra do resto escolhe a aresta e o rótulo é comparado de uma vez com o início do resto. Em cada passo vale um dos casos abaixo (exemplos na árvore com "ar", "arco", "arte" e "as"):

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

Caso 1 — Nenhuma aresta começa com a letra

Cria-se uma folha com o resto da chave como rótulo, marcada como fim.

Caso 2 — O rótulo casa inteiro com o início do resto

Desce-se para o filho e continua-se com o que sobrou da chave.

Caso 3 — O rótulo casa só em parte

Divide-se a aresta: um nó novo guarda o prefixo comum, e o resto do rótulo vira filho dele, levando junto a subárvore e a marca de fim antigas. Dois sub-casos, conforme sobre ou não parte da chave:

Caso 4 — A chave acaba num nó que já existe

Nada é criado; basta olhar a marca de fim desse nó:

2.3 Busca

Descemos como na inserção, mas sem criar nada. A chave só é encontrada no caso 1; os outros quatro são falhas.

Caso 1 — Encontrada

Os rótulos casam inteiros até consumir a chave e o último nó marca fim.

Caso 2 — Nenhuma aresta começa com a letra

No nó atual, nenhum filho tem rótulo começando com a próxima letra da chave.

Caso 3 — O rótulo diverge no meio

A aresta começa com a letra certa, mas alguma letra seguinte do rótulo difere da chave.

Caso 4 — A chave acaba no meio de um rótulo

O que sobrou da chave é um prefixo do rótulo, mas não o rótulo inteiro.

Caso 5 — A chave acaba num nó que não marca fim

Os rótulos casam inteiros, mas a palavra não termina ali.

2.4 Remoção

Busca-se a palavra e desmarca-se o fim. Depois, para manter a árvore comprimida: um nó sem filhos é apagado, e um nó que ficou com um único filho e sem marca de fim é fundido com esse filho (os rótulos se concatenam). Os casos:

Caso 1 — A palavra não existe

A busca falha e a árvore não muda.

Caso 2 — O nó da palavra tem dois ou mais filhos

Nada é apagado nem fundido: só se desmarca o fim.

Caso 3 — O nó da palavra tem um único filho

Ao desmarcar o fim, o nó fica com um único filho e sem fim: funde-se com esse filho.

Caso 4 — O nó da palavra é folha

Apaga-se a folha (e a aresta que chega nela). Depois olha-se o pai:

4a — O pai continua necessário (marca fim ou ainda tem outro filho): nada mais muda.

4b — O pai fica com um único filho e sem fim: funde-se com esse filho.

2.5 Exemplo completo: todos os casos em sequência

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

Uma sequência de operações sobre uma única árvore, partindo da árvore vazia. Cada passo indica qual caso (das seções de inserção, busca e remoção acima) ele exemplifica; no conjunto, os passos cobrem todos os casos das três operações, como mostra a tabela. Nos desenhos, cada passo mostra a árvore após a operação (nas remoções, antes e depois).

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

2.6 Complexidade

m = comprimento da chave (número de letras); n = número de chaves (palavras) armazenadas; |Σ| = tamanho do alfabeto (26 para a-z), tratado como constante; p = comprimento do prefixo buscado; t = nós visitados abaixo do prefixo (pelo menos o número de palavras encontradas e, no máximo, o total de letras delas).

Pior caso = o maior custo que pode acontecer, para o pior conjunto de palavras e a pior ordem de inserção. Caso médio = o custo típico, com palavras em ordem aleatória. Quando as duas colunas coincidem, o custo não depende de azar nos dados.

Por que o tempo continua O(m)?

Intuição: a compressão economiza nós e ponteiros, não letras. Para saber se uma chave está na árvore ainda precisamos conferir as m letras dela; a diferença é que as conferimos em blocos: em cada nó comparamos um rótulo inteiro (várias letras de uma vez) com o trecho correspondente da chave e consumimos esse trecho. Nunca voltamos atrás, então cada letra da chave é consumida no máximo uma vez: no total, no máximo m comparações de letras → O(m).

• Como na Trie, o custo não depende de n nem da forma da árvore: pior caso e caso médio coincidem.
• Em cada nó, achar a aresta certa é olhar a lista de irmãos (até |Σ| arestas, constante). Cada nó visitado consome pelo menos uma letra, então visitamos no máximo m nós: continua O(m) para alfabeto fixo. (A Patrícia visita menos nós que a Trie, mas compara as mesmas letras.)
• Inserção: desce O(m) e, no final, acontece no máximo uma divisão de aresta e no máximo uma folha nova (copiar o resto da chave, até m letras). Nunca mais que isso, porque depois da divisão as duas pontas já são distintas.
• Remoção: desce O(m) e faz ajustes locais: desmarcar o fim, apagar uma folha e, se o pai ficar com um único filho e sem fim, fundir duas arestas (concatenar os rótulos). Só o pai imediato pode ficar nessa situação, então há no máximo uma fusão.^*

^* Concatenar rótulos copia letras de outras palavras; na análise, m deve ser o tamanho da maior palavra envolvida. Se os rótulos forem guardados como (início, tamanho) na palavra original, a fusão custa O(1).

Por que no máximo 2n nós?

Depois da compressão, todo nó (menos a raiz) tem uma razão para existir: ou termina uma palavra (no máximo n nós assim) ou se bifurca, isto é, tem pelo menos dois filhos. Uma árvore com f folhas tem, no máximo, f − 1 nós que se bifurcam; e toda folha termina uma palavra, então f ≤ n. Logo: raiz + (≤ n nós de fim) + (< n bifurcações) ≤ 2n. Esse limite vale para qualquer conjunto de palavras (é uma garantia de pior caso), ao contrário da Trie, cujo número de nós pode chegar a n × m.

Os rótulos, porém, guardam letras: no pior caso (palavras sem prefixo em comum) cada palavra vira um único rótulo com todas as suas letras, somando O(n × m) letras. Guardando (início, tamanho) em vez de cópias, cada rótulo ocupa O(1) e o total cai para O(n).

2.7 Estrutura e funções em C

Cada nó guarda o rótulo da aresta que chega nele (uma string, não um caractere), a marca de fim de palavra e seus filhos. Como a Patrícia existe justamente para evitar vetores de 26 ponteiros, os filhos ficam numa lista encadeada de irmãos: filhos aponta para o primeiro filho e irmao para o próximo irmão. Dois irmãos nunca começam com a mesma letra, então a primeira letra do rótulo identifica a aresta certa.

typedef struct NodoPat {
    char *rotulo;             /* rótulo da aresta que chega neste nó */
    int   fim;                /* 1 se uma palavra termina neste nó */
    struct NodoPat *filhos;   /* primeiro filho */
    struct NodoPat *irmao;    /* próximo irmão (mesmo pai) */
} NodoPat;

NodoPat *criarPat(void);                                /* cria a raiz (rótulo vazio) */
void     inserirPat(NodoPat *raiz, const char *s);     /* insere s, criando folha ou dividindo aresta */
int      buscarPat(NodoPat *raiz, const char *s);      /* 1 se s está armazenada, 0 caso contrário */
void     destruirPat(NodoPat *raiz);                    /* libera todos os nós */

main de demonstração:

int main(void) {
    NodoPat *raiz = criarPat();

    const char *palavras[] = {"ar", "arco", "arte", "as", "asa", "bola", "bolo"};
    for (int i = 0; i < 7; i++)
        inserirPat(raiz, palavras[i]);

    inserirPat(raiz, "arca");                /* divide a aresta "co" */

    printf("buscarPat(arco) = %d\n", buscarPat(raiz, "arco"));   /* 1 */
    printf("buscarPat(arca) = %d\n", buscarPat(raiz, "arca"));   /* 1 */
    printf("buscarPat(arc)  = %d\n", buscarPat(raiz, "arc"));    /* 0: é só um prefixo */
    printf("buscarPat(bol)  = %d\n", buscarPat(raiz, "bol"));    /* 0: aresta "bol", sem fim */

    destruirPat(raiz);
    return 0;
}

2.8 O problema

Os rótulos são strings de tamanho variável: dividir uma aresta obriga a copiar e realocar texto, e achar a aresta certa significa percorrer uma lista de irmãos. Seria mais simples ter nós todos iguais, de tamanho fixo e com um único caractere. É o que a TST oferece.

3. TST (Ternary Search Tree / Árvore de Busca Ternária)

3.1 Estrutura

Vale olhar o que as duas estruturas anteriores deixaram em aberto:

• Trie: segue a chave letra por letra e é simples de implementar, mas cada nó carrega um vetor com um ponteiro para cada letra possível (26 para a-z), quase todos NULL. A memória vai quase toda para ponteiros vazios, e piora para alfabetos grandes.
• Patrícia: elimina o desperdício fundindo os nós de passagem, mas paga com nós mais complicados: rótulos que são strings de tamanho variável, divisão e fusão de arestas e listas de filhos para percorrer.

A TST (Ternary Search Tree) busca o meio-termo: mantém a simplicidade da Trie (um caractere por nó, seguindo a chave letra a letra), mas troca o vetor de 26 ponteiros por apenas três, e não precisa dos rótulos de tamanho variável da Patrícia. Todos os nós têm o mesmo tamanho pequeno:

• Cada nó armazena um único caractere e tem três filhos.
• esq e dir escolhem entre caracteres diferentes na mesma posição da chave (como numa ABP de caracteres); centro avança para o próximo caractere.
• O nó tem sempre 3 ponteiros, qualquer que seja o alfabeto.

A lógica é: em cada nó, comparamos o i-ésimo caractere da chave com c. Se menor, vamos para esq (sem avançar i). Se maior, vamos para dir (sem avançar i). Se igual, vamos para centro e avançamos i em 1.

Exemplo usado em toda a seção: as palavras "ar", "as", "arco" e "arte", inseridas nesta ordem. Arestas: < esq, = centro, > dir.

3.2 Inserção

Em cada nó visitado comparamos a letra atual da chave com o caractere c do nó: menor → esq; maior → dir; igual → centro, avançando uma letra. Quando o filho escolhido não existe, ele é criado. Os casos (exemplos na TST com "ar", "as", "arco" e "arte"):

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

Caso 1 — A letra é menor que a do nó

Vai-se para a esq. Se ela estiver vazia, cria-se o nó ali.

Caso 2 — A letra é maior que a do nó

Vai-se para a dir. Se ela estiver vazia, cria-se o nó ali.

Caso 3 — A letra é igual e ainda há letras na chave

Vai-se para o centro e avança-se uma letra. Se o centro estiver vazio, cria-se o nó ali (e os seguintes).

Caso 4 — A letra é igual e é a última da chave

Não se cria nó algum; basta olhar a marca de fim:

Exemplo combinado

Os casos se encadeiam numa mesma inserção:

3.3 Busca

Comparamos a letra atual com o nó visitado, como na inserção, mas sem criar nada. A chave só é encontrada no caso 1; os demais são falhas.

Caso 1 — Encontrada

A última letra casa num nó que marca fim.

Caso 2 — Precisa ir para a esq e ela está vazia

A letra é menor que a do nó e não há filho à esquerda.

Caso 3 — Precisa ir para a dir e ela está vazia

A letra é maior que a do nó e não há filho à direita.

Caso 4 — Precisa ir para o centro e ele está vazio

A letra casa, ainda faltam letras na chave, mas o nó não tem continuação.

Caso 5 — A última letra casa num nó que não marca fim

A chave é apenas prefixo de outras palavras.

3.4 Remoção

Busca-se a palavra e desmarca-se o fim do nó da última letra. Depois, subindo pelo caminho, apaga-se cada nó que ficou sem nenhum dos três filhos e sem marca de fim; a subida pára no primeiro nó que ainda é necessário. Os casos:

Caso 1 — A palavra não existe

A busca falha e a árvore não muda.

Caso 2 — O nó da última letra tem filhos

Outras palavras dependem desse nó (ou do que está abaixo dele): só se desmarca o fim.

Caso 3 — O nó da última letra não tem filhos

Apaga-se o nó e sobe-se, apagando cada nó que ficar sem filhos e sem fim. Três situações:

3a — Apaga um nó e pára num nó que ainda tem outro filho:

3b — Apaga vários nós antes de parar:

3c — Pára num nó que marca fim:

3.5 Exemplo completo: todos os casos em sequência

Exemplos retráteis: os exemplos desta aula ficam recolhidos (clique em "Ver exemplo" ou no título do passo). Expandir todos | Recolher todos

Uma sequência de operações sobre uma única árvore, partindo da árvore vazia. Cada passo indica qual caso (das seções de inserção, busca e remoção acima) ele exemplifica; no conjunto, os passos cobrem todos os casos das três operações, como mostra a tabela. Nos desenhos, cada passo mostra a árvore após a operação (nas remoções, antes e depois).

Verde = caminho percorrido (verde forte = encontrado); vermelho = onde a busca para, ou o que será removido (tracejado); amarelo = novo ou alterado; círculo duplo = fim de palavra.

3.6 Complexidade

m = comprimento da chave (número de letras); n = número de chaves (palavras) armazenadas; |Σ| = tamanho do alfabeto (26 para a-z), tratado como constante; p = comprimento do prefixo buscado; t = nós visitados abaixo do prefixo (pelo menos o número de palavras encontradas e, no máximo, o total de letras delas).

Pior caso = o maior custo que pode acontecer, para o pior conjunto de palavras e a pior ordem de inserção. Caso médio = o custo típico, com palavras em ordem aleatória. Quando as duas colunas coincidem, o custo não depende de azar nos dados.

Por que essa complexidade? Passos centrais e passos laterais

Intuição: na TST, cada posição da chave funciona como uma pequena ABP de letras. Ao percorrer a árvore damos dois tipos de passo:

• Passo central (=): a letra casou, avançamos para a próxima letra da chave. Acontece exatamente m vezes, uma por letra.
• Passo lateral (< ou >): a letra ainda não casou e procuramos entre as letras irmãs, como numa ABP. Quantos acontecem depende de como essa pequena ABP ficou.

Total de passos = m (centrais) + L (laterais). Tudo se resume a quanto vale L.

Pior caso: O(m × |Σ|)

Em uma posição há no máximo |Σ| letras diferentes (as irmãs têm letras distintas), então a pequena ABP daquela posição tem no máximo |Σ| nós. Se as letras forem inseridas em ordem alfabética (a, b, c, ..., z), essa ABP degenera numa lista e chegar à letra z custa 25 passos laterais. Se isso acontecer em todas as posições da chave, L chega a m × (|Σ| − 1): o pior caso é O(m × |Σ|). Isso não é só teoria: acontece quando as palavras são inseridas em ordem alfabética, por exemplo ao ler de uma lista já ordenada.

Repare que o pior caso não é O(m + log n): o log n só vale quando as pequenas ABPs estão razoavelmente balanceadas, e a TST não garante isso. Com |Σ| = 26 o estrago é limitado (no máximo uns 26 passos por letra), e para alfabetos enormes (Unicode) o pior caso fica ainda mais relevante.

Caso médio: ≈ m + log n

Com palavras inseridas em ordem aleatória, duas coisas ajudam:

• As ramificações só acontecem nas primeiras posições (cerca de log_|Σ| n delas). Depois que o prefixo identifica uma única palavra, os nós só têm filho central e não há mais passos laterais.
• Em cada posição ramificada, a pequena ABP (aleatória) tem profundidade média da ordem de log |Σ|.

Multiplicando: (log_|Σ| n posições) × (log |Σ| passos por posição) = log n passos laterais no total, pagos uma única vez ao longo da chave inteira (e não a cada letra). Outra forma de ver: cada passo lateral descarta, em média, cerca de metade das palavras que ainda poderiam casar, exatamente como numa ABP de n palavras. Por isso o custo típico é m + log n.

Atenção à notação: o "O(m + log n)" que aparece na literatura é esse custo médio/típico, não uma garantia de pior caso. (Com |Σ| constante, os dois são O(m), mas a constante do pior caso pode ser até |Σ| vezes maior que a do caso típico.) Embaralhar as palavras antes de inserir evita o pior caso na prática.

Inserção e remoção

• Inserção: a mesma descida da busca (centrais + laterais) mais a criação de, no máximo, m nós novos (O(1) cada). Mesmos limites: pior caso O(m × |Σ|), caso médio ≈ m + log n.
• Remoção: a descida da busca mais a subida apagando nós que ficaram sem filhos e sem fim; a subida percorre, no máximo, os mesmos nós da descida. Mesmos limites da busca.
• Busca por prefixo: chegar ao nó do prefixo custa como uma busca de p letras (pior caso p × |Σ|, médio ≈ p + log n), e percorrer a subárvore custa t, proporcional à resposta.

Espaço

• Cada nó guarda uma letra de uma posição, compartilhada por todas as palavras com o mesmo início. Pior caso: palavras sem prefixo em comum → um nó por letra de cada palavra: até n × m nós. Caso típico: bem menos, pelos prefixos compartilhados.
• O que diferencia a TST da Trie é o tamanho do nó: 3 ponteiros, 1 letra e 1 marca, sempre, em vez de |Σ| ponteiros. Por isso, mesmo com o mesmo número de nós, a TST ocupa muito menos memória.

3.7 Estrutura e funções em C

typedef struct NodoTST {
    char c;
    int  fim;
    struct NodoTST *esq, *centro, *dir;
} NodoTST;

/* pos = índice do caractere de s que está sendo processado (começar com 0) */
NodoTST *inserirTST(NodoTST *no, const char *s, int pos);   /* devolve a (nova) raiz da subárvore */
int      buscarTST(NodoTST *no, const char *s, int pos);    /* 1 se s está armazenada, 0 caso contrário */

main de demonstração:

int main(void) {
    NodoTST *raiz = NULL;                    /* TST vazia */

    raiz = inserirTST(raiz, "ar",   0);
    raiz = inserirTST(raiz, "as",   0);
    raiz = inserirTST(raiz, "arco", 0);
    raiz = inserirTST(raiz, "arte", 0);

    printf("buscarTST(arco) = %d\n", buscarTST(raiz, "arco", 0));   /* 1 */
    printf("buscarTST(arca) = %d\n", buscarTST(raiz, "arca", 0));   /* 0 */
    printf("buscarTST(ar)   = %d\n", buscarTST(raiz, "ar",   0));   /* 1 */
    return 0;
}

4. Aplicações

4.1 Aplicações Reais

• Trie: autocompletar (Google Search, IDE), verificador ortográfico (spell checker), dicionários de compressão (LZ78), filtros de palavras proibidas.
• Patrícia (Trie Comprimida): tabelas de roteamento IP (longest-prefix-match), servidores DNS, índices de strings em sistemas de arquivos.
• TST: autocompletar com alfabeto grande (Unicode, CJK), indexação de textos em linguagens com muitos caracteres, implementações de dicionários em compiladores.

5. Comparativo geral: ABP × Trie × Patrícia × TST

m = comprimento da chave; n = número de chaves; p = comprimento do prefixo; k = número de palavras encontradas; t = nós visitados abaixo do prefixo (≥ k e ≤ total de letras das palavras encontradas); |Σ| = tamanho do alfabeto. O caso médio da ABP e da TST supõe palavras inseridas em ordem aleatória (árvore razoavelmente balanceada). Na Trie e na Patrícia o tempo só depende de m: pior caso e caso médio coincidem.

Em uma frase cada:

• ABP: guarda palavras inteiras e compara a palavra toda a cada nó visitado.
• Trie: um caractere por nível; rápida e simples, mas gasta memória com o vetor de ponteiros.
• Patrícia: a Trie sem os nós de passagem; economiza memória, com nós e operações mais complexos.
• TST: um caractere por nó com apenas 3 ponteiros; nós pequenos e todos iguais, mas o tempo depende da ordem de inserção.

Resumo

Exercícios

1. Insira as palavras "gato", "gata", "pato", "pata" em uma Trie com alfabeto de letras minúsculas. Desenhe a estrutura resultante. O que acontece ao tentar inserir "gato" pela segunda vez?


2. Busque "pata" na Trie do exercício anterior. Quais nós são visitados, em que ordem, e qual a conclusão final?


3. Por que uma tabela hash não suporta busca por prefixo? Explique com um exemplo concreto usando as palavras "pre", "prefixo", "preto" e "preço".


4. Uma Trie com alfabeto de 26 letras minúsculas tem 1.000 nós. Quantos ponteiros são armazenados no total? Se o vocabulário for de palavras em português com comprimento médio de 7 caracteres, quantos desses ponteiros provavelmente são NULL?


5. Qual é a diferença fundamental entre uma Trie e uma Patrícia (Trie Comprimida)? Em que tipo de vocabulário a compressão é mais eficiente?


6. Na TST, por que o nó raiz não armazena o "primeiro caractere de todas as palavras" como faz a Trie (onde a raiz distribui pelas primeiras letras)?


7. Comparando Trie e TST: em qual a busca por prefixo "pre" é mais simples de implementar? Por quê?


8. Uma Trie contém as palavras "pre", "preto", "prefixo", "preço". O que a busca pelo prefixo "pre" retorna? Qual a diferença entre buscar "pre" como palavra e buscar "pre" como prefixo?


9. Para construir um sistema de autocompletar para um teclado de celular com 50.000 palavras em português, qual estrutura você escolheria entre Trie, Patrícia (Trie Comprimida) e TST? Justifique levando em conta memória disponível e eficiência de busca por prefixo.

Gabaritos

Busca de "pata":

1. Raiz → filhos['p'−'a'] = nó 'p'. Existe.
2. Nó 'p' → filhos['a'−'a'] = nó 'a'. Existe.
3. Nó 'a' → filhos['t'−'a'] = nó 't'. Existe.
4. Nó 't' → filhos['a'−'a'] = nó 'a'. Existe.
5. String terminou (s[4]='\0'). Verificar fim do nó 'a': fim=1.

Conclusão: ENCONTRADO. Foram visitados 4 nós (excluindo a raiz),
correspondendo exatamente ao comprimento da palavra. Custo: O(4) = O(m).

hash("pre")    = 41723
hash("prefixo")= 89204
hash("preto")  = 12567
hash("preço")  = 73891