字典树及GO实现_实现中文文本搜索的最佳数据结构:trie字典树及其在go语言中的应用

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的3个基本性质：

1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。

具体参考：字典树

type TriNode struct {
    Path int//有多少单词公用该节点
    IsWord bool//有多少单词以这个节点结尾
    Next []*TriNode
}
 
func NewTriNode()*TriNode{
    return &TriNode{
        Next:make([]*TriNode,26),
    }
}
 
func (this *TriNode)Insert(word string){
    if len(word)==0{
        return
    }
    cur:=this
    for i:=range word{
        if cur.Next[int(word[i]-'a')]==nil{
            //new
            cur.Next[int(word[i]-'a')]=NewTriNode()
        }
        cur=cur.Next[int(word[i]-'a')]
    }
    if cur.IsWord==false{
       cur.IsWord=true
       cur.Path++ 
    }
}
//是否包含某单词
func (this *TriNode)Find(word string)bool {
    if len(word)==0{
        return false
    }
    cur:=this
    for i:=range word{
        if cur.Next[int(word[i]-'a')]==nil{
            return false
        }
    }
    return cur.IsWord
}
 
//是否包含preWith前缀的单词
func (this *TriNode)FindPre(preWith string)bool{
    if len(preWith)==0{
        return false
    }
    cur:=this
    for i:=range preWith{
        if cur.Next[int(preWith[i]-'a')]==nil{
            return false
        }
    }
    return true
}

leetcode：删除子文件夹