前缀树golang实现

2023-05-14 21:05:34 前缀 Golang

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

  1. 什么是前缀树?

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

前缀树的核心概念是“节点”(node),每个节点包含以下信息:

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

下图是一个包含四个字符串(apple,apply,app,banana)的前缀树的示例:

example_trie

  1. 前缀树的基本操作

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

2.1 插入

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

具体步骤如下:

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

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

trie_insertion

2.2 查找

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

具体步骤如下:

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

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

trie_search

2.3 删除

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

具体步骤如下:

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

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

trie_deletion

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

  1. 总结

前缀树是一种存储和查找字符串的高效数据结构。本文介绍了前缀树的基本概念及其基本操作,并通过 Golang 实现了前缀树的插入、查找和删除功能。希望读者通过本文的学习,能够加深对前缀树的理解,并能够使用 Golang 实现其他高效数据结构。

以上就是前缀树golang实现的详细内容,更多请关注其它相关文章!

相关文章