树3：字典树（Trie树）

Trie 树，也叫“字典树”，它是一个树形结构，是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。是属于多模式匹配的一种解法。

这种数据结构在搜索补全建议的时候常会用到。结构如下：

// 对于这些单词的补全建议，hey、hell、hi、how、see、am
    [nil]
    / | \
   h  s  a
  /|\  \   \
 e i o  e   m
/ \   \  \
y  l   w   e
    \
     l

如此在用户输入的时候可以实时查询给出单词建议。当用户输入h的时候，可以匹配上hi、how、hey、hell获取到之后返回给用户作为输入建议，用户输入he的时候可以匹配上hey、hell作为输入建议。

同理，我们也可以在此结构上做句子补全：

                  [nil]
                 /  |  \
              how  what where
             / | \   \     \
         much many to  time are
        / | \   \   \        |
    money i  is times draw   you
          |   |
        love  it
          |
         you

用户在输入单词how时，how much、how many、how to可以作为输入建议给到用户。

实现

package cn.lishiyuan.algorithm.tree;  
  
  
import java.util.*;  
import java.util.function.Function;  
  
public class TrieTree {  
    private final Node root;  
    // 分词  
    private final Function<String,List<String>> split;  
    // 合并词  
    private final Function<List<String>,String> merge;  
  
    public TrieTree(Function<String,List<String>> split,Function<List<String>,String> merge){  
        this.split = split;  
        this.merge = merge;  
        root = new Node(null);  
    }  
  
    private static class Node{  
        String word;  
  
        // 子节点  
        Map<String, Node> children;  
  
        // 是否是最后一个字母或者单词  
        boolean isEndWord = false;  
  
        Node(String word){  
            this.word = word;  
            this.children = new HashMap<>();  
        }  
    }  
  
  
    public void insert(String words) {  
  
        if (words == null || words.trim().isEmpty()){  
            return;  
        }  
  
        // 分词，构建树节点  
        List<String> wordsList = split.apply(words);  
        // 匹配字典数据  
        Node parent = root;  
  
        for (int i = 0; i < wordsList.size(); i++) {  
  
            String word = wordsList.get(i);  
  
            if (parent.children.containsKey(word)){  
                // 存在相同节点则继续向后查找  
                parent = parent.children.get(word);  
            }else {  
                // 如果没有响应子节点就构建新的子节点  
                Node node = new Node(word);  
                node.isEndWord = (i == (wordsList.size() - 1));  
                parent.children.put(word,node);  
                parent = node;  
            }  
        }  
    }  
  
    public List<String> search(String words) {  
  
        if (words == null || words.trim().isEmpty()){  
            return Collections.emptyList();  
        }  
  
        // 分词，构建树节点  
        List<String> wordsList = split.apply(words);  
        // 匹配字典数据  
        Node parent = root;  
        int startIndex = 0;  
  
        for (; startIndex < wordsList.size(); startIndex++) {  
            String word = wordsList.get(startIndex);  
            if (parent.children.containsKey(word)) {  
                parent = parent.children.get(word);  
            }else {  
                break;  
            }  
        }  
  
        // 如果不最后一个词（也就是中途break了），则返回空列表  
        List<String> result = new ArrayList<>();  
  
        if (startIndex == wordsList.size()){  
            // 最后一个词则需要恢复句子  
            String baseStr = merge.apply(wordsList);  
            result = resumeWords(baseStr,parent);  
        }  
  
        return result;  
    }  
  
    private List<String> resumeWords(String prefix,Node node) {  
        List<String> resumeWords = new ArrayList<>();  
        if(node.isEndWord){  
            resumeWords.add(prefix);  
  
        }  
  
        Collection<Node> values = node.children.values();  
        for (Node child : values) {  
            String base = merge.apply(List.of(prefix , child.word));  
            resumeWords.addAll(resumeWords(base,child));  
        }  
  
        return resumeWords;  
    }  
  
}

字典树结构非常简单，逻辑也没什么复杂。

在我的实现中，提供了分词器（split） 与 合并器（merge）：
分词器将需要插入的字符串分割单词、字母或者其他的短字符串，在查找和插入单词句子的时候都需要使用到它来分割。
合并器在查找到节点之后，用来将短字符串恢复成单词或者句子。
在节点结构中， 子节点使用map加速查找过程，isEndWord标识是否是一个完整的单词或者句子。

字典树只适合在前缀匹配的情况。