Trie树

文章目录

Trie树

Trie树介绍

字典树

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

总的来讲，Trie树是一种高效的存储和查找字符串集合的数据结构。

应用场景举例

使用用Trie树来存储单词。

如图:

在这里插入图片描述

Trie树是一个多叉树，每一个字母存储为Trie树的一个结点，我们用Trie树来存储小写字母组成的单词，如 apple 的存储就像上方一样，此时每个结点都可以后26个子节点。

代码实现

class TrieNode {boolean isEnd;TrieNode[] childNode;public TrieNode() {isEnd = false;childNode = new TrieNode[26];}
}public class Trie {TrieNode root;public Trie() {root = new TrieNode();}// 插入public void insert(String word) {TrieNode p = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);int mapIdx = c - 'a'; // 设置每一个字母都映射一个下标值: 0 ~ 25if (p.childNode[mapIdx] == null) { // 如果没有字母对应的映射也就是p.childNode[mapIdx] = new TrieNode();}p = p.childNode[mapIdx];}// 此时指针p已经移动到了单词的末尾位置, 就将isEnd变为truep.isEnd = true;}// 查询public boolean search(String word) {TrieNode p = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);int mapIdx = c - 'a';if (p.childNode[mapIdx] != null) {p = p.childNode[mapIdx];} else {return false;}}/*i == word.length() 跳出循环时可能p指向的字母可能不是一个单词的结尾,因此可以直接返回p.isEnd, 如果是true就代表找到了; 如果是false,就代表没找到。*/return p.isEnd;}// 判断是否有与指定条件相同的前缀public boolean startWiths(String word) {TrieNode p = root;for (int i = 0; i < word.length(); i++) {char c = word.charAt(i);int mapIdx = c - 'a';if (p.childNode[mapIdx] != null) {p = p.childNode[mapIdx];} else {return false;}}return true;}
}

上面的代码使用new的方式创建结点对象，便于理解，但是在解题过程中，大量的new操作可能会导致超时。

所以可以用空间来换取时间，开辟数组来保存Trie树的结构。

public class Tire {static final int N = 100010; // 可以根据题目的数据范围来指定数组的大小static int[][] trie = new int[N][26]; // 开辟trie数组，用于保存结点信息 N行数据范围，26代表26个字母static int[] count = new int[N]; // 记录每个字母作为结尾出现的次数static int idx; // 定义idx用于实现插入操作，保证不同的idx值对应不同的结点public static void insert(char[] s) {int p = 0;for (int i = 0; i < s.length; i++) {int u = s[i] - 'a';if (trie[p][u] == 0) {trie[p][u] = ++idx;}p = trie[p][u];}count[p]++;}public static int query(char[] s) {int p = 0;for (int i = 0; i < s.length; i++) {int u = s[i] - 'a';if (trie[p][u] == 0) return 0;p = trie[p][u];}return count[p];}
}

例题

leetcode 208. 实现 Trie (前缀树)

请你实现 Trie 类：

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

示例:

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数总计不超过 3 * 104 次

题解：

class Trie {static int N = 100009; // 设置为十万级static int[][] trie = new int[N][26];static int[] count = new int[N];static int idx = 0;// 在构造方法中完成重置 static 成员数组的操作// 这样做的目的是为减少 new 操作（无论有多少测试数据，上述 static 成员只会被 new 一次）public Trie() {for (int row = idx; row >= 0; row--) {Arrays.fill(trie[row], 0);}Arrays.fill(count, 0);idx = 0;}public void insert(String word) {int p = 0;for (int i = 0; i < word.length(); i++) {int u = word.charAt(i) - 'a';if (trie[p][u] == 0) trie[p][u] = ++idx;p = trie[p][u];}count[p] ++;}public boolean search(String word) {int p = 0;for (int i = 0; i < word.length(); i++) {int u = word.charAt(i) - 'a';if (trie[p][u] == 0) return false;p = trie[p][u];}return count[p] != 0;}public boolean startsWith(String prefix) {int p = 0;for (int i = 0; i < prefix.length(); i++) {int u = prefix.charAt(i) - 'a';if (trie[p][u] == 0) return false;p = trie[p][u];}return true;}
}

AcWing 835. Trie字符串统计

维护一个字符串集合，支持两种操作：

I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。

共有 N 个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。

输入格式

第一行包含整数 N，表示操作数。

接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

1≤N≤2∗10^4

输入样例：

5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
0
1

题解：

import java.util.Scanner;public class Main {static final int N = 100010;static int[][] son = new int[N][26];static int[] cnt = new int[N];static int idx;public static void insert(char[] s) {int p = 0;for (int i = 0; i < s.length; i ++) {int u = s[i] - 'a';if (son[p][u] == 0) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;}public static int query(char[] s) {int p = 0; for (int i = 0; i < s.length; i++) {int u = s[i] - 'a';if (son[p][u] == 0) return 0;p = son[p][u];}return cnt[p];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();while (n-- != 0) {String input = sc.next();String s;if ("I".equals(input)) {s = sc.next();insert(s.toCharArray());} else {s = sc.next();int res = query(s.toCharArray());System.out.println(res);}}}
}