Trie

  |  

摘要: 经典的 Trie 的实现,附代码模板和应用

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们以力扣 208 作为模板题来学习一下 Trie 的建树,插入和查找。并形成代码模板。

模板题

Trie(发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。

请你实现 Trie 类:

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。

提示:

1
2
3
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 1e4 次

示例:
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
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

算法:Trie

Trie 的背景

Trie 是一颗度 m >= 2 的树(N叉树),其每一层分支不是依赖整个 key 的值确定的,而是有 key 的一个分量决定的。例如:

  • key 是单词,节点只包含单独的字母
  • key 是数值,节点只含一个数位

以字符串为例:

  • 在第 0 层,表示空字符串
  • 在第 i 层,所有 key 根据它们的第 i 个字符,划分到互不相交的子树中,每个节点(子树)都表示以其根节点中 key 的开头的一个字符串,它是 key 的一个前缀。

Trie 3 条性质:

  • 根节点不含字符,其它节点包含一个字符。
  • 根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符各不相同。

Trie 将集合,子集,元素之间的层次关系表示的很清楚,这对搜索有好处。Trie 有广泛的应用,例如自动补全,拼写检查等等。

Trie 的节点定义

按照 Trie 的性质,节点定义如下。其中有一个常数规定字母的个数,一个 vector<TrieNode*> 维护的指向子节点(子树)的指针`。一个结束标记,表示该节点表示的前缀是否是一个词。

1
2
3
4
5
6
7
8
9
10
11
struct TrieNode {
const int ALPHABETS = 26;
vector<TrieNode*> children;
bool terminal;
TrieNode()
{
terminal = false;
children = vector<TrieNode*>(ALPHABETS, nullptr);
}
~TrieNode(){}
};

除了以上定义中用 vector 以外,维护子节点指针还有哈希映射这一种主流方式:

1
unordered_map<char, TrieNode*> children;

下面是这两种维护子节点的实现方式的优缺点对比。

unordered_map 的好处:

  • 由于只存储需要的子节点,因此节省了空间。
  • 通过相应的字符来访问特定的子节点比 vector 的方式更为容易

unordered_map 的坏处:

  • 比使用 vector 稍慢一些。
  • 不同字符的子节点的顺序不受控制

vector<TrieNode*> 的好处:

  • 访问子节点速度快。因为在大多数情况下,很容易将一个字符转换为索引。
  • 可以根据对应的字符自定义子节点的顺序

vector<TrieNode*> 的坏处:

  • 存储了很多用不到的子节点指针,可能会导致空间的浪费。

Trie 的插入(建树)

插入时候,根据当前节点值(字母)和待插入字符串对应位置的字母之间的关系,确定目标字符串需要去往哪个子节点。

例如在 Trie 中插入一个字符串 s:

  • 从根节点开始。根据 s[0] 选择一个子节点,并进入,此时若该子节点不存在,则进入之前先添加一个新的子节点。
  • 进入第 i 个节点(从0开始计),根据 S[i] 选择子节点。进入第 i + 1 个节点。
  • 直到遍历完 S 中的所有字符并到达末尾。 此时末端节将表示字符串 s 的节点。将该点的 terminal 标记设置为 true。
1
2
3
4
5
6
7
8
9
10
void insert(string word) {
TrieNode *iter = root;
for(const char c: word)
{
if(!(iter -> children[c - 'a']))
(iter -> children)[c - 'a'] = new TrieNode();
iter = (iter -> children)[c - 'a'];
}
iter -> terminal = true;
}

以上通过对比待插入值和节点值的关系确定去往的子树的策略,与二叉查找树的插入一样。

Trie 的查找

查找分为两种,一种是查找前缀,一种是查找单词。

查找前缀

查找前缀接口bool startsWith(string prefix),根据需求,也可以返回所有持有目标前缀的单词。

因为节点的后代都与该节点相对应字符串有共同前缀。因此可以高效搜索以特定前缀开头的任何单词。

查找单词

查找单词接口bool search(string word)

过程与查找前缀类似,根据给定的前缀沿着树形结构搜索下去。一旦找不到想要的子节点(根据当前字符得到的目标子节点为空),搜索失败。

遍历完待查找字符串且到达的末尾字符所在节点,若该节点的终止标记为 true,则搜索成功,查找的单词存在,否则搜索仍然失败。

代码(模板)

c++,子节点用 vector 实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct TrieNode {
const int ALPHABETS = 26;
vector<TrieNode*> children;
bool terminal;
TrieNode()
{
terminal = false;
children = vector<TrieNode*>(ALPHABETS, nullptr);
}
~TrieNode(){}
};

class Trie {
public:
Trie()
{
root = new TrieNode();
}

~Trie()
{
delete_sub_tree(root);
}

void insert(string word)
{
TrieNode *iter = root;
for(const char c: word)
{
if(!(iter -> children[c - 'a']))
(iter -> children)[c - 'a'] = new TrieNode();
iter = (iter -> children)[c - 'a'];
}
iter -> terminal = true;
}

bool search(string word)
{
const TrieNode* iter = find(word);
return iter && iter -> terminal;
}

bool startsWith(string prefix)
{
return find(prefix) != nullptr;
}

private:
TrieNode *root;

void delete_sub_tree(TrieNode *node)
{
for(TrieNode *child: node -> children)
if(child)
delete_sub_tree(child);
delete node;
node = nullptr;
}

const TrieNode* find(const string& prefix) const
{
const TrieNode* iter = root;
for(const char c: prefix)
{
iter = (iter -> children)[c - 'a'];
if(iter == nullptr) break;
}
return iter;
}
};

c++,子节点用 unordered_map 实现

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
struct TrieNode
{
bool terminal;
unordered_map<char, TrieNode*> children;
TrieNode()
{
terminal = false;
children = unordered_map<char, TrieNode*>();
}
~TrieNode(){}
};

class Trie
{
public:
Trie()
{
root = new TrieNode();
}

~Trie()
{
if(root)
delete_sub_tree(root);
delete root;
root = nullptr;
}

void insert(const string& word)
{
TrieNode *iter = root;
for(const char& ch: word)
{
if((iter -> children).count(ch) == 0)
(iter -> children)[ch] = new TrieNode();
iter = (iter -> children)[ch];
}
iter -> terminal = true;
}

bool search(string word)
{
const TrieNode* iter = find(word);
return iter && iter -> terminal;
}

bool startsWith(string prefix)
{
return find(prefix) != nullptr;
}

private:
TrieNode *root;

void delete_sub_tree(TrieNode* node)
{
auto it = (node -> children).begin();
while(it != (node -> children).end())
{
TrieNode *child = it -> second;
if(child)
delete_sub_tree(child);
delete child;
child = nullptr;
++it;
}
}

const TrieNode* find(const string& prefix) const
{
TrieNode* iter = root;
for(const char c: prefix)
{
if((iter -> children).count(c) == 0)
return nullptr;
iter = (iter -> children)[c];
}
return iter;
}
};

Python,子节点用 list 实现

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
ALPHABETS = 26;

class TrieNode:
def __init__(self):
self.terminal = False
self.children = [None] * ALPHABETS

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word: str) -> None:
node_iter = self.root
for c in word:
if node_iter.children[ord(c) - ord('a')] is None:
node_iter.children[ord(c) - ord('a')] = TrieNode()
node_iter = node_iter.children[ord(c) - ord('a')]
node_iter.terminal = True

def search(self, word: str) -> bool:
node_iter = self._find(word)
return node_iter is not None and node_iter.terminal

def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None

def _find(self, prefix):
node_iter = self.root
for c in prefix:
node_iter = (node_iter.children)[ord(c) - ord('a')]
if node_iter is None:
break
return node_iter

Python,子节点用 dict 实现

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:
def __init__(self):
self.terminal = False
self.children = dict()

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word: str) -> None:
node_iter = self.root
for c in word:
if c not in node_iter.children:
node_iter.children[c] = TrieNode()
node_iter = node_iter.children[c]
node_iter.terminal = True

def search(self, word: str) -> bool:
node_iter = self._find(word)
return node_iter is not None and node_iter.terminal

def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None

def _find(self, prefix):
node_iter = self.root
for c in prefix:
if c not in node_iter.children:
return None
node_iter = (node_iter.children)[c]
return node_iter

Share