Question

如何在 Swift 中使用字典树

Answer 1

如果上 Google 搜“酷酷的数据结构”，你首先会看到 这个 结果。其中主要是 stackoverflow 上的一个问题：“哪些是我们很少知道但是很有用的数据结构？”。而点赞最多的答案，就是本期主题：字典树。我读了一下，发现了很多酷酷的东西都是关于字典树的用途(同时发现我也是那种会去 Google 搜“酷酷的数据结构”的人，哈哈)。然后我就打开 playground，开始写这篇文章。
字典树是一种前缀树。它是一种递归的数据结构：每个字典树包含子字典树，子字典树通过前缀来辨认。
字典树这种数据结构不仅广泛使用，而且也有一些有用的应用。它也有类似 Set 一样的操作，比如插入和查找都是 O(n) 复杂度，其中 n 是查找序列的长度。目前，Set是哈希化(hashable)和元素无序化的最好方式。但是，如果要查找的序列中元素是哈希化的，那么字典树就很适合。(有一点要注意：Set 本身是哈希化的，所以，假如需要保存的序列是无序的话，那么 Set 的集合会更合适)

在 Swift 中，我们可以让字典树包含一系列的前缀和子字典树来实现。代码如下：
public struct Trie<Element : Hashable> {
private var children: [Element:Trie<Element>]
}

我们定义的结构可以递归，因为我不是直接在字典树里保存字典树——我们保存的是引用子字典树的字典类型。在这个字典中，把前缀当作键。那么我们怎么初始化呢？可以像列表那样使用生成器的分解属性。
extension Trie {
private init<G : GeneratorType where G.Element == Element>(var gen: G) {
if let head = gen.next() {
children = [head:Trie(gen:gen)]
} else {
children = [:]
}
}
public init
<S : SequenceType where S.Generator.Element == Element>
(_ seq: S) {
self.init(gen: seq.generate())
}
}