介紹

Trie樹:又稱為單詞查找樹,是一種樹形結(jié)構(gòu),可以應(yīng)用于統(tǒng)計(jì)字符串,會(huì)在搜索引擎系統(tǒng)中用于對文本的詞頻統(tǒng)計(jì),下圖是一個(gè)Trie樹的結(jié)構(gòu),同時(shí)它也是在插入數(shù)時(shí)的一個(gè)順序圖.

流程

• 首先應(yīng)該先創(chuàng)建一個(gè)結(jié)構(gòu)體，里面保存的是每一個(gè)節(jié)點(diǎn)的信息
• 初始化根節(jié)點(diǎn),根節(jié)點(diǎn)應(yīng)該初始化啥？啥也不用初始化，給個(gè)空就好看上圖
• 插入：串轉(zhuǎn)字符數(shù)組；遍歷數(shù)組，如果下一個(gè)節(jié)點(diǎn)為空，創(chuàng)建，則繼續(xù)遍歷
• 查找：串轉(zhuǎn)字符數(shù)組，遍歷如何所有字符都在樹里面存在，并則最后一個(gè)字符Node中的end不為零，就視為存在
• 刪除: 字符串轉(zhuǎn)數(shù)組，遍歷數(shù)組，在樹上找到對應(yīng)的字符,path-1

代碼

type Node struct {
	path     int
	end      int
	children [26]*Node
}

在這個(gè)結(jié)構(gòu)體里面有一個(gè)path,它的作用是啥呢？當(dāng)有經(jīng)過此字符的時(shí)候這個(gè)path就加一

end又是干啥的呢？當(dāng)一個(gè)單詞的詞尾是這個(gè)字符的時(shí)候end這個(gè)值就加一，就代表著這個(gè)字符做為一個(gè)單詞的結(jié)尾

children是保存的啥呢？這個(gè)里面當(dāng)然是保存的子節(jié)點(diǎn)啦，不用多說了叭~~~

初始化

func main() {
	list := &Node{path: 0, end: 0}
}

初始化根節(jié)點(diǎn),上面說過根節(jié)點(diǎn)里面是不用保存數(shù)據(jù)的,這個(gè)我就把里面的參數(shù)初始化成0,當(dāng)然也可以不用初始化里面的參數(shù),children這里就沒有創(chuàng)建出來,因?yàn)橄旅嫖揖鸵_始插入的操作了

插入

/*
 * 插入數(shù)據(jù)
*/
func insertTrie(str string, root *Node) {
	if len(str) == 0 {
		return
	}
	tempNode := root
	for _, value := range str {
		if tempNode.children[value-'a'] == nil {
			tempNode.children[value-'a'] = &Node{path: 0, end: 0}
		}
		tempNode = tempNode.children[value-'a']
		tempNode.path++
	}
	tempNode.end++
}

在插入之前先說一點(diǎn):在傳入的參數(shù)中,str我傳入前我將其轉(zhuǎn)換成了小寫的,當(dāng)然也可以轉(zhuǎn)換成大寫或者是大小寫都有的

插入之前先對字符串進(jìn)行了一個(gè)判空的處理,如果為空就return了,在整個(gè)過程中,對字符串進(jìn)行了遍歷,像我在流程中那樣說的將字符串轉(zhuǎn)成字符數(shù)組,是應(yīng)該這樣操作,但是我發(fā)現(xiàn)在golang中可以直接對一個(gè)字符串進(jìn)行了遍歷,或許將語言換成了Java就需要將其轉(zhuǎn)成字符數(shù)組了

for循環(huán)里面if判斷時(shí)為什么數(shù)組的下標(biāo)要用value-'a'這個(gè)東西來表示?可以想像一下,一個(gè)節(jié)點(diǎn)的children里面有26個(gè)子元素,比如這里的vlaue是b,那么就相當(dāng)于是b-a,就是b的ASCII碼減去a的ASCII碼,這個(gè)就得到的是1

當(dāng)當(dāng)前的字符在數(shù)組里面沒有對應(yīng)的數(shù)據(jù)的時(shí)候創(chuàng)建一個(gè)就好,如果有的時(shí)候只要將當(dāng)前數(shù)組的下標(biāo)交給臨時(shí)變量tempNode就好,所經(jīng)過字符的path加1,將最后一個(gè)字符所對應(yīng)的end加1,將其標(biāo)記為一個(gè)此字符是一個(gè)單詞的結(jié)尾即可.

查找

/*
 *查找數(shù)據(jù)
*/
func searchStr(str string,root *Node) bool {
	if len(str) == 0{
		return false
	}
	tempNode := root
	for _,value := range str{

		if tempNode.children[value - 'a'] == nil{
			return false
		}
		tempNode = tempNode.children[value - 'a']
	}
	if tempNode.end != 0{
		return true
	}
	return false
}

同樣,在查找數(shù)據(jù)的時(shí)候也是將需要查找的字符串和前綴樹的ROOT傳入,字符串的判空處理也是必做的,這個(gè)里面的tempNode可以有也可以沒有,我寫tempNode可以是說是我的一個(gè)編碼的習(xí)慣,同樣,在查找單詞的時(shí)候也是要遍歷這個(gè)字符串(在插入的時(shí)候我就已經(jīng)解釋過了我這里為啥和流程中寫的不一樣,沒有把字符串轉(zhuǎn)成字符數(shù)組),在for循環(huán)里面第一個(gè)if如果第一個(gè)字符沒有在前綴樹中找到,那么就視為所要查找的字符串沒有出現(xiàn)在這個(gè)前綴樹里面,則將當(dāng)前的字符節(jié)點(diǎn)交給臨時(shí)變量tempNode,當(dāng)整個(gè)循環(huán)遍歷完成之后,也就說明我要查找的字符串中的每一個(gè)字符都在這顆前綴樹里面并連續(xù)著.這個(gè)時(shí)候如果最后一個(gè)單詞的end屬性為大于0的一個(gè)數(shù),那么這個(gè)要查找的字符串就一定在這顆前綴樹里面,返回true

統(tǒng)計(jì)以XXX開頭的單詞個(gè)數(shù)

這個(gè)前綴樹很強(qiáng)大,上面的解釋也說到過,可以對文本的統(tǒng)計(jì)

strArgs:=[]string{"qQYgMU","FFpdCl","nyyJmh","XJCebb","OrCiHb","xvDdzZ","nyCebF","hi","hello","nyyJmn"}

在前綴樹里面插入了這個(gè)數(shù)組里面的字符串,我現(xiàn)在要統(tǒng)計(jì)以n開頭的單詞有幾個(gè)?如何處理呢?

這里就用到了在結(jié)構(gòu)體中定義的Path屬性了,在插入的時(shí)候說過當(dāng)有一個(gè)字符經(jīng)過這個(gè)path就會(huì)加1,所以我只需要找到所要查找前綴的最后一個(gè)單詞拿到了它的path屬性就可以知道以這個(gè)字符串開頭的單詞有幾個(gè)

/*
 *查找以XX開頭的數(shù)據(jù)有幾個(gè)
*/
func searchPrefixCount(str string,root *Node) int{
	if len(str) == 0{
		return -1
	}
	tempNode := root
	for _,value := range str{
		if tempNode.children[value - 'a'] == nil {
			return 0
		}
		tempNode = tempNode.children[value - 'a']
		return tempNode.path
	}
	return -1
}

刪除數(shù)據(jù)

刪除數(shù)據(jù)的時(shí)候同樣也是要遍歷字符串,不過在此之前應(yīng)該先查找一次這顆樹里面有沒有要?jiǎng)h除的字符串,如果沒有就直接return就好

/*
 * 刪除數(shù)據(jù)
*/
func delStr(str string,root *Node) bool {
	if len(str) == 0{
		return false
	}
	if !searchStr(strings.ToLower(str),root) {
		return false
	}
	tempNode := root
	for _,value := range str{
		if tempNode.children[value - 'a'].path > 1 {
			tempNode.children[value - 'a'].path--
			tempNode = tempNode.children[value - 'a']
		}else{
			tempNode.children[value - 'a'] = nil
			return true
		}
	}
	return false
}

path是當(dāng)有字符經(jīng)過的時(shí)候加一,那么在刪除數(shù)據(jù)的時(shí)候只要查找到字符將這個(gè)字符串所經(jīng)過的字符的path減1, 我這里還加了一個(gè)else,當(dāng)path等于1的時(shí)候也就是說明當(dāng)前所要?jiǎng)h除的字符串是最后一個(gè)經(jīng)過此字符的字符串,這里直接將其置空,等系統(tǒng)回收就好了