前缀树golang实现

WBOY原创: 2023-05-14 14:17:39115浏览

前缀树（Trie）是一种数据结构，主要用于字符串的存储与匹配。在本文中，我们将介绍如何使用 Golang 实现前缀树。

什么是前缀树？

前缀树，也叫字典树，是一种树形数据结构，用于存储字符串集合，主要用于在大量文本中高效地查找某个字符串。与其他数据结构（如哈希表）相比，前缀树的时间复杂度是 O(k)，其中 k 表示要查找的字符串的长度。

前缀树的核心概念是“节点”（Node），每个节点包含以下信息：

一个字符 c；
一个布尔值 isLeaf，表示以此节点结尾的字符串是否存在；
一个哈希表 children，用于存储子节点，且 key 为子节点对应的字符。

下图是一个包含四个字符串（apple，apply，app，banana）的前缀树的示例：

example_trie

前缀树的基本操作

前缀树的基本操作包括插入、查找和删除：

2.1 插入

向前缀树中插入一个字符串时，我们需要从根节点开始遍历。

具体步骤如下：

初始化当前节点为根节点；
遍历字符串中的每个字符，若当前字符不在当前节点的子节点中，则创建一个新的节点，并将其存入子节点中；
如果当前字符在当前节点的子节点中，则移动到该节点；
遍历完字符串后，将当前节点的 isLeaf 标记为 true。

下面是插入字符串 “apple” 及其执行过程的示例：

trie_insertion

2.2 查找

查找一个字符串时，我们需要从根节点开始遍历。

具体步骤如下：

初始化当前节点为根节点；
遍历字符串中的每个字符，若当前字符不在当前节点的子节点中，则说明该字符串不存在于前缀树中；
如果当前字符在当前节点的子节点中，则移动到该节点；
遍历完字符串后，如果当前节点的 isLeaf 标记为 true，说明该字符串存在于前缀树中；否则，说明前缀存在于前缀树中，但该字符串不存在于前缀树中。

下面是查找字符串 “appl” 及其执行过程的示例：

trie_search

2.3 删除

删除一个字符串时，我们需要从根节点开始遍历。

具体步骤如下：

初始化当前节点为根节点；
遍历字符串中的每个字符，若当前字符不在当前节点的子节点中，则说明该字符串不存在于前缀树中；
如果当前字符在当前节点的子节点中，且已经遍历到字符串的最后一个字符，则将该节点的 isLeaf 标记为 false；
如果当前字符在当前节点的子节点中，且还没有遍历到字符串的最后一个字符，则移动到该节点；
若删除该节点后，当前节点的 children 为空且 isLeaf 为 false，则继续删除该节点的父节点。

下面是删除字符串 “apple” 及其执行过程的示例：

trie_deletion

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() 函数用于删除一个字符串。