数据结构与算法 - Tire Tree

Tire 树又称单词查找树、前缀树，是一种哈希树变种的树形结构。核心思想是空间换时间，利用字符串的公共前缀来提高查询效率，常常被应用字符统计、检索等场景，比如搜索引擎的词频统计和提示等

原理

前缀树的存储原理很简单，即合并字符串相同的字符前缀进行存储。

比如，存储dog、cat、doing三个字符串的树结构：

需要注意：前缀树不是二叉树，而是多叉树。

前缀树的特征：

1. 根结点不存储任何内容。
2. 每个节点只存储 1 个字符。
3. 根节点到任意子节点是为存储的字符串。
4. 写入和查询操作的时间复杂度均为 O(N)。

如何实现

一般可以通过以下两种方式来实现，

1. 单向链表（本文采用方式）
2. 二维数组

• 存储

// 定义根结点
type Tire struct {
	Root *Node
	Size int // 总共存储多少个字符
}

// 定义存储字符的节点
type Node struct {
	Char   string         // 当前节点存储的字符
	Count  int            // 出现过多少次
	IsWord bool           // 是否是完整的单词（字符串结尾）
	Next   map[rune]*Node // 存储下一个字符的节点
}

从结构可以看出，其实前缀树就是把字符串按字符顺序存储。

func (r *Tire) Append(s string) {
	if r.Find(s, true) {
		return
	}
	node := r.Root
	for _, c := range s {
		v, ok := node.Next[c] // 是否存在该字符，如果不存在则进行存储，反之取下一个字符
		if !ok {
			v = &Node{
				Char:   string(c),
				IsWord: false,
				Count:  1,
				Next:   make(map[rune]*Node, 0),
			}
			node.Next[c] = v
			r.Size += 1
		} else {
			v.Count += 1
		}
		node = v
	}
	node.IsWord = true // 最后一个字符把IsWord标记为true
}

• 查找

func (r *Tire) Find(s string, isFullMatch bool) bool {
	node := r.Root
	for _, c := range s {
		v, ok := node.Next[c] // 是否存在该字符，如果不存在则直接返回false，反之继续查找下一个字符
		if !ok {
			return false
		}
		node = v
	}
	return (!isFullMatch && !node.IsWord) || node.IsWord
}

• 删除

删除是前缀树中稍复杂一点的操作，如果字符被其他字符串使用，不能直接删除。

func (r *Tire) Remove(s string) bool {
	if !r.Find(s, true) {
		return false
	}
	node := r.Root
	prev := r.Root
	for i, c := range s {
		node = node.Next[c]
		node.Count -= 1
		if node.Count == 0 {
			r.Size -= (len(s) - i)
			break
		}
		prev = node
	}
	if node.Count == 0 {
		delete(prev.Next, rune(node.Char[0]))
	} else {
		node.IsWord = false
	}
	return true
}

最后

附上完整代码：tire