Tries

after work

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

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s