資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學使用Golang實現Trie資料結構
Trie 是一種類似樹的資料結構，用於儲存和搜尋動態字串集合。在處理鍵共享公共字首（如字典單詞）的資料時非常有用。Trie 與其他檢索資料結構的不同之處在於其高效的字串操作和檢索特性。在本文中，我們將學習如何在 Go 程式語言中實現 Trie 資料結構。
解釋
Trie，也稱為檢索樹，是一種樹形資料結構，通常用於儲存和管理字串集合。它提供對儲存字串的訪問。支援各種操作，如插入和刪除。這使得它特別適用於涉及搜尋和提供建議的任務。
讓我們看看 Trie 樹
(root)
/ | \
a b b
/ \ \
p a a
/| \ \
p p t l
/ \ \
l le l
/
e
我們在頂部有一個根節點，沒有字元。
邊連線節點，每條邊表示一個字元。
節點可以有多個子節點和字元。
路徑 a->p->p->l->e 表示 apple。
路徑 b->a->t 表示 bat
語法
func NewTrie() *Trie
語法定義了一個名為 NewTrie() 的函式，用於初始化一個新的 Trie 例項，該例項具有一個根節點，該節點包含一個用於子節點的對映。
func (t *Trie) StartsWith(prefix string) (words []string)
語法定義了一個名為 StartsWith 的函式，該函式對於給定的字首，透過 Trie 導航以識別共享該字首的單詞，方法是遞迴遍歷從根到字首的節點。它收集在該字首下找到的單詞，並將它們作為列表返回。
演算法
首先建立一個 TrieNode 型別結構，該結構具有一個對映來儲存子節點。
然後定義一個 Insert 函式，將單詞新增到 Trie 中。
開發一個 Search 函式，檢查 Trie 中是否存在單詞。
構建一個 StartsWith 函式，查詢具有給定字首的所有單詞。
最後，設計一個 Print 函式來視覺化 Trie 結構。
示例
在此示例中，我們使用 TrieNode 結構定義了一個 Trie 資料結構，其中包括一個用於儲存子節點的對映和一個布林值以標記單詞的結尾。Insert 函式透過迭代字元並在需要時建立節點來幫助新增字串。Search 函式遍歷 Trie 以確定單詞是否存在。最後，printTrie 函式以可視方式顯示 Trie 的結構。
package main
import "fmt"
type TrieNode struct{ children map[rune]*TrieNode; isEnd bool }
type Trie struct{ root *TrieNode }
func NewTrie() *Trie { return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}}
func (t *Trie) Insert(word string) {
node := t.root
for _, c := range word {
if node.children[c] == nil { node.children[c] = &TrieNode{children: make(map[rune]*TrieNode)}}
node = node.children[c]
}
node.isEnd = true
}
func (t *Trie) Search(word string) bool {
node := t.root
for _, c := range word {
if node.children[c] == nil { return false }
node = node.children[c]
}
return node.isEnd
}
func printTrie(node *TrieNode, level int, prefix string) {
if node == nil { return }
fmt.Printf("%s%d\n", prefix, level)
for c, childNode := range node.children {
printTrie(childNode, level+1, fmt.Sprintf("%s──", prefix))
fmt.Printf("%s%s\n", prefix, string(c))
}
}
func main() {
trie := NewTrie()
words := []string{"apple", "app", "banana", "bat"}
for _, w := range words { trie.Insert(w); }
fmt.Println("\nTrie Structure:"); printTrie(trie.root, 0, "")
fmt.Println("\nSearch 'app':", trie.Search("app"))
fmt.Println("Search 'banana':", trie.Search("banana"))
fmt.Println("Search 'batman':", trie.Search("batman"))
}
輸出
Trie Structure: 0 ──1 ────2 ──────3 ────────4 ──────────5 ────────e ──────l ────p ──p a ──1 ────2 ──────3 ────────4 ──────────5 ────────────6 ──────────a ────────n ──────a ────n ──────3 ────t ──a b Search 'app': true Search 'banana': true Search 'batman': false
現實生活中的應用
聯絡人或電話簿應用程式：嘗試管理聯絡人資訊可用於開發聯絡人或電話簿應用程式。Trie 資料結構允許透過其節點對聯絡人姓名中的特定字元進行編碼，從而可以透過輸入部分名稱來搜尋聯絡人。
IDE 中的自動完成功能：作為整合開發環境 (IDE) 中的普遍功能，程式碼自動完成功能需要簡化的實現。Trie 有助於快速識別與輸入字首匹配的有效程式碼片段，從而實現簡化的體驗。
結論
Trie 資料結構是字串操作的基本工具，提供有效的單詞儲存和檢索。在本文中，我們探討了 Trie 的概念，使用兩種不同的方法在 Go 中實現了 Trie 資料結構。第一種方法強調插入和搜尋，以突出 Trie 對字典或拼寫檢查器中單詞查詢的適用性。第二種方法透過實現字首匹配引入了 Trie 的多功能性，這對於自動完成或建議等任務很有用。
564 次檢視
