数据结构-字典树

什么是Trie树

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

avatar

它有3个基本性质：

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

树的构建

class TireTree(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.word_end = -1

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curNode = self.root
        for c in word:
            if not c in curNode:
                curNode[c] = {}
            curNode = curNode[c]
        curNode[self.word_end] = True

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        curNode = self.root
        for c in word:
            if not c in word:
                return False
            curNode = curNode[c]

        if self.word_end not in curNode:
            return False

        return True

    def startsWith(self, prefix):

        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        curNode = self.root
        for c in prefix:
            if not c in curNode:
                return False
            curNode = curNode[c]

        return True


if __name__ == '__main__':
    tire = TireTree()
    tire.insert("hello world")
    print(tire.search("hello world"))
    print(tire.startsWith("hello"))

应用场景

典型应用是用于统计，排序和公共字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。

字符串的快速查找

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

字典树在“串”排序方面的应用

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出用字典树进行排序，采用数组的方式创建字典树，这棵树的每个节点的所有儿子很显然地按照其字母大小排序,对这棵树进行先序遍历即可。

字典树在最长公共前缀问题的应用

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的节点的公共前缀。

什么是Trie树

树的构建

应用场景

参考文献