字典树 - 元素码农

发布时间: 2025-03-21 19:53

↑

# 字典树

字典树（Trie树）是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这种数据结构有时也被称为前缀树，因为它可以快速找到具有共同前缀的全部键值。

## 基本概念

### 结构特点

字典树具有以下特点：
- 根节点不包含字符
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
- 通常用于存储和搜索字符串集合

### 节点结构

每个节点通常包含：
- 子节点指针数组或映射
- 是否为字符串结尾的标记
- 可能包含附加信息（如频次统计）

## 基本实现

### 数据结构定义

```go
// Trie节点结构
type TrieNode struct {
    children map[rune]*TrieNode // 子节点映射
    isEnd    bool               // 是否是单词结尾
    count    int                // 经过该节点的单词数量
}

// Trie树结构
type Trie struct {
    root *TrieNode
}

// 创建新的字典树
func NewTrie() *Trie {
    return &Trie{
        root: &TrieNode{
            children: make(map[rune]*TrieNode),
        },
    }
}
```

### 基本操作

```go
// 插入单词
func (t *Trie) Insert(word string) {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{
                children: make(map[rune]*TrieNode),
            }
        }
        node = node.children[ch]
        node.count++
    }
    node.isEnd = true
}

// 搜索单词
func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}

// 查找前缀
func (t *Trie) StartsWith(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}

// 删除单词
func (t *Trie) Delete(word string) bool {
    return t.delete(t.root, word, 0)
}

func (t *Trie) delete(node *TrieNode, word string, depth int) bool {
    if depth == len(word) {
        if !node.isEnd {
            return false
        }
        node.isEnd = false
        return len(node.children) == 0
    }
    
    ch := rune(word[depth])
    if node.children[ch] == nil {
        return false
    }
    
    shouldDeleteChild := t.delete(node.children[ch], word, depth+1)
    
    if shouldDeleteChild {
        delete(node.children, ch)
        return len(node.children) == 0
    }
    
    return false
}
```

## 高级功能

### 前缀统计

```go
// 统计指定前缀的单词数量
func (t *Trie) CountPrefix(prefix string) int {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return 0
        }
        node = node.children[ch]
    }
    return node.count
}

// 获取所有以指定前缀开头的单词
func (t *Trie) GetWordsWithPrefix(prefix string) []string {
    var result []string
    node := t.root
    
    // 找到前缀的最后一个节点
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return result
        }
        node = node.children[ch]
    }
    
    // 从该节点开始深度优先搜索
    t.dfs(node, prefix, &result)
    return result
}

func (t *Trie) dfs(node *TrieNode, prefix string, result *[]string) {
    if node.isEnd {
        *result = append(*result, prefix)
    }
    
    for ch, child := range node.children {
        t.dfs(child, prefix+string(ch), result)
    }
}
```

### 通配符匹配

```go
// 支持通配符'.'的搜索
func (t *Trie) SearchPattern(pattern string) bool {
    return t.searchPattern(t.root, pattern, 0)
}

func (t *Trie) searchPattern(node *TrieNode, pattern string, depth int) bool {
    if depth == len(pattern) {
        return node.isEnd
    }
    
    if pattern[depth] == '.' {
        for _, child := range node.children {
            if t.searchPattern(child, pattern, depth+1) {
                return true
            }
        }
        return false
    }
    
    ch := rune(pattern[depth])
    if node.children[ch] == nil {
        return false
    }
    return t.searchPattern(node.children[ch], pattern, depth+1)
}
```

## 应用场景

### 自动补全

1. 搜索建议
   - 输入提示
   - 拼写检查
   - 关键词推荐

2. IDE自动补全
   - 代码提示
   - API补全
   - 变量名补全

### 字符串检索

1. 敏感词过滤
   - 文本审核
   - 内容过滤
   - 关键词屏蔽

2. IP地址路由
   - 最长前缀匹配
   - 路由表查找
   - 网络包转发

### 文本分析

1. 单词统计
   - 词频分析
   - 关键词提取
   - 文本分类

2. 模式匹配
   - 字符串匹配
   - 正则表达式
   - 通配符匹配

## 性能分析

### 时间复杂度

1. 基本操作
   - 插入：O(m)，m为字符串长度
   - 查找：O(m)
   - 删除：O(m)
   - 前缀查找：O(p)，p为前缀长度

2. 空间复杂度
   - 最坏情况：O(ALPHABET_SIZE * m * n)
   - n为字符串数量
   - m为平均字符串长度
   - ALPHABET_SIZE为字符集大小

### 优化方向

1. 内存优化
   - 压缩前缀
   - 节点合并
   - 位图优化

2. 查询优化
   - 缓存热点数据
   - 并行查询
   - 批量操作

## 实践建议

### 实现技巧

1. 数据结构选择
   - 数组vs哈希表
   - 内存vs速度
   - 可扩展性考虑

2. 边界处理
   - 空字符串
   - 特殊字符
   - 大小写敏感

### 使用建议

1. 应用场景
   - 适合前缀匹配
   - 不适合后缀匹配
   - 考虑数据规模

2. 性能考虑
   - 内存使用
   - 并发访问
   - 更新频率

## 总结

1. 优点
   - 高效的前缀匹配
   - 空间利用率高
   - 支持增量更新

2. 缺点
   - 内存消耗较大
   - 不适合精确匹配
   - 不支持后缀查询

3. 使用场景
   - 需要前缀匹配
   - 数据量适中
   - 查询频繁