数据结构-Trie树（前缀树、字典树）Go语言_trie树和字典树

数据结构-Trie树（前缀树、字典树）Go语言

Trie树简介

Trie树（前缀树）是一个可以快速插入与查询字符串前缀的字典树。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

如图在Trie树插入"apple","appal","app","banana"4个字符串，红色节点表示结尾。

Go语言版本的Trie树我们需要关注结点的定义：

代码实现

208. 实现 Trie (前缀树)

// Trie数（结点）
type Trie struct {
    Next [26]*Trie
    isEnd bool
}

// 构造函数
func Constructor() Trie {
    return Trie{}
}

// 插入
func (this *Trie) Insert(word string)  {
    node := this
    for _,c := range word {
        c -= 'a'
        if node.Next[c] == nil {
            node.Next[c] = &Trie{}
        }
        node = node.Next[c]
    }
    node.isEnd = true
}

// 获取结点
func (this *Trie) SearchNode(str string) *Trie {
    node := this
    for _,c := range str {
        c -= 'a'
        if node.Next[c] == nil {
            return nil
        }
        node = node.Next[c]
    }
    return node
}

// 查询
func (this *Trie) Search(word string) bool {
    node := this.SearchNode(word)
    return node != nil && node.isEnd
}

// 前缀查询
func (this *Trie) StartsWith(prefix string) bool {
    return this.SearchNode(prefix) != nil
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48