Trie

Finalmente voltei a ter tempo para voltar a escrever algo no blog.
Hoje trago uma estrutura de dados que considero muito útil que é a Trie.
É utilizada para armazenar strings e tem a vantagem de procurá-las muito mas mesmo muito rapidamente!

Adiciona uma string em O(M) em que M é o tamanho de string e o melhor é que procura em O(M) também! Com um típico array de strings teriamos uma tempo de pesquisa O(N) em que N é a quantidade de strings, ainda teríamos mais a comparação da string que queremos procurar com a que estamos a "atravessar" no momento, mas decidi desprezar esse factor.

O código está em C++ mas é facilmente "traduzido" para C (linguagem que costumo usar nestes meus posts aka artigos).

Deixo também mais alguma informação sobre a mesma estrutura de dados:
* Wikipédia
* TopCoder

Trie - Código

Este código lê as strings (1 string por cada linha) de um ficheiro chamado wordlist.in, não esquecer isto!

Resumindo:
* Tempo de inserção: O(M * N), N = Quantidade de strings (tempo total)
* Tempo de pesquisa: O(M)

Boas programações.