Skip to content

Trie

In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within as set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters. Unlike a binary search tree, nodes in the trie do not store their associated key, Instead, a node's position in the trie defines the key with which it is associated.

trie

Implementation

An implementation of trie can be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Trie {
  struct Node {
    bool is_word{false};
    vector<Node*> child{};
    Node() : child(26, nullptr) {};
  };
  Node* root{new Node{}};
 public:
  void insert(const string& word) {
    auto node = root;
    for (auto c : word) {
      if (!node->child[c - 'a']) node->child[c - 'a'] = new Node{};
      node = node->child[c - 'a'];
    }
    node->is_word = true;
  }

  bool search(const string& word) {
    auto node = root;
    for (auto c : word) {
      if (!node->child[c - 'a']) return false;
      node = node->child[c - 'a'];
    }
    return node->is_word;
  }

  bool startsWith(const string& prefix) {
    auto node = root;
    for (auto c : prefix) {
      if (!node->child[c - 'a']) return false;
      node = node->child[c - 'a'];
    }
    return true;
  }
};