Implement the following trie/radix tree/suffix tree using only the included preprocessors with the running times listed #include  #include  using namespace std; class Trie { // For the mandatory running times below: // Assume that the length of every string is O(1). public: // Creates a new trie with an empty dictionary. // Must run in O(1) time. Trie(); // Adds a string x to the dictionary. // If x is already in the dictionary, does nothing. // Must run in O(1) time. void insert(string x, int freq); // Returns the number of strings in the dictionary. // Must run in O(1) time. int size(); // Fills the vector T with the three most-frequent completions of x. // If x has less than three completions, then // T is filled with all completions of x. // The completions appear in T from most to least frequent. // // Must run in O(1) time. void completions(string x, vector &T); private: // A helper class that stores a string and a frequency. class Entry { public: string s; int freq; }; // A helper class that implements a trie node. class Node { public: Node() { this->marked = false; for (int i = 0; i < 256; ++i) children[i] = nullptr; } bool marked; vector top; Node* children[256]; }; // Root of the trie-based data structure Node* root; // Number of marked nodes in the trie-based data structure int count; };