Prefix tree golang implementation

The prefix tree (Trie) is a data structure mainly used for the storage and matching of strings. In this article, we will introduce how to implement a prefix tree using Golang.

1. What is a prefix tree?

Prefix tree, also called dictionary tree, is a tree-shaped data structure used to store string collections, mainly used to efficiently find a certain string in a large amount of text. Compared to other data structures such as hash tables, the time complexity of a prefix tree is O(k), where k represents the length of the string to be found.

The core concept of the prefix tree is "node", each node contains the following information:

• A character c;
• A Boolean value isLeaf, Indicates whether the string ending with this node exists;
• A hash table children, used to store child nodes, and the key is the character corresponding to the child node.

The following figure is an example of a prefix tree containing four strings (apple, apply, app, banana):

2. Basic operations of prefix tree

The basic operations of prefix tree include insertion, search and deletion:

2.1 Insertion

When inserting a string into the prefix tree , we need to start traversing from the root node.

The specific steps are as follows:

• Initialize the current node as the root node;
• Traverse each character in the string, if the current character is not a child node of the current node , create a new node and store it in the child node;
• If the current character is in the child node of the current node, move to that node;
• After traversing the characters After string, mark isLeaf of the current node as true.

The following is an example of inserting the string "apple" and its execution process:

2.2 Find

Find a character string, we need to start traversing from the root node.

The specific steps are as follows:

• Initialize the current node as the root node;
• Traverse each character in the string, if the current character is not a child node of the current node , it means that the string does not exist in the prefix tree;
• If the current character is in the child node of the current node, move to that node;
• After traversing the string, if If the isLeaf mark of the current node is true, it means that the string exists in the prefix tree; otherwise, it means that the prefix exists in the prefix tree, but the string does not exist in the prefix tree.

The following is an example of finding the string "appl" and its execution process:

2.3 Delete

Delete a character string, we need to start traversing from the root node.

The specific steps are as follows:

• Initialize the current node as the root node;
• Traverse each character in the string, if the current character is not a child node of the current node , it means that the string does not exist in the prefix tree;
• If the current character is in the child node of the current node and the last character of the string has been traversed, mark the isLeaf of the node as false;
• If the current character is in the child node of the current node and the last character of the string has not been traversed, move to the node;
• If the node is deleted, the current If the node's children is empty and isLeaf is false, continue to delete the node's parent node.

The following is an example of deleting the string "apple" and its execution process:

3. Golang implements prefix tree

According to the previous description, we can use Golang to implement the prefix tree.

The code is as follows:

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
        }
    }
}

In the code, the NewTrie() function is used to create a new prefix tree node; the Insert() function is used to insert a string into the prefix tree; Search( ) function is used to find whether a string exists in the prefix tree; the Delete() function is used to delete a string.

4. Summary

The prefix tree is an efficient data structure for storing and searching strings. This article introduces the basic concepts of prefix trees and their basic operations, and implements the insertion, search, and deletion functions of prefix trees through Golang. I hope that readers can deepen their understanding of prefix trees through studying this article and be able to use Golang to implement other efficient data structures.

The above is the detailed content of Prefix tree golang implementation. For more information, please follow other related articles on the PHP Chinese website!