golang 字典树实现

用Golang实现字典树

什么是字典树

字典树，也被称为前缀树或Trie树，是一种特定的树型数据结构，用于高效地存储和检索字符串集合。字典树将每个字符串分解为字符序列，并使用节点来表示这些字符。每个节点可以包含一个值，通常用于表示字符串的结束。

实现字典树的基本结构

在Golang中，我们可以使用结构体来表示字典树的基本结构。每个节点表示一个字符，并包含一个值和对子节点的引用。

type TrieNode struct {
    value    interface{}
    children map[rune]*TrieNode
}

在上面的代码中，value字段表示该节点代表的字符串的值，children字段是一个映射，用于存储子节点。我们使用rune类型来表示字符，并使用指向TrieNode的指针来引用子节点。

实现插入操作

插入操作用于将字符串添加到字典树中。从根节点开始，遍历字符串的每个字符，如果当前字符不存在于当前节点的子节点列表中，则创建一个新的子节点并添加引用。最后，将字符串的值设置为叶子节点的value字段。

func (n *TrieNode) Insert(key string, value interface{}) {
    node := n
    for _, char := range key {
        if node.children == nil {
            node.children = make(map[rune]*TrieNode)
        }
        if _, ok := node.children[char]; !ok {
            node.children[char] = &TrieNode{}
        }
        node = node.children[char]
    }
    node.value = value
}

实现查找操作

查找操作用于从字典树中检索特定字符串的值。从根节点开始，遍历目标字符串的每个字符，并沿着子节点的引用前进。如果遇到字符不存在于子节点列表中，则字符串不存在于字典树中。最后，返回叶子节点的value字段作为结果。

func (n *TrieNode) Search(key string) interface{} {
    node := n
    for _, char := range key {
        if node.children != nil {
            if _, ok := node.children[char]; !ok {
                return nil
            }
            node = node.children[char]
        } else {
            return nil
        }
    }
    return node.value
}

实现删除操作

删除操作用于从字典树中删除指定字符串。从根节点开始，遍历目标字符串的每个字符，并沿着子节点的引用前进。如果遇到字符不存在于子节点列表中，则字符串不存在于字典树中。如果字符串的最后一个字符存在于最后一个节点的子节点列表中，可以将该子节点从子节点列表中删除。

func (n *TrieNode) Delete(key string) {
    var deleteNode func(*TrieNode, int)
    deleteNode = func(node *TrieNode, i int) {
        char := rune(key[i])
        if i == len(key)-1 {
            if node.children != nil {
                delete(node.children, char)
            }
        } else {
            if _, ok := node.children[char]; ok {
                deleteNode(node.children[char], i+1)
            }
        }
    }

    deleteNode(n, 0)
}

func delete(children map[rune]*TrieNode, char rune) {
    delete(children, char)
    if len(children) == 0 {
        children = nil
    }
}

使用字典树

现在我们可以使用上面实现的字典树来存储和检索字符串。通过使用Insert操作将字符串添加到字典树中，然后使用Search操作检索特定字符串的值。如果要删除字符串，则使用Delete操作。

func main() {
    trie := &TrieNode{}

    trie.Insert("apple", 1)
    trie.Insert("banana", 2)
    trie.Insert("cat", 3)

    fmt.Println(trie.Search("apple"))   // 输出：1
    fmt.Println(trie.Search("banana"))  // 输出：2
    fmt.Println(trie.Search("dog"))     // 输出：nil

    trie.Delete("banana")

    fmt.Println(trie.Search("banana"))  // 输出：nil
}

总结

字典树是一种非常有用的数据结构，特别适用于高效地存储和检索字符串集合。通过使用Golang，我们可以轻松地实现字典树的基本操作，包括插入、查找和删除。

希望本文对于理解和学习如何使用Golang实现字典树有所帮助。如果您对字典树还有其他问题或者需要更深入的学习，请参考相关的学习资料和文档。