字典树是什么？

字典树（Trie）是一种树状的、常用于信息检索的数据结构。它就像一本字典一样，可以让你快速进行字符插入、字符串搜索等。

字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。它利用了字符串的共同前缀作为存储依据，来加速搜索，同时也节省空间（相比于每一个单词都要全文保存）。Trie的字符串搜索时间复杂度为O(m), m为字符串的长度。

 

字典树的性质

1. 根节点(Root)不包含字符，除根节点以外每一个节点都仅包含一个字符。
2. 从根节点到某一节点所经过的所有字符连接起来，即可构成一个字符串。
3. 任意节点的所有子节点所包含的字符都不相同。

如下图的 Trie 树中包含了字符串集合 ["Joe", "John", "Johnny", "Jane", "Jack"]。

 

 

Trie关键词查找过程：

1. 每次从根节点开始搜索
2. 获取关键词的第一个字符，根据该字符选择对应的子节点，转到该子节点就检索。
3. 在相应的子节点上，获取关键词的第二个字符，进一步选择对应的子节点进行检索。
4. 以此类推。
5. 在某个节点处，关键词的所有字母已被取出，查找完成。

python实现Trie

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = {}

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        tree = self.d
        for s in word:
            if s not in tree:
                tree[s] = {}
            tree = tree[s]
        tree["#"] = "#"

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        tree = self.d
        for s in word:
            if s not in tree:
                return False
            tree = tree[s]
        if "#" in tree:
            return True
        return False

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        tree = self.d
        for s in prefix:
            if s not in tree:
                return False
            tree = tree[s]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

 

Trie的应用

• 字符串的检索：判断一个字符串是否出现过或者统计频率
• 搜索引擎的“搜索建议”（前缀匹配）