Erica has just started her new software developer job at Initech. Her boss Bill

Question

Erica has just started her new software developer job at Initech. Her boss Bill wants her to write a map data structure for use at the company. This means she has no starter code to work with, but she does know the operations her coworkers want supported. They want to be able to insert and retrieve key value pairs like we did for our hash map, however they also want to be able to list all the key value pairs in sorted order by the keys. Because she needs to support retrieving the sorted order, Erica decided she would implement an AVL tree. To test her implementation she is planning to use her AVL tree to store the company's employee id number database.

Your AVL implementation must support at least three operations: insert, lookup, and print. The insert method should allow a user to insert a key value pair into the AVL tree. The lookup method should allow a user to lookup the value associated with a key. Finally the print method must print all of the key value pairs in sorted order one per line and separated with a comma.

To test out your AVL tree, we have provided the employee id data for Initech in the employee.txt file located in the data folder. Each line in the file consists of an employee's name and id number. Using your AVL tree insert the employees with their ids, lookup the id for a particular employee, and then use your print method to print them out in sorted order. The main.cpp file already contains code to parse this file.

Please help me solve this in C++ code. I have helper functions to help me get the height, balance factor and the different rotations to flip the nodes around. I have a struct AVLNode that looks like this:

template <class K, class V>
struct AVLNode {
   K key;
   V value;
   AVLNode* left, *right, *parent;
int height;
};

Then I am unsure as to how to create a AVLTree class that implements the different methods I need for my assignment. I'm not sure what I should intialize for the constructor, how to implement the insert method, etc. I have looked at more than 10 online resources. I have tried to put the knowledge I gather from these websites together, but I end up with code that I don't understand. Any help+ comments would be very much appreciated.

Thanks.

Explanation / Answer

}

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.