# Árvore de Prefixos (Trie) Na ciência da computação, uma **trie**, também chamada de árvore digital (digital tree) e algumas vezes de _radix tree_ ou _prefix tree_ (tendo em vista que eles podem ser pesquisados por prefixos), é um tipo de árvore de pesquisa, uma estrutura de dados de árvore ordenada que é usado para armazenar um conjunto dinâmico ou matriz associativa onde as chaves são geralmente _strings_. Ao contrário de uma árvore de pesquisa binária (binary search tree), nenhum nó na árvore armazena a chave associada a esse nó; em vez disso, sua posição na árvore define a chave com a qual ela está associada. Todos os descendentes de um nó possuem em comum o prefixo de uma _string_ associada com aquele nó, e a raiz é associada com uma _string_ vazia. Valores não são necessariamente associados a todos nós. Em vez disso, os valores tendem a ser associados apenas a folhas e com alguns nós internos que correspondem a chaves de interesse. Para a apresentação otimizada do espaço da árvore de prefixo (_prefix tree_), veja árvore de prefixo compacto.  *Made with [okso.app](https://okso.app)* ## Referências - [Wikipedia](https://en.wikipedia.org/wiki/Trie) - [YouTube](https://www.youtube.com/watch?v=zIjfhVPRZCg&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8&index=7&t=0s)