A **radix tree** is a data structure optimised for storing key-value pairs in a way optimised for searching. This makes them very, very good for efficiently matching data against keys, and retrieving the values *associated* with those keys.

`triebeard`

provides an implementation of radix trees for Rcpp (and also for use directly in R). To start using radix trees in your Rcpp development, simply modify your C++ file to include at the top:

```
//[[Rcpp::depends(triebeard)]]
#include <radix.h>
```

Trees are constructed using the syntax:

`radix_tree<type1, type2> radix;`

Where `type`

represents the type of the keys (for example, `std::string`

) and `type2`

the type of the values.

Radix trees can have any scalar type as keys, although strings are most typical; they can also have any scalar type for values. Once you’ve constructed a tree, new entries can be added in a very R-like way: `radix[new_key] = new_value;`

. Entries can also be removed, with `radix.erase(key)`

.

We then move on to the fun bit: matching! As mentioned, radix trees are really good for matching arbitrary values against keys (well, keys of the same type) and retrieving the associated values.

There are three types of supported matching; longest, prefix, and greedy. Longest does exactly what it says on the tin: it finds the key-value pair where the longest initial part of the key matches the arbitrary value:

```
radix_tree<std::string, std::string> radix;
radix["turnin"] = "entry the first";
radix["turin"] = "entry the second";
radix_tree<std::string, std::string>::iterator it;
it = radix.longest_match("turing");
if(it = radix.end()){
printf("No match was found :(");
} else {
std::string result = "Key of longest match: " + it->first + " , value of longest match: " + it->second;
}
```

Prefix matching provides all trie entries where the value-to-match is a *prefix* of the key:

```
radix_tree<std::string, std::string> radix;
radix["turnin"] = "entry the first";
radix["turin"] = "entry the second";
std::vector<radix_tree<std::string, std::string>::iterator> vec;
std::vector<radix_tree<std::string, std::string>::iterator>::iterator it;
it = radix.prefix_match("tur");
if(it == vec.end()){
printf("No match was found :(");
} else {
for (it = vec.begin(); it != vec.end(); ++it) {
std::string result = "Key of a prefix match: " + it->first + " , value of a prefix match: " + it->second;
}
}
```

Greedy matching matches very, very fuzzily (a value of ‘bring’, for example, will match ‘blind’, ‘bind’ and ‘binary’) and, syntactically, looks exactly the same as prefix-matching, albeit with `radix.greedy_match()`

instead of `radix.prefix_match()`

.

If you have ideas for other trie-like structures, or functions that would be useful with *these* tries, the best approach is to either request it or add it!