Trie树

Trie树，又称字典树，前缀树，是一种很常用的树结构，它被广泛用于各个方面，比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等。

字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的共同前缀（Common Prefix）作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 O(m)，m 为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用

字典树的性质

根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；

从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；

任意节点的所有子节点所包含的字符都不相同；

下图就是一个字典树的构造

image.png

使用golang 定义trie 树节点，定义一个支持汉字的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("湖北"))
}