Here, youll improve your implementation, replacing the file-based dictionary construction with one-at-a-time insertion. This allows creating dictionaries in any order, and on-the-fly word additions (like when a user adds their name or address to the dictionary). Individual insertions must take O(log(n)) time and all other operations must maintain their efficiency. To achieve this, youll need to use a self-balancing BST - namely an AVL tree.

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//autocompleter.h

#ifndef AUTOCOMPLETER_H #define AUTOCOMPLETER_H #include  #include  using namespace std; class Autocompleter { // For the mandatory running times below: // n is the number of strings in the dictionary. // Assume that the length of every string is O(1). public: // Creates a new Autocompleter with an empty dictionary. // // Must run in O(1) time. Autocompleter(); // Adds a string x to the dictionary. // If x is already in the dictionary, does nothing. // // Must run in O(log(n)) time. void insert(string x, int freq); // Returns the number of strings in the dictionary // of possible completions. // // Must run in O(n) 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(log(n) + k) time, // where k is the number of completions of x in the dictionary. 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 binary search tree node. class Node { public: Node() { height = 0; left = right = nullptr; } Node(Entry e) { this->e = e; height = -1; left = right = nullptr; } Entry e; int height; Node* left; Node* right; }; // A convenience method for getting the height of a subtree. // Useful for rebalance(). static int height(Node* root) { if (root == nullptr) return -1; return root->height; } // Root of the binary-search-tree-based data structure Node* root; // Optional helper methods (you'll probably want them) // Returns the size of the binary tree rooted at root. // // Should run in O(n) time. int size_recurse(Node* root); // Fills C with the completions of x in the BST rooted at root. // // Should run in O(log(n) + k), where // -n is the size of the BST rooted at root. // -k is the number of Entrys in the BST rooted at root // whose strings start with x. void completions_recurse(string x, Node* root, vector &C); // Inserts an Entry into an AVL tree rooted at root. // // Should run in O(log(n)) time. void insert_recurse(Entry e, Node* root); // Rebalances the AVL tree rooted at root. // Helpful for insert(). // Should be called on every node visited during // the search in reverse search order. // // Should run in O(1) time. void rebalance(Node* root); // Perform left and right rotations around the root // of an AVL tree (helpful for implementing rebalance). // // Should run in O(1) time. void right_rotate(Node* root); void left_rotate(Node* root); }; #endif 

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//main.cpp

#include  #include  #include  #include  #include  #include  #include "autocompleter.h" using namespace std; inline void _test(const char* expression, const char* file, int line) { cerr  C; while (cin) { string line; getline(cin, line); words.completions(line, C); for (string s : C) cout  R; // Test constructor and size() Autocompleter animals; test(animals.size() == 0); animals.insert("aardvark", 629356); animals.insert("albatross", 553191); animals.insert("alpaca", 852363); animals.insert("armadillo", 393754); animals.insert("crow", 4592109); animals.insert("crocodile", 1658300); animals.insert("cat", 46839855); animals.insert("camel", 11005001); animals.insert("goat", 5231735); animals.insert("gorilla", 1931906); animals.insert("goose", 3739382); animals.insert("goatfish", 19984); animals.insert("giraffe", 978584); test(animals.size() == 13); Autocompleter words; test(words.size() == 0); ifstream f; f.open("words2.txt"); assert(f.is_open()); // If this fails, you're missing words2.txt string line; while (getline(f, line)) { words.insert(line.substr(0, line.find(" ")), stoi(line.substr(line.find(" ")+1))); } f.close(); test(words.size() == 293147); // Test insert() and size() animals.insert("buffalo", 17808542); test(animals.size() == 14); animals.insert("deer", 10007644); test(animals.size() == 15); animals.insert("horse", 58453720); test(animals.size() == 16); animals.insert("bullfrog", 273571); test(animals.size() == 17); // Test completions() animals.completions("a", R); test(R.size() == 3); test(R[0] == "alpaca"); test(R[1] == "aardvark"); test(R[2] == "albatross"); animals.completions("b", R); test(R.size() == 2); test(R[0] == "buffalo"); test(R[1] == "bullfrog"); animals.completions("c", R); test(R.size() == 3); test(R[0] == "cat"); test(R[1] == "camel"); test(R[2] == "crow"); animals.completions("d", R); test(R.size() == 1); test(R[0] == "deer"); animals.completions("e", R); test(R.size() == 0); animals.completions("f", R); test(R.size() == 0); animals.completions("g", R); test(R.size() == 3); test(R[0] == "goat"); test(R[1] == "goose"); test(R[2] == "gorilla"); animals.completions("h", R); test(R.size() == 1); test(R[0] == "horse"); animals.completions("aa", R); test(R.size() == 1); test(R[0] == "aardvark"); animals.completions("al", R); test(R.size() == 2); test(R[0] == "alpaca"); test(R[1] == "albatross"); animals.completions("an", R); test(R.size() == 0); animals.completions("bo", R); test(R.size() == 0); animals.completions("da", R); test(R.size() == 0); animals.completions("de", R); test(R.size() == 1); test(R[0] == "deer"); animals.completions("go", R); test(R.size() == 3); test(R[0] == "goat"); test(R[1] == "goose"); test(R[2] == "gorilla"); animals.completions("cro", R); test(R.size() == 2); test(R[0] == "crow"); test(R[1] == "crocodile"); animals.completions("goat", R); test(R.size() == 2); test(R[0] == "goat"); test(R[1] == "goatfish"); animals.completions("gir", R); test(R.size() == 1); test(R[0] == "giraffe"); animals.completions("croc", R); test(R.size() == 1); test(R[0] == "crocodile"); animals.completions("crow", R); test(R.size() == 1); test(R[0] == "crow"); animals.completions("", R); test(R.size() == 3); test(R[0] == "horse"); test(R[1] == "cat"); test(R[2] == "buffalo"); animals.completions("CAT", R); test(R.size() == 0); animals.completions("cAt", R); test(R.size() == 0); animals.completions("giraffez", R); test(R.size() == 0); animals.completions("robotron", R); test(R.size() == 0); animals.completions("Y", R); test(R.size() == 0); animals.completions("YOLO", R); test(R.size() == 0); animals.completions("!error", R); test(R.size() == 0); words.completions("a", R); test(R.size() == 3); test(R[0] == "and"); test(R[1] == "a"); test(R[2] == "are"); words.completions("b", R); test(R.size() == 3); test(R[0] == "by"); test(R[1] == "be"); test(R[2] == "but"); words.completions("c", R); test(R.size() == 3); test(R[0] == "can"); test(R[1] == "contact"); test(R[2] == "click"); words.completions("!", R); test(R.size() == 0); words.completions("ba", R); test(R.size() == 3); test(R[0] == "back"); test(R[1] == "based"); test(R[2] == "baby"); words.completions("be", R); test(R.size() == 3); test(R[0] == "be"); test(R[1] == "been"); test(R[2] == "best"); words.completions("th", R); test(R.size() == 3); test(R[0] == "the"); test(R[1] == "that"); test(R[2] == "this"); words.completions("aft", R); test(R.size() == 3); test(R[0] == "after"); test(R[1] == "afternoon"); test(R[2] == "afterwards"); words.completions("cat", R); test(R.size() == 3); test(R[0] == "categories"); test(R[1] == "category"); test(R[2] == "catalog"); words.completions("syz", R); test(R.size() == 3); test(R[0] == "syzygy"); test(R[1] == "syzygium"); test(R[2] == "syzhthsh"); words.completions("sy$", R); test(R.size() == 0); words.completions("bird", R); test(R.size() == 3); test(R[0] == "bird"); test(R[1] == "birds"); test(R[2] == "birding"); words.completions("hola", R); test(R.size() == 3); test(R[0] == "hola"); test(R[1] == "holabird"); test(R[2] == "holanda"); words.completions("word", R); test(R.size() == 3); test(R[0] == "word"); test(R[1] == "words"); test(R[2] == "wordpress"); words.completions("birdz", R); test(R.size() == 0); words.completions("yello", R); test(R.size() == 3); test(R[0] == "yellow"); test(R[1] == "yellowstone"); test(R[2] == "yellowpages"); cout  
 ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
