前缀树先容

数风流人物，还看如今！
  前缀树

Trie（发音类似 "try"）大概说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据会集的键。这一数据结构有相当多的应用环境，比方自动补全和拼写查抄。
前缀树，也叫做字典树（Trie），是一种专门处理处罚字符串数据的数据结构。它特殊恰当用来处理处罚和查询大量的字符串，好比词汇表、域名等。
想象一下，你有一大堆单词，你想快速地查找某个单词是否存在，大概找到以某个前缀开始的全部单词。用平凡的列表大概哈希表来做这些操纵大概不太高效，尤其是当数据量很大时。这时，前缀树就能派上用场了。
前缀树的根本头脑是利用字符串的公共前缀来淘汰查询的时间。它就像一棵倒立的树，每个节点代表一个字符。从根节点开始，每条边代表一个字符，通向下一个节点。如许，整个路径就构成了一个字符串。
举个简单的例子，假设有以下几个单词：cat, car, dog, dart，dac

如许，每个单词都有一条从根节点到叶节点的路径，路径上的字符连起来就是这个单词。
前缀树的锋利之处在于，它可以非常快速地查找以某个前缀开始的单词。好比，假如你想找出全部以 ‘ca’ 开头的单词，你只必要从根节点沿着 ‘c’ 和 ‘a’ 的边走下去，然后网络全部从谁人节点出发的路径，就能得到 ‘cat’ 和 ‘car’。
别的，前缀树还可以用来查抄一个单词是否已经存在。你只必要沿着单词的每个字符走路径，看是否能到达一个体现单词竣事的节点。
请你实现 Trie 类：

• Trie() 初始化前缀树对象。
  
• void insert(String word) 向前缀树中插入字符串 word 。
  
• boolean search(String word) 假如字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  
• boolean startsWith(String prefix) 假如之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false
  

这是208. 实现 Trie (前缀树)

1. struct Node {
2.     vector<Node*>son;
3.     bool end ; // 创建一个bool值的end，代表是否是终止节点
4.     Node():son(26,NULL),end(false){}
5. };
6. class Trie {
7.     Node* root = new Node(); // 创建一个根节点
8.     // 返回三种数字，0，1，2
9.     // 0代表没有这个单词
10.     // 1代表有这个单词，但不是结尾
11.     // 2代表有这个单词，且是结尾
12.     int find(string word) {
13.         auto cur = root; // 遍历字符串 word，同时用一个变量 cur 表示当前在 26
14.                           // 叉树的哪个节点，初始值为 root。
15.         for (auto c : word) {
16.             c -= 'a';
17.             if (cur->son[c] == nullptr) {
18.                 return 0;
19.             } // 如果 word[i] 不是 cur 的儿子，返回 0。search 和
20.             // startsWith 收到 0 之后返回 false。
21.             cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。
22.         }
23.         // 如果cur->end为true，说明有这个单词，且是结尾
24.         // 如果cur->end为false，说明有这个单词，但并不是结尾，中间就结束了
25.         return cur->end ? 2 : 1;
26.     }
28. public:
29.     void insert(string word) {
30.        auto cur =root; // 变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。
31.         for (auto c : word) {
32.             c -= 'a';
33.             // 如果之前没有就新建一个节点
34.             if (cur->son[c] == nullptr) {
35.                 cur->son[c] = new Node();
36.             }
37.             cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。
38.         }
39.         cur->end = true; // 把end置为空
40.     }
41.     // search:如果字符串word已经在前缀树当中，返回true
42.     bool search(string word) { 
43.         return find(word) == 2; 
44.     }
45.     // startwith：如果前缀prefix已经在前缀树当中，返回true
46.     bool startsWith(string prefix) {
47.         // 是1，2都行,0不行
48.         return find(prefix) != 0;
49.     }
50. };

复制代码

很遗憾，在力扣内里是付费的，牛客内里不付费。

这个是1804.实现前缀树II，这里和上面的差异在于，一个是判断word单词是否出现，一个是查询前缀树里，word单词出现了反复，一个是查询前缀树里，是否有单词以pre做前缀，一个是一个是查询前缀树里，有多少单词以pre做前缀

此时的节点是维护pass,end,和nexts数组，假如有节点颠末，pass++，一个单词竣事end++，维护这两个信息。

1. // 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
2. public class Code01_TrieTree {
4.  // 路是数组实现的
5.  class Trie{
7.   class TrieNode {
8.    public int pass;
9.    public int end;//单词的结尾
10.    public TrieNode[] nexts;
12.    public TrieNode() {
13.     pass = 0;
14.     end = 0;
15.     nexts = new TrieNode[26];
16.    }
17.   }
19.   private TrieNode root;
21.   public Trie() {
22.    root = new TrieNode();
23.   }
25.   public void insert(String word) {
26.    TrieNode node = root;
27.    node.pass++;
28.    for (int i = 0, path; i < word.length(); i++) { // 从左往右遍历字符
29.     path = word.charAt(i) - 'a'; // 由字符，对应成走向哪条路
30.     if (node.nexts[path] == null) {
31.      node.nexts[path] = new TrieNode();
32.     }
33.     node = node.nexts[path];
34.     node.pass++;
35.    }
36.    node.end++;
37.   }
39.   // 如果之前word插入过前缀树，那么此时删掉一次
40.   // 如果之前word没有插入过前缀树，那么什么也不做
41.   public void erase(String word) {
42.    if (countWordsEqualTo(word) > 0) {
43.     TrieNode node = root;
44.     node.pass--;
45.     for (int i = 0, path; i < word.length(); i++) {
46.      path = word.charAt(i) - 'a';
47.      if (--node.nexts[path].pass == 0) {
48.       node.nexts[path] = null;
49.       return;
50.      }
51.      node = node.nexts[path];
52.     }
53.     node.end--;
54.    }
55.   }
57.   // 查询前缀树里，word单词出现了几次
58.   public int countWordsEqualTo(String word) {
59.    TrieNode node = root;
60.    for (int i = 0, path; i < word.length(); i++) {
61.     path = word.charAt(i) - 'a';
62.     if (node.nexts[path] == null) {
63.      return 0;
64.     }
65.     node = node.nexts[path];
66.    }
67.    return node.end;
68.   }
70.   // 查询前缀树里，有多少单词以pre做前缀
71.   public int countWordsStartingWith(String pre) {
72.    TrieNode node = root;
73.    for (int i = 0, path; i < pre.length(); i++) {
74.     path = pre.charAt(i) - 'a';
75.     if (node.nexts[path] == null) {
76.      return 0;
77.     }
78.     node = node.nexts[path];
79.    }
80.    return node.pass;
81.   }
83.  }

复制代码