Trie Algorithm

The Trie Algorithm, also known as the Prefix Tree or Digital Tree, is an efficient data structure used for organizing a collection of strings or sequences into a tree-like structure. The primary purpose of a trie is to enable fast retrieval of strings that share a common prefix. This algorithm is widely used in applications such as autocomplete features, spell-checkers, IP routing, and many other search-related tasks. The trie algorithm constructs a tree where each node represents a single character of a string or sequence. The root node is an empty node, while the child nodes represent the first characters of the strings. Each subsequent level of the tree holds the next character in the strings. When searching for a string in the trie, one can simply traverse the tree from the root node, following the child nodes that match the characters of the string. If the traversal reaches a leaf node, the string is found in the trie. This structure allows for efficient string queries and insertions, making it a highly useful algorithm in computer science and information retrieval systems.
package Trie

type Node struct {
	last     bool
	parent   *Node
	children map[int32]*Node
}

type Trie struct {
	root *Node
}

func (trie *Trie) Init() {
	trie.root = &Node{children: map[int32]*Node{}}
}

func (trie Trie) Add(item string) {
	currentNode := trie.root
	for _, r := range item {
		if _, ok := currentNode.children[r]; ok {
			currentNode = currentNode.children[r]
		} else {
			node := &Node{children: map[int32]*Node{}, parent: currentNode}
			currentNode.children[r] = node
			currentNode = node
		}
	}
	currentNode.last = true
}

func (trie Trie) Search(item string) bool {
	currentNode := trie.root
	for _, r := range item {
		if _, ok := currentNode.children[r]; ok {
			currentNode = currentNode.children[r]
		} else {
			return false
		}
	}
	if currentNode.last == false {
		return false
	}
	return true
}

func (trie Trie) Remove(item string) bool {
	currentNode := trie.root
	for _, r := range item {
		if _, ok := currentNode.children[r]; ok {
			currentNode = currentNode.children[r]
		} else {
			return false
		}
	}
	if currentNode.last == false {
		return false
	}
	currentNode.last = false
	symbolIndex := len(item) - 1
	for len(currentNode.children) == 0 {
		delete(currentNode.children, int32(item[symbolIndex]))
		currentNode = currentNode.parent
		symbolIndex--
	}
	return true
}

LANGUAGE:

DARK MODE: