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

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

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) —

推荐阅读：
一乘二分之一加二乘三分之一加…九十九乘一百分之一加一百乘一百零一分之一等于多少？求答题过程和答案。　 为什么所有剩下的钱加起来是51元？　 十二个乒乓球特征相同，其中只有一个重量异常　 某银行有两种储蓄计划——单利和复利的问题　 大院里养了三种动物。每只小山羊戴3个铃铛，每只狗戴1个铃铛　 某本书正文所标注的页码共用了2989个阿拉伯数字，问这本书的正文一共有多少页？　 有两棵古槐树，500年前有个学者说　 高中生儿童节作文　 勿以恶小而为之勿以善小而不为　 美丽的长岛作文　
评论列表
添加评论