Trie

How it is used

Used for prefix lookup and dictionaries. Unlike a suffix tree, it need not index every suffix of a text.

Example sentences

1. The autocomplete service uses a trie to find names beginning with the typed letters.

   Following the typed prefix narrows the search to one part of the tree.

2. Several route prefixes share the same initial path in our trie.

   Common starting elements are represented together rather than repeated independently.

Common collocations

• prefix trie
• trie traversal

Related terms

• treeA data structure with a root at the top and branches of child nodes below it, used for data that has levels, such as folders, menus or a page's HTML.
• suffix treeA tree structure that stores all suffixes of a string, allowing fast searches for substrings and repeated patterns.

More terms: Data Structures and Algorithms

• algorithm
• data structure
• array
• iterate
• hash map
• recursion
• Big O notation
• time complexity
• index
• sort
• stack
• queue