README
¶
go-trie
A primitive implementation of the Trie data structure in Golang. The Trie data structure allows for quick information retrieval, typically strings, and prefix searching. It stores data as an associative array. Keys and their respective values are stored as bytes.
Typically, values in a Trie are unnecessary, rather, they are not traditionally needed. In such cases such as these, you can simply store some terminal or constant value.
Usage
// Construct an empty trie with a single root node
trie := NewTrie()
// Insert a key value pair into the trie
trie.Insert([]byte("someKey"), []byte("someValue"))
// Search for some value
value, ok := trie.Search([]byte("someKey"))
// Get all keys stored in the trie
keys := trie.GetAllKeys()
// Get all values stored in the trie
values := trie.GetAllValues()
// Get all keys stored in the trie that contain a specific prefix
keyByPrefix := trie.GetPrefixKeys([]byte("somePrefix"))
// Get all values stored in the trie who's corresponding keys contain a
// specific prefix.
valuesByPrefix := trie.GetPrefixValues(prefix)
Tests
$ go test -v
Contributing
- Fork it
- Create your feature branch (
git checkout -b feature/my-new-feature) - Commit your changes (
git commit -m 'Add some feature') - Push to the branch (
git push origin feature/my-new-feature) - Create a new Pull Request
Documentation
¶
Overview ¶
Package trie contains a primitive implementation of the Trie data structure.
Copyright 2017 Aleksandr Bezobchuk.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Trie implements a thread-safe search tree that stores byte key value pairs and allows for efficient queries.
func (*Trie) GetAllKeys ¶
GetAllKeys returns all the keys that exist in the trie. Keys are retrieved by performing a DFS on the trie where at each node we keep track of the current path (key) traversed thusfar and if that node has a value. If so, the full path (key) is appended to a list. After the trie search is exhausted, the final list is returned.
func (*Trie) GetAllValues ¶
GetAllValues returns all the values that exist in the trie. Values are retrieved by performing a BFS on the trie where at each node we examine if that node has a value. If so, that value is appended to a list. After the trie search is exhausted, the final list is returned.
func (*Trie) GetPrefixKeys ¶
GetPrefixKeys returns all the keys that exist in the trie such that each key contains a specified prefix. Keys are retrieved by performing a DFS on the trie where at each node we keep track of the current path (key) and prefix traversed thusfar. If a node has a value the full path (key) is appended to a list. After the trie search is exhausted, the final list is returned.
func (*Trie) GetPrefixValues ¶
GetPrefixValues returns all the values that exist in the trie such that each key that corresponds to that value contains a specified prefix. Values are retrieved by performing a DFS on the trie where at each node we check if the prefix is exhausted or matches thusfar and the current node has a value. If the current node has a value, it is appended to a list. After the trie search is exhausted, the final list is returned.
func (*Trie) Insert ¶
Insert inserts a key value pair into the trie. If the key already exists, the value is updated. Insertion is performed by starting at the root and traversing the nodes all the way down until the key is exhausted. Once exhausted, the currNode pointer should be a pointer to the last symbol in the key and reflect the terminating node for that key value pair.
Source Files