//words2.text (small sample below, full text can be obtained at http://andrewwinslow.com/3333/hwAC2/words2.txt)
 
a 908117 aa 3052 aaa 1024 aaaa 159 aaaah 5 aaaai 3 aaaargh 1 aaab 2 aaabooksearch 2 aaac 3 aaace 6 aaacn 16 aaae 5 aaah 14 aaahh 2 aaahhh 2 aaai 25 aaal 2 aaalac 1 aaand 2 aaap 1 aaargh 4 aaas 41 aaasc 2 aaat 1 aab 33 aaba 4 aabb 9 aabbccdd 5 aabc 3 aaberg 1 aabt 2 aac 250 aaca 6 aacap 2 aacc 23 aacd 1 aace 11 aach 1 aachen 75 aaci 1 aacn 7 aacp 4 aacplus 2 aacr 6 aacraid 3 aacrao 2 aacs 12 aacsb 13 aact 2 aacte 1 aacute 8 aad 38 aada 1 aadac 2 aadc 4 aadd 3 aade 3 aadl 2 aads 2 aadt 6 aadult 2 aadvantage 18 aae 17 aaea 3 aaec 3 aaem 2 aaene 4 aaeon 8 aaep 1 aaf 31 aafa 2 aafc 10 aafco 2 aafes 8 aafp 17 aag 47 aagaard 4 aagard 1 aage 5 aah 33 aaha 2 aahe 3 aahh 2 aahhh 1 aahperd 2 aahs 2 aahsa 3 aahz 4 aai 28 aaia 2 aaid 7 aais 2 aaj 41 aaja 4 aajtk 3 aak 8 aakash 2
  The following files have been given to you: 1. A C++ header file (autocompleter.h) declaring the Autocompleter class. 2. A C++ source file (main.cpp) containing a main function with tests. 3. A text file (words2.txt) containing 293147 common English words and their frequencies. Download the files at http://andrewwinslow.com/3333/hwAC2/. Create a new C++source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocom- pleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file autocompleter.cpp.  The following files have been given to you: 1. A C++ header file (autocompleter.h) declaring the Autocompleter class. 2. A C++ source file (main.cpp) containing a main function with tests. 3. A text file (words2.txt) containing 293147 common English words and their frequencies. Download the files at http://andrewwinslow.com/3333/hwAC2/. Create a new C++source file named autocompleter.cpp that implements the class declared in autocompleter.h, so that autocom- pleter.cpp and the provided files compile into a program that runs with no failed tests. Submit the source file autocompleter.cpp