This is my 5th time asking the same question, please be as thorough as possible.

ID: 666226 • Letter: T

Question

This is my 5th time asking the same question, please be as thorough as possible. I need my code revised/fixed/rewritten with comments that will help me understand the thinking process. The error I'm getting is the following..

ERROR MESSAGE:

terminating with uncaught exception of type std::bad_alloc: std::bad_alloc
make: *** [run] Aborted (core dumped)

The project:

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_HPP__
#define __AVL_TREE_HPP__
#include <iostream>

template <class K, class V>
class AVLNode {
   //default class variables/functions are set to private
   public:
       K key;
       V value;
       int balance_factor;

       AVLNode* left, *right, *parent;

       AVLNode(K k, V v, AVLNode* np) : key(k), value(v), balance_factor(0),
           left(NULL),right(NULL),parent(np) {}

       ~AVLNode(){
           delete right;
           delete left;}

};

template <class K, class V>
class AVLTree {
   public:
       //default constuctor
       AVLTree();
       //destructor
       ~AVLTree();
       //insert function
       bool insert(K key, V value);
       //lookup function
       V lookup(K key, AVLNode<K,V>* tree_root);
       //print function
       void printTree();

   private:
       //root node
       AVLNode<K,V>* root;
       //fix the balance factor of a node
       void fixBalance(AVLNode<K,V>* np);
       //returns the height of a node
       int findHeight(AVLNode<K,V>* np);
       //balances the node
       void balance(AVLNode<K,V>* np);
       //rotate functions
       AVLNode<K,V>* rotateRight(AVLNode<K,V>* nq);
       AVLNode<K,V>* rotateLeft(AVLNode<K,V>* nq);
       AVLNode<K,V>* leftRightRotate(AVLNode<K,V>* np);
       AVLNode<K,V>* rightLeftRotate(AVLNode<K,V>* np);

};
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;
}

//insert function here
template <class K,class V>
bool AVLTree<K,V>::insert(K key, V value) {
   if (root == NULL) {
        root = new AVLNode<K,V>(key, value, NULL);

    }
    else {
        AVLNode<K,V>
            *np = root,
            *parent;

        while (true) {

            if (np->key == key){
                return false;
           }
            parent = np;

            bool lookLeft = np->key > key;

            if (lookLeft){
               np = np->left;
           }
           else{
               np = np->right;
           }

            if (np == NULL) {
                if (lookLeft) {
                    parent->left = new AVLNode<K,V>(key, value, parent);

                }
                else {
                    parent->right = new AVLNode<K,V>(key, value, parent);

                }

                fixBalance(parent);
                break;
            }
        }
    }

}
//lookup function here
template <class K, class V>
V AVLTree<K,V>::lookup(K key, AVLNode<K,V>* tree_root){
   if (root == NULL){
       return 0;
   }
   else if (key < root->key){
       return lookup(key, root->left);
   }
   else if (key > root->key){
       return lookup(key, root->right);
   }
   else{
       return root->value;
   }

}

template <class K, class V>
void AVLTree<K,V>::printTree(){
std::cout << "I feel like I'm really close to having complete code but can't find the error in my code." << std::endl;
}

template <class K, class V>
int AVLTree<K,V>::findHeight(AVLNode<K,V>* np){
   if (np == NULL){
       return -1;
   }
   else {
       return 1 + std::max(findHeight(np->left), findHeight(np->right));
   }
}

template <class K, class V>
void AVLTree<K,V>::balance(AVLNode<K,V>* np){
np->balance_factor = findHeight(np->right) - findHeight(np->left);
}

template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rotateLeft(AVLNode<K,V>* nq){
   AVLNode<K,V>* np = nq->right;
   np->parent = nq->parent;
   nq->right = np->left;

   if (nq->right != NULL){
       nq->right->parent = nq;
   }
   np->left = nq;
   nq->parent = np;

   if (np->parent != NULL){
       if (np->parent->right == nq) {
           np->parent->right = np;
       }
       else {
           np->parent->left = np;
       }
   }
   balance(nq);
   balance(np);

   return np;
}

