Introduction

Trying to Understand Tries

• special trees (prefix trees) that make searching and storing strings more efficient
• tries have many practical applications, such as conducting searches and providing autocomplete. It is helpful to know these common applications so that you can easily identify when a problem can be efficiently solved using a trie
• the size of a trie is directly correlated to the size of all the possible values that the trie could represent

Advantages

• Sometimes Space-Efficient
  • if you're storing lots of words that start with similar patterns, tries may reduce the overall storage cost by storing shared prefixes once
• Efficient Prefix Queries
  • Tries can quickly answer queries about words with shared prefixes, like:
    • How many words start with "choco"?
    • What's the most likely next letter in a word that starts with "strawber"?

Disadvantages

• Usually Space-Inefficient
  • tries rarely save space when compared to storing strings in a set
  • ASCII characters in a string are one byte each.
  • each link between trie nodes is a pointer to an address - eight bytes on a 64-bit system
  • so, the overhead of linking nodes together often outweighs the savings from storing fewer characters
• Not Standard
  • most languages don't come with a built-in trie implementation, you'll need to implement one yourself

Corner cases

• Searching for a string in an empty trie
• Inserting empty strings into a trie
• Sometimes preprocessing a dictionary of words (given in a list) into a trie, will improve the efficiency of searching for a word of length k, among n words. Searching becomes O(k) instead of O(n).

Operations

Create

Trie()

Initializes the trie object.