一篇學(xué)好如何實現(xiàn) Trie
本文轉(zhuǎn)載自微信公眾號「我好困啊」,作者mengxin。轉(zhuǎn)載本文請聯(lián)系我好困啊公眾號。
Trie又稱為字典樹,主要用于單詞的查找得名。如將一個單詞 Hello存放在字典樹中的數(shù)據(jù)結(jié)構(gòu)為:
當(dāng)再次加入help時,此時的字典樹為:
當(dāng)添加hero時,此時的字典樹為:
可以看到樹以每個單詞的字符為一個節(jié)點,直到字符添加完畢后設(shè)置上flag,標(biāo)記當(dāng)前節(jié)點結(jié)束為一個單詞(即從根節(jié)點到當(dāng)前節(jié)點為一個單詞)。
當(dāng)有新的單詞進(jìn)來時,只需要添加到樹中即可,查找時,從根節(jié)點出發(fā),遍歷整棵樹(其實總是遍歷樹的某個分支)。如果其中一個字符不在樹中,則說明查找失敗,否則所有的word按每個字符的順序都能查找到,最后判斷結(jié)束節(jié)點是否為一個單詞,是,則查找成功。
代碼實現(xiàn)
- //葉子節(jié)點
- type Node struct {
- isWord bool //是否為一個單詞
- next map[uint8]*Node //葉子節(jié)點對應(yīng)的單個字符及其next指針
- }
- type Trie struct {
- root *Node
- size int64
- }
- func Constructor() Trie {
- return Trie{&Node{
- isWord: false,
- next: make(map[uint8]*Node),
- },0}
- }
- /** 添加單詞到字典中 */
- func (this *Trie) Insert(word string) {
- if word ==""{
- return
- }
- cur := this.root
- for i:= 0;i< len(word);i++ {
- r := word[i]
- if cur.next[r]== nil{
- cur.next[r] = &Node{false, make(map[uint8]*Node)}
- }
- cur = cur.next[r]
- }
- if !cur.isWord {
- cur.isWord = true
- }
- }
- /** 查找單詞 */
- func (this *Trie) Search(word string) bool {
- if word ==""{
- return false
- }
- cur := this.root
- for i:= 0;i< len(word);i++ {
- r := word[i]
- if cur.next[r]== nil{
- return false
- }
- cur = cur.next[r]
- }
- return cur.isWord
- }
- /**查找對應(yīng)前綴 */
- func (this *Trie) StartsWith(prefix string) bool {
- if prefix ==""{
- return false
- }
- cur := this.root
- for i:= 0;i< len(prefix);i++ {
- r := prefix[i]
- if cur.next[r]== nil{
- return false
- }
- cur = cur.next[r]
- }
- return true
- }