Trie 树——Golang实现_golang trie

Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

现在，我们先来看下，Trie 树到底长什么样子。

我举个简单的例子来说明一下。我们有 6 个字符串，它们分别是：how，hi，her，hello，so，see。我们希望在里面多次查找某个字符串是否存在。如果每次查找，都是拿要查找的字符串跟这 6 个字符串依次进行字符串匹配，那效率就比较低，有没有更高效的方法呢？

这个时候，我们就可以先对这 6 个字符串做一下预处理，组织成 Trie 树的结构，之后每次查找，都是在 Trie 树中进行匹配查找。Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。最后构造出来的就是下面这个图中的样子。

其中，根节点不包含任何信息。每个节点表示一个字符串中的字符，从根节点到红色节点的一条路径表示一个字符串（注意：红色节点并不都是叶子节点）。

 为了让你更容易理解 Trie 树是怎么构造出来的，我画了一个 Trie 树构造的分解过程。构造过程的每一步，都相当于往 Trie 树中插入一个字符串。当所有字符串都插入完成之后，Trie 树就构造好了。

 当我们在 Trie 树中查找一个字符串的时候，比如查找字符串“her”，那我们将要查找的字符串分割成单个的字符 h，e，r，然后从 Trie 树的根节点开始匹配。如图所示，绿色的路径就是在 Trie 树中匹配的路径。

 如果我们要查找的是字符串“he”呢？我们还用上面同样的方法，从根节点开始，沿着某条路径来匹配，如图所示，绿色的路径，是字符串“he”匹配的路径。但是，路径的最后一个节点“e”并不是红色的。也就是说，“he”是某个字符串的前缀子串，但并不能完全匹配任何字符串。

Golang实现

1、基于数组的代码实现

以下代码用于判断a-z小写的单词是否存在

package main
 
import "fmt"
 
const Size = 26 //数组大小为26
 
type TireNode struct {
	Data   uint8
	IsWord bool
	Next   []*TireNode
}
type TireHead struct {
	Len  int
	Next []*TireNode
}
 
func NewTire() *TireHead {
	//next := make([]*TireNode, Size, Size)
	head := &TireHead{
		Len:  0,
		Next: nil,
	}
	return head
}
func (t *TireHead) Insert(str string) {
	//index := str[0] - 'a'
	if t.Next == nil {
		t.Next = make([]*TireNode, Size, Size)
	}
	cur := t.Next
	index := uint8(0)
	for i := 0; i < len(str); i++ {
		index = str[i] - 'a'   //只能比较 a-z的Size个字符（26个）
		if cur[index] == nil { //TODO 注意：如果节点为空，需要创建
			newNode := &TireNode{
				Data:   str[i],
				IsWord: false,
				Next:   make([]*TireNode, Size, Size),
			}
			cur[index] = newNode
		} else {
			cur[index].Data = str[i] //todo 如果节点已经有了，就直接使用可以了
		}
		if i == len(str)-1 {
			cur[index].IsWord = true //todo 最后一个字符对应的 标志位需要设置为true，代表是一个完整的字符
		}
		cur = cur[index].Next
	}
}
func (t *TireHead) isExist(str string) bool {
	if t.Next == nil {
		return false
	}
	cur := t.Next
	index := uint8(0)
	for i := 0; i < len(str); i++ {
		index = str[i] - 'a'
		if cur[index] == nil {
			//todo 特别要注意条件的判断：如果找到对应的内容为nil了，就直接返回。
			// 不然从nil对应的变量中取数据，包报错
			return false
		}
		if cur[index].Data != str[i] {
			return false
		}
		if i == len(str)-1 && cur[index].IsWord == true {
			return true
		}
		cur = cur[index].Next
		if cur == nil {
			return false
		}
	}
	return false
}
func main() {
	tire := NewTire()
	//tire.Insert("ab")
	//tire.Insert("ok")
	tire.Insert("he")
	tire.Insert("ok")
	tire.Insert("hello")
	fmt.Println("he:",tire.isExist("a"))
	fmt.Println("ok：",tire.isExist("ok"))
	fmt.Println("hel:",tire.isExist("hel"))
}

2、基于hashmap的代码实现

package main
 
import (
	"fmt"
)
 
//数据节点；存储数据：数据值、是否结束标志位、下一个节点指针
type TNode struct {
	Data   byte
	IsWord bool
	Next   map[byte]*TNode
}
 
//根节点，存储数据为：1、字符串个数；2、数据节点map序列
type TNRoot struct {
	Len  int
	Node map[byte]*TNode
}
 
func CreateTire() TNRoot {
	tn := make(map[byte]*TNode)
	//创建节点的时候，需要将node赋值
	tRoot := TNRoot{
		Len:  0,
		Node: tn, //todo 技巧：需要赋值，不然后续没有办法操作
	}
	return tRoot
}
func (tn *TNRoot) insert(str string) {
	cur := tn.Node
	for i := 0; i < len(str); i++ {
		if cur[str[i]] == nil {
			newNode := &TNode{
				Data:   str[i],
				IsWord: false,
				Next:   make(map[byte]*TNode), //TODO 技巧：下一个节点需要实例化，不然是空，后续无法操作。
			}
			cur[str[i]] = newNode
		}
		if i == len(str)-1 {
			cur[str[i]].IsWord = true
		}
		cur = cur[str[i]].Next
	}
	tn.Len++
 
}
func (tn *TNRoot) isExist(str string) bool {
	if tn.Node == nil {
		return false
	}
	cur := tn.Node
	for i := 0; i < len(str); i++ {
		if cur[str[i]] == nil { //如果比较的数据不存在，直接返回
			return false
		}
		if cur[str[i]].Data != str[i] {
			return false
		}
		if i == len(str)-1 { //判断最后一个比较的字符是否是结束标志位
			if cur[str[i]].IsWord == true {
				return true
			}
		}
		cur = cur[str[i]].Next
	}
	return false
}
func main() {
	tire := CreateTire()
	tire.insert("hello")
	tire.insert("ok")
	tire.insert("he")
	fmt.Println(tire.isExist("ok"))
	fmt.Println(tire.isExist("he"))
	fmt.Println(tire.isExist("hel"))
	fmt.Println("tire树的字符串数量：", tire.Len)
}