dsa_trie.md

DSA - 前缀树 Trie

概念

前缀树(字典树、Trie) 是一个树型结构，是一个用空间换时间的数据结构，操作包括插入、查找和删除。一般用来存字符串，每一个节点代表字符串中的一个字符。

组成

• 根节点：无实际意义，只是维护一系列指针执行其他节点。
• 其他节点：每个节点代表一个字符，除了存储数据外还维护指向其他节点的指针。
• 节点的数据结构：可以自定义，看实际需要，比如 isEnd 是否最后一个节点，count 前缀出现的次数。

操作

插入

insert(word) {
    let crawl = this.root
    for (let char of word) {
        // 将字母转换成对应的 0~25 下标
        const index = this._char2Index(char)

        // 如果当前字符没有对应的节点，那就新建一个节点
        if (!crawl.pointers[index]) {
            crawl.pointers[index] = this._getTrieNode('')
        }
        // 继续深入
        crawl = crawl.pointers[index]
    }

    // 标识一下最后的节点，把 word 存在这里只是方式之一
    // 也可以存储别的信息，看实际需求
    crawl.value = word
}

查找

search(word) {
    let crawl = this.root
    for (let char of word) {
        const index = this._char2Index(char)
        if (!crawl.pointers[index]) return false

        crawl = crawl.pointers[index]
    }
    // word 可能在 trie 中只是一个前缀，不是一个词
    // 所以要判断一下当前节点是不是最后的节点，是则说明 word 存在
    return !!crawl.value
}

删除

先去查找 word，

• 如果找到的话：
  • 先把最后一个节点的 value 清空，
  • 再判断它的 pointers 是否都是空指针：
    • 是，可以把这个节点删掉了
    • 否，不用做什么
• 没找到的话，不用做什么

复杂度

	Worst Case	说明
建树(space)	$O(n^{k})$	n 是字符集中字符个数，k 是字符串长度 (满 k 叉树的节点总数)
插入(time)	O(k)	k 是字符串长度
查询(time)	O(k)	k 是字符串长度

哈希表 vs 前缀树

	哈希表	前缀树
相似	数组 + 链表	数组 + 指针
不同	需要哈希函数、需要处理哈希冲突	没有 key collision，但存空指针要消耗更多空间

优点

• 可能节省空间：如果我们要存的是一系列长得很像的词，由于公共前缀只需要存一次，因此整体来说可以节省一些存储空间。
• 快速前缀查询：如果我们想要查询哪些词以某个前缀开头，用前缀树效率会比较高。

缺点

• 一般情况下前缀树是比较消耗空间的：每个 ASCII 字符占用的空间是 1 个字节，而每个前缀树节点之间是通过指针连接的，在 64 位操作系统上，每个地址要占 8 个字节的空间。一般来说，公共前缀节省的空间还是不能抵消指针占用的空间。
• 一般语言都没有提供这种数据结构，需要自己实现。

应用

• autocomplete
• matching algorithms
• spellchecker
• radix sort