Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。小写英文字母或大写英文字母的字典数是一个26叉树。Trie树的根结点是不保存数据的，所有的数据都保存在它的孩子节点中。有字符串go, golang, php, python, perl，它这棵Trie树可如下图所示构造：
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
2 基本性质- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
(1) 从根结点开始一次搜索；
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
其他操作类似处理.
package main
import (
"fmt"
)
const MAXCAP = 26 // a-z
type Trie struct {
next map[rune]*Trie
isWord bool
}
/** Initialize your data structure here. */
func Constructor() Trie {
root := new(Trie)
root.next = make(map[rune]*Trie, MAXCAP)
root.isWord = false
return *root
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
for _, v := range word {
if this.next[v] == nil {
node := new(Trie)
//子节点数量为26
node.next = make(map[rune]*Trie, MAXCAP)
//初始化节点单词标志为假
node.isWord = false
this.next[v] = node
}
this = this.next[v]
}
this.isWord = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
for _, v := range word {
if this.next[v] == nil {
return false
}
this = this.next[v]
}
return this.isWord
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
for _, v := range prefix {
if this.next[v] == nil {
return false
}
this = this.next[v]
}
return true
}
func main(){
t := Constructor()
t.Insert("Hello")
fmt.Print(t.Search("Hello"),"\n")
fmt.Print(t.Search("Hallo"),"\n")
}
输出：
