字典树(Trie)

0 字典树的引入

我们已经知道树和二叉搜索树等数据结构，那么字典树或者前缀树是用来做什么的呢？

假设我们需要创建一个能提供单词拼写检查的程序，它能给出这个单词是否有效(不需要给出建议的单词)。那么我们该如何实现呢？

最简单的方式是利用一个具有所有已知词汇的哈希表，该哈希表能在O(1)的时间内判断单词是否存在，但是它需要的存储将会是O(n*m)，n是单词的个数，m是单词的长度。如果利用字典树(前缀树)，那么将能够降低空间复杂度只牺牲一点时间性能。

1 基础的字典树

首先来看有着"a"，"add"和"hi"的基础字典树:

利用字典实现： 

1
2
3
4
5
6
7
8
9
10
11
12
basic_trie = {
	# a 和 add
	'a':{
		'd':{
			'd':{'word_end': True},
			'word_end': False},
		'word_end': True},
	# hi
	'h':{
		'i':{'word_end': True},
		'word_end': False}
}
在遍历词汇所拥有的字母后检查word_end是否为True来查找词汇。在basic_trie中，a与add有重叠(拥有共同的前缀)，这就是字典树节省存储空间的地方(不用再单独为a和add开辟空间)。下面的is_word函数便是用于检查一个词汇是否存在于basic_trie中：

1
2
3
4
5
6
7
8
9
def is_word(word):
    current_node = basic_trie

    for char in word:
        if char not in basic_trie:
            return False
        
        current_node = current_node[char]
    return current_node['word_end']

测试is_word: 

1
2
3
4
5
6
test_words = ['ap', 'add']
for word in test_words:
    if is_word(word):
        print('"{}" is a word.'.format(word))
    else:
        print('"{}" is not a word.'.format(word))

2 字典树

从上面的简单的字典树中可以看出，字典树是一棵多叉树，根节点不包含字符，从根节点到某节点的路径上的字符连起来就是该节点对应的字符串。

实现代表字典树的类

字典树的类中包含一个存储字符的字典，还有add和exist方法分别用于增加一个词汇、判断词是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class TrieNode(object):
    def __init__(self):
        self.is_word = False ## 记录从根节点开始到当前节点路径上的字符是否为词汇
        self.children = {} ## 存放子节点
        
class Trie(object):
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, word):
        """
        增加一个word到字典树中
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True
                
    def exists(self, word):
        """
        判单word是否存在于字典树
        """
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            else:
                node = node.children[char]
        return node.is_word

测试上面的Trie类： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
word_list = ['apple', 'bear', 'goo', 'good', 'goodbye', 'goods', 'goodwill', 'gooses'  ,'zebra']
word_trie = Trie()

# Add words
for word in word_list:
    word_trie.add(word)

# Test words
test_words = ['bear', 'goo', 'good', 'goos']
for word in test_words:
    if word_trie.exists(word):
        print('"{}" is a word.'.format(word))
    else:
        print('"{}" is not a word.'.format(word))
"bear" is a word.

"goo" is a word.

"good" is a word.

"goos" is not a word.

3 字典树查找的时间复杂度

字典树查找的时间复杂度是O(h)，h是单词的长度。

4 完成leetcode上的《实现 Trie (前缀树)

题目链接在这里

4.1 题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

1
2
3
4
5
6
7
8
Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串。

4.2 python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = {}

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_word = True


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_word

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char in node.children:
                node = node.children[char]
            else:
                return False
        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)