Fork me on GitHub

【译】Swift算法俱乐部-字典树

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Trie


字典树(Trie)

这个话题已经有个辅导文章

什么是字典树

Trie(在一些其他实现中也称为前缀树或基数树)是用于存储关联数据结构的特殊类型的树。 Trie作为一个字典可能如下所示:

A Trie

存储英语是Trie的主要用处。 Trie中的每个节点都代表一个单词的单个字符。 然后,一系列节点组成一个单词。

为什么需要字典树?

字典树对某些情况非常有用。 以下是一些优点:

  • 查找值通常具有更好的最坏情况时间复杂度。
  • 与哈希映射不同,Trie不需要担心键冲突。
  • 不使用散列来保证元素的唯一路径。
  • Trie结构默认按字母顺序排列。

常用算法

包含(或任何常规查找方法)

Trie结构非常适合查找操作。 对于模拟英语语言的Trie结构,找到一个特定的单词就是几个指针遍历的问题:

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
func contains(word: String) -> Bool {
guard !word.isEmpty else { return false }

// 1
var currentNode = root

// 2
var characters = Array(word.lowercased().characters)
var currentIndex = 0

// 3
while currentIndex < characters.count,
let child = currentNode.children[characters[currentIndex]] {

currentNode = child
currentIndex += 1
}

// 4
if currentIndex == characters.count && currentNode.isTerminating {
return true
} else {
return false
}
}

contains方法相当简单:

  1. 创建对root的引用。 此引用将允许您沿着节点链向下走。
  2. 跟踪你想要匹配的单词的字符。
  3. 将指针向下移动节点。
  4. isTerminating是一个布尔标志,表示该节点是否是单词的结尾。 如果满足此if条件,则意味着您可以在trie中找到该单词。

插入

插入Trie需要您遍历节点,直到您停止必须标记为terminating的节点,或者到达需要添加额外节点的点。

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
func insert(word: String) {
guard !word.isEmpty else {
return
}

// 1
var currentNode = root

// 2
for character in word.lowercased().characters {
// 3
if let childNode = currentNode.children[character] {
currentNode = childNode
} else {
currentNode.add(value: character)
currentNode = currentNode.children[character]!
}
}
// Word already present?
guard !currentNode.isTerminating else {
return
}

// 4
wordCount += 1
currentNode.isTerminating = true
}
  1. 再次,您创建对根节点的引用。 您将此引用沿着节点链移动。
  2. 逐字逐句地逐字逐句
  3. 有时,要插入的节点已存在。 这是Trie里面两个共享字母的词(即“Apple”,“App”)。如果一个字母已经存在,你将重复使用它,并简单地遍历链条。 否则,您将创建一个表示该字母的新节点。
  4. 一旦结束,将isTerminating标记为true,将该特定节点标记为单词的结尾。

删除

从字典树中删除键有点棘手,因为还有一些情况需要考虑。 Trie中的节点可以在不同的单词之间共享。 考虑两个词“Apple”和“App”。 在Trie中,代表“App”的节点链与“Apple”共享。

如果你想删除“Apple”,你需要注意保持“App”链。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func remove(word: String) {
guard !word.isEmpty else {
return
}

// 1
guard let terminalNode = findTerminalNodeOf(word: word) else {
return
}

// 2
if terminalNode.isLeaf {
deleteNodesForWordEndingWith(terminalNode: terminalNode)
} else {
terminalNode.isTerminating = false
}
wordCount -= 1
}
  1. findTerminalNodeOf遍历字典树,找到代表word的最后一个节点。 如果它无法遍历字符串,则返回nil
  2. deleteNodesForWordEndingWith遍历后缀,删除word表示的节点。

时间复杂度

设n是Trie中某个值的长度。

  • contains - 最差情况O(n)
  • insert - O(n)
  • remove - O(n)

其他值得注意的操作

  • count:返回Trie中的键数 —— O(1)
  • words:返回包含Trie中所有键的列表 —— O(1)
  • isEmpty:如果Trie为空则返回true,否则返回false —— O(1)

扩展阅读字典树的维基百科

作者:Christian Encarnacion, Kelvin Lau
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
0%