前綴樹golang實現-Golang-PHP中文網

前綴樹golang實現

WBOY

發布： 2023-05-14 14:17:39

原創

853 人瀏覽過

前綴樹（Trie）是一種資料結構，主要用於字串的儲存與匹配。在本文中，我們將介紹如何使用 Golang 實作前綴樹。

什麼是前綴樹？

前綴樹，也叫字典樹，是一種樹狀資料結構，用於儲存字串集合，主要用於在大量文字中高效地查找某個字串。與其他資料結構（如雜湊表）相比，前綴樹的時間複雜度是 O(k)，其中 k 表示要尋找的字串的長度。

前綴樹的核心概念是「節點」（Node），每個節點包含以下資訊：

一個字元c；
一個布林值isLeaf，表示以此節點結尾的字串是否存在；
一個哈希表children，用於儲存子節點，且key 為子節點對應的字元。

下圖是一個包含四個字串（apple，apply，app，banana）的前綴樹的範例：

前綴樹golang實現

前綴樹的基本操作

前綴樹的基本操作包括插入、尋找和刪除：

2.1 插入

在向前綴樹中插入字串時，我們需要從根節點開始遍歷。

具體步驟如下：

初始化目前節點為根節點；
#遍歷字串中的每個字符，若當前字元不在目前節點的子節點中，則建立一個新的節點，並將其存入子節點中；
如果當前字元在目前節點的子節點中，則移動到該節點；
遍歷完字符串後，將目前節點的isLeaf 標記為true。

下面是插入字串「apple」及其執行程序的範例：

前綴樹golang實現

#2.2 尋找

#找出一個字符串時，我們需要從根節點開始遍歷。

具體步驟如下：

初始化目前節點為根節點；
#遍歷字串中的每個字符，若當前字元不在目前節點的子節點中，則表示該字串不存在於前綴樹中；
如果當前字元在目前節點的子節點中，則移動到該節點；
遍歷完字串後，如果當前節點的isLeaf 標記為true，表示字串存在於前綴樹中；否則，說明前綴存在於前綴樹中，但該字串不存在於前綴樹中。

以下是尋找字串「appl」及其執行過程的範例：

前綴樹golang實現

2.3 刪除

#刪除一個字符串時，我們需要從根節點開始遍歷。

具體步驟如下：

初始化目前節點為根節點；
#遍歷字串中的每個字符，若當前字元不在目前節點的子節點中，則說明該字串不存在於前綴樹中；
如果當前字符在當前節點的子節點中，且已經遍歷到字串的最後一個字符，則將該節點的isLeaf 標記為false;
如果當前字符在目前節點的子節點中，且還沒有遍歷到字串的最後一個字符，則移動到該節點；
若刪除該節點後，當前節點的children 為空且isLeaf 為false，則繼續刪除該節點的父節點。

以下是刪除字串「apple」及其執行程序的範例：

前綴樹golang實現

#Golang 實作前綴樹

根據前面的敘述，我們可以使用Golang 實作前綴樹。

程式碼如下：

type Trie struct {
    children map[byte]*Trie
    isLeaf   bool
}

func NewTrie() *Trie {
    return &Trie{children: make(map[byte]*Trie)}
}

func (t *Trie) Insert(word string) {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            curr.children[c] = NewTrie()
        }
        curr = curr.children[c]
    }
    curr.isLeaf = true
}

func (t *Trie) Search(word string) bool {
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return false
        }
        curr = curr.children[c]
    }
    return curr.isLeaf
}

func (t *Trie) Delete(word string) {
    nodes := make([]*Trie, 0)
    curr := t
    for i := 0; i < len(word); i++ {
        c := word[i]
        if _, ok := curr.children[c]; !ok {
            return
        }
        nodes = append(nodes, curr)
        curr = curr.children[c]
    }
    curr.isLeaf = false
    if len(curr.children) > 0 {
        return
    }

    for i := len(nodes) - 1; i >= 0; i-- {
        node := nodes[i]
        delete(node.children, word[i])
        if len(node.children) > 0 || node.isLeaf {
            return
        }
    }
}

登入後複製

程式碼中，NewTrie() 函數用於建立一個新的前綴樹節點；Insert() 函數用於在向前綴樹中插入字串；Search( ) 函數用於尋找字串是否存在於前綴樹中；Delete() 函數用於刪除一個字串。