Trie

  • A trie is used to store strings.
  • Each Trie node represents a string (a prefix).
  • Toot node is associated with the empty string.
  • All the descendants of a node have a common prefix
  • We can declare a boolean in each node as a flag to indicate if the string represented by this node is a word or not.

Trie Representation

First Solution - Map

struct TrieNode {
    unordered_map<char, TrieNode*> children;
};

Second Solution - Array

// change this value to adapt to different cases
#define N 26
struct TrieNode {
    TrieNode* children[N];
};

Insertion in Trie

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          cur.children[c] = new Trie node
5.      cur = cur.children[c]
6. cur is the node which represents the string S

Search in Trie

1. Initialize: cur = root
2. for each char c in target string S:
3.      if cur does not have a child c:
4.          search fails
5.      cur = cur.children[c]
6. search successes

Technique 1: Update trie node value with delta

When inserting key with values, we can use a delta value (the difference between old key and new key) to update each node. This will require extra space to store old key value.

  • Map Sum Pairs

A Trie is a special form of a Nary tree. Typically, a trie is used to store strings. Each Trie node represents a string (a prefix). Each node might have several children nodes while the paths to different children nodes represent different characters. And the strings the child nodes represent will be the origin string represented by the node itself plus the character on the path.

  • The value of the node is exactly formed by the letters in the path from the root to the node sequentially.

  • It is worth noting that the root node is associated with the empty string.

  • One important property of Trie is that all the descendants of a node have a common prefix of the string associated with that node. That's why Trie is also called prefix tree.

Second Solution - Map

We can declare a hashmap in each node. The key of the hashmap are characters and the value is the corresponding child node.

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    // you might need some extra values according to different cases
};

/** Usage:
 *  Initialization: TrieNode root = new TrieNode();
 *  Return a specific child node with char c: (root->children)[c]
 */

It saves some space since we only store the children nodes we need. It is also more flexible because we are not limited by a fixed length and fixed range.

Search Word

If search fails which means that no words start with the target word, the target word is definitely not in the Trie.

If search succeeds, we need to check if the target word is only a prefix of words in Trie or it is exactly a word. To solve this problem, you might want to modify the node structure a little bit.

Hint: A boolean flag in each node might work.

results matching ""

    No results matching ""