前缀树是一种存储数据的树形结构。是一种高效的检索字符串的方法,是一种多叉树的结构。它的插入与删除的效率比较高,时间复杂度为O(m).

前缀树

前缀树的结构如下图所示:

trie

前缀树的结构特点为:

  1. 根节点不包含字符,除根结点外,其他节点只包含一个字符
  2. 从根节点出发叶子结点,组成一个完整的字符串
  3. 每个节点包含的字符均不相同

前缀树的实现

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 Trie(object):

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

def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
a = self.res
for i in word:
if i not in a:
a[i] = {}
a = a[i]
a['end'] = {}

def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
a = self.res
for i in word:
if i not in a:
return False
a = a[i]
if 'end' in a:
return True
else:
return False

def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
a = self.res
for i in prefix:
if i not in a:
return False
a = a[i]
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)

上面代码用dict代替书的结构,一级一级的向下延展,前缀树由根节点往下,每一个节点的字节点就是他的key的数目,选择其中一个key,然后一级一级往下,当一个单词结束的时候,填入end作为终结符。