Trie 前缀树

基础与数据结构

说明

按字符逐层共享前缀；插入和查询耗时与单词长度成正比。

分析

从根到节点的路径对应一个字符串前缀，相同前缀只存储一次。Insert 缺少边时创建新节点，Has 逐字符跟随边并检查结束标记。

只插入gopher时，go的路径存在却不是词尾，因此Has(go)为false。插入go只需给已有o节点设结束标记。rune表示Unicode码点，不自动完成大小写折叠或Unicode规范化。

查看图表代码

适用前提与边界

它适合前缀检索；字符集很大时，节点中的映射和指针会带来明显内存开销。 空字符串会把根标记为词尾；示例按rune比较，不进行大小写或Unicode规范化，业务需先统一文本规则。

示例输入与调用

trie := new(Trie)
	trie.Insert("gopher")
	fmt.Println(trie.Has("gopher"), trie.Has("go"))

运行输出

true false

完整 Go 示例

package main

import "fmt"

type Trie struct {
	next map[rune]*Trie
	end  bool
}

func (t *Trie) Insert(s string) {
	for _, r := range s {
		if t.next == nil {
			t.next = map[rune]*Trie{}
		}
		if t.next[r] == nil {
			t.next[r] = &Trie{}
		}
		t = t.next[r]
	}
	t.end = true
}
func (t *Trie) Has(s string) bool {
	for _, r := range s {
		t = t.next[r]
		if t == nil {
			return false
		}
	}
	return t.end
}

func main() {
	trie := new(Trie)
	trie.Insert("gopher")
	fmt.Println(trie.Has("gopher"), trie.Has("go"))
}