简介

Trie 树，又叫字典树、前缀树、单词查找树，是一种多叉树结构。如下图：

上图是一棵 Trie 树，表示了关键字集合{“to”, “tea”, “ten”, “a”, “in”, “inn”}。由图可以得知 Trie 树的基本性质：

根节点不包含字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点表示的字符串互不相同

Trie 树通常会在节点设置一个标志，用来标记到该节点为止，是否构成一个单词（关键字），例如上图中，节点为蓝色说明该标记位 true，到该节点为止构成一个单词。

Trie 树把每个关键字保存在一条路径上，而不是一个节点中。

优缺点

Trie 树的核心思想是以空间换时间，利用字符串的字符顺序查找，减少不必要的字符串比较，来提升查找字符串和字符串前缀的效率。

优点

插入和查询的效率很高，都是 O(m)，m 为字符串的长度。虽然 hash 表的时间复杂度为 O(1)，但如果哈希函数不好，可能会有很多的冲突，效率不一定比 Trie 树高。
Trie 树不同的关键字不会产生冲突。
Trie 树不用求 hash 值。通常，求 hash 值也是要遍历字符串的。

缺点

当 hash 函数很好时，Trie 树的查找效率低于 hash 表。
空间消耗比较大。

应用场景

字符串检索
字符串排序
前缀匹配

Trie 树的实现及应用（Java）

Trie 树的实现

class TrieNode {
    private TrieNode[] links;
    private final int R = 26;   // 限定为小写字母
    
    // 该标记为 true 时，说明到该节点的路径所代表的字符串为其中一个关键字
    private boolean isEnd;      

    public TrieNode() {
        this.links = new TrieNode[R];
    }

    public boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return links[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        links[ch - 'a'] = node;
    }

    public void setEnd() {
        isEnd = true;
    }

    public boolean isEnd() {
        return isEnd;
    }
}

Trie 树的应用

应用 Trie 树进行字符串检索以及字符串前缀匹配：

private TrieNode root;

public Trie() {
    root = new TrieNode();
}

/**
 * 插入字符串
 */    
public void insert(String word) {
    TrieNode node = root;
    // 从根开始，根据字符顺序查找对应链接
    for (int i = 0; i < word.length(); i++) {
        char currChar = word.charAt(i);
        // 如果不能链接到下一字符，创建新的节点，并将它链接到父节点上
        if (!node.containsKey(currChar)) {
            node.put(currChar, new TrieNode());
        }
        // 根据链接获取到下一节点
        node = node.get(currChar);
    }
    // 标志链接结束
    node.setEnd();
}

/**
 * 根据前缀查找，返回最后查找到的 TrieNode
 */
private TrieNode searchPrefix(String prefix) {
    TrieNode node = root;
    for (int i = 0; i < prefix.length(); i++) {
        char currChar = prefix.charAt(i);
        if (node.containsKey(currChar)) {
            node = node.get(currChar);
        } else {
            return null;
        }
    }

    return node;
}

/**
 * 字符串检索，存在该字符串则返回 true
 */
public boolean search(String word) {
    TrieNode node = searchPrefix(word);
    // 如果可以得到 TrieNode，并且在该 TrieNode 处终止，说明存在该单词
    return node != null && node.isEnd();
}

/**
 * 前缀匹配，存在拥有该前缀的字符串则返回 ture
 */
public boolean startsWith(String prefix) {
    TrieNode node = searchPrefix(prefix);
    // 如果可以得到 TrieNode，不管是否在此终止，都说明存在带有该前缀的单词
    return node != null;
}

Trie 树（前缀树）

简介

优缺点

优点

缺点

应用场景

Trie 树的实现及应用（Java）

Trie 树的实现

Trie 树的应用

参考