STL Compatible TRIE data structure implementation

Trie

Trie is nothing but a data structure in the form of a tree which is in turn used to retrieve data. Trie store value against a key which is a string, Since each character of a string gets a new node, Trie is also known as a prefix tree. Data in a Trie is stored in a lexographical order.

Tries offer retreival of data against a string in O(M) where M is the key size unlike binary tree which takes O(M * log(N)) where N is the total number of keys stored.

There are certain memory optimized data structures derived from TRIE such as TSTs but this project deals only with TRIEs.

Navigate

• Trie
• Navigate
• Reference
  • Constructor
  • Insert
  • Exist
  • Empty
  • Iterator
    • Begin iterator
    • End iterator
    • Reverse Begin iterator
    • Reverse End iterator
  • Find
• Copyright & License

Image Courtesy: Article

Reference

Constructor trie<T>()

T -> std::string || char* || char[]

Constructor function returns a reference to newly initialized trie data structure.

#include <string>
#include <trie>

int main() {
  trie<std::string> t; // Default Constructor
  return 0;
}

or

#include <string>
#include <trie>

int main() {
  trie<std::string> t = *(new trie<std::string>());
  return 0;
}

Insert: void trie<T>::insert(std::string key, T value)

Insert member function is used to insert key & value into the trie data structure.

#include <string>
#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  std::string s = "helloworld";
  t.insert(s, 11);
  return 0;
}

Exist: bool trie<T>::exist(std::string key)

Exist member function is used to check existence of a key in the trie data structure.

#include <string>
#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  std::string s = "helloworld";
  t.insert(s, 11);
  t.exist(s); // true
  t.exist("hello"); // false
  return 0;
}

Empty: bool trie<T>::empty()

Return true/false depending on if the data structure is empty or not.

#include <string>
#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  std::string s = "helloworld";
  t.empty(); // true;
  t.insert(s, 11);
  t.empty(); // false
  return 0;
}

Iterator: trie<T>::iterator

Iterators are a very important part of STL. Trie project also has iterators to support the same.

#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  trie<std::int>::iterator it;
  return 0;
}

Begin iterator: typename trie<T>::iterator trie<T>::begin()

Points to the beginning of the data structure.

#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  trie<std::int>::iterator it = t.begin();
  return 0;
}

End iterator: typename trie<T>::iterator trie<T>::end()

Points to end of the data structure.

#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  trie<std::int>::iterator it = t.end();
  return 0;
}

Note: If Trie is empty begin == end

Reverse Begin iterator: typename trie<T>::iterator trie<T>::rbegin()

Points to the last element of the data structure.

#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  trie<std::int>::iterator it = t.rbegin();
  return 0;
}

Reverse End iterator: typename trie<T>::iterator trie<T>::rend()

Points to reverse end of the data structure. Used by reverse begin iterator to find the end.

#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  trie<std::int>::iterator it = t.rend();
  return 0;
}

Note: If Trie is empty rbegin == rend

PS: Iterators can both be incremented and decremented.

Find: typename trie<T>::iterator trie<T>::find(std::string key)

Find is used to search and return iterator pointing to that particular key. If key is not present find returns end iterator.

#include <iostream>
#include <string>
#include <trie>

int main() {
  trie<std::int> t; // Default Constructor
  std::string s = "helloworld";
  t.insert(s, 11);
  trie<std::int>::iterator it = t.find(s);
  std::cout << *it; // 11
  return 0;
}

Copyright & License

MIT License

Copyright (c) 2019 Akshit Grover