6.2.901.900
8 Tries
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.
A trie with keys of type K and values of type
V.
(tries values keys) → (Trie K V)
|
| values : (Listof V) |
| keys : (Listof (Listof K)) |
Function
tries creates a trie with each value assigned to the list
in keys at the corresponding location.
Example: |
| > (tries (list 1 2 3 4 5) | | (map string->list (list "abc" "xyz" "abcfg" "abxyz" "xyz12"))) |
| - : (Trie Char Integer) | #<Trie> |
|
In the above example, "abc" will have the value 1, "xyz" will get 2
and so on.
(trie keys) → (Trie K Integer)
|
| keys : (Listof (Listof K)) |
Function
trie creates a trie by assigning a integer value to each list
in keys.
Example: |
| > (trie (map string->list (list "abc" "xyz" "abcfg" "abxyz" "xyz12"))) | - : (Trie Char Integer) | #<Trie> |
|
In the above example, "abc" will have the value 1, "xyz" will get 2
and so on.
(insert values keys trie) → (Trie K V)
|
| values : (Listof V) |
| keys : (Listof (Listof K)) |
| trie : (Trie K V) |
Inserts multiple keys into the trie.
Example: |
| > (insert (list 4 5) | | (map string->list (list "abcfg" "abxyz")) | | (tries (list 1 2) | | (map string->list (list "abc" "xyz")))) |
| - : (Trie Char Integer) | #<Trie> |
|
In the above example, "abcfg" will have the value 4, "abxyz" will get 5
(bind key value trie) → (Trie K V)
|
| key : (Listof K) |
| value : V |
| trie : (Trie K V) |
Inserts a key into the trie.
Example: |
| > (bind (string->list "abcfg") 3 | | (tries (list 1 2) | | (map string->list (list "abc" "xyz")))) |
| - : (Trie Char Integer) | #<Trie> |
|
(lookup key trie) → V
|
| key : (Listof K) |
| trie : (Trie K V) |
Looks for the given key. If found, the value corresponding to the key is
returned. Else throws an error.
Examples: |
| > (lookup (string->list "abcde") | | (tries (list 1 2 3 4) | | (map string->list (list "123" "abc" "xyz" "abcde")))) |
| - : Integer | 4 | | > (lookup (string->list "abc") | | (tries (list 1 2 3 4) | | (map string->list (list "123" "abc" "xyz" "abcde")))) |
| - : Integer | 2 | | > (lookup (string->list "abcd") | | (tries (list 1 2 3 4) | | (map string->list (list "123" "abc" "xyz" "abcde")))) |
| lookup: given key not found in the trie |
|