View source for Trie

== Overview ==
Tries are a form of string-indexed look-up data structure, which is used to store a dictionary list of words that can be searched on in a manner that allows for efficient generation of [[Autocomplete|completion lists]].<ref>{{cite web|url=https://ds.cs.rutgers.edu/assignment-trie/|title=Trie|year=2022|publisher=School of Arts and Science, [[Rutgers University]]|archive-url=https://ghostarchive.org/archive/20220417170426/https://ds.cs.rutgers.edu/assignment-trie/|url-status=live|archive-date=17 April 2022|access-date=17 April 2022}}</ref><ref>{{cite journal|publisher=[[Syracuse University]]|url=https://surface.syr.edu/eecs_techreports/162/ |doi=10.1017/S0960129500000803|first1=Richard H.|last1=Connelly|first2=F. Lockwood|last2=Morris|year=1993|title= A generalization of the trie data structure|journal= Mathematical Structures in Computer Science|volume=5 |issue=3 |pages=381–418 |s2cid=18747244 }}</ref>{{rp|p=1}} A prefix trie is an [[ordered tree]] data structure used in the representation of a set of strings over a finite alphabet set, which allows efficient storage of words with common prefixes.<ref name="cvr14" />

Tries can be efficacious on [[string-searching algorithm]]s such as [[predictive text]], [[approximate string matching]], and [[spell checking]] in comparison to binary search trees.<ref name="aho75" /><ref name="Liang1983" />{{r|reema18|p=358}} A trie can be seen as a tree-shaped [[deterministic finite automaton]].<ref>{{cite conference|conference= International Conference on Implementation and Application of Automata |title=Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings|first=Jan|last=Daciuk|date=24 June 2003|doi=10.1007/3-540-44977-9_26|url=https://link.springer.com/chapter/10.1007/3-540-44977-9_26|isbn= 978-3-540-40391-3|publisher=[[Springer Publishing]]|pages=255–261|url-access=subscription}}</ref>