本文主要作为自己的学习笔记，并不具备过多的指导意义。
前缀树
何为前缀树
前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。多用于词频搜索或者模糊查询。
查询时只与单样本长度有关，而与样本量无关。
举例：
给出一组单词，inn, int, at, age, adv,ant, 我们可以得到下面的Trie：
如此，在进行依次输入进行查询时。只需要顺着之前的树继续查询即可，而不需要每次修改字符串都遍历所有信息。
在删除了字符时，也只需要回滚到上层即可。
基本代码结构
-
树节点
一个多叉树结构的节点。前缀树的功能，取决于节点的健壮性。
//前缀树节点public class TrieNode { public var end :Bool //是否为某个单词最后节点，查询用 public var path :Int //记录有几个字符串经过了这个节点，删除用 public var nexts:Dictionary //子树路径，基本功能 public init() { self.end = false self.nexts = Dictionary.init() self.path = 0 }}复制代码 其中子树路径，如果只存储字符串的话。当样本量太大可以干脆使用数组[26]的形式存储。
-
前缀树结构
持有一个根节点，具备增删改查的功能
//前缀树public class Trie { private var root:TrieNode public init() { self.root = TrieNode.init() } /// 添加字符串 public func insert(word:String) { ... } //查找 public func search(word:String) -> Bool { ... } //删除 public func delete(word:String) { ... }}复制代码 -
插入数据
将字符串按字母分割，从根节点依次追加进前缀树
需要注意如果树中已经存在该节点路径，则复用
/// 添加字符串public func insert(word:String) { if word == nil { return } let strs = wordToArr(word: word) if strs.count == 0 { return } //从根节点开始建立前缀树 var node = root for i in 0.. -
查找数据
查找与插入类似，但需要判断最后一个节点的end属性是否被标记
//查找public func search(word:String) -> Bool { if word == nil { return false } let strs = wordToArr(word: word) if strs.count == 0 { return false } //从根节点开始建立前缀树 var node = root for i in 0.. -
删除数据
先类似查找的方式确定是否存在该数据，然后尝试删除。
每次删除，其实是将节点的path属性-1。当path属性==0时，从上级节点的nexts列表中remove掉该节点即可return结束。
//删除public func delete(word:String) { if word == nil { return } let strs = wordToArr(word: word) if strs.count == 0 { return } //尝试查找指定字符串，并且保存在nodes备用 var node = root var nodes : [TrieNode] = Array.init() nodes.append(node) for i in 0.. 前缀树的应用
- 字符串的快速检索 前缀树的查询时间复杂度是O(L)，L是字符串的长度。所以效率还是比较高的。字典树的效率比hash表高。
- 字符串排序 多叉树本身已经是有序的，只要按照每层都先遍历低位节点的方式即可。
后缀树
相对于前缀树来说，后缀树并不是针对大量字符串的，而是针对一个或几个字符串来解决问题。比如字符串的回文子串，两个字符串的最长公共子串等等。
比如blanana这个单词，在后缀树的结构中将以如下结构展现(为了方便看到后缀，我没有合并相同的前缀)
后缀树的应用
- 查找字符串
an是否在banana中 如上图所致，a+n的节点顺序已经存在于后缀树中，所以返回true - 查找字符串
a+n在banana中重复的次数。 如上图所致，a+n中n节点的path计数为2，所以重复次数为2.