Golang实现Trie树及其相关操作

2021 年 12 月 16 日

752 次浏览

6254字数

介绍

trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

说白了，Trie树是一种N叉树，除根节点外，每个节点都保存了这个单词的一个字母，比如，对于保存了 Trie和 Tree这两个单词的Trie树，他的结构如下：

再比如，如下图所示也是一个Trie树

一个保存了8个键的trie结构，"A", "to", "tea", "ted", "ten", "i", "in", "inn".：

相关操作

节点设计

type TreeNode struct {
    Val       rune               //节点值
    Count     int                //分支数量
    ChildNode map[rune]*TreeNode //子节点
    IsWord    bool               //是否为完整字符串
}

插入节点

//插入节点
func insertNode(root *TreeNode, str string) {
    node := root
    arr := []rune(str) //将字符串转为字符数组
    //遍历数组和节点
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在当前子节点，插入子节点，若存在，继续遍历
        if !ok {
            child = &TreeNode{
                Val:       v,
                ChildNode: make(map[rune]*TreeNode),
            }
            node.ChildNode[v] = child
            node.Count++
        }
        node = child
    }
    node.IsWord = true //最后一个字符串，将该节点设置为单词节点
}

查询节点

//查找是否存在该词
func findWord(root *TreeNode, str string) bool {
    node := root
    arr := []rune(str)
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在直接返回false
        if !ok {
            return false
        }
        node = child
    }
    //遍历到最后一个节点，返回是否为单词节点
    return node.IsWord
}

删除节点

//删除节点
func removeNode(root *TreeNode, str string) {
    arr := []rune(str)
    node := root
    for _, v := range arr {
        child, _ := node.ChildNode[v]
        child.Count-- //子节点的子节点数量-1
        //若小于0，说明不再有其他节点分支，直接删除并返回
        //若大于等于0，说明还有其他节点分支，继续遍历
        if child.Count < 0 {
            delete(node.ChildNode, v)
            return
        }
        node = child
    }
    //如果能走到这一步，说明这个单词在公共前缀上，把单词标识改为false即可
    node.IsWord = false
}

Golang实现

trie.go

package trie

type TreeNode struct {
    Val       rune               //节点值
    Count     int                //分支数量
    ChildNode map[rune]*TreeNode //子节点
    IsWord    bool               //是否为完整字符串
}

type Tree struct {
    Root *TreeNode
}

func NewTrieTree() *Tree {
    return &Tree{
        Root: &TreeNode{
            ChildNode: make(map[rune]*TreeNode),
        },
    }
}

// Insert 插入
func (t *Tree) Insert(str string) {
    if len(str) == 0 {
        return
    }
    insertNode(t.Root, str)
}

// Search 查找
func (t *Tree) Search(str string) bool {
    if len(str) == 0 {
        return false
    }
    return findWord(t.Root, str)
}

// Remove 删除
func (t *Tree) Remove(str string) {
    if !findWord(t.Root, str) {
        return
    }
    removeNode(t.Root, str)
}

//插入节点
func insertNode(root *TreeNode, str string) {
    node := root
    arr := []rune(str) //将字符串转为字符数组
    //遍历数组和节点
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在当前子节点，插入子节点，若存在，继续遍历
        if !ok {
            child = &TreeNode{
                Val:       v,
                ChildNode: make(map[rune]*TreeNode),
            }
            node.ChildNode[v] = child
            node.Count++
        }
        node = child
    }
    node.IsWord = true //最后一个字符串，将该节点设置为单词节点
}

//查找是否存在该词
func findWord(root *TreeNode, str string) bool {
    node := root
    arr := []rune(str)
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在直接返回false
        if !ok {
            return false
        }
        node = child
    }
    //遍历到最后一个节点，返回是否为单词节点
    return node.IsWord
}

//删除节点
func removeNode(root *TreeNode, str string) {
    arr := []rune(str)
    node := root
    for _, v := range arr {
        child, _ := node.ChildNode[v]
        child.Count-- //子节点的子节点数量-1
        //若小于0，说明不再有其他节点分支，直接删除并返回
        //若大于等于0，说明还有其他节点分支，继续遍历
        if child.Count < 0 {
            delete(node.ChildNode, v)
            return
        }
        node = child
    }
    //如果能走到这一步，说明这个单词在公共前缀上，把单词标识改为false即可
    node.IsWord = false
}

trie_test.go （测试）

package trie

import (
    "fmt"
    "testing"
)

func TestTrieTree(t *testing.T) {
    tree := NewTrieTree()
    tree.Insert("trie")
    fmt.Println(tree.Search("trie"))
    tree.Insert("tree")
    tree.Insert("treea")
    fmt.Println(tree.Search("tree"))
    tree.Remove("treea")
    fmt.Println(tree.Search("tree"))
    fmt.Println(tree.Search("treea"))
    fmt.Println(tree.Search("trie"))
}

Leetcode 208. 实现 Trie（前缀树）

题目描述

Trie（发音类似 "try"）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中d的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串word 。
boolean search(String word) 如果字符串word 在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串word 的前缀之一为prefix ，返回true ；否则，返回false 。

题解

题目给的范围是，仅由小写英文字母组成，我这里懒得再写一遍了，没有优化空间，直接用了 rune数组和 map，所以会偏大，实际上使用长度为26的数组去表示可以优化空间

type Trie struct {
    Val       rune           //节点值
    Count     int            //分支数量
    ChildNode map[rune]*Trie //子节点
    IsWord    bool           //是否为完整字符串
}

func Constructor() Trie {
    return Trie{
        ChildNode: make(map[rune]*Trie),
    }
}

func (this *Trie) Insert(word string) {
    node := this
    arr := []rune(word) //将字符串转为字符数组
    //遍历数组和节点
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在当前子节点，插入子节点，若存在，继续遍历
        if !ok {
            child = &Trie{
                Val:       v,
                ChildNode: make(map[rune]*Trie),
            }
            node.ChildNode[v] = child
            node.Count++
        }
        node = child
    }
    node.IsWord = true //最后一个字符串，将该节点设置为单词节点
}

func (this *Trie) Search(word string) bool {
    node := this
    arr := []rune(word)
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在直接返回false
        if !ok {
            return false
        }
        node = child
    }
    //遍历到最后一个节点，返回是否为单词节点
    return node.IsWord
}

func (this *Trie) StartsWith(prefix string) bool {
    node := this
    arr := []rune(prefix)
    for _, v := range arr {
        child, ok := node.ChildNode[v]
        //若不存在直接返回false
        if !ok {
            return false
        }
        node = child
    }
    //遍历到最后一个节点，返回是否为单词节点
    return true
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

结果

执行用时：60 ms, 在所有 Go 提交中击败了35.82%的用户

内存消耗：16.6 MB, 在所有 Go 提交中击败了75.54%的用户

Golang实现Trie树及其相关操作

kakkk • 2021 年 12 月 16 日

介绍

相关操作

节点设计

插入节点

查询节点

删除节点

Golang实现

trie.go

trie_test.go （测试）

Leetcode 208. 实现 Trie（前缀树）

题目描述

题解

结果

发表评论 取消回复

Golang实现Trie树及其相关操作

发表评论取消回复