字典树数据结构与算法

1. 字典树

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

2. 字典树的性质 【字典树】

文章图片

除了根节点外，每一个节点都只包含一个字符
每个节点的所有子节点包含的字符都不相同
从根节点到某个节点，路径上的字符连接起来，为该节点对应的字符串

3. 构造字典树

public class Trie { static class TrieNode { // 表示当前节点的值 char value; // 表示当前节点是否是终止节点（这里不是指叶子节点，是指是否为单词的结尾） boolean flag; // 表示当前节点的子节点的数组，不考虑大小写共有26个字母，所以初始化大小为26 TrieNode[] nextNodes = new TrieNode[26]; public TrieNode() { }public TrieNode(char value) { this.value = https://www.it610.com/article/value; } }/** * 插入一个新单词 * * @param root 根节点 * @param str 要插入的新单词 */ public void insert(TrieNode root, String str) { if (root == null || str == null || str.length() == 0) { return; } for (int i = 0; i < str.length(); i++) { // index表示当前字符在字符表中的位置 int index = str.charAt(i) -'a'; // 如果该分支不存在，则创建一个新节点 if (root.nextNodes[index] == null) { root.nextNodes[index] = new TrieNode(str.charAt(i)); } // 把该节点赋给root，进入树的下一层 root = root.nextNodes[index]; } // 设置当前节点为终止节点 root.flag = true; } }

4. 查找单词是否在字典树中存在

/** * 查找一个单词是否存在 * * @param root 根节点 * @param str 要查找的单词 */ public boolean search(TrieNode root, String str) { if (root == null || str == null || str.length() == 0) { return false; } for (int i = 0; i < str.length(); i++) { // index表示当前的字符在中的字符表中的位置 int index = str.charAt(i) - 'a'; // 如果该分支不存在，则说明不存在该字符 if (root.nextNodes[index] == null) { return false; } // 把当前节点赋给root，进入树的下一层 root = root.nextNodes[index]; } // 如果当前节点是终止节点，则说明存在，否则不存在 return root.flag; }