Trie 樹肌幽，也叫字典樹，專門做字符串匹配的數(shù)據(jù)結(jié)構(gòu)糯耍，也可快速的做字符串前綴匹配扔字。
它是一種多叉樹，即把前綴相同的字符串合并在一起温技，根節(jié)點默認(rèn)不存儲字符革为。如下圖所示：
上圖中 hi 、her舵鳞、how 共用節(jié)點 h震檩，它們相同的前綴是 h。hello 與 her 也是同理蜓堕，相同前綴是 he抛虏。
舉個栗子，hi 套才、her迂猴、how 的插入過程如下：
那么如何進(jìn)行查找呢？
栗子1 -- 查找 hi 過程：
- 從根節(jié)點
root開始背伴，查找其子節(jié)點有無h沸毁，結(jié)果是有 - 查找
h的子節(jié)點有無i峰髓，結(jié)果也有，同時i是末尾節(jié)點以清，表示是個完整的字符串儿普，匹配完成。
栗子2 -- 查找 he 過程：
- 從根節(jié)點
root開始掷倔，查找其子節(jié)點有無h眉孩，結(jié)果是有 - 查找
h的子節(jié)點有無e，結(jié)果也有勒葱，但e不是末尾節(jié)點浪汪，表示其只是匹配到了前綴，并不能完全匹配到he凛虽。
通過上述描述死遭，我們知道其插入、查找的過程凯旋。那么如何用代碼實現(xiàn)呢呀潭？
實現(xiàn)
前面提到過，Trie 樹是多叉樹至非，節(jié)點的取值范圍在字符串的所有可能出現(xiàn)的字符集內(nèi)钠署。如字符串包含的只是 a-z，那么最多只需要 26 個子節(jié)點荒椭；如果字符串包含 a-zA-Z谐鼎，那么最多需要 52 個自己點；以此類推趣惠。
當(dāng)然狸棍，不是每個節(jié)點的子節(jié)點都會包含所有字符集，不存在的子節(jié)點設(shè)置為 null味悄。
所以草戈，假設(shè)字符集為 a-z ，總共 26 個小寫字母傍菇，其數(shù)據(jù)結(jié)構(gòu)如下：
class TrieNode {
var data: Character
// 字符集 26 個小寫字母
var children: [TrieNode?]
var isEnd: Bool = false
init(data: Character) {
self.data = data
children = [TrieNode]()
// 初始化 26 個
var i = 0
while i < 26 {
children.append(nil)
i += 1
}
}
}
需要取子節(jié)點時猾瘸，只需要算出 index = ch - 'a' ，然后根據(jù) p.children[index] 取出即可丢习，為 null 則表示不存在該 ch 字符牵触。
Trie 樹定義如下，包含插入和查找兩個方法咐低。
class Trie {
let root = TrieNode(data: Character("/"))
// 插入
func insert(text: String) {}
// 查找
func match(text: String) -> Bool {}
// 計算index
func indexOfChar(_ ch: Character) -> Int {
let index = ch.toInt() - Character("a").toInt()
return index
}
}
插入
逐個遍歷字符串揽思，若當(dāng)前節(jié)點不存在該字符對應(yīng)的子節(jié)點，則生成新的節(jié)點插入见擦；若存在钉汗，則沿著樹的分支繼續(xù)往下走羹令。當(dāng)遍歷完成，將最后一個節(jié)點結(jié)束符 isEnd 置為 true损痰。
func insert(text: String) {
var p = root
var i = 0
while i < text.count {
let strIndex = text.index(text.startIndex, offsetBy: i)
let ch = text[strIndex]
// 計算 index
let index = indexOfChar(ch)
if index < 0 || index >= 26 {
assert(false, "包含非法字符")
}
if (index >= 0 && index <= p.children.count) {
if p.children[index] == nil {
// 插入新節(jié)點
let node = TrieNode(data: ch)
p.children[index] = node
}
p = p.children[index]!
}
i += 1
}
// 標(biāo)記結(jié)束
p.isEnd = true
}
查找
逐個遍歷字符串福侈，若當(dāng)前節(jié)點不存在該字符對應(yīng)的子節(jié)點，則說明不匹配卢未；若存在肪凛，則沿著樹的分支繼續(xù)往下走。當(dāng)遍歷完成辽社，若最后一個節(jié)點是結(jié)束符伟墙，則完全匹配；否則只是前綴匹配滴铅。
func match(text: String) -> Bool {
var p = root
var i = 0
while i < text.count {
let strIndex = text.index(text.startIndex, offsetBy: i)
let ch = text[strIndex]
// 計算 index
let index = indexOfChar(ch)
if (index >= 0 && index <= p.children.count) {
if p.children[index] != nil {
p = p.children[index]!
} else {
// 不匹配
return false
}
} else {
return false
}
i += 1
}
// 完全匹配
if p.isEnd {
return true
}
return false
}
效率
Trie 樹構(gòu)建時戳葵，需要遍歷所有的字符串，因此時間復(fù)雜度為所有字符串長度總和 n汉匙，時間復(fù)雜度為 O(n)拱烁。
但是 Trie 樹的查找效率很高，如果字符串長度為 k噩翠，那么時間復(fù)雜度 為 O(k)邻梆。
Trie 是一種以空間換時間的結(jié)構(gòu)，當(dāng)字符集較大時绎秒，會占用很多空間，同時如果前綴重合較少尼摹，空間會占用更多见芹。所以其比較適合查找前綴匹配。
