radixtree

A data structure that represents a space-optimized trie (prefix tree) in which each node that is the only child is merged with its parent.

This implementation will store strings with values, the trie allow nil values to be stored but not nil.

API

Create new

Create a new RadixTree

trie = trie.NewRadixTree()

Put key value

Put key value into the trie

trie = trie.NewRadixTree()
trie.Put("abc", 1)

Get value

Retrieve the value stored in the trie for the key else else nil.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
result, _ = trie.Get("abc")

Delete value

Delete the value stored in the trie for the key, returns true if a key was found and the value was deleted else returns false.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
deleted, _ = trie.Delete("abc")

Check if key stored with value

Return true if key was found in the trie.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
deleted, _ = trie.Contains("abc")

Longest Prefix

Find the key with longest prefix in the trie for the query string.

trie = trie.NewRadixTree()
trie.Put("abc", 1)
key, _ = trie.LongestPrefixOf("abcdef")

Keys For Prefix

Return all the keys in the trie that starts with this prefix.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.KeyWithPrefix("www.")

All Keys

Return all the keys in the trie.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.Keys()

All Key Value Pairs

Return all the key value pairs.

trie = trie.NewRadixTree()
trie.Put("www.test.com", 1)
trie.Put("www.example.com", 1)
key_channel = trie.Items()

Tests

The tests can be invoked with go test

License

MIT © Oliver Daff