概叙
科普文：算法和数据结构系列【算法和数据结构概叙】-CSDN博客
科普文：算法和数据结构系列【非线性数据结构：树Tree和堆Heap的原理、应用、以及java实现】-CSDN博客
科普文：算法和数据结构系列【树：4叉树、N叉树】_动态维护四叉树-CSDN博客
科普文：算法和数据结构系列【二叉树总结-上篇：满二叉树、完全二叉树、大顶堆/小顶堆、二叉搜索树、自平衡二叉树、红黑树总结】-CSDN博客
科普文：算法和数据结构系列【二叉树总结-下篇：满二叉树、完全二叉树、大顶堆/小顶堆、二叉搜索树、自平衡二叉树、红黑树总结】-CSDN博客
科普文：算法和数据结构系列【数据库喜欢的数据结构：B-树、B+树原理、应用、以及java实现示例】-CSDN博客
科普文：算法和数据结构系列【B+树java示例代码解读】-CSDN博客
科普文：算法和数据结构系列【压缩和通信利器：哈夫曼树（Huffman Tree）java示例代码解读】-CSDN博客
今天我们再来看一种树型结构：字典树又名前缀树、单词查找树、Trie树，是哈希树的变种，是一种存储大量字符串的树形数据结构，相比于HashMap存储，在存储单词（和语种无关，任意语言都可以）的场景上，节省了大量的内存空间。
下面是一颗结构非常简单的Trie树，每个节点都有26(字符的个数，也可以更多)个孩子，每一条路径都代表了一个字符串，而这个字符串可以是英文单词、或是其他专用的字符串。
典型应用是用于统计，排序和保存大量的字符串串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树树高。他们对比如下：
一、原理
-
字典树（Trie树）：是一种树形结构，每个节点代表一个字符，从根节点到叶子节点的路径表示一个字符串。利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。
-
哈希树：基于哈希函数实现，通过哈希函数将关键字映射到存储位置，实现快速存取。理想情况下具有O(1)的查找时间复杂度，但存在哈希冲突的问题。
二、优缺点
-
字典树（Trie树）：
-
优点：查询效率高，特别适用于大量字符串的查找和前缀匹配场景；利用公共前缀减少查询时间。
-
缺点：空间复杂度较高，因为每个节点可能包含多个子节点（通常等于字符集大小），是一个以空间换时间的算法。
-
-
哈希树：
-
优点：在理想情况下具有极高的查找效率，时间复杂度接近O(1)。
-
缺点：存在哈希冲突，需要解决冲突以保证数据的正确存取；不支持动态查询，即必须等待用户输入完整的字符串后才能进行哈希查询。
-
三、适用场景
-
字典树（Trie树）：适用于需要前缀匹配、自动完成功能或大量字符串查找的场景，如搜索引擎、文本编辑器中的自动补全等。
-
哈希树：适用于需要快速精确匹配的场景，且对存储空间要求较为敏感的情况（但注意这里对比的是哈希树，而哈希表可能更为常用且符合这一描述）。然而，由于哈希树的具体应用场景不如哈希表广泛，且存在哈希冲突等问题，因此在实际应用中可能较少直接使用哈希树。
四、空间复杂度与时间复杂度
-
字典树（Trie树）：
- 空间复杂度：有公共前缀的字符串只需要存储一次，但每个节点可能包含多个子节点，因此空间复杂度较高。
- 时间复杂度：插入和查询字符串的复杂度都是O(m)，其中m是待插入或查询字符串的长度。
-
哈希树：
- 空间复杂度：取决于哈希函数和哈希表的大小，以及解决哈希冲突的方法。
- 时间复杂度：理想情况下为O(1)，但存在哈希冲突时可能增加查找时间。
五、注意事项
-
字典树（Trie树）：实现时需要注意字符集的大小，以及如何处理不同字符的存储和比较。在进行前缀匹配时，可以利用公共前缀信息减少计算量。
-
哈希树：需要选择合适的哈希函数以减少哈希冲突。需要设计合理的解决哈希冲突的方法，如链地址法或开放地址法等。
字典树（Trie）
字典树（Trie树）：是一种树形结构，每个节点代表一个字符，从根节点到叶子节点的路径表示一个字符串。利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。的
原理：
Trie树利用字符串之间的公共前缀来减少不必要的字符串比较，从而提高查询效率。每个节点代表一个字符，从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串。
优缺点：
- 优点：查询效率高，最大限度地减少无谓的字符串比较；支持前缀匹配，适合用于搜索引擎的词频统计等场景。
- 缺点：空间复杂度可能较高，特别是当存储大量字符串时。
- 空间消耗：对于不共享前缀的字符串集合，Trie 可能消耗大量内存。
- 不适合动态数据：如果需要频繁地插入和删除字符串，维护 Trie 的代价可能较高。
复杂度：
- 时间复杂度：插入、查找和前缀匹配操作的时间复杂度通常为O(L)，其中L是字符串的长度。
- 空间复杂度：取决于存储的字符串数量和长度。
应用场景：
应用场景：搜索引擎的词频统计、自动补全、拼写检查等。
1)搜素引擎
2)区块链：trie树的进阶版，Merkle Patricia Tree，他能够高效、安全地验证大型数据结构中的数据，我从别的地方摘抄了下摘要：
一种经过改良的、融合了默克尔树和前缀树两种树结构优点的数据结构，以太坊中，MPT是一个非常重要的数据结构，在以太坊中，帐户的交易信息、状态以及相应的状态变更，还有相关的交易信息等都使用MPT来进行管理，其是整个数据存储的重要一环。交易树，收据树，状态树都是采用的MPT结构。
3)IP路由，倒排索引，这个感兴趣的可以去了解下，我也不太了解，这是听说过可以
4)分词，常见的分词库，或多或少会用到字典树，或者其它类似的存储字符串的树形数据结构（比如"双数组trie树"）。原因就是因为它能提供良好的前缀查询（一些分词算法需要大量调用该方法）。python有一个很著名的分词库叫做jieba，里面就用到了字典树（虽说由于jieba源码里字典树实现得不够优雅，后来被替代了）。这个库有java版本叫做jieba-analysis，但是已经很久不更新了，而且分词结果和python版本的不一致！
注意事项：实现时需要考虑内存使用，避免浪费空间。
优化方向 节省空间： 压缩字典树，但是维护成本更高; 三分搜索树
压缩前缀树：合并只有一个子节点的节点，可以减少内存使用。
Ternary Search Tree：每个节点有三个子节点，可以在某些情况下提供更好的平衡。
使用哈希表：在每个节点使用哈希表而不是数组来存储子节点，可以处理更大的字符集。
Java代码实现
/**
* Trie4LowerChar结构特点
* 根节点不包含字符，除根节点外每个节点都只包含一个字符
* 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
* 每个节点的所有子节点包含的字符都不相同
*
* @author zhouxx
* @create 2025-01-17 13:23
*/
public class Trie4LowerChar {
private TrieNode4LowerChar root;
public Trie4LowerChar() {
root = new TrieNode4LowerChar();
}
// 插入单词
public void insert(String word) {
word = word.toLowerCase();
if(search(word)){
return;
}
TrieNode4LowerChar current = root;
for (char ch : word.toCharArray()) {
if (!current.containsKey(ch)) {
current.setChild(ch);
}
current = current.getChild(ch);
}
// todo 同拼写，不同读音的单词这里有问题。 eg：Live：直播/实况，居住。
current.setEndOfWord(true);
System.out.println(word+" insert TrieNode : "+current);
System.out.println(word+" insert TrieNode/root : "+root);
}
// 搜索单词
public boolean search(String word) {
word = word.toLowerCase();
TrieNode4LowerChar node = searchNode(word);
return node != null && node.isEndOfWord();
}
// 检查是否有以给定前缀开头的单词
public boolean startsWith(String prefix) {
prefix = prefix.toLowerCase();
return searchNode(prefix) != null;
}
private TrieNode4LowerChar searchNode(String word) {
word = word.toLowerCase();
TrieNode4LowerChar current = root;
for (char ch : word.toCharArray()) {
if (!current.containsKey(ch)) {
return null;
}
current = current.getChild(ch);
}
return current;
}
//删除
public void delete(String word) {
word = word.toLowerCase();
if(!search(word)){
return;
}
TrieNode4LowerChar current = root;
for (char ch : word.toCharArray()) {
current = current.getChild(ch);
}
// todo 同拼写，不同读音的单词这里有问题。 eg：Live：直播/实况，居住。
current.setEndOfWord(false);
//System.out.println(word+" delete TrieNode : "+current);
System.out.println(word+" delete TrieNode/root : "+root);
}
}
class TrieNode4LowerChar {
private TrieNode4LowerChar[] children;
private boolean EndOfWord;
TrieNode4LowerChar() {
children = new TrieNode4LowerChar[26]; // 假设只包含小写字母
EndOfWord = false;
}
public boolean containsKey(char ch) {
return children[ch - 'a'] != null;
}
public TrieNode4LowerChar getChild(char ch) {
return children[ch - 'a'];
}
public void setChild(char ch) {
setChild(ch,new TrieNode4LowerChar());
}
public void setChild(char ch, TrieNode4LowerChar node) {
children[ch - 'a'] = node;
}
public boolean isEndOfWord() {
return EndOfWord;
}
public void setEndOfWord(boolean isEndOfWord) {
this.EndOfWord = isEndOfWord;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("{");
stringBuilder.append("isEndOfWord=").append(EndOfWord).append(",");
stringBuilder.append("children=").append(children == null || children.length == 0 ? "[]" : printChildren());
stringBuilder.append("}");
return stringBuilder.toString();
//return value.toString();
}
public String printChildren(){
StringBuilder stringBuilder=new StringBuilder("{");
for (int i = 0; i < children.length; i++) {
if (children[i] == null) {
//stringBuilder.append(i).append(",");
} else {
stringBuilder.append("[").append(i).append("]").append(children[i]).append(",");
}
}
return stringBuilder.append("}").toString().replaceAll(",}","}");
}
}字典树的节点定义类：TrieNode4LowerChar 类
专门用于存储小写字母的 Trie 树节点。
类成员变量
private TrieNode4LowerChar[] children;：一个TrieNode4LowerChar类型的数组，用于存储当前节点的子节点。数组的大小是 26，对应 26 个小写英文字母。private boolean EndOfWord;：一个布尔值，用于标记当前节点是否是一个单词的结束。
构造方法
TrieNode4LowerChar()：构造方法初始化children数组为大小为 26 的TrieNode4LowerChar类型数组，并将所有元素初始化为null。同时，将EndOfWord设置为false。
方法
containsKey(char ch)：检查当前节点的子节点中是否存在对应字符ch的节点。通过计算ch - 'a'得到字符在children数组中的索引，然后判断该索引位置的元素是否为null。getChild(char ch)：返回对应字符ch的子节点。如果子节点不存在，则返回null。setChild(char ch)和setChild(char ch, TrieNode4LowerChar node)：这两个方法用于设置对应字符ch的子节点。第一个方法创建一个新的TrieNode4LowerChar节点并设置，而第二个方法则使用提供的节点进行设置。isEndOfWord()和setEndOfWord(boolean isEndOfWord)：这两个方法用于检查和设置EndOfWord标志。toString()：重写toString方法，用于返回当前节点的字符串表示形式。包括isEndOfWord标志和子节点信息。printChildren()：一个辅助方法，用于生成children数组的字符串表示形式。它遍历children数组，将非null的子节点转换为字符串，并将它们连接起来。
注意事项
- 这个类假设只处理小写字母，因此
children数组的大小被硬编码为 26。 containsKey、getChild和setChild方法都依赖于字符'a'的 ASCII 值来计算数组索引，因此只能处理小写字母。toString和printChildren方法提供了节点的可视化表示，有助于调试和测试。
字典树的主类：Trie4LowerChar 类
* 根节点不包含字符，除根节点外每个节点都只包含一个字符 * 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 * 每个节点的所有子节点包含的字符都不相同
类成员变量
private TrieNode4LowerChar root;：一个TrieNode4LowerChar类型的变量，代表 Trie 树的根节点。
构造方法
Trie4LowerChar()：构造方法初始化 Trie 树的根节点。它创建了一个新的TrieNode4LowerChar对象，并将其赋值给root变量。
插入方法：insert
用于向 Trie 树中插入一个单词。
TrieNode4LowerChar current = root;
for (char ch : word.toCharArray()) {
if (!current.containsKey(ch)) {
current.setChild(ch);
}
current = current.getChild(ch);
}
初始化一个 TrieNode4LowerChar 类型的变量 current，并将其设置为 Trie 树的根节点 root。然后，遍历单词的每个字符 ch：
- 如果当前节点
current不包含字符ch的子节点，则调用setChild(ch)方法创建一个新的子节点。 - 无论是否创建了新子节点，都将
current更新为字符ch对应的子节点。
遍历完单词的所有字符后，将当前节点（即单词的最后一个字符对应的节点）标记为单词的结束节点。
搜索方法/前缀方法：search/startsWith
搜索单词方法 search
这个方法用于检查 Trie 树中是否存在给定的单词。它首先将单词转换为小写，然后调用 searchNode 方法（该方法在代码段中未给出，但我们可以假设它存在并用于查找单词对应的节点）来查找单词的最后一个字符对应的节点。如果找到了该节点，并且该节点被标记为单词的结束，则返回 true，否则返回 false。
检查前缀方法 startsWith
这个方法用于检查 Trie 树中是否存在以给定前缀开头的单词。它首先将前缀转换为小写，然后调用 searchNode 方法来查找前缀的最后一个字符对应的节点。如果找到了该节点，则返回 true，否则返回 false。
注意事项和潜在问题
-
searchNode方法：代码中多次调用了searchNode方法，但这个方法的具体实现没有给出。这个方法是实现搜索和前缀检查的关键，需要确保它能够正确地遍历 Trie 树并找到对应的节点。 -
大小写处理：所有方法都将输入的单词或前缀转换为小写字母，这意味着 Trie 树将不区分大小写。这是设计上的选择，但需要确保所有与 Trie 树交互的操作都遵循这一规则。
-
同音异义词问题：注释中提到了同音异义词可能导致的问题，但在这些方法的实现中并没有处理这个问题。如果需要区分同音异义词，可能需要额外的数据结构或信息。
-
性能考虑：插入、搜索和前缀检查的时间复杂度都与单词或前缀的长度成正比，即 O(m)，其中 m 是单词或前缀的长度。在大多数情况下，这是可以接受的，但对于非常长的单词或前缀，可能需要考虑性能优化。
-
调试信息：
insert方法中包含了打印调试信息的代码，这在实际使用中可能不是必需的。在生产环境中，应该移除这些打印语句或使用日志记录器来记录必要的信息。
删除方法：delete
用于从 Trie 树中删除一个单词。逻辑同insert，只是最后将单词的结束改成false。（简单粗暴）
current.setEndOfWord(false);取消单词结束标记：遍历完单词的所有字符后，将当前节点（即单词的最后一个字符对应的节点）的单词结束标记设置为 false，表示该节点不再是一个单词的结束。
注意事项和潜在问题
-
search方法：代码中调用了search方法来检查单词是否存在，但这个方法的具体实现没有给出。确保search方法能够正确地遍历 Trie 树并检查单词是否存在。 -
大小写处理：代码将输入的单词转换为小写字母，这意味着 Trie 树将不区分大小写。如果这是期望的行为，那么确保所有与 Trie 树交互的操作都遵循这一规则。
-
同音异义词问题（todo 注释）：
// todo 同拼写，不同读音的单词这里有问题。 eg：Live：直播/实况，居住。这个注释指出了同音异义词（即拼写相同但读音或意义不同的单词）可能导致的问题。在标准的 Trie 树实现中，同音异义词会被视为相同的单词，因为它们具有相同的拼写。要处理这种情况，可能需要额外的数据结构或信息来区分不同的读音或意义。然而，这个删除方法并没有处理这个问题，它只是简单地删除了拼写相同的单词，不考虑读音或意义的差异。
-
删除后的节点处理：这个方法只是取消了单词结束标记，并没有处理可能存在的孤立节点（即没有其他单词经过的节点）。在某些情况下，可能需要进一步清理这些孤立节点以节省空间。但这通常是一个更复杂的问题，需要额外的逻辑来处理。
-
性能考虑：删除操作的时间复杂度与单词的长度成正比，即 O(m)，其中 m 是单词的长度。在大多数情况下，这是可以接受的，但对于非常长的单词，可能需要考虑性能优化。
总的来说，这个方法实现了从 Trie 树中删除单词的基本功能，并考虑了大小写处理和潜在的同音异义词问题（尽管后者没有在这段代码中解决）。要确保这个方法的正确性，需要确保 search 方法的正确实现，并考虑如何处理同音异义词和孤立节点等特殊情况。在实际应用中，可能还需要进一步优化和完善这个方法。
测试结果
Trie4LowerChar trie = new Trie4LowerChar();
trie.insert("Hello");
trie.insert("World");
System.out.println("'Hello' search in trie:"+trie.search("Hello")); // 返回 true
System.out.println("'He' search in trie:"+trie.search("He")); // 返回 false
System.out.println("'He' startsWith in trie:"+trie.startsWith("He")); // 返回 true
trie.insert("He");
System.out.println("'He' search in trie:"+trie.search("He")); // 返回 true
trie.delete("He");
System.out.println("'He' search in trie:"+trie.search("He")); // 返回 false
trie.insert("Hell");
System.out.println("'He' search in trie:"+trie.search("He")); // 返回 true