Trie树

helloGlobal · · 1878 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

本文来自:简书

感谢作者:helloGlobal

查看原文:Trie树

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

1878 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传