Trie

From DmWiki

The name Trie is excerpted from the word retrieve and is one of the fastest data structures for associating lists of small data types to a structure. (Such as strings of characters.)

The most common use of trie structures is as an associative array using a string as the key value to index from. It is often preferred over a hash table when speed is of the essence becuase the trie structure is guarenteed to use constant time every time while the hash table degenerates from contstant time to O(n) as the load factor increases.

A trie is implemented using an array of pointers (each to the next node in the trie structure depending on the value of the current element) thus producing an n-ary tree structure.

This article is a stub. You can help improve the article by expanding it.