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数组的时间将是不可接受的。words(matching:)的时间复杂度是O(k*n)，其中k是集合中最长的字符串，n是你需要检查的单词数。

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

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

为了说明三段式的性能优势，请看下面的例子，你需要找到前缀为CU的词。

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

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

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

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

实施

像往常一样，打开本章的起始Playground。

TrieNode

你将从创建三角形的节点开始。在Sources目录下，创建一个名为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持有对其父节点的弱引用。这个引用可以简化后面的remove方法。
3. 在二进制搜索树中，节点有一个左边和右边的孩子。在trie中，一个节点需要持有多个不同的元素。你已经声明了一个children字典来帮助解决这个问题。
4. 正如前面所讨论的，isTerminating作为一个集合结束的指标。

Trie

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

public class Trie<CollectionType: Collection>
    where CollectionType.Element: Hashable {

  public typealias Node = TrieNode<CollectionType.Element>

  private let root = Node(key: nil, parent: nil)

  public init() {}
}

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

接下来, 你将为trie实现四个操作: insert, contains, remove和前缀匹配.

插入

尝试对任何符合Collection的类型进行操作。trie将接受集合并将其表示为一系列节点--集合中的每个元素。

在Trie中添加以下方法：

public func insert(_ collection: CollectionType) {
  // 1
  var current = root

  // 2
  for element in collection {
    if current.children[element] == nil {
      current.children[element] = Node(key: element, parent: current)
    }
    current = current.children[element]!
  }

  // 3
  current.isTerminating = true
}

以下是发生的情况：

1. current记录了你的遍历进度，从根节点开始。
2. trie将每个集合元素存储在一个单独的节点中。对于集合中的每个元素，你首先检查该节点是否当前存在于children字典中。如果不存在，你就创建一个新的节点。在每个循环中，你把current移到下一个节点。
3. 在for循环迭代之后，current应该引用代表集合末端的节点。你将该节点标记为终止节点。

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

含有

contains与insert非常相似。在Trie中添加以下方法：

public func contains(_ collection: CollectionType) -> Bool {
  var current = root
  for element in collection {
    guard let child = current.children[element] else {
      return false
    }
    current = child
  }
  return current.isTerminating
}

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

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

为了测试insert和contains，请导航到Playground页面并添加以下代码：

example(of: "insert and contains") {
  let trie = Trie<String>()
  trie.insert("cute")
  if trie.contains("cute") {
    print("cute is in the trie")
  }
}

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

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

移除

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

在contains下面写一个方法：

public func remove(_ collection: CollectionType) {
  // 1
  var current = root
  for element in collection {
    guard let child = current.children[element] else {
      return
    }
    current = child
  }
  guard current.isTerminating else {
    return
  }
  // 2
  current.isTerminating = false
  // 3
  while let parent = current.parent,
        current.children.isEmpty && !current.isTerminating {
      parent.children[current.key!] = nil
      current = parent
  }
}

逐一进行评论：

1. 这一部分应该很熟悉，因为它是contains的实现。你在这里用它来检查集合是否是三角形的一部分，并将current指向集合的最后一个节点。
2. 你把isTerminating设置为false，这样当前节点就可以在下一步被循环删除。
3. 这是个棘手的部分。由于节点可以共享，你不希望删除属于另一个集合的元素。如果在当前节点中没有其他子节点，这意味着其他集合不依赖于当前节点。 你还要检查当前节点是否是终止的。如果是，那么它就属于另一个集合。只要current满足这些条件，你就不断地回溯parent属性并删除节点。

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

回到Playground页面，在底部添加以下内容：

example(of: "remove") {
  let trie = Trie<String>()
  trie.insert("cut")
  trie.insert("cute")

  print("\n`* Before removing `*")
  assert(trie.contains("cut"))
  print("\"cut\" is in the trie")
  assert(trie.contains("cute"))
  print("\"cute\" is in the trie")

  print("\n`* After removing cut `*")
  trie.remove("cut")
  assert(!trie.contains("cut"))
  assert(trie.contains("cute"))
  print("\"cute\" is still in the trie")
}

你应该看到以下输出被添加到控制台：

---Example of: remove---

*** Before removing ***
"cut" is in the trie
"cute" is in the trie

*** After removing cut ***
"cute" is still in the trie

前缀匹配

trie最具代表性的算法是前缀匹配算法。在Trie.swift的底部写上以下内容：

public extension Trie where CollectionType: RangeReplaceableCollection {

}

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

接下来，在扩展中添加以下方法：

func collections(startingWith prefix: CollectionType) -> [CollectionType] {
  // 1
  var current = root
  for element in prefix {
    guard let child = current.children[element] else {
      return []
    }
    current = child
  }

  // 2
  return collections(startingWith: prefix, after: current)
}

1. 你首先要验证三角形是否包含前缀。如果没有，则返回一个空数组。
2. 找到标志着前缀结束的节点后，调用递归辅助方法collections(startingWith:after:)来找到current节点之后的所有序列。

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

private func collections(startingWith prefix: CollectionType,
                         after node: Node) -> [CollectionType] {
  // 1
  var results: [CollectionType] = []

  if node.isTerminating {
    results.append(prefix)
  }

  // 2
  for child in node.children.values {
    var prefix = prefix
    prefix.append(child.key!)
    results.append(contentsOf: collections(startingWith: prefix,
                                           after: child))
  }

  return results
}

1. 你创建一个数组来保存结果。如果当前节点是终止的，你就把它加入到结果中。
2. 接下来，你需要检查当前节点的子节点。对于每个子节点，你递归地调用collections(startingWith:after:)来寻找其他终止节点。

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

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

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

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

example(of: "prefix matching") {
  let trie = Trie<String>()
  trie.insert("car")
  trie.insert("card")
  trie.insert("care")
  trie.insert("cared")
  trie.insert("cars")
  trie.insert("carbs")
  trie.insert("carapace")
  trie.insert("cargo")

  print("\nCollections starting with \"car\"")
  let prefixedWithCar = trie.collections(startingWith: "car")
  print(prefixedWithCar)

  print("\nCollections starting with \"care\"")
  let prefixedWithCare = trie.collections(startingWith: "care")
  print(prefixedWithCare)
}

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

---Example of: prefix matching---

Collections starting with "car"
["car", "carbs", "care", "cared", "cars", "carapace", "cargo", "card"]

Collections starting with "care"
["care", "cared"]

关键点

• Tries在前缀匹配方面提供了很好的性能指标。
• 由于单个节点可以在许多不同的值之间共享，因此尝试的内存效率相对较高。例如，"car"、"carbs"和"care"可以共享这个词的前三个字母。