本文只是自己的筆記，并不具備過多的指導(dǎo)意義。

前綴樹

何為前綴樹

前綴樹又名字典樹，單詞查找樹，Trie樹，是一種多路樹形結(jié)構(gòu)，是哈希樹的變種，和hash效率有一拼，是一種用于快速檢索的多叉樹結(jié)構(gòu)。多用于詞頻搜索或者模糊查詢。

查詢時(shí)只與單樣本長度有關(guān)，而與樣本量無關(guān)。

舉例：

給出一組單詞，inn, int, at, age, adv,ant, 我們可以得到下面的Trie：

image

如此，在進(jìn)行依次輸入進(jìn)行查詢時(shí)。只需要順著之前的樹繼續(xù)查詢即可，而不需要每次修改字符串都遍歷所有信息。

在刪除了字符時(shí)，也只需要回滾到上層即可。

基本代碼結(jié)構(gòu)

• 樹節(jié)點(diǎn)

一個(gè)多叉樹結(jié)構(gòu)的節(jié)點(diǎn)。前綴樹的功能，取決于節(jié)點(diǎn)的健壯性。

//前綴樹節(jié)點(diǎn)
public class TrieNode {
    public var end :Bool //是否為某個(gè)單詞最后節(jié)點(diǎn)，查詢用
    public var path :Int //記錄有幾個(gè)字符串經(jīng)過了這個(gè)節(jié)點(diǎn)，刪除用
    public var nexts:Dictionary<String, TrieNode> //子樹路徑，基本功能
    
    public init() {
        self.end = false
        self.nexts = Dictionary.init()
        self.path = 0
    }
}

其中子樹路徑，如果只存儲(chǔ)字符串的話。當(dāng)樣本量太大可以干脆使用數(shù)組[26]的形式存儲(chǔ)。

• 前綴樹結(jié)構(gòu)

持有一個(gè)根節(jié)點(diǎn)，具備增刪改查的功能

//前綴樹
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) {
        ...
    }
}

• 插入數(shù)據(jù)

將字符串按字母分割，從根節(jié)點(diǎn)依次追加進(jìn)前綴樹

需要注意如果樹中已經(jīng)存在該節(jié)點(diǎn)路徑，則復(fù)用

/// 添加字符串
public func insert(word:String) {
    if word == nil {
        return
    }
    
    let strs = wordToArr(word: word)
    if strs.count == 0 {
        return
    }
    
    //從根節(jié)點(diǎn)開始建立前綴樹
    var node = root
    for i in 0..<strs.count {
        if node.nexts[strs[i]] == nil {
            node.nexts.updateValue(TrieNode.init(), forKey: strs[i]) //沒有可服用路徑,新建節(jié)點(diǎn)
        }
        node = node.nexts[strs[i]]! //node跳到下層
        node.path+=1 // 將當(dāng)前節(jié)點(diǎn)計(jì)數(shù)+1
    }
    
    node.end = true //標(biāo)記最后一個(gè)節(jié)點(diǎn)
}

• 查找數(shù)據(jù)

查找與插入類似，但需要判斷最后一個(gè)節(jié)點(diǎn)的end屬性是否被標(biāo)記

//查找
public func search(word:String) -> Bool {
    if word == nil {
        return false
    }
    
    let strs = wordToArr(word: word)
    if strs.count == 0 {
        return false
    }
    
    //從根節(jié)點(diǎn)開始建立前綴樹
    var node = root
    for i in 0..<strs.count {
        if node.nexts[strs[i]] == nil {
            return false  //任何一步有空，說明未被插入過
        }
        
        node = node.nexts[strs[i]]!
    }
    
    return node.end //返回最后一個(gè)節(jié)點(diǎn)的標(biāo)記狀態(tài)
}

• 刪除數(shù)據(jù)

先類似查找的方式確定是否存在該數(shù)據(jù)，然后嘗試刪除。

每次刪除，其實(shí)是將節(jié)點(diǎn)的path屬性-1。當(dāng)path屬性==0時(shí)，從上級(jí)節(jié)點(diǎn)的nexts列表中remove掉該節(jié)點(diǎn)即可return結(jié)束。

//刪除
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..<strs.count {
        if node.nexts[strs[i]] == nil {
            return
        }
        
        node = node.nexts[strs[i]]!
        nodes.append(node)  //將查詢到的節(jié)點(diǎn)放入數(shù)組備用
    }
    
    //如果最后一個(gè)節(jié)點(diǎn)不是end，說明不存在該字符串
    if node.end == true{
        
        //遍歷nodes數(shù)組，當(dāng)某個(gè)節(jié)點(diǎn)path==1說明可以直接刪除該節(jié)點(diǎn)了
        for i in 1..<nodes.count { //從1開始，0是root節(jié)點(diǎn)
            if nodes[i].path == 1 {
                nodes[i-1].nexts.removeValue(forKey: strs[i-1])
                return
            }
            nodes[i].path -= 1
        }
    }
}

前綴樹的應(yīng)用

1. 字符串的快速檢索
   前綴樹的查詢時(shí)間復(fù)雜度是O(L)，L是字符串的長度。所以效率還是比較高的。字典樹的效率比hash表高。
2. 字符串排序
   多叉樹本身已經(jīng)是有序的，只要按照每層都先遍歷低位節(jié)點(diǎn)的方式即可。

后綴樹

相對(duì)于前綴樹來說，后綴樹并不是針對(duì)大量字符串的，而是針對(duì)一個(gè)或幾個(gè)字符串來解決問題。比如字符串的回文子串，兩個(gè)字符串的最長公共子串等等。

比如blanana這個(gè)單詞，在后綴樹的結(jié)構(gòu)中將以如下結(jié)構(gòu)展現(xiàn)(為了方便看到后綴，我沒有合并相同的前綴)

image

后綴樹的應(yīng)用

1. 查找字符串an是否在banana中
   如上圖所致，a+n的節(jié)點(diǎn)順序已經(jīng)存在于后綴樹中，所以返回true
2. 查找字符串a+n在banana中重復(fù)的次數(shù)。
   如上圖所致，a+n中n節(jié)點(diǎn)的path計(jì)數(shù)為2，所以重復(fù)次數(shù)為2.

前綴樹和后綴樹