Trie: diferenças entre revisões
Faltavam chaves na legenda da figura "Trie example.svg" |
|||
| Linha 1: | Linha 1: | ||
[[Imagem:trie example.svg|thumb |
[[Imagem:trie example.svg|thumb|250px|Uma '''trie''' para as chaves "A", "to", "tea", "ted", "ten", "i", "in" e "inn".]] |
||
Em [[ciência da computação]], uma '''trie''', ou '''árvore de prefixos''', é uma [[estrutura de dados]] do tipo [[árvore ordenada]], que pode ser usada para armazenar um [[array associativo]] em que as chaves são normalmente [[cadeia de caracteres|cadeias de caracteres]]. [[Edward Fredkin]], o inventor, usa o termo '''trie''' (do [[Língua inglesa|inglês]] "re'''trie'''val") (recuperação), porque essa estrutura é basicamente usada na recuperação de dados. De acordo com essa [[etimologia]] ele é pronunciado [tri] ("tree"), embora alguns encoragem o uso de [traɪ] ("try") de modo a diferenciá-lo do termo mais geral [[árvore (estrutura de dados)|tree]]. |
Em [[ciência da computação]], uma '''trie''', ou '''árvore de prefixos''', é uma [[estrutura de dados]] do tipo [[árvore ordenada]], que pode ser usada para armazenar um [[array associativo]] em que as chaves são normalmente [[cadeia de caracteres|cadeias de caracteres]]. [[Edward Fredkin]], o inventor, usa o termo '''trie''' (do [[Língua inglesa|inglês]] "re'''trie'''val") (recuperação), porque essa estrutura é basicamente usada na recuperação de dados. De acordo com essa [[etimologia]] ele é pronunciado [tri] ("tree"), embora alguns encoragem o uso de [traɪ] ("try") de modo a diferenciá-lo do termo mais geral [[árvore (estrutura de dados)|tree]]. |
||
Revisão das 14h30min de 5 de setembro de 2014
Em ciência da computação, uma trie, ou árvore de prefixos, é uma estrutura de dados do tipo árvore ordenada, que pode ser usada para armazenar um array associativo em que as chaves são normalmente cadeias de caracteres. Edward Fredkin, o inventor, usa o termo trie (do inglês "retrieval") (recuperação), porque essa estrutura é basicamente usada na recuperação de dados. De acordo com essa etimologia ele é pronunciado [tri] ("tree"), embora alguns encoragem o uso de [traɪ] ("try") de modo a diferenciá-lo do termo mais geral tree.
Ao contrário de uma árvore de busca binária, nenhum nó nessa árvore armazena a chave associada a ele; ao invés disso, ela é determinada pela sua posição na árvore. Todos os descendentes de qualquer nó têm um prefixo comum com a cadeia associada com aquele nó, e a raiz é associada com a cadeia vazia. Normalmente, valores não são associados com todos os nós, apenas com as folhas e alguns nós internos que correspondem a chaves de interesse.
No exemplo mostrado na imagem, as chaves estão listadas nos nós e os valores abaixo dos mesmos. Cada palavra completa tem um valor inteiro associado a ela. Uma trie pode ser vista como um autômato finito determinístico, embora o símbolo em cada aresta é freqüentemente implícito na ordem dos galhos.
Não é necessário que as chaves sejam explicitamente armazenadas nos nós. (Na imagem, as palavras são mostradas apenas para ilustrar como a trie funciona.)
Embora seja o mais comum, tries não precisam utilizar cadeias de caracteres como chaves. Os mesmos algoritmos podem facilmente ser adaptados para funções similares de listas ordenadas de qualquer construção, como permutações em uma lista de dígitos, etc.
Vantagens e desvantagens com relação a árvore de busca binária
As principais vantagens de trie sobre Árvore de busca binária, são:
- A busca é mais rápida.
- Uma árvore Trie requer menos espaço quando contém um grande número de cadeias curtas, porque as chaves não são armazenadas de forma explícita e os nós das chaves iniciais comuns são compartilhados.
Aplicações
Substituição de outras estrutura de dados
Árvore trie pode substituir uma tabela hash.
Representar um dicionário
É comumente usada para localizar uma palavra em um dicionário.