mirror of
https://github.com/trekhleb/javascript-algorithms.git
synced 2025-12-08 19:06:00 +00:00
da6ae08851
* Update README.pt-BR.md * TRIE README.pt-BR typo * TREE README.pt-BR typo * Stack README.pt-BR typo * Priority Queue README.pt-BR typo * hash-table README.pt-BR typo * doubly-linked-list README.pt-BR typo * disjoint-set README.pt-BR typo * bloom-filter README.pt-BR typo * merge-sort pt-BR translation * merge-sort README added pt-BR option * insertion sort pt-BR translation * insertion sort README added pt-br option * heap-sort pt-BR translation * heap-sort READMED added pt-BR option * bubble sort pt-BR typo * pt-BR translation for sorting algorithms Fixed typos and translated all the missing algorithms * Update README.pt-BR.md * linked list pt-BR translation * ml pt-BR translation * fix typo in README Co-authored-by: Oleksii Trekhleb <trehleb@gmail.com>
28 lines
1.3 KiB
Markdown
28 lines
1.3 KiB
Markdown
# Á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)
|