Trie 树（前缀树，字典树）

2024-03-22 18:04:22

参考

字典树(前缀树) Trie树（字典树，前缀树，键树）分析详解 Trie Tree 的实现 (适合初学者) https://leetcode-cn.com/problems/implement-trie-prefix-tree/solution/shi-xian-trie-qian-zhui-shu-by-leetcode/ 数据结构之Hash树

概述

字典树(TrieTree)，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。 Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。

应用

Trie树典型应用是用于快速检索（最长前缀匹配），自动补全，拼写检查，统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie树与二叉搜索树

数据规模为n时，二叉搜索树插入、查找、删除操作的时间复杂度通常只有O(logn)，最坏情况下整棵树所有的节点都只有一个子节点，退变成一个线性表，此时插入、查找、删除操作的时间复杂度是O(n)。

通常情况下，Trie树的高度n要远大于搜索字符串的长度m，故查找操作的时间复杂度通常为O(m)，最坏情况下（当字符串非常长）的时间复杂度才为O(n)。很容易看出，Trie树最坏情况下的查找也快过二叉搜索树。

Trie树与Hash表

既然有了其他的数据结构，如平衡树和哈希表，使我们能够在字符串数据集中搜索单词。为什么我们还需要 Trie 树呢？尽管哈希表可以在 O(1) 时间内寻找键值，却无法高效的完成以下操作：

找到具有同一前缀的全部键值。
按词典序枚举字符串的数据集。

Trie 树优于哈希表的另一个理由是，随着哈希表大小增加，会出现大量的冲突，时间复杂度可能增加到 O(n)，其中 n 是插入的键的数量。与哈希表相比，Trie 树在存储多个具有相同前缀的键时可以使用较少的空间。此时 Trie 树只需要O(m) 的时间复杂度，其中 m 为键长。而在平衡树中查找键值需要 O(mlogn) 时间复杂度。

定义类 Trie

正常的树节点定义是怎么样的

struct TreeNode {
    VALUETYPE value;    //结点值
    TreeNode* children[NUM];    //指向孩子结点
};

下面是Trie的结点定义，体会二者的不同

class Trie {

    boolean isEnd = false;      // 标记是否为最终结点
    Trie[] next;        // 所有孩子结点

    /** Initialize your data structure here. */
    public Trie() {
        next = new Trie[26];    // 26个孩子结点
    }
}

插入

描述：向 Trie 中插入一个单词 word

实现：这个操作和构建链表很像。首先从根结点的子结点开始与 word 第一个字符进行匹配，一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点，直到插入完 word 的最后一个字符，同时还要将最后一个结点isEnd = true;，表示它是一个单词的末尾。

public void insert(String word) {
    // 有则共享且继续向下遍历，否则新建结点
    Trie node = this;       // node指针用来遍历
    for(char ch : word.toCharArray()){
        int index = ch - 'a';
        if(node.next[index] == null){   // 新建结点
            node.next[index] = new Trie();
        }
        node = node.next[index];    // 指针后移
    }
    node.isEnd = true;      // 标记为最终结点
}

查找

描述：查找 Trie 中是否存在单词 word

实现：从根结点的子结点开始，一直向下匹配即可，如果出现结点值为空就返回 false，如果匹配到了最后一个字符，那我们只需判断 node->isEnd即可。

public boolean find(String word) {
    // 有则共享且继续向下遍历，否则新建结点
    Trie node = this;       // node指针用来遍历
    for(char ch : word.toCharArray()){
        int index = ch - 'a';
        if(node.next[index] == null){   // 新建结点
            return false;
        }
        node = node.next[index];    // 指针后移
    }
    return node.isEnd;
}

前缀匹配

描述：判断 Trie 中是或有以 prefix 为前缀的单词

实现：和 search 操作类似，只是不需要判断最后一个字符结点的isEnd，因为既然能匹配到最后一个字符，那后面一定有单词是以它为前缀的

public boolean startsWith(String prefix) {
    // 和search方法其实差不多，但是结束判断后直接返回true, 因为是判断前缀而已
    Trie node = this;
    for(char ch : prefix.toCharArray()){
        int index = ch - 'a';
        if(node.next[index] == null){
            return false;
        }
        node = node.next[index];    // 指针后移
    }
    return true;
}

总结

通过以上介绍和代码实现我们可以总结出 Trie 的几点性质：

Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。
Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

最后，关于 Trie 的应用场景，希望你能记住 8 个字：一次建树，多次查询。

码农公寓

参考

概述

应用

Trie树与二叉搜索树

Trie树与Hash表

定义类 Trie

插入

查找

前缀匹配

相关文章