当前位置：首页 > news >正文

前缀树介绍

news 来源：原创 2025/5/17 23:39:48

数风流人物，还看今朝！

前缀树

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 (前缀树)

struct Node {vector<Node*>son;bool end ; // 创建一个bool值的end，代表是否是终止节点Node():son(26,NULL),end(false){}
};
class Trie {Node* root = new Node(); // 创建一个根节点// 返回三种数字，0，1，2// 0代表没有这个单词// 1代表有这个单词，但不是结尾// 2代表有这个单词，且是结尾int find(string word) {auto cur = root; // 遍历字符串 word，同时用一个变量 cur 表示当前在 26// 叉树的哪个节点，初始值为 root。for (auto c : word) {c -= 'a';if (cur->son[c] == nullptr) {return 0;} // 如果 word[i] 不是 cur 的儿子，返回 0。search 和// startsWith 收到 0 之后返回 false。cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。}// 如果cur->end为true，说明有这个单词，且是结尾// 如果cur->end为false，说明有这个单词，但并不是结尾，中间就结束了return cur->end ? 2 : 1;}public:void insert(string word) {auto cur =root; // 变量 cur 表示当前在 26 叉树的哪个节点，初始值为 root。for (auto c : word) {c -= 'a';// 如果之前没有就新建一个节点if (cur->son[c] == nullptr) {cur->son[c] = new Node();}cur = cur->son[c]; // 更新 cur 为儿子列表中的相应节点。}cur->end = true; // 把end置为空}// search:如果字符串word已经在前缀树当中，返回truebool search(string word) { return find(word) == 2; }// startwith：如果前缀prefix已经在前缀树当中，返回truebool startsWith(string prefix) {// 是1，2都行,0不行return find(prefix) != 0;}
};

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

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

此时的节点是维护pass,end,和nexts数组，如果有节点经过，pass++，一个单词结束end++，维护这两个信息。

// 测试链接 : https://leetcode.cn/problems/implement-trie-ii-prefix-tree/
public class Code01_TrieTree {// 路是数组实现的class Trie{class TrieNode {public int pass;public int end;//单词的结尾public TrieNode[] nexts;public TrieNode() {pass = 0;end = 0;nexts = new TrieNode[26];}}private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;node.pass++;for (int i = 0, path; i < word.length(); i++) { // 从左往右遍历字符path = word.charAt(i) - 'a'; // 由字符，对应成走向哪条路if (node.nexts[path] == null) {node.nexts[path] = new TrieNode();}node = node.nexts[path];node.pass++;}node.end++;}// 如果之前word插入过前缀树，那么此时删掉一次// 如果之前word没有插入过前缀树，那么什么也不做public void erase(String word) {if (countWordsEqualTo(word) > 0) {TrieNode node = root;node.pass--;for (int i = 0, path; i < word.length(); i++) {path = word.charAt(i) - 'a';if (--node.nexts[path].pass == 0) {node.nexts[path] = null;return;}node = node.nexts[path];}node.end--;}}// 查询前缀树里，word单词出现了几次public int countWordsEqualTo(String word) {TrieNode node = root;for (int i = 0, path; i < word.length(); i++) {path = word.charAt(i) - 'a';if (node.nexts[path] == null) {return 0;}node = node.nexts[path];}return node.end;}// 查询前缀树里，有多少单词以pre做前缀public int countWordsStartingWith(String pre) {TrieNode node = root;for (int i = 0, path; i < pre.length(); i++) {path = pre.charAt(i) - 'a';if (node.nexts[path] == null) {return 0;}node = node.nexts[path];}return node.pass;}}

前缀树

相关文章：