template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rotateRight(AVLNode<K,V>* nq){
   AVLNode<K,V>* np = nq->left;
   np->parent = nq->parent;
   nq->left = np->right;

   if (nq->left != NULL){
       nq->left->parent = nq;
   }
   np->right = nq;
   nq->parent = np;

   if (np->parent != NULL){
       if (np->parent->right == nq) {
           np->parent->right = np;
       }
       else {
           np->parent->left = np;
       }
   }
   balance(nq);
   balance(np);

   return np;
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::leftRightRotate(AVLNode<K,V>* np){
   np->left = rotateLeft(np->left);
   return rotateRight(np);
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rightLeftRotate(AVLNode<K,V>* np){
   np->right = rotateRight(np->right);
   return rotateLeft(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.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;
    tree.printTree();
    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);
        //problem with insert function, core dumped.
        tree.insert(employee_id,employee_name);
        //std::cout << "id: " << employee_id << " name: " << employee_name << std::endl;
        //need to find a node to plug into lookup parameters

        //std::cout << tree.lookup("6028220004", );
    }

    return 0;
}

Explanation / Answer

avl_tree.hpp

//AVL TREE
//should include insert, lookup, print
#ifndef __AVL_TREE_HPP__
#define __AVL_TREE_HPP__
#include <iostream>
template <class K, class V>
class AVLNode {
//default class variables/functions are set to private
public:
K key;
V value;
int balance_factor;

AVLNode* left, *right, *parent;

AVLNode(K k, V v, AVLNode* np) : key(k), value(v), balance_factor(0),
left(NULL),right(NULL),parent(np) {}

~AVLNode(){
delete right;
delete left;}

};
template <class K, class V>
class AVLTree {
public:
//default constuctor
AVLTree();
//destructor
~AVLTree();
//insert function
bool insert(K key, V value);
//lookup function
void lookup(K key,AVLNode<K,V>* tree_root);
//helper function for lookup
void lookup_utility(K key);
//print function
void printTree(AVLNode<K,V>* tree_root);
//helper function for printTree
       void print();

private:
//root node
AVLNode<K,V>* root;
//fix the balance factor of a node
void fixBalance(AVLNode<K,V>* np);
//returns the height of a node
int findHeight(AVLNode<K,V>* np);
//balances the node
void balance(AVLNode<K,V>* np);
//rotate functions
AVLNode<K,V>* rotateRight(AVLNode<K,V>* nq);
AVLNode<K,V>* rotateLeft(AVLNode<K,V>* nq);
AVLNode<K,V>* leftRightRotate(AVLNode<K,V>* np);
AVLNode<K,V>* rightLeftRotate(AVLNode<K,V>* np);

};
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;
}
//insert function here
template <class K,class V>
bool AVLTree<K,V>::insert(K key, V value) {
   //std::cout<<key<<" - "<<value;
if (root == NULL) {
root = new AVLNode<K,V>(key, value, NULL);

}
else {
AVLNode<K,V>
*np = root,
*parent;

while (true) {

if (np->key == key){
return false;
}
parent = np;

bool lookLeft = np->key > key;

if (lookLeft){
np = np->left;
}
else{
np = np->right;
}

if (np == NULL) {
if (lookLeft) {
parent->left = new AVLNode<K,V>(key, value, parent);

}
else {
parent->right = new AVLNode<K,V>(key, value, parent);

}

fixBalance(parent);
break;
}
}
}

}
//lookup function here
template <class K, class V>
void AVLTree<K,V>::lookup(K key,AVLNode<K,V>* tree_root)
{
if (tree_root == NULL){
return ;
}
if(key == tree_root->key){
std::cout<< " Employee: "<<tree_root->value<<" id: "<<tree_root->key;
return;
}
else if (key < tree_root->key){
lookup(key,tree_root->left);
}
else{
lookup(key, tree_root->right);
}

}

//it is utility function to call the lookup function, from main we can pass the id and root is a private member and therfore can only be accessed
//from the member functions. Changed the code so that it prints the corresponding value inside the function itself.
template <class K, class V>
void AVLTree<K,V>::lookup_utility(K key)
{
lookup(key,root);
}

template <class K, class V>
void AVLTree<K,V>::print()
{
printTree(root);
}

template <class K, class V>
void AVLTree<K,V>::printTree(AVLNode<K,V>* tree_root){
//std::cout << "I feel like I'm really close to having complete code but can't find the error in my code." << std::endl;
if (tree_root == NULL){
return ;
}
printTree(tree_root->left);
std::cout<< " Employee: "<<tree_root->value<<" id: "<<tree_root->key;
printTree(tree_root->right);
}

template <class K, class V>
void AVLTree<K,V>::fixBalance(AVLNode<K,V>* np){
balance(np);
if (np->balance_factor == 2){
if (findHeight(np->right->right) >= findHeight(np->right->left)){
np = rotateLeft(np);
}
else{
np = rightLeftRotate(np);
}
}
else if (np->balance_factor == -2) {
if (findHeight(np->left->left) >= findHeight(np->left->right)){
np = rotateRight(np);
}
else{
np = leftRightRotate(np);
}
}
if (np->parent != NULL) {
fixBalance(np->parent);
}
else {
root = np;
}
}
template <class K, class V>
int AVLTree<K,V>::findHeight(AVLNode<K,V>* np){
if (np == NULL){
return -1;
}
else {
return 1 + std::max(findHeight(np->left), findHeight(np->right));
}
}
template <class K, class V>
void AVLTree<K,V>::balance(AVLNode<K,V>* np){
np->balance_factor = findHeight(np->right) - findHeight(np->left);
}

template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rotateLeft(AVLNode<K,V>* nq){
AVLNode<K,V>* np = nq->right;
np->parent = nq->parent;
nq->right = np->left;

if (nq->right != NULL){
nq->right->parent = nq;
}
np->left = nq;
nq->parent = np;

if (np->parent != NULL){
if (np->parent->right == nq) {
np->parent->right = np;
}
else {
np->parent->left = np;
}
}
balance(nq);
balance(np);

return np;
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rotateRight(AVLNode<K,V>* nq){
AVLNode<K,V>* np = nq->left;
np->parent = nq->parent;
nq->left = np->right;

if (nq->left != NULL){
nq->left->parent = nq;
}
np->right = nq;
nq->parent = np;

if (np->parent != NULL){
if (np->parent->right == nq) {
np->parent->right = np;
}
else {
np->parent->left = np;
}
}
balance(nq);
balance(np);

return np;
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::leftRightRotate(AVLNode<K,V>* np){
np->left = rotateLeft(np->left);
return rotateRight(np);
}
template <class K, class V>
AVLNode<K,V>* AVLTree<K,V>::rightLeftRotate(AVLNode<K,V>* np){
np->right = rotateRight(np->right);
return rotateLeft(np);
}
#endi

main.cpp

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
// 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.hpp"
int main()
{
std::string file_name = "C:/Users/S.M/Documents/c++/employees.txt"; //path of file

//or you can keep the input file in the same folder, where the main.cpp is located and just put file name.
std::ifstream in_file(file_name.c_str());

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);
//problem with insert function, core dumped.
tree.insert(employee_id,employee_name);
//std::cout << "id: " << employee_id << " name: " << employee_name << std::endl;
//need to find a node to plug into lookup parameters
   }
std::cout << " printing the tree: ";
tree.print();
std::string id;
std::cout << " enter the id to be searched: ";
std::cin>>id;
std::cout<<" ***searching for the key in tree*** ";
       tree.lookup_utility(id);

return 0;
}

Navigate

This is my 4th time posting this. Please help me with the part (c) only. I know

This is my CREATBL.sql code CREATE TABLE JOB( JOB_CODE VARCHAR (9) NOT NULL, JOB

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

This is my 5th time asking the same question, please be as thorough as possible.

Question

Explanation / Answer

Related Questions

Navigate