I will implement (for fun and practice) several trie (and related) data structures
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
Radix_Tree
TST
test
trie
.codedocs
.gitignore
.travis.yml
CMakeLists.txt
LICENSE
README.md
conanfile.txt
documentation.dox

README.md

Build Status Coverity Scan Build Status Coverage Status Documentation

Trie / Ternary Search Tree (TST) / Radix Tree

Description of this project

I have created three data structures that are implementations of the abstract data type dictionary. But they are enhanced with an extra method called "keys", this returns the keys with that share a provided prefix. This can be useful to use it in tasks such as autocomplete searches.

The aim of this study is to compare the performance of these three data structures in different scenarios and against the std::map and std::unordered_map. Moreover, the second aim of this project is to practice new things added in the standard C++11 and the Google Test as a unit test framework.

Operations supported by the three data structures tested in this project.

Operation Description
clear Removes all the content of the data structure
find Returns the value stored in the data structure for a specific key provided
insert Adds a new pair of key and value to the data structure
size Returns the amount of elements stored in the data structure
show Prints the content of the data structure in the dot format
erase Removes the value stored in the data structure for a specific key provided
contains Returns true if there is a value associated to the key provided
keys Returns a std::vector with all the keys in the data structure that have the provided prefix. If no prefix is provided returns a std::vector with all the keys in the data structure.
lcp Returns the longest common prefix of all keys stored in the data structure.

Scenarios tested

I have develop several test scenarios (and I am still developing new ones) to compare the performance of these five data structures.

  • Memory
    • Random values
    • Dictionaries
  • Insert
    • Random values
  • Remove
    • Random values
      • Found
      • Not found
    • Dictionaries
      • Found
      • Not found
  • Seach
    • Random values
      • Found
      • Not found
    • Dictionaries
      • Found
      • Not found
  • Get Keys
    • Random values
    • Dictionaries
  • Get Keys with Prefix
    • Random values
    • Dictionaries
  • Longest Common Path
    • Random values
    • Dictionaries