This is my 3rd time asking the same question, I will not thumbs up the same pers
ID: 666160 • Letter: T
Question
This is my 3rd time asking the same question, I will not thumbs up the same person that answered the question twice.
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.
More notes
As we discussed in class, an AVL tree is a type of binary seach tree that uses tree rotations to keep itself from becoming very unbalanced. A good way to start this project would be to write a binary search tree. Once you have those working properly you can begin implementing the more complicated AVL tree methods. In your tree node struct, I recommend having a left, right, and parent node pointer; a key and a value; and a height or balance factor. Be careful in your pointer code. Maintaining the pointers when performing rotations can be tricky.'
Insertiong into an AVL tree, starts by inserting the key following the normal binary search tree strategy: compare to the current node and recurse into the proper subtree based on the result. After creating the new node, the path from the new node to the root is traversed and at any node with a balance factor other than -1, 0, or +1 a rotation is performed to fix it. If you implemented your insertion method recursively, then the recursive calls can be used todo this traversal. If you implemented your insertion iteratively, then you can follow your parent pointers to travel to the root node.
Lookup in an AVL tree, is the exact same as in a normal binary search tree. To implement the print method, you should write an inorder traversal of the tree.
I will provide the main.cpp and avl_tree.hpp files that I need help correcting. I am looking for help completing my code and comments that will help me understand the principles behind the logic.
CODE:
avl_tree_2.hpp
//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>
class AVLNode {
public:
K key;
V value;
AVLNode *left, *right, *parent;
//change functions to match balance factor
int balance_factor;
AVLNode(K k, V v, AVLNode* np) : key(k), value(v),
left(NULL),right(NULL),parent(np), balance_factor(0) {}
~AVLNode(){
delete right;
delete left;}
};
template <class K, class V>
class AVLTree{
public:
//default constructor
AVLTree();
//destructor
~AVLTree();
//lookup function
V lookup(AVLTree tree,K key);
//print inOrder traversal of tree
void printTree();
//insert function
void insert(K key, V value);
//put function that is used in the insert function
void put(AVLNode<K,V>* root, K key, V value);
//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
int fixNodeHeight(AVLNode<K,V>* np);
//set balance factor
void setBalance(AVLNode<K,V>* np);
//rotate node right
AVLNode<K,V>* rightRotate(AVLNode<K,V>* np);
//rotate node left
AVLNode<K,V>* leftRotate(AVLNode<K,V>* np);
private:
//not sure if any private variables need to be initialized.
AVLNode<K,V>* root;
};
//not sure what to initialize in default constructor
template <class K, class V>
AVLTree<K,V>::AVLTree(): root(NULL){
}
//no idea how to clear up memory once all functions are called.
template <class K, class V>
AVLTree<K,V>::~AVLTree(){
delete root;
}
//lookup function here
template <class K, class V>
V AVLTree<K,V>::lookup(AVLTree tree, K key){
if (tree.root == NULL){
return 0;
}
else if (key < tree.root->key){
return lookup(key, tree.root->left);
}
else if (key > tree.root->key){
return lookup(key, tree.root->right);
}
else{
return tree.root->value;
}
}
//print in sorted inOrder traversal
template <class K, class V>
void AVLTree<K,V>::printTree(){
//TODO
}
template <class K, class V>
void AVLTree<K,V>::insert(K key, V value){
if (root == NULL) {
root = new AVLNode<K,V>(key,value,NULL);
}
else {
put(root,key,value);
}
}
template <class K, class V>
void AVLTree<K,V>::put(AVLNode<K,V>* root, K key, V value){
if (root->key > key) {
if (root->left != NULL){
put(root->left, key,value);
balance(root,key);
}
else{
root->left = new AVLNode<K,V>(key, value, NULL);
root->balance_factor = nodeHeight(root->left) - nodeHeight(root->right);
root->left->parent = root;
}
}
else {
if (root->right != NULL) {
put(root->right, key, value);
balance(root, key);
}
else {
root->right = new AVLNode<K,V>(key, value, NULL);
root->balance_factor = nodeHeight(root->left) - nodeHeight(root->right);
root->right->parent = root;
}
}
}
//definition of rotate functions
//redundancies here
template <class K, class V>
void AVLTree<K,V>::balance(AVLNode<K,V>* root, K key) {
setBalance(root);
//root->balance_factor = 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);
}
}
//more redundancy
template <class K, class V>
int AVLTree<K,V>:: nodeHeight(AVLNode<K,V>* np){
if (np){
return fixNodeHeight(np);
}
else{
return 0;
}
}
//more redundancy
template <class K, class V>
int AVLTree<K,V>::fixNodeHeight(AVLNode<K,V>* np) {
if (np == NULL){
return -1;
}
else{
return 1 + std::max(fixNodeHeight(np->left), fixNodeHeight(np->right));
}
}
//NEW function
//more redundancy
template <class K, class V>
void AVLTree<K,V>::setBalance(AVLNode<K,V>* np){
np->balance_factor = fixNodeHeight(np->right) - fixNodeHeight(np->left);
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rightRotate(AVLNode<K,V>* np) {
AVLNode<K,V>* nq = np->left;
np->left = nq->right;
nq->right = np;
setBalance(np);
setBalance(nq);
return nq;
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::leftRotate(AVLNode<K,V>* nq) {
AVLNode<K,V>* np = nq->left;
nq->right = nq->left;
np->left = nq;
setBalance(nq);
setBalance(np);
return np;
}
#endif
main.cpp
// ICS/CSE 46 Summer 2015
// Project 3
//
// This file parses the employee id file. You will edit this to
// add the employees with their ids to your AVL tree, perform a lookup
// of an employee, and print the employees with their ids in sorted order.
//
#include <fstream>
#include "avl_tree_2.hpp"
int main()
{
std::string file_name = "data/employees.txt";
std::ifstream in_file(file_name);
AVLTree<std::string, std::string> tree;
//Parse the employee names and idss out of the text file
std::string line;
while(std::getline(in_file,line))
{
// Gets the employees name
std::string employee_name = line.substr(0,line.find(","));
// Gets the employees id number
std::string employee_id = line.substr(line.find(",")+1);
//insert function causes program to fail after a delay
tree.insert(employee_id,employee_name);
//std::cout << "id: " << employee_id << " name: " << employee_name << std::endl;
//std::cout << tree.lookup(tree, "6028220004");
}
return 0;
}
Explanation / Answer
void AvL<T>::insert(string val, T k)
{
if (head == NULL)
{
head = new AvLNode<T>(val, k);
}
Else//Condition starts
{
put(head, val, k);
}
template <class T>
void AvL<T>::put(AvLNode<T>* root,string val,T key1)
{
if (root->key > key1)//Condition
{
if (root->left != NULL)
{
put(root->left, val, key1);
Balance(root, key1);
}
else
{
root->left = new AvLNode<T>(val, key1);
root->bf = nodeHeight(root->left) - nodeHeight(root->right);
root->left->parent = root;
}
}
Else
{
if (root->right != NULL)
{
put(root->right, val, key1);
Balance(root, key1);
}
Else
{
root->right = new AvLNode<T>(val, key1);
root->bf = nodeHeight(root->left) - nodeHeight(root->right);
root->right->parent = root;
}
}
template<class T>
void AvL<T>::Balance(AvLNode<T>* root, T key1)
{
root->bf = nodeHeight(root->left) - nodeHeight(root->right);
if (root->bf < -1 && key1 > root->right->key)
{
cout << "here1 ";
LeftRotate(root);
}
else if (root->bf > 1 && key1 < root->left->key)
{
cout << "here2 ";//Get the input values
RightRotate(root);
}
else if (root->bf < -1 && key1 < root->right->key)
{
RightRotate(root->right);
cout << "here3 ";
LeftRotate(root);
}
else if (root->bf > 1 && key1 > root->left->key)
{
LeftRotate(root->left);
cout << "here4 ";
RightRotate(root);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.