第18章： Tries

trie（读作try）是一种树，专门用于存储可以表示为集合的数据，如英语单词。

每个字符串都映射到一个节点，其中最后一个节点（上图中用点标记）是终止的。通过在前缀匹配的背景下看三角形的好处是最好的说明。

在这一章中，你将首先比较 trie 和数组的性能。然后，你将从头开始实现trie!

例子

你得到了一个字符串的集合。你将如何建立一个处理前缀匹配的组件？这里有一个方法。

class EnglishDictionary { 
  private var words: [String] 
  func words(matching prefix: String) -> [String] { 
    words.filter { 
      $0.hasPrefix(prefix) 
    } 
  } 
}

words(matching:)将浏览字符串集合，并返回符合前缀的字符串。

如果 words 数组中的元素数量很少，这种算法是合理的。但是如果你要处理的是超过几千个单词，那么浏览单词数组的时间将是不可接受的。words(matching:)的时间复杂度是O(k*n)，其中k是集合中最长的字符串，n是你需要检查的词的数量。

trie数据结构在这个问题上有很好的性能特点；作为一个支持多个子节点的树，每个节点可以代表一个字符。

你通过追踪从根部到节点的字符集合形成一个词，节点上有一个特殊的指示器--终结符，用黑点表示。trie的一个有趣的特点是，多个词可以共享相同的字符。

为了说明treee的性能优势，请考虑下面的例子，你需要找到带有前缀CU的词。

首先，你前往包含C的节点，这很快就把三角形的其他分支排除在搜索操作之外。

接下来，你需要找到有下一个字母U的词，你遍历到U节点。

由于这是你的前缀的结束，tree将返回从U节点开始的节点链所形成的所有集合。在这种情况下，CUT和CUTE这两个词将被返回。想象一下，如果这个 trie 包含成百上千的词，那么你可以避免多少次的比较。

通过使用 trie，你可以避免大量的比较。

实现

像往常一样，打开本章的启动器playground。

trieNode

你将从创建 trie 的节点开始。在Source目录下，创建一个名为TrieNode.swift的新文件。在该文件中添加以下内容。

public class TrieNode<Key: Hashable> {

  // 1 
  public var key: Key?

  // 2 
  public weak var parent: TrieNode?

  // 3 
  public var children: [Key: TrieNode] = [:]

  // 4 
  public var isTerminating = false

  public init(key: Key?, parent: TrieNode?) { 
    self.key = key
    self.parent = parent
  }
}

与你遇到的其他节点相比，这个界面略有不同。

1.key保存节点的数据。这是可选的，因为 trie 的根节点没有键。

2. TrieNode持有对其父节点的弱引用。这个引用简化了后面的删除方法。

3. 在二进制搜索树中，节点有一个左边和右边的孩子。在 trie 中，一个节点需要持有多个不同的元素。你已经声明了一个children dictionary来帮助解决这个问题。

4. 正如前面所讨论的，isTerminating充当了一个集合结束的指标。

Trie

接下来，你将创建Trie本身，它将管理这些节点。在Source文件夹中，创建一个名为Trie.swift的新文件。在该文件中添加以下内容。

你可以将Trie类用于所有采用Collection协议的类型，包括String。除了这个要求之外，集合里面的每个元素都必须是Hashable。这个额外的限制是必须的，因为你将使用集合中的元素作为TrieNode中的children字典的键。

接下来，你将为Trie实现四个操作：插入、包含、移除和前缀匹配。

插入

尝试与任何符合集合的类型一起工作。trie将采取集合，并将其表示为一系列的节点--一个节点代表集合中的每个元素。

在Trie中添加以下方法。

下面是发生的事情。

1. current跟踪你的遍历进度，它从根节点开始。

2. trie将每个集合元素存储在一个单独的节点中。对于集合中的每个元素，你首先检查该节点当前是否存在于子字典中。如果不存在，你就创建一个新的节点。在每个循环中，你把当前的节点移到下一个节点。

3. 通过for循环迭代后，current应该引用代表集合末端的节点。你将该节点标记为终止节点。

这个算法的时间复杂度是O(k)，其中k是你试图插入的集合中的元素数量。这个成本是因为你需要遍历或创建代表每个新集合元素的节点。

包含

包含与插入非常相似。在Trie中添加以下方法。

在这里，你以一种类似于插入的方式遍历三角形。你检查集合中的每个元素，看它是否在树中。当你到达集合的最后一个元素时，它必须是一个终止的元素。如果不是，那么这个集合就没有被添加，你所找到的是一个更大的集合的子集。

contains的时间复杂度是O(k)，其中k是你用来搜索的集合中的元素数。这个时间复杂度来自于遍历k个节点以确定集合是否在 trie 中。

要测试insert和contains，请导航到playground页面并添加以下代码。

你应该看到下面的控制台输出。

---Example of: insert and contains--
cute is in the trie

移除

在 trie 中删除一个节点是比较麻烦的。在移除每个节点时需要特别小心，因为多个集合可以共享节点。

写下下面的方法，就在contains下面。

逐条评论。

1. 这一部分看起来应该很熟悉，因为它是contains的实现。你在这里用它来检查集合是否是三角形的一部分，并将当前指向集合的最后一个节点。

2. 你把isTerminating设置为false，这样当前节点就可以在下一步被循环删除。

3. 这是最棘手的部分。由于节点可以被共享，你不想删除属于另一个集合的元素。如果在当前节点中没有其他子节点，这意味着其他集合不依赖于当前节点。

你也要检查一下当前节点是否是终止的。如果是，那么它就属于另一个集合。只要current满足这些条件，你就不断地回溯父属性并删除节点。

这个算法的时间复杂度是O(k)，其中k代表你试图移除的集合中的元素数量。

回到playground页面，在底部添加以下内容。

你应该看到控制台中加入了以下输出。

预测匹配

三元组最有代表性的算法是前缀匹配算法。在Trie.swift的底部写上以下内容。

你的前缀匹配算法将位于这个扩展中，其中CollectionType被限制为RangeReplaceableCollection。这种一致性是必须的，因为该算法需要访问RangeReplaceableCollection类型的append方法。

接下来，添加辅助方法的代码。

1. 你首先要验证三角形是否包含前缀。如果没有，则返回一个空数组。

2. 找到标志着前缀结束的节点后，调用递归辅助方法collection(startingWith:after:)来找到当前节点之后的所有序列。

接下来，添加辅助方法的代码。

1. 你创建一个数组来保存结果。如果当前节点是终止的，你就把它添加到结果中。

2. 接下来，你需要检查当前节点的子节点。对于每一个子节点，你都要递归地调用collection(startingWith:after:)来寻找其他终止的节点。

collection(startingWith:)的时间复杂度为O(k*m)，其中k代表匹配前缀的最长集合，m代表匹配前缀的集合的数量。

回顾一下，数组的时间复杂度为O(k*n)，其中n是集合中元素的数量。

对于每个集合均匀分布的大型数据集，尝试的性能远远好于使用数组进行前缀匹配。

是时候让这个方法转一转了。导航到playground页面，添加以下内容。

你应该在控制台看到以下输出。

关键点

• 在前缀匹配方面，Tries提供了很好的性能指标。

• 尝试的内存效率相对较高，因为单个节点可以在许多不同的值之间共享。例如，"car"、"carbs "和 "care "可以共享这个词的前三个字母。

---

上一章	目录	下一章