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

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

字典树（Trie）

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

什么是字典树

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

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

为什么需要字典树？

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

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

常用算法

包含（或任何常规查找方法）

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

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方法相当简单：

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

插入

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

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
}

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

删除

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

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

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
}

findTerminalNodeOf遍历字典树，找到代表word的最后一个节点。如果它无法遍历字符串，则返回nil。
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