Sebuah trie (pohon awalan) adalah pohon di mana setiap sisi mewakili karakter dan setiap jalur dari akar mengeja awalan. Kata-kata yang berbagi awalan berbagi jalur yang sama, membuat pencarian awalan sangat cepat.
Structure
text
Insert "cat", "car", "dog":
root
/ \
c d
| |
a o
/ \ |
t* r* g* (* marks end-of-word)
