loading...

Tries

jjb profile image JB Updated on ・2 min read

Resources

  1. Trie Overview
  2. Trie Overview + Implementation
  3. Trie Operations + Implementations
  4. In Depth Trie Explanation
  5. A good implementation of the delete operation

(Also worth mentioning is this article from the Visual Studio Magazine. The article explains tries and why you might want to use them.)

Takeaways:

  • A trie is an ordered tree that compactly stores strings. Each node in a trie represents a single character in a string. Say we store the words "car" and "cars" in a trie - the trie would only use four nodes for both - one for each distinct letter of the words (c,a,r,s).
  • They are also known as digital trees and prefix trees.
  • A trie is most efficient when it is storing strings with similar prefixes, but in general tries are usually not space efficient. They have a space complexity of O(n + k).
  • They are useful for queries involving string prefixes, such as suggesting the next character(s) for a given prefix.
  • Tries are not usually found in standard libraries of popular languages (Java & C#, for example, do not have a trie data structure).
  • Tries are typically implemented using arrays or hash tables.
  • Although hash table implementations are more flexible, array implementations can be more efficient by placing limitations on the trie (like only allowing characters a-z)
  • Many trie implementations will use booleans to mark the end of words/strings. But some implementations will use an additional node appended after the last character of the word. This additional node might contain a NULL value or a special character.
  • Similarly, the root/head node of a trie can be represented in various ways. For my implementations I used a special character ($) to denote the root node.
  • Inserting and searching are both O(k) operations.
  • A related data structure is a radix tree
  • Radix trees are basically a space efficient trie. A trie only stores one character per node, whereas a radix tree can store many. A radix tree is essentially a trie where all nodes that are the only child are merged with their parent nodes - this means less total nodes are required for the same number of words.

Below you will find two trie implementations:

As always, if you found any errors in this post please let me know!

Discussion

pic
Editor guide