Skip to content

Tries

April 13, 2013

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 find anything no matter how large the number of elements by examining about 50-100 bits of information.

Advertisements

From → Algorithms

Leave a Comment

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

%d bloggers like this: