字典树实现_数据结构与算法之字典树（Golang实现）

1. 字典树

算法描述：trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。时间复杂度：构建O(n)，查询O(k)

1.1.1. 算法步骤

• 根节点/ 什么都不表示

• 做一个字典比如a-z 字母表

• 没一个节点包含这26个字母的字典表，每个位置保存下个节点的指针。

1.1.2. 算法分析

缺点：

• trie树比较消耗内存：因为他没一层都保存一个字典表，就算这层的节点只有一个也要有一组表

• 使用的是指针类型，内存不连续对存储不友好，性能打折扣 优点：

• 查询效率比较高，对于一些范围较小的或者内存不敏感的应用可以使用

• 特别适用自动补全类应用

package mainimport "fmt"type TrieNode struct {    value      int    dictionary [26]*TrieNode}type TrieTree struct {    root *TrieNode}func main() {    tree := createTree()//fmt.Println(tree)    flag := tree.findWord("her")    fmt.Println(flag)    flag = tree.findWord("x")    fmt.Println(flag)}func createTree() TrieTree {    arrList := []string{"how", "hi", "her", "hello", "so", "see"}    myTree := TrieTree{}//添加跟节点    myTree.root = &TrieNode{}for _, value := range arrList {        myTree.addWord(value)}return myTree}func (t *TrieTree) addWord(word string) {    fmt.Println(word)    nowNode := t.root    a := int('a')var char intfor i := 0; i < len(word); i++ {        char = int(word[i])if nowNode.dictionary[char-a] != nil {            nowNode = nowNode.dictionary[char-a]continue} else {            newNode := &TrieNode{}            nowNode.dictionary[char-a] = newNode            nowNode = newNodecontinue}}}func (t *TrieTree) findWord(word string) int {    nowNode := t.root    a := int('a')var char intfor i := 0; i < len(word); i++ {        char = int(word[i])if nowNode.dictionary[char-a] != nil {return 0} else {            nowNode = nowNode.dictionary[char-a]}if i == len(word)-1 {return 1}}return 0}

好文点赞收藏