You are here
Home ›trie
Primary tabs
trie
A trie is a digital tree for storing a set of strings in which there is one node for every prefix of every string in the set. The name comes from the word retrieval, and thus is pronounced the same as tree (which leads to much confusion when spoken aloud). The word retrieval is stressed, because a trie has a lookup time that is equivalent to the length of the string being looked up.
If a trie is to store some set of strings (where is an alphabet), then it takes the following form. Each edge leading to non-leaf nodes in the trie is labelled by an element of . Any edge leading to a leaf node is labelled by (some symbol not in ). For every string , there is a path from the root of the trie to a leaf, the labels of which when concatenated form (where is the string concatenation operator). For every path from the root of the trie to a leaf, the labels of the edges concatenated form some string in .
Example
Suppose we wish to store the set of strings . The trie that stores would be
Mathematics Subject Classification
05C05 Trees68P20 Information storage and retrieval
- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new Education: Project: PlanetMath Outlines Series by unlord
May 17
new image: sinx_approx.png by jeremyboden
new image: approximation_to_sinx by jeremyboden
new image: approximation_to_sinx by jeremyboden
new question: Solving the word problem for isomorphic groups by unlord
new image: LineDiagrams.jpg by m759
new image: ProjPoints.jpg by m759
new image: AbstrExample3.jpg by m759
new image: four-diamond_figure.jpg by m759
May 16
new problem: Curve fitting using the Exchange Algorithm. by jeremyboden


