前缀树

从定义上来说，前缀树 trie 是 n 叉树 的一种典型的应用。正如字面意思，前缀树是一种存储字符串形成前缀匹配路径的数据结构。 树中每一个节点代表一个字符，并与其祖先节点构成一个前缀，节点的后代节点所代表的字符串都有一个相同的字符串前缀。这正是前缀树名称的由来。前缀树又称字典树，在搜索引擎关键字索引编排，输入法文字匹配，动态路由匹配，不可变数据（如 immutable.js）等等领域都有广泛应用实践。

语言前置

在 golang 中函数实参是默认 按值传递，除非传入显式指针。当我们在结构体的指针上定义方法时，在方法中将获得结构体的指针，而非值的副本，此时，可在方法中通过指针修改结构体本身。反之，获得的是值的副本（当结构体过大时，创建值的副本可能影响运行时效率），此时无法在方法中修改结构体。那么要实现保证执行效率且支持在方法中修改结构体值时，传递指针优于传递值methods on values or pointers。

故本文将以结构体指针的方法定义来实现 Trie 数据结构。

基于映射构建前缀树

一个典型的前缀树节点定义如下：

package trie
// Trie defines a trie node
// @see https://en.wikipedia.org/wiki/Trie
type Trie struct {
  isWord bool
  next map[rune]*Trie
}

其中 isWord 字段表示当前节点是否是表示单词的结尾，即从根节点到当前节点的路径构成一个完成的单词，而不是单词前缀。next 字段表示存储了所有以当前节点及其父节点为前缀的其他字符的映射。

创建前缀树根节点

// Create is used to initialize a Trie struct
func Create() Trie {
  return Trie{isWord: false, next: make(map[rune]*Trie)}
}

在上文代码中实例化 Trie 结构体时，必须使用 make 函数显式实例化 next 字段，以防止 nil map。因为 golang map 的初始零值为 nil map。其在 golang spec 中被定义为不能添加任意元素的空映射。

A new, empty map value is made using the built-in function make, which takes the map type and an optional capacity hint as arguments.

A nil map is equivalent to an empty map except that no elements may be added.

新建路径

在前缀树中，insert 插入操作，被认为是对实参字符串的序列化操作，将依次迭代实参字符串的字符，进而在 某一树的路径 上 深入 构建字符路径。实参的每一个字符（除首项）都是前一字符的直接子节点。如下：

// Insert is used to insert a new node if the path does not exist
func (root *Trie) Insert(word string) {
  for _, char := range word {
    // char is rune type
    if _, ok := root.next[char]; !ok {
      children := Create()
      root.next[char] = &children
    }
    root = root.next[char]
  }
  root.isWord = true
}

尤其注意的是，在上述代码实现中，执行至最后一行时，此时的 root 变量为实参单词的最后一个字符，即当前前缀树中某一个单词路径的 叶子节点。另外，在前缀树中，单词节点 并不一定是 叶子节点（如单词 hash 与 hashmap 将存在公共路径 hash，h 为非叶子节点，但它是单词节点），但叶子节点 一定是 单词节点。

搜索前缀

// StartsWith is used to judge prefix string
func (root *Trie) StartsWith(prefix string) bool {
  for _, char := range word {
    if _, ok := root.next[char]; !ok {
      return false
    }
    root = root.next[char]
  }
  return true
}

前缀树的搜索的核心实现仍与插入的核心思想一致，基于 DFS 的迭代，实现路径上的字符查找，当实参某一字符无法在路径上找到时，那么即实参单词不存在于当前前缀树路径所构成的单词集合中。

反之，结束迭代后，表示实参 prefix 存在一条路径与之匹配，那么就存在以实参 prefix 为前缀的单词，故返回 true。

搜索单词

// Search is used to search node from specific trie
func (root *Trie) Search(word string) bool {
  for _, char := range word {
    if _, ok := root.next[char]; !ok {
      return false
    }
    root = root.next[char]
  }
  return root.isWord
}

搜索单词本质上是上文 搜索前缀 的特殊用例。在结束迭代后，此时不能单纯的返回 true，而应根据此时迭代结束时 root 变量所对应的叶子节点是否时单词节点来返回实际结果。

基于数组构建前缀树

数组相较于映射的明显优势在于，能在有限的内存空间内形成 连续的 内存空间地址。那么在 有限 的字符集合下，数组实现的 runtime 性能开销优于映射实现。在本例中，基于数据实现的前缀树节点大致与基于映射的实现相同，不同之处仅在于实现细节：

下文以限定字符集为 a - z 共 26 个字母为例，可根据实际情况改写 size 或使用 slice 实现。

package trie

type Trie {
  isWord bool
  next [26]*Trie
}

因为此时我们是基于数组实现，那么 next 字段修改为 Array 类型，且子项为后代 Trie 节点的指针。

创建节点

同映射实现：

func New() Trie {
  return Trie{}
}

节点操作

基于数组实现的节点逻辑框架与映射实现 一致，不同之处在于不直接使用字符的 ascii 码，而转为计算据 a 字符（即 a 字符对应数组索引 0 位置）的差异值得到存储区域的索引值：

新建路径

func (root *Trie) Insert(word string) {
  for _, char := range word {
    index := char -'a'
    if ptr := root.next[index]; ptr == nil {
      root.next[index] = new(Trie)
    }
    root = root.next[index]
  }
  root.isWord = true
}

当插入一个 M 长度的单词时，需要逐个检查字符，直到单词尾部，即需要 M 次操作。故时间复杂度为 O(M)。最坏情况下，需要插入的单词，与已有前缀全不匹配，那么需要新建 M 个节点，故此时空间复杂度为 O(M)。

搜索前缀

func (root *Trie) StartsWith(prefix string) bool {
  for _, char := range prefix {
    index := char - 'a'
    if ptr := root.next[index]; ptr == nil {
      return false
    }
    root = root.next[index]
  }
  return true
}

当查找一个长度为 M 的前缀时，最坏情况需要执行 M 次节点比较，故时间复杂度为 O(M)。此时并不会有额外空间使用，即空间恒定，故空间复杂度为 O(1)。

搜索单词

func (root *Trie) Search(word string) bool {
  for _, char := range word {
    index := char - 'a'
    if ptr := root.next[index]; ptr == nil {
      return false
    }
    root = root.next[index]
  }
  return root.isWord
}

时间空间复杂度同 搜索前缀。

节点操作框架

不论是上述基于数组还是基于映射的前缀树实现，我们通过归纳不难得到以下前缀树的节点操作抽象逻辑：

1. 迭代实参字符串；

   1. 基于 1 中的单个字符，检测其是否能够命中当前层的前缀树节点，即是否满足特定前缀；

      1. 能，深入前缀树的下一层，即进入 1 的下一个字符的比较（下一个前缀的匹配）；

      2. 不能，退出整个函数运行，即 1 所表示的字符串不存在于当前前缀树中；

2. 完成迭代，到达叶子节点，即此时获取到某个单词节点，且能够完全匹配实参字符串，且它是实参字符串的某一前缀或完全等价于实参字符串。

func (root *Trie) Operate(word string) {
  for _, char := range word {
    if _, ok := isExistInAuxContainer(char); !ok {
      // do something if char does not exist
    }
    // continue to process next character
    root = deepIntoChild(root, char)
  }
  // do something when we arrival at leaf node
}