Trie树

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

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

字典树的性质

根节点(Root)不包含字符,除根节点外的每一个节点都仅包含一个字符;

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

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

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

使用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("湖北"))
}

有疑问加站长微信联系(非本文作者)

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传