keys can be implemented by building a trie for the given keys and traversing the tree in pre-order fashion; this is also a form of radix sort. Tries are also fundamental data structures for burstsort, which is notable for being the fastest string sorting algorithm as of 2007, accompanied for its efficient use of CPU cache. Full-text search A special kind of trie, called a suffix tree, can be used to index all suffixes in a text to carry out fast full-text searches. Web search engines A specialized kind of trie called a compressed trie, is used in web search engines for storing the indexes - a collection of all searchable words. Each terminal node is associated with a list of URLs—called occurrence list—to pages that match the keyword. The trie is stored in the main memory, whereas the occurrence is kept in an external storage, frequently in large clusters, or the in-memory index points to documents stored in an external location. Bioinformatics Tries are used in Bioinformatics, notably in sequence alignment software applications such as BLAST, which indexes all the different substring of length k (called k-mers) of a text by storing the positions of their occurrences in a compressed trie sequence databases. Internet routing Compressed variants of tries, such as databases for managing Forwarding Information Base (FIB), are used in storing IP address prefixes within routers and bridges for prefix-based lookup to resolve mask-based operations in IP routing. See also Suffix tree Hash trie Hash array mapped trie Prefix hash tree Ctrie HAT-trie References External links NIST's Dictionary of Algorithms and Data Structures: Trie Trees (data structures) Finite automata Articles with example Python (programming language) code