Pular para o conteúdo

O básico de tries

Aula 1 de 4 · 5 min

O básico de tries

Passo 1 de 10

Uma trie (árvore de prefixos) vazia é um único nó raiz. Toda palavra começa seu caminho aqui.

A ideia

Uma trie (árvore de prefixos) soletra as palavras em vez de guardá-las inteiras. Cada aresta carrega um caractere, então o caminho que desce da raiz é um prefixo. Palavras que compartilham um prefixo compartilham esses nós.

Uma flag por nó marca “uma palavra termina aqui” — sem ela, você não distingue a palavra car do prefixo dentro de cart.

Exemplo do mundo real

O velho fichário de uma biblioteca: gavetas etiquetadas A–C, dentro delas divisórias para a segunda letra, depois para a terceira. Ninguém guarda o título duas vezes só porque dois livros começam com “Ca” — você percorre as etiquetas e todo livro atrás daquela divisória é um acerto.

O código

Sua vez

O que isto imprime?

root = {}
for word in ["do", "dorm"]:
  node = root
  for ch in word:
      node = node.setdefault(ch, {})
  node["$"] = True
print(sorted(root["d"]["o"]))

Mini quiz

1 / 3

O que uma aresta de uma trie representa?