介紹

Trie樹:又稱為單詞查找樹,是一種樹形結構,可以應用于統計字符串,會在搜索引擎系統中用于對文本的詞頻統計,下圖是一個Trie樹的結構,同時它也是在插入數時的一個順序圖.

流程

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

代碼

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

在這個結構體里面有一個path,它的作用是啥呢？當有經過此字符的時候這個path就加一

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

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

初始化

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

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

插入

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

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

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

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

當當前的字符在數組里面沒有對應的數據的時候創建一個就好,如果有的時候只要將當前數組的下標交給臨時變量tempNode就好,所經過字符的path加1,將最后一個字符所對應的end加1,將其標記為一個此字符是一個單詞的結尾即可.

查找

/*
 *查找數據
*/
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
}

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

統計以XXX開頭的單詞個數

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

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

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

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

/*
 *查找以XX開頭的數據有幾個
*/
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
}

刪除數據

刪除數據的時候同樣也是要遍歷字符串,不過在此之前應該先查找一次這顆樹里面有沒有要刪除的字符串,如果沒有就直接return就好

/*
 * 刪除數據
*/
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是當有字符經過的時候加一,那么在刪除數據的時候只要查找到字符將這個字符串所經過的字符的path減1, 我這里還加了一個else,當path等于1的時候也就是說明當前所要刪除的字符串是最后一個經過此字符的字符串,這里直接將其置空,等系統回收就好了