Trie樹，又稱字典樹，前綴樹，是一種很常用的樹結(jié)構(gòu)，它被廣泛用于各個(gè)方面，比如字符串檢索、中文分詞、求字符串最長(zhǎng)公共前綴和字典排序等等。

字典樹設(shè)計(jì)的核心思想是空間換時(shí)間，所以數(shù)據(jù)結(jié)構(gòu)本身比較消耗空間。但它利用了字符串的共同前綴（Common Prefix）作為存儲(chǔ)依據(jù)，以此來(lái)節(jié)省存儲(chǔ)空間，并加速搜索時(shí)間。Trie 的字符串搜索時(shí)間復(fù)雜度為 O(m)，m 為最長(zhǎng)的字符串的長(zhǎng)度，其查詢性能與集合中的字符串的數(shù)量無(wú)關(guān)。其在搜索字符串時(shí)表現(xiàn)出的高效，使得特別適用于構(gòu)建文本搜索和詞頻統(tǒng)計(jì)等應(yīng)用

字典樹的性質(zhì)

根節(jié)點(diǎn)（Root）不包含字符，除根節(jié)點(diǎn)外的每一個(gè)節(jié)點(diǎn)都僅包含一個(gè)字符；

從根節(jié)點(diǎn)到某一節(jié)點(diǎn)路徑上所經(jīng)過(guò)的字符連接起來(lái)，即為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；

任意節(jié)點(diǎn)的所有子節(jié)點(diǎn)所包含的字符都不相同；

下圖就是一個(gè)字典樹的構(gòu)造

image.png

使用golang 定義trie 樹節(jié)點(diǎn)，定義一個(gè)支持漢字的Trie樹

type runeTireNode struct {
    child map[rune]*runeTireNode
    Vaule interface{}
}
type RuneTire struct {
    root *runeTireNode
}

func NewRuneTire() *RuneTire  {
    return &RuneTire{root:&runeTireNode{child:make(map[rune]*runeTireNode)}}
}
func (r *RuneTire) Insert(key string,value interface{})  {
    node := r.root
    for _,c := range key{
        if n,ok :=node.child[c];!ok{
            newNode := &runeTireNode{child:make(map[rune]*runeTireNode)}
            node.child[c] = newNode
            node = newNode
        }else{
            node = n
        }
    }
    node.Vaule = value
}

func (r *RuneTire) Get(key string) interface{}  {
    node := r.root
    for _,c := range key{
        if n,ok := node.child[c];!ok{
            return nil
        }else{
            node = n
        }
    }
    return node.Vaule
}
func main() {
    r := NewRuneTire()
    r.Insert("河北","河北")
    r.Insert("湖南","湖南")
    r.Insert("湖北","湖北省")
    fmt.Println(r.Get("湖北"))
}