trie test Algorithm

The trie test algorithm is a technique used to efficiently search for and retrieve information in a data structure called a trie. A trie, also known as a prefix tree, is a tree-like data structure that stores a dynamic set of strings, where each node in the trie represents a character in a string. The trie test algorithm traverses the trie by following the edges that correspond to the characters of the input string, ultimately reaching the desired node or determining that the input string is not present in the trie. This algorithm is particularly useful and efficient for tasks such as searching in dictionaries, implementing auto-complete features, and IP routing, as it allows for fast lookups and insertions of strings. To perform the trie test algorithm, the process starts at the root node of the trie and proceeds through the tree by following the edges that match the characters of the input string. If a matching edge is not found, the algorithm concludes that the input string is not present in the trie. If the traversal reaches the end of the input string, the algorithm checks the current node for an end-of-word marker (usually a special character or a boolean flag) to determine if the input string is a valid word stored in the trie. By using this algorithm, the time complexity for searching, inserting, and deleting strings in a trie is generally O(L), where L is the length of the input string. This makes the trie test algorithm highly efficient and scalable when dealing with large data sets of strings.
package trie

import (
	"testing"
)

func TestTrie(t *testing.T) {
	n := NewNode()

	insertWords := [...]string{
		"nikola",
		"tesla",
	}
	checkWords := map[string]bool{
		"thomas": false,
		"edison": false,
		"nikola": true,
	}

	for _, w := range insertWords {
		n.insert(w)
		t.Logf(
			"added \"%s\" to the Trie.",
			w,
		)
	}

	for k, v := range checkWords {
		ok := n.find(k)
		if ok != v {
			t.Fatalf(
				"\"%s\" is supposed to be %sin the Trie.",
				k,
				map[bool]string{true: "", false: "NOT "}[v],
			)
		}
		t.Logf(
			"\"%s\" is %sin the Trie.",
			k,
			map[bool]string{true: "", false: "NOT "}[ok],
		)
	}
}

func BenchmarkTrie(b *testing.B) {
	for i := 0; i < b.N; i++ {
		n := NewNode()

		n.insert("nikola")
		n.insert("tesla")

		n.find("thomas")
		n.find("edison")
		n.find("nikola")
	}
}

func ExampleNode() {
	// creates a new node
	node := NewNode()

	// adds words
	node.insert("nikola")
	node.insert("tesla")

	// finds words
	node.find("thomas") // false
	node.find("edison") // false
	node.find("nikola") // true
}

LANGUAGE:

DARK MODE: