Trie字典树详解

一、什么是Trie？

1. 定义

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

2. Trie图示

在这个图示中我们定义了4个单词（cat dog deer panda），每个节点都存一个字符；如果考虑到不同语言以及其他的不同情况，每一个子节点都需要若干个指向下个节点的指针；由于这里显示空间有限，我们暂时就使用4个单词来表示。

其实我们可以自己想一下，我们如果要查询cat这个词，我们在查询的时候就已经知道我们要到c这个节点了，所以这个值应该直接存储在到达之前的路径上。

然后当查询到最后的子节点是代表这个查询结束。

但是有一种情况也是必须要考虑的，如果某一个单词是另外一个单词的词缀需要怎么进行存储呢？这个时候其实可以在维护一个标示，来记录这个这个值。

二、代码简单实现Trie字典树基础

class Trie:
    class Node:
        def __init__(self, is_word=False):
            self.is_word = is_word
            self.next = {}

    def __init__(self):
        self.root = self.Node()
        self.size = 0

    def get_size(self):
        """
        获得Trie中存储的单词数量
        """
        return self.size

    def add(self, word):
        """
        向Trie中添加一个新的单词word
        """
        cur = self.root
        for i in range(len(word)):
            c = word[i]
            if c not in cur.next:
                cur.next[c] = self.Node()
            cur = cur.next[c]

        if not cur.is_word:
            cur.is_word = True
            self.size += 1

三、Trie字典树的查询

def contains(self, word):
    """
    查询单词word是否在Trie中
    """
    cur = self.root
    for i in range(len(word)):
        c = word[i]
        if c not in cur.next:
            return False
        cur = cur.next[c]
    return cur.is_word

四、Trie的前缀查询

1. 前缀查询概念解析

从图中我们可以看出，Trie在进行搜索的时候实际上进行的就是前缀的查询，比如说cat，当查询到c的时候，我们可以认为c就是cat的前缀，所以在Trie上进行的查询本质上就是前缀的查询。

2. 代码实现前缀查询

def is_prefix(self, prefix):
    """
    查询在Trie中是否有单词以prefix为前缀
    """
    cur = self.root
    for i in range(len(prefix)):
        c = prefix[i]
        if c not in cur.next:
            return False
        cur = cur.next[c]
    return True