Erica has just started her new software developer job at Initech. Her boss Bill
ID: 666006 • Letter: E
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 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 lookup and print method. 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. I would like for the reader to correct my code and write meaningful comments so I can understand the thinking process. In my code I have included comments on where I need help and the keyword "ERROR:" when an error occurs during compilation.
My code:
//AVL TREE
//should include insert, lookup, print
#ifndef __AVL_TREE_2_HPP__
#define __AVL_TREE_2_HPP__
#include <iostream>
//keeping track of balance_factor here
template <class K, class V>
struct AVLNode {
K key;
V value;
AVLNode *left, *right, *parent;
int balance_factor;
};
template <class K, class V>
class AVLTree{
public:
//default constructor
AVLTree();
//destructor
~AVLTree();
//insert function
void insert(V value, K key);
//put function that is used in the insert function
void put(AVLNode<K,V>* root, V value, K key);
//balance function to balance nodes
void balance(AVLNode<K,V>* root, K key);
//return height of node
int nodeHeight(AVLNode<K,V>* np);
//fix the nodeHeight
void fixNodeHeight(AVLNode<K,V>* np);
//rotate node right
//ERROR: invalid use of template-name 'AVLNode' without an argument list
AVLNode* rightRotate(AVLNode<K,V>* np);
//rotate node left
//ERROR: invalid use of template-name 'AVLNode' without an argument list
AVLNode* leftRotate(AVLNode<K,V>* np);
private:
//not sure if any private variables need to be initialized.
//need to make a head pointer point to NULL??
};
//not sure what to initialize in default constructor
template <class K, class V>
AVLTree<K,V>::AVLTree(){
//TODO
}
//no idea how to clear up memory once all functions are called.
template <class K, class V>
AVLTree<K,V>::~AVLTree(){
//TODO
}
//head is undefined,
template <class K, class V>
void AVLTree<K,V>::insert(V value, K key){
if (head == NULL) {
head = new AVLNode<K,V>(value,key);
}
else {
put(head,value,key);
}
}
template <class K, class V>
void AVLTree<K,V>::put(AVLNode<K,V>* root, V value, K key){
if (root->key > key) {
if (root->left != NULL){
put(root->left, value,key);
balance(root,key);
}
else{
root->left = new AVLNode<K,V>(value, key);
root->balance_factor = nodeHeight(root->left) - nodeHeight(root->right);
root->left->parent = root;
}
}
else {
if (root->right != NULL) {
put(root->right, value, key);
balance(root, key);
}
else {
root->right = new AVLNode<K,V>(value, key);
root->balance_factor = nodeHeight(root->left) - nodeHeight(root->right);
root->right->parent = root;
}
}
}
//definition of rotate functions
template <class K, class V>
void AVLTree<K,V>::balance(AVLNode<K,V>* root, K key) {
root->bf = nodeHeight(root->left) - nodeHeight(root->right);
if (root->balance_factor < -1 && key > root->right->key) {
std::cout << "here1 ";
leftRotate(root);
} else if (root->balance_factor > 1 && key < root->left->key) {
std::cout << "here2 ";
rightRotate(root);
} else if (root->balance_factor < -1 && key < root->right->key) {
rightRotate(root->right);
std::cout << "here3 ";
leftRotate(root);
} else if (root->balance_factor > 1 && key > root->left->key) {
leftRotate(root->left);
std::cout << "here4 ";
rightRotate(root);
}
}
template <class K, class V>
int AVLTree<K,V>:: nodeHeight(AVLNode<K,V>* np){
if (np){
return np->height;
}
else{
return 0;
}
}
template <class K, class V>
void AVLTree<K,V>::fixNodeHeight(AVLNode<K,V>* np) {
int leftHeight = nodeHeight(np->left);
int rightHeight = nodeHeight(np->right);
if (leftHeight > rightHeight) {
np->height = leftHeight+1;
}
else if (rightHeight >= leftHeight) {
np->height = rightHeight+1;
}
}
//ERROR: invalid use of template-name AVLNode without an argument list
AVLNode* AVLTree<K,V>::rightRotate(AVLNode<K,V>* np) {
AVLNode* nq = np->left;
np->left = nq->right;
nq->right = np;
fixNodeHeight(np);
fixNodeHeight(nq);
return q;
}
//ERROR: invalid use of template-name AVLNode without an argument list
AVLNode* AVLTree<K,V>::leftRotate(AVLNode<K,V>* nq) {
AVLNode* np = nq->left;
nq->right = nq->left;
np->left = nq;
fixNodeHeight(nq);
fixNodeHeight(np);
return np;
}
#endif
Thanks :)
Explanation / Answer
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.