Tries are a very fast data structure to use for associative arrays, since most of their operations (add/update/delete) are based on the size of the key rather than the number of values actually stored in the data structure.
There are many kinds of tries (pronounced “trys”). Sidenote, “trie” comes from the word retrieval, but was pronounced “try” instead of “tree” to avoid confusing with tree data structures. The basic, R-way Trie, wastes a lot of space marking null leaves. Less wasteful versions of tries have been created like: TST (ternary search trie) and Patricia trie (Radix Tree).
TSTs are popular, and used by projects that need to search for text such as Apache Lucene. Besides the speed improvements over hash tables, TSTs also provide operations that other associative array implementations like the functions: prefix matching, wildcard matching, longest prefix.
Bottom line: Using a data structure like Trie, you can…
View original post 17 more words