The Beginners’ Guide to Trie: How to Use the Trie in C++?

  • 时间：2020-09-23 15:50:46
  • 分类：网络文摘
  • 阅读：113 次

The Trie is common used data structure to speed up the word searching. The Trie is a structure to index the words character by character.

trie-example The Beginners' Guide to Trie: How to Use the Trie in C++? algorithms c / c++ data structure tutorial

trie-example

Trie Definition in C++

Take a lowercase 26 letters for example, we can define a Trie node as a struct, as the follows:

1
2
3
4
5

struct TrieNode {
    TrieNode* children[26] = { nullptr };
    bool isWord = false; // denote if up to this point a word is complete
    string word = ""; // optional
};
struct TrieNode {
    TrieNode* children[26] = { nullptr };
    bool isWord = false; // denote if up to this point a word is complete
    string word = ""; // optional
};

Of course, you can define it as a class, but a Struct is lightweight, and serve the purpose. Each TrieNode will have an array of pointers indicating its next character. Meantime, it will have a boolean field to denote weather current node is the end of a word.

Insert/Index a Word in the Trie

First, we can declare a root node, then, we can call the following functoin to insert/index a word in the Trie.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void insert(struct TrieNode* root, string key) {
    struct TrieNode *p = root;
    for (const auto &n: key) {
        int index = n - 'a';
        if (p->children[index] == nullptr) { 
            // not found, create a new child node
            p->children[index] = new TrieNode();
        }
        // navigate the Trie Path            
        p = p->children[index];        
    }
    // reaching the end of the word, mark it complete
    p->isWord = true;    
    p->word = key;
}
void insert(struct TrieNode* root, string key) {
    struct TrieNode *p = root;
    for (const auto &n: key) {
        int index = n - 'a';
        if (p->children[index] == nullptr) { 
            // not found, create a new child node
            p->children[index] = new TrieNode();
        }
        // navigate the Trie Path            
        p = p->children[index];        
    }
    // reaching the end of the word, mark it complete
    p->isWord = true;    
    p->word = key;
}

The indexing takes O(N) for inserting a word to the dictionary where N is the length of the word string.

Search a Word in the Trie

Given a root of TrieNode, we can easily follow the path until it has reached the end of the word i.e. the TrieNode’s isWord is true or NULL which indicates that the word is not in the dictionary. 

1
2
3
4
5
6
7
8
9
10
11
12

bool search(struct TrieNode* root, string key) {
    struct TrieNode *p = root;
    for (const auto &n: key) {
        int index = n - 'a';
        // not found in the dictionary
        if (p->children[index] == nullptr) return false;
        // navigate to next letter
        p = p->children[index];
    }
    // the current node is the end of the word        
    return (p != nullptr) && (p->isWord);
}
bool search(struct TrieNode* root, string key) {
    struct TrieNode *p = root;
    for (const auto &n: key) {
        int index = n - 'a';
        // not found in the dictionary
        if (p->children[index] == nullptr) return false;
        // navigate to next letter
        p = p->children[index];
    }
    // the current node is the end of the word        
    return (p != nullptr) && (p->isWord);
}

Finding a word is O(N) where N is the number of the characters.

Example of Using Trie

1
2
3
4

struct TrieNode *root = new TrieNode();
insert(root, "hello world!");
search(root, "hello"); // false
search(root, "hello world!"); // true
struct TrieNode *root = new TrieNode();
insert(root, "hello world!");
search(root, "hello"); // false
search(root, "hello world!"); // true

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
求一个数是另一个数的几分之几，为什么要用第一个数除以第二个数？　 这筐苹果至少有多少个？　 最终得到的一位数是多少？　 怎样才能全部过河？　 最多多少页？最少多少页？　 欧拉公式F+V-E=2　 Ｘ侦探和万能公式　 音乐数3、4、6　 试管中的所有空间被细胞占满　 走马灯数　
评论列表
添加评论