trie（字典树）原理及C++代码实现

字典树，又称前缀树，是用于存储大量字符串或类似数据的数据结构。

它的原理是利用相同前缀来减少查询字符串的时间。

不同于BST把关键字保存在本结点中，TRIE可以想象成把关键字和下一个结点的指针绑定，事实上我也是用map来实现的，所以不熟悉map的提前熟悉map的操作。

Tire的逻辑比较抽象，所以如果是第一次见到这种组织方式的建议先熟悉熟悉这种逻辑再开始写代码，这样会比较顺畅。

代码如下：（仅供参考）

 1 struct Node {
 2 public :
 3     bool isWord;
 4     unordered_map<char, Node*> next;
 5 public :
 6     Node(bool Isword = false) : isWord(Isword) {}
 7 };
 8 
 9 class Trie {
10     Node root;
11     int size;
12 
13 public :
14     Trie() : size(0) {}
15     int getSize() {return size;}
16     void add(string word);  //添加一个新单词
17     bool contains(string word); //查询是否有该单词
18     bool isPrefix(string prefix); //查询是否有单词以该prefix为前缀
19     void del(string word);  //删除一个单词
20 };
21 
22 void Trie::add(string word) {
23     Node *curr = &root;
24 
25     for (int i = 0; i < word.length(); ++i) {
26         Node* ptr = nullptr;
27         auto ret = curr->next.insert({word[i], ptr});
28         if (ret.second)
29             ret.first->second = new Node();
30         curr = ret.first->second;
31     }
32 
33     if (!curr->isWord) {
34         curr->isWord = true;
35         ++size;
36     }
37 }
38 
39 bool Trie::contains(string word) {
40     const Node *curr = &root;
41 
42     for (int i = 0; i < word.length(); ++i) {
43         auto ret = curr->next.find(word[i]);
44 
45         if (ret == curr->next.end()) {
46             return false;
47         }
48         curr = ret->second;
49     }
50     return curr->isWord;
51 }
52 
53 bool Trie::isPrefix(string prefix) {
54     const Node *curr = &root;
55 
56     for (int i = 0; i < prefix.length(); ++i) {
57         auto ret = curr->next.find(prefix[i]);
58 
59         if (ret == curr->next.end()) {
60             return false;
61         }
62         curr = ret->second;
63     }
64     return true;
65 }
66 
67 void Trie::del(string word) {
68     if (!contains(word))
69         return ;
70 
71     vector<Node*> preNode;
72     Node *curr = &root;
73 
74     for (int i = 0; i < word.length(); ++i) {
75         preNode.push_back(curr);
76         curr = curr->next.find(word[i])->second;
77     }
78     if (curr->next.size() == 0) {
79         for (int i = word.length() - 1; i >= 0 ; --i) {
80             Node *pre = preNode.back();
81             preNode.pop_back();
82 
83             if ((i != word.length() - 1) && (curr->isWord || curr->next.size() != 0))
84                 break;
85             delete curr;
86             pre->next.erase(word[i]);
87             curr = pre;
88         }
89     } else {
90         curr->isWord = false;
91     }
92     --size;
93 }

原文链接: https://www.cnblogs.com/yxsrt/p/12249815.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/326401

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

trie（字典树）原理及C++代码实现

相关推荐