字典树

字典树 Trie

在计算机科学中，Trie 又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 这个 术语来自于 retrieval。根据词源学，trie 的发明者 Edward Fredkin 把它读作 /ˈtriː/，但是，其他作者把它读作/ˈtraɪ/。

image.png

在图示中，键标注在节点中，值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机，尽管边上的符号一般是隐含在分支的顺序中的。

键不需要被显示地保存在节点中。图示中标注出完整的单词，只是为了演示 trie 的原理。

trie 的键通常是字符串，但也可以是其它的结构。trie 的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者 形状的排列。比如，bitwise trie 中的键是一串比特，可以用于表示整数或者内存地址。

Trie 树的结点结构

Trie 树是一个有根的树，其结点具有以下字段：

• 最多 R 个指向子节点的链接，其中每个链接对应字母表数据集中的一个字母。
• 布尔字段，以指定节点是对应键的结尾还是只是键前缀。

Trie 树的常见操作

向 Trie 树中插入键

我们通过搜索 Trie 树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况：

• 链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
• 链接不存在。创建一个新的节点，并将它与父节点的链接相连，该链接与当前的键字符相匹配。
  重复以上步骤，直到到达键的最后一个字符，然后将当前节点标记为结束节点，算法完成。

插入键复杂度分析

• 时间复杂度：O(m)，其中 m 为键长。在算法的每次迭代中，我们要么检查要么创建一个节点，直到到达键尾。只需要 m 次操作。
• 空间复杂度：O(m)，最坏的情况下，新插入的键和 Trie 树中已有的键没有公共前缀。此时需要添加 m 个结点，使用 O(m) 空间。

在 Trie 树中查找键

每个键在 trie 中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始。检查当前节点中与键字符对应的链接。有两种情况：

• 存在链接。我们移动到该链接后面路径中的下一个节点，并继续搜索下一个键字符。
• 不存在链接。若已无键字符，且当前节点标记为 isEnd，则返回 true。否则有两种可能，均返回 false：
  • 还有键字符剩余，但无法跟随 Trie 树的键路径，找不到键。
  • 没有键字符剩余，但当前节点没有标记 isEnd。也就是说，待查找只是 Trie 树中另一个键的前缀。

查找键复杂度分析

• 时间复杂度：O(m)。算法 的每一步均搜索下一个键字符。最坏的情况下需要 m 次操作。
• 空间复杂度：O(1)。

查找 Trie 树中的键前缀

该方法与在 Trie 树中搜索键时使用的方法非常相似。我们从根遍历 Trie 树，直到键前缀中没有字符，或者无法用当前的键字符继续 Trie 中的路径。与上面提到的“搜索键”算法唯一的区别是：到达键前缀的末尾时，总是返回 true。我们不需要考虑当前 Trie 节点是否用 isEnd 标记，因为我们搜索的是键的前缀，而不是整个键。

查找键前缀复杂度分析

• 时间复杂度：O(m)。
• 空间复杂度：O(1)。

应用

trie 树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

1. 自动补全
2. 拼写检查
3. IP 路由（最长前缀匹配）
4. T9（九宫格）打字预测
5. 单词游戏

实现方式

trie 树实际上是一个确定有限状态自动机（DFA），通常用转移矩阵表示。行表示状态，列表示输入字符，（行、列）位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。于是人们提出了下面两种结构。

三数组 Trie

三数组 Trie（Triple-Array Trie）结构包括三个数组：base，next 和 check 。

二数组

二数组 Trie（Double-Array Trie）包含 base 和 check 两个数组。base 数组的每个元素表示一个 Trie 节点，即一个状态；check 数组表示某个状态的前驱状态。

Trie 树代码模版

Python 版

class Trie(object):
    def __init__(self):
        self.root = {}
        self.end_of_word = “#"

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word):
        node = sel.root;
        for char in word:
            if char not in node:
                return False;
            node = node[char]
        return self.end_of_word in node

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True

Java 版

// Trie 树的结点结构
class TrieNode {
    private TrieNode[] links;

    private final int R = 26;

    private boolean isEnd;

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

    public boolean containsKey(chat 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
class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char currentChar = word.charAt(i);
            if (!node.containsKey(currentChar)) {
                node.put(currentChar, new TrieNode());
            }
            node = node.get(currentChar);
        }
        node.setEnd();
    }

    // search a prefix or whole key in trie and
    // returns the node where search ends
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            char curLetter = word.charAt(i);
            if (node.containsKey(curLetter)) {
                node = node.get(curLetter);
            } else {
                return null;
            }
        }
        return node;
    }

    // returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}