字典树
定义
字典树，顾名思义，是关于“字典”的一棵树。即：它是对于字典的一种存储方式（所以是一种数据结构而不是算法）。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径，路径中每条边的字母连起来就是一个单词。
结构实例
字典树的功能
根据字典树的概念，我们可以发现：字典树的本质是把很多字符串拆成单个字符的形式，以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质，我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下：
- 1、维护字符串集合（即字典）。
- 2、向字符串集合中插入字符串（即建树）。
- 3、查询字符串集合中是否有某个字符串（即查询）。
- 4、统计字符串在集合中出现的个数（即统计）。
- 5、将字符串集合按字典序排序（即字典序排序）。
- 6、求集合内两个字符串的LCP（Longest Common Prefix，最长公共前缀）（即求最长公共前缀）。
我们可以发现，以上列举出的功能都是建立在“字符串集合”的基础上的。再一次强调，字典树是“字典”的树，一切功能都是“字典”的功能。这也为我们使用字典树的时候提供了一个准则：看到一大堆字符串同时出现，就往哈希和Trie树那边想一下。
基于字典树实现的域名匹配
有一个需求，给出一个域名名单，当输入一个新域名之后判断其是否存在域名名单中，要求支持通配符匹配
代码实现
根据字典树结构，使用go语言实现如下：
package main
import (
"fmt"
"github.com/gookit/goutil/arrutil"
"github.com/gookit/goutil/maputil"
"strings"
)
type TrieNode struct {
children map[string]*TrieNode
isEnd bool
}
type Trie struct {
root *TrieNode
}
func initTrie() *Trie {
return &Trie{root: &TrieNode{children: make(map[string]*TrieNode)}}
}
func (t *Trie) insertDomain(domain string) {
parts := strings.Split(domain, ".")
arrutil.Reverse(parts)
node := t.root
for _, part := range parts {
if node.children[part] == nil {
node.children[part] = &TrieNode{children: make(map[string]*TrieNode)}
}
node = node.children[part]
}
node.isEnd = true
}
func (t *Trie) searchDomain(domain string) bool {
parts := strings.Split(domain, ".")
arrutil.Reverse(parts)
node := t.root
for _, part := range parts {
isNil := node.children[part] == nil
if isNil && !maputil.HasKey(node.children, "*") {
return false
}
if isNil {
node = node.children["*"]
} else {
node = node.children[part]
}
}
return node != nil && node.isEnd
}
func main() {
trie := initTrie()
// 示例域名
domains := []string{"wx.*.com", "example.com", "test.org"}
// 插入域名到 Trie 中
for _, domain := range domains {
trie.insertDomain(domain)
}
// 搜索示例
searchDomains := []string{"wx.qq.com", "openai.com", "test.org", "wx.qq1.com"}
// 搜索域名是否存在于 Trie 中
for _, domain := range searchDomains {
if trie.searchDomain(domain) {
fmt.Printf("%s 存在\n", domain)
} else {
fmt.Printf("%s 不存在\n", domain)
}
}
}