A Trie (also known as a Digital Search Tree) is a data structure which takes advantage of the structure of aggregate types to achieve good running times for its operations. Our implementation provides Tries in which the keys are lists of the element type; this is sufficient for representing many aggregate data structures. In our implementation, each trie is a multiway tree with each node of the multiway tree carrying data of base element type. Tries provide lookup and insert operations with better asymptotic running times than hash tables. This data structure is very useful when used for an aggregate type like strings.
syntax
( Trie KV)
(mapstring->list(list"abc""xyz""abcfg""abxyz""xyz12")))- : #(struct:Trie
((U (Some Positive-Byte) Mt)
(Immutable-HashTable Char (Trie Char Positive-Byte))))
#<Trie>
In the above example, "abc" will have the value 1, "xyz" will get 2 and so on.
- : #(struct:Trie
((U (Some Integer) Mt) (Immutable-HashTable Char (Trie Char Integer))))
#<Trie>
In the above example, "abc" will have the value 1, "xyz" will get 2 and so on.
In the above example, "abcfg" will have the value 4, "abxyz" will get 5
- : Integer [more precisely: Positive-Byte]
4
- : Integer [more precisely: Positive-Byte]
2
lookup: given key not found in the trie