介紹

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

流程

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

代碼

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

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

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

children是保存的啥呢？這個里面當然是保存的子節(jié)點啦，不用多說了叭~~~

初始化

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

初始化根節(jié)點,上面說過根節(jié)點里面是不用保存數(shù)據(jù)的,這個我就把里面的參數(shù)初始化成0,當然也可以不用初始化里面的參數(shù),children這里就沒有創(chuàng)建出來,因為下面我就要開始插入的操作了

插入

/*
 * 插入數(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++
}

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

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

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

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

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

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

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

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

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

/*
 *查找以XX開頭的數(shù)據(jù)有幾個
*/
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ù)的時候同樣也是要遍歷字符串,不過在此之前應(yīng)該先查找一次這顆樹里面有沒有要刪除的字符串,如果沒有就直接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是當有字符經(jīng)過的時候加一,那么在刪除數(shù)據(jù)的時候只要查找到字符將這個字符串所經(jīng)過的字符的path減1, 我這里還加了一個else,當path等于1的時候也就是說明當前所要刪除的字符串是最后一個經(jīng)過此字符的字符串,這里直接將其置空,等系統(tǒng)回收就好了

到此這篇關(guān)于go語言數(shù)據(jù)結(jié)構(gòu)之前綴樹Trie的文章就介紹到這了,更多相關(guān)go 前綴樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論