字首樹 - 一種好玩的樹型資料結構

資料結構 · 發表 2018-10-13 16:47:17

摘要：上篇內容有在介紹 Gin 的路由實現時提到了字首樹，這次我們稍微深入探究一下字首樹的實現。 MapSum 問題 LeetCode 上有一道程式設計題是這樣的實現一個MapSum 類裡的兩個方法，insert 和 sum 。 ...

上篇內容有在介紹 Gin 的路由實現時提到了字首樹，這次我們稍微深入探究一下字首樹的實現。

MapSum 問題

LeetCode 上有一道程式設計題是這樣的

實現一個MapSum 類裡的兩個方法，insert 和 sum 。

對於方法 insert ，你將得到一對（字串，整數）的鍵值對。字串表示鍵，整數表示值。如果鍵已經存在，那麼原來的鍵值對將被替代成新的鍵值對。

對於方法 sum ，你將得到一個表示字首的字串，你需要返回所有以該字首開頭的鍵的值的總和。

示例 1:

輸入: insert("apple", 3), 輸出: Null
輸入: sum("ap"), 輸出: 3
輸入: insert("app", 2), 輸出: Null
輸入: sum("ap"), 輸出: 5

字首樹

根據題意，我們定義的MapSum 的資料結構為：

type MapSum struct {
charbyte
childrenmap[byte]*MapSum
valint
}

/** Initialize your data structure here. */
func Constructor() MapSum { 
}

func (this *MapSum) Insert(key string, val int){
}

func (this *MapSum) Sum(prefix string) int {
}

假設輸入資料為：

m := Constructor()
m.Insert("inter", 1)
m.Insert("inner", 2)
m.Insert("in", 2)
m.Insert("if", 4)
m.Insert("game", 8)

則構造的字首樹應該是：

字首樹特性：

根節點不包含字元，除根節點外的每一個子節點都包含一個字元
從根節點到某一節點的路徑上的字元連線起來，就是該節點對應的字串。
每個節點的所有子節點包含的字元都不相同。

Insert 函式

Insert 函式的簽名：

func (this *MapSum) Insert(key string, val int)

我們把this 當做父節點，當插入的key 長度為 1 時，則直接說明key 對應的節點應該是this 的孩子節點。

if len(key) == 1 {
for i, m := range this.children {
// c 存在與孩子節點
// 直接更新
if i == c {
m.val = val
return
}
}

// 未找到對應孩子
// 直接生成新孩子
this.children[c] = &MapSum{
char: c,
val: val,
children: make(map[byte]*MapSum),
}

return
}

當插入的key 長度大於 1，則尋找key[0] 對應的子樹，如果不存在，則插入新孩子節點；設定this = this.children[key[0]] 繼續迭代;

c := key[0]
for i, m := range this.children {
if i == c {
key = key[1:]
this = m
continue walk
}
}

// 未找到節點
this.children[c] = &MapSum{
char: c,
val: 0,
children: make(map[byte]*MapSum),
}

this = this.children[c]
key = key[1:]
continue walk

Sum 函式

Sum 函式簽名：

func (this *MapSum) Sum(prefix string) int

Sum 函式的基本思想為：先找到字首prefix 對應的節點，然後統計以該節點為樹根的的子樹的val 和。

// 先找到符合字首的節點
// 然後統計和
for prefix != "" {
c := prefix[0]
var ok bool
if this, ok = this.children[c]; ok {
prefix = prefix[1:]
continue
} else{
// prefix 不存在
return 0
}
}
return this.sumNode()

sumNode 函式統計了子樹的val 和，使用遞迴遍歷樹：

s := this.val
for _, child := range this.children{
s += child.sumNode()
}
return s

以上是一種標準的字首樹的做法。當字串公用的節點比較少的時候，對於每個字元都要建立單獨的節點，有點浪費空間。有一種壓縮字首樹的演算法，在處理字首樹問題的時候能夠使用更少的節點。

壓縮字首樹

對與上面的例子來說，壓縮字首樹是這樣的結果：

對於該例子來說，明顯少了很多節點。另外，我們的 MapSum 結構體也稍微有了變化：

type MapSum struct {
// 之前的 charbyte 變成了 keystring
keystring
childrenmap[byte]*MapSum
valint
}

Insert

壓縮字首樹與字首樹的實現不同點在於節點的分裂。比如，當樹中已經存在"inner", "inter" 的情況加，再加入"info" 時，原"in" 節點需要分裂成"i" -> "n" 兩個節點，如圖：

在Insert 時，需要判斷當前插入字串key 與節點字串this.key 的最長公共字首長度n ：

minLen := min(len(key), len(this.key))
// 找出最長公共字首長度 n
n := 0
for n < minLen && key[n] == this.key[n] {
n ++
}

然後拿n 與len(this.key) 比較，如果比this.key 長度短，則this.key 需要分裂，否則，不需要分裂。

this 節點分裂邏輯：

// 最前公共字首 n < len(this.key)
// 則該節點需要分裂
child := &MapSum{
val: this.val,
key: this.key[n:],
children: this.children,
}

// 更新當前節點
this.key = this.key[:n]
this.val = 0
this.children = make(map[byte]*MapSum)
this.children[child.key[0]] = child

然後再判斷n 與len(key) ，如果n == len(key) ，則說明key 對應該節點。直接更新val

if n == len(key) {
this.val = val
return
}

n < len(key) 時，如果有符合條件子樹，則繼續迭代，否則直接插入孩子節點：

key = key[n:]
c := key[0]

// 如果剩餘 子key 的第一個字元存在與 children
// 則繼續向下遍歷樹
if a, ok := this.children[c]; ok {
this = a
continue walk
} else{
// 否則，新建節點
this.children[c] = &MapSum{
key: key,
val: val,
children: make(map[byte]*MapSum),
}
return
}

以上是壓縮字首樹的做法。

演算法優化

上述MapSum 的children 使用的是map ，但是map 一般佔用記憶體較大。可以使用節點陣列children + 節點字首陣列indices 的方式維護子節點，其中indices 與children 一一對應。

此時的結構體應該是這樣的：

type MapSum struct {
keystring
indices[]byte
children[]*MapSum
valint
}

查詢子樹時，需要拿key[:n][0] 與indices 中的字元比較，找到下標後繼續迭代子樹；未找到時插入子樹即可。

以上。

Y_xx