概述

前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。

典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

栗子

下图是一个前缀树，这个前缀树是由[“abc”,”abd”,”abcd”,”b”bcd,”efg”,”hij”]组成的。
第一行代表一个根节点，不存放任何值
根节点下的每一条路径，都可以代表一个前缀字符串，红色实心代表当前节点为某个前缀字符串的结尾，比如最左侧的路径 a -> b -> c -> d，可以代表abc和abcd

image.png

从上面可以发现一些Trie树的特性： 1）根节点不包含字符，除根节点外的每一个子节点都包含一个字符。 2）从根节点到某一节点的路径上的字符连接起来，就是该节点对应的字符串。 3）每个节点的所有子节点包含的字符都不相同。 4）每条边对应一个字母。每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。

Java实现

示例代码

  1. /**
  2.  * @author xuyj
  3.  * @date 2022年01月19日 23:21
  4.  */
  5. public class Trie {
  7.     /**
  8.      * 子节点
  9.      */
  10.     private Trie[] children;
  12.     /**
  13.      * 是否叶子节点
  14.      */
  15.     private boolean isEnd;
  17.     /**
  18.      * 无参构造函数，初始化
  19.      */
  20.     public Trie() {
  21.         children = new Trie[26];
  22.         isEnd = false;
  23.     }
  25.     /**
  26.      * 将单词插入前缀树
  27.      * @param word
  28.      */
  29.     public void insert(String word) {
  30.         Trie node = this;
  31.         for (int i = 0; i < word.length(); i++) {
  32.             char ch = word.charAt(i);
  33.             int index = ch - 'a';
  34.             // 如果字母不在此路径下，则在改路径上增加一个子节点
  35.             if (node.children[index] == null) {
  36.                 node.children[index] = new Trie();
  37.             }
  38.             // 增加子节点
  39.             node = node.children[index];
  40.         }
  41.         // 标记叶子结点
  42.         node.isEnd = true;
  43.     }
  45.     /**
  46.      * 查找单词在前缀树中是否存在
  47.      * @param word
  48.      * @return
  49.      */
  50.     public boolean search(String word) {
  51.         Trie node = searchPrefix(word);
  52.         // 找到该前缀并且以叶子结点结尾
  53.         // 比如存在路径abcde,查找abc,则返回false
  54.         return node != null && node.isEnd;
  55.     }
  57.     public boolean startsWith(String prefix) {
  58.         return searchPrefix(prefix) != null;
  59.     }
  61.     private Trie searchPrefix(String prefix) {
  62.         Trie node = this;
  63.         for (int i = 0; i < prefix.length(); i++) {
  64.             char ch = prefix.charAt(i);
  65.             int index = ch - 'a';
  66.             // 存在字符不在前缀树下，直接返回空
  67.             if (node.children[index] == null) {
  68.                 return null;
  69.             }
  70.             node = node.children[index];
  71.         }
  72.         return node;
  73.     }

这里只是创建了一个基本的前缀树形结构，如果需要调整，增加成员变量即可。

例题

leetcode上的例题648需要用到前缀树的结构，leetcode648. 单词替换

image.png

思路和算法

把所有的词根放入前缀树中，在树上查找每个单词的最短词根，该操作可在线性时间内完成。

示例代码

  1. class Solution {
  2.     //前缀树数据结构是一个字符多叉树，用一个数组来保存其子节点， isValid用来标记截止到该节点是否为一个完整的单词
  3.     class TrieNode{
  4.         TrieNode[] kids;
  5.         boolean isValid;
  6.         public TrieNode(){
  7.             kids = new TrieNode[26];
  8.         }
  9.     }
  11.     TrieNode root = new TrieNode();
  12.     public String replaceWords(List<String> dictionary, String sentence) {
  13.         String[] words = new String[dictionary.size()];
  14.         for(int i = 0; i < words.length; ++i) words[i] = dictionary.get(i);
  15.         //建树过程
  16.         for(String word : words){
  17.             insert(root, word);
  18.         }
  19.         String[] strs = sentence.split(" ");
  20.         for(int i = 0; i < strs.length; ++i){
  21.             //如果可以在树中找到对应单词的前缀，那么将这个单词替换为它的前缀
  22.             if(search(root, strs[i])){
  23.                 strs[i] = replace(strs[i], root);
  24.             }
  25.         }
  26.         //用StringBuilder来把字符串数组还原成原字符串句子的转换目标字符串
  27.         StringBuilder sb = new StringBuilder();
  28.         for(String s : strs){
  29.             sb.append(s).append(" ");
  30.         }
  31.         sb.deleteCharAt(sb.length()-1);
  32.         return sb.toString();
  33.     }
  34.     //建前缀树模版
  35.     public void insert(TrieNode root, String s){
  36.         TrieNode node = root;
  37.         for(char ch : s.toCharArray()){
  38.             if(node.kids[ch - 'a'] == null) node.kids[ch - 'a'] = new TrieNode();
  39.             node = node.kids[ch - 'a'];
  40.         }
  41.         node.isValid = true;
  42.     }
  43.     //查询是否存在传入的字符串的前缀
  44.     public boolean search(TrieNode root, String s){
  45.         TrieNode node = root;
  46.         for(char ch : s.toCharArray()){
  47.             if(node.isValid == true) break;
  48.             if(node.kids[ch - 'a'] == null) return false;
  49.             node = node.kids[ch - 'a'];
  50.         }
  51.         return true;
  52.     }
  53.     //将传入的字符串替换为它在前缀树中的前缀字符串
  54.     public String replace(String s, TrieNode root){
  55.         TrieNode node = root;
  56.         StringBuilder sb = new StringBuilder();
  57.         for(char ch : s.toCharArray()){
  58.             if(node.isValid || node.kids[ch - 'a'] == null) break;
  59.             node = node.kids[ch - 'a'];
  60.             sb.append(ch);
  61.         }
  62.         return sb.toString();
  63.     }
  64. }

复杂度分析

时间复杂度：O(N)O(N)，其中 NN 是 sentence 的长度。每次查询操作为线性时间复杂度。
空间复杂度：O(N)O(N)，前缀树的大小。