Editing Trie (section)

=== Compressed tries ===
{{main|Radix tree}}

[[Radix tree]], also known as a '''compressed trie''', is a space-optimized variant of a trie in which any node with only one child gets merged with its parent; elimination of branches of the nodes with a single child results in better metrics in both space and time.<ref>{{cite web|url=https://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|publisher=[[University of Florida]]|access-date=17 April 2022|archive-url=https://web.archive.org/web/20160703161316/http://www.cise.ufl.edu/~sahni/dsaac/enrich/c16/tries.htm|archive-date=3 July 2016|url-status=live|author=Sartaj Sahni|title=Data Structures, Algorithms, & Applications in C++: Tries|year=2004}}</ref><ref>{{cite book|title=Handbook of Data Structures and Applications|first1=Dinesh P.|last1=Mehta|first2=Sartaj|last2=Sahni|isbn= 978-1498701853 |publisher=[[Chapman & Hall]], [[University of Florida]]|url=https://www.routledge.com/Handbook-of-Data-Structures-and-Applications/Mehta-Sahni/p/book/9780367572006|edition=2|date=7 March 2018|chapter=Tries}}</ref>{{rp|p=452}} This works best when the trie remains static and set of keys stored are very sparse within their representation space.<ref>{{cite journal|title=Incremental Construction of Minimal Acyclic Finite-State Automata|volume=26|issue=1|date=1 March 2000|author1=Jan Daciuk |author2=Stoyan Mihov |author3=Bruce W. Watson |author4=Richard E. Watson |journal = [[Computational Linguistics (journal)|Computational Linguistics]] |pages=3–16|publisher=[[MIT Press]]|doi=10.1162/089120100561601|arxiv=cs/0007009|bibcode=2000cs........7009D|url=https://direct.mit.edu/coli/article/26/1/3/1628/Incremental-Construction-of-Minimal-Acyclic-Finite|doi-access=free}}</ref>{{rp|p=3–16}}

One more approach is to "pack" the trie, in which a space-efficient implementation of a sparse packed trie applied to automatic [[hyphenation algorithm|hyphenation]], in which the descendants of each node may be interleaved in memory.<ref name=Liang1983>{{cite thesis|degree=Doctor of Philosophy|title=Word Hy-phen-a-tion By Com-put-er|url=http://www.tug.org/docs/liang/liang-thesis.pdf|author=Franklin Mark Liang|year=1983|publisher=Stanford University|access-date=2010-03-28|archive-url=https://web.archive.org/web/20051111105124/http://www.tug.org/docs/liang/liang-thesis.pdf|url-status=live|archive-date=2005-11-11}}</ref>

==== Patricia trees ====
{{multiple image
| direction = vertical
| image1 = Patricia tree.png
| image2 = Patricia tree ASCII to binary.png
| footer = Patricia tree representation of the string set<br/>{{mono|{{(}}in, integer, interval, string, structure{{)}}}}.
| width = 400
}}
Patricia trees are a particular implementation of the compressed binary trie that uses the [[Binary code|binary encoding]] of the string keys in its representation.<ref>{{cite web|url=https://xlinux.nist.gov/dads/HTML/patriciatree.html|publisher=[[National Institute of Standards and Technology]]|archive-date=14 February 2022|archive-url=https://web.archive.org/web/20220214182428/https://xlinux.nist.gov/dads/HTML/patriciatree.html|url-status=live|access-date=17 April 2022|title=Patricia tree}}</ref><ref name="gonnet91">{{cite book|title=Handbook of algorithms and data structures: in Pascal and C|edition=2|date=January 1991|isbn=978-0-201-41607-7|publisher=[[Addison-Wesley]]|location=[[Boston]], [[United States]]|first1=G. H.|last1=Gonnet|first2=R. Baeza|last2=Yates|url=https://dl.acm.org/doi/book/10.5555/103324}}</ref>{{rp|p=140}} Every node in a Patricia tree contains an index, known as a "skip number", that stores the node's branching index to avoid empty subtrees during traversal.{{r|gonnet91|p=140-141}} A naive implementation of a trie consumes immense storage due to larger number of leaf-nodes caused by sparse distribution of keys; Patricia trees can be efficient for such cases.{{r|gonnet91|p=142}}{{r|maxime09|p=3}}

A representation of a Patricia tree is shown to the right. Each index value adjacent to the nodes represents the "skip number"—the index of the bit with which branching is to be decided.<ref name="maxime09">{{cite book|title=Encyclopedia of Database Systems|first1=Maxime|last1=Crochemore|first2=Thierry|last2=Lecroq|url=https://link.springer.com/referencework/10.1007/978-0-387-39940-9|doi=10.1007/978-0-387-39940-9|isbn=978-0-387-49616-0|publisher=[[Springer Publishing]]|location=[[Boston]], [[United States]]|year=2009|chapter=Trie|bibcode=2009eds..book.....L |via=[[HAL (open archive)]]}}</ref>{{rp|p=3}} The skip number 1 at node 0 corresponds to the position 1 in the binary encoded ASCII where the leftmost bit differed in the key set {{mvar|X}}.{{r|maxime09|p=3-4}} The skip number is crucial for search, insertion, and deletion of nodes in the Patricia tree, and a [[bit masking]] operation is performed during every iteration.{{r|gonnet91|p=143}}