Data Analysis using Binary Search Trees IN C++ For this assignment you are imple
ID: 3707283 • Letter: D
Question
Data Analysis using Binary Search Trees IN C++
For this assignment you are implementing a system for detecting trends in consumer products over a 48 hour period. We are interested in knowing which products are purchased and sold, the least and most, by various retail stores throughout the United States. When a product is tagged as purchased it indicates that a certain retail store bought units of the product from a supplier. When a product is tagged as sold it indicates that a certain retail store sold that many units of a product. Your system must read product data from a .csv file, and store the data in a way that inserts data in better than linear time (O(n)) in most cases. Since, a binary search tree (BST) is a reasonably efficient data structure for inserting and searching data (O (log n) for balanced trees), you must create two BSTs; one tree represents the products that were sold and the other tree represents the products that were bought. The system must leverage the organization of the trees to display, which products were least bought and sold, and which were most bought and sold for that 48 hour period. Your system is only required to output the following to the screen:
The contents of the two BSTs, which will be printed in order
The product that type and number of units that sold the most
The product that type and number of units that sold the least
The product that type and number of units that were purchased the most
The product that type and number of units that were purchased the least
Class Design:
For this assignment you are required to implement a dynamically linked binary search tree. You will first need to start by defining an abstract base class Node, which encapsulates the following:
Data members:
# mData : std::string // # denotes protected
# mpLeft : Node *
# mpRight : Node *
Member functions:
+ virtual destructor // + denotes public
+ constructor which accepts a string to set the data in the node; each pointer in the node is set to NULL
+ setters – one for each data member (3 total should be defined)
+ getters – one for each data member (3 total should be defined, the 2 defined to get the pointers should return a reference to the pointer, i.e. Node *&)
+ pure virtual printData () function, which must be overridden in class TransactionNode
Next define a class TransactionNode, which publically inherits from abstract base class Node. Class TransactionNode must encapsulate the following:
New Data members:
- mUnits : int // - denotes private
New Member functions:
+ destructor // + denotes public
+ constructor which accepts a string to set the data and an integer to set the number of units in the node; should invoke class Node’s constructor
+ setter
+ getter
+ printData (), which overrides the pure virtual function in class Node
Now define a class BST, which encapsulates the following:
Data members:
- mpRoot : Node * // yes, we want a pointer to a Node, not TransactionNode here!
Member functions:
+ destructor // calls destroyTree ()
- destroyTree () // yes, it’s private, and it should visit each node in postOrder to delete them
+ default constructor
+ setter
+ getter
+ insert () // public used to hide pointer information, i.e. won’t pass in the root of the tree into this function, only the private insert () function
- insert () // yes, it’s private, and it dynamically allocates a TransactionNode and inserts recursively in the correct subtree based on mUnits; should pass in a reference to a pointer (i.e. Node *& pT)
+ inOrderTraversal () // yes, once again it’s private to hide pointer information
- inOrderTraversal (), which recursively visits and prints the contents (mData and mUnits) of each node in the tree in order; each node’s printData () should be called
contents should be printed on a separate line; must call the printData () function associated with the TransactionNode
+ findSmallest (), which returns a reference to a TransactionNode (i.e TransactionNode &) with the smallest mUnits
+ findLargest (), which returns a reference to a TransactionNode with the largest mUnits
Lastly, define a class DataAnalysis, which encapsulates the following:
Data members:
- mTreeSold : BST
- mTreePurchased : BST
- mCsvStream : ifstream
Member functions:
- A function that opens data.csv // yes, it’s private, and must use mCsvStream to open the file
- A function that reads one line from the file and splits the line into units, type, and transaction fields
- A function that loops until all lines are read from the file; calls the function below, and then displays the current contents of both BSTs; use inOrderTraversal () to display the trees
- A function that compares the transaction field and inserts the units and type into the appropriate tree (mTreeSold or mTreePurchased) // note with the way the data.csv file is organized the trees will be fairly balanced
- A function that writes to the screen the trends we see in our tree; the function must display the type and number of units that are least purchased and sold, and the most purchased and sold
+ runAnalysis (), which is the only public function in the class, aside from possibly a constructor and/or destructor; this function calls the other private functions
What should go in main ()?
DataAnalysis obj;
obj.runAnalysis ();
Explanation / Answer
CODING:
main.cpp
-----------------------------------------------------------------
#include "DataAnalysis.h"
int main()
{
DataAnalysis start;
start.runAnalysis();
return 0;
}
---------------------------------------------------------------
DataAnalysis.cpp
----------------------------------------
#include "DataAnalysis.h"
DataAnalysis::DataAnalysis()
{
}
DataAnalysis::~DataAnalysis()
{
}
//opens the .csv file to read from
void DataAnalysis::openFile()
{
csvFile.open("data.csv", ios::in);
if (csvFile.is_open())
{
readFile();
}
else
cout << "Unable to open your file";
}
//reads the file one line at a time until EOF
void DataAnalysis::readFile()
{
string header; //read in the header
std::getline(csvFile, header);
while (!csvFile.eof())
{
string units; //read in units
std::getline(csvFile, units, ',');
int numUnits = 0;
numUnits = atoi(units.c_str()); //convert the string units to an int amount of units
string type; //read in type
std::getline(csvFile, type, ',');
string transaction; //read in transaction
std::getline(csvFile, transaction, ' ');
insertDataFromFile(numUnits, type, transaction);
}
}
//analyzes transaction type and inserts the units and type into the proper tree
void DataAnalysis::insertDataFromFile(int units, string type, string transaction)
{
if (transaction == "Purchased") //if what was read from file was transaction type purchase, insert into purchase BST
{
mTreePurchased.insertInBST(units, type);
}
else if (transaction == "Sold")
{
mTreeSold.insertInBST(units, type);
}
}
//displays the trees, least purchased and sold, most purchased and sold
void DataAnalysis::displayTree()
{
cout << "Purchased information: " << endl;
cout << "--------------------" << endl;
cout << "Largest: " << endl;
mTreePurchased.findLargest(mTreePurchased.getRoot());
cout << "Smallest: " << endl;
mTreePurchased.findSmallest(mTreePurchased.getRoot());
cout << "All purchased units: " << endl;
mTreePurchased.inOrderTraversal();
cout << endl;
cout << "Sold information: " << endl;
cout << "--------------------" << endl;
cout << "Largest: " << endl;
mTreeSold.findLargest(mTreeSold.getRoot());
cout << "Smallest: " << endl;
mTreeSold.findSmallest(mTreeSold.getRoot());
cout << "All sold units: " << endl;
mTreeSold.inOrderTraversal();
}
//runs entire program
void DataAnalysis::runAnalysis()
{
openFile(); //open the file for reading
readFile(); //read from file, insert into proper tree
displayTree(); //dislay the smallest units/type and largest units/type
csvFile.close(); //close the file
}
-------------------------------------------------------------------------------------------------
DataAnalysis.h
------------------------------------------------
#pragma once
#include "BST.h"
#include "TransactionNode.h"
#include "Node.h"
class DataAnalysis
{
BST mTreeSold;
BST mTreePurchased;
ifstream csvFile;
void openFile();
void readFile();
void insertDataFromFile(int units, string type, string transaction);
void displayTree();
public:
DataAnalysis();
~DataAnalysis();
//run program
void runAnalysis();
};
------------------------------------------------------------------------------------------------
BST.cpp
--------------------------------------------------
#include "BST.h"
BST::BST()
{
mpRoot = nullptr;
}
BST::~BST()
{
//call private function
destroyTree(mpRoot);
}
void BST::setMpRoot(Node *newRoot)
{
mpRoot = newRoot;
}
Node *& BST::getRoot()
{
return mpRoot;
}
void BST::inOrderTraversal()
{
inOrderTraversal(mpRoot);
}
void BST::insertInBST(int mUnits, string mData)
{
insertInBST(mpRoot, mUnits, mData); //calling private insert to protect root
}
TransactionNode & BST::findSmallest(Node *root)
{
TransactionNode *pMem = dynamic_cast<TransactionNode *>(root);
//traverse tree to as far left as possible
if (pMem->getMpLeft() != nullptr)
{
return findSmallest(pMem->getMpLeft());
}
cout << *(pMem);
return *(pMem);
}
TransactionNode & BST::findLargest(Node *root)
{
TransactionNode *pMem = dynamic_cast<TransactionNode *>(root);
//traverse tree to as far left as possible
if (pMem->getMpRight() != nullptr)
{
return findLargest(pMem->getMpRight());
}
cout << *(pMem);
return *(pMem);
}
//PRIVATE FUNCTIONS
void BST::destroyTree(Node *root)
{
if (root != nullptr)
{
destroyTree(root->getMpLeft()); //go as far left as possible
destroyTree(root->getMpRight()); //go as far right as possible
delete root; //delete
}
}
void BST::insertInBST(Node *& root, int mUnits, string mData)
{
TransactionNode *pMem = dynamic_cast<TransactionNode *>(root); //cast Node *root to TransactionNode which is now pMem
//check for empty list
if (root == nullptr)
{
//set root to first insert
pMem = new TransactionNode(mUnits, mData);
root = pMem;
}
else //tree is not empty
{
if (mUnits < pMem->getUnits())
{
//go left
insertInBST(pMem->getMpLeft(), mUnits, mData);
}
else if (mUnits > pMem->getUnits())
{
//go right
insertInBST(pMem->getMpRight(), mUnits, mData);
}
}
}
void BST::inOrderTraversal(Node *root)
{
TransactionNode *pMem = dynamic_cast<TransactionNode *>(root);
if (pMem != nullptr)
{
inOrderTraversal(pMem->getMpLeft());
cout << "Item: " << pMem->getData() << endl;
cout << "Units: " << pMem->getUnits() << endl;
inOrderTraversal(pMem->getMpRight());
}
}
ostream & operator<<(ostream &lhs, TransactionNode & rhs)
{
lhs << rhs.getData() << endl << rhs.getUnits() << endl;
return lhs;
}
-----------------------------------------------------------------------------------------
BST.h
-----------------------------------------------
#pragma once
#include "Node.h"
#include "TransactionNode.h"
class BST
{
Node *mpRoot;
void destroyTree(Node *root);
void insertInBST(Node *& root, int mUnits, string mData);
void inOrderTraversal(Node *root);
public:
BST();
~BST();
//setters
void setMpRoot(Node *newRoot);
//getters
Node *& getRoot();
void inOrderTraversal();
TransactionNode & findSmallest(Node *root);
TransactionNode & findLargest(Node *root);
void insertInBST(int mUnits, string mData);
};
ostream & operator<<(ostream &lhs, TransactionNode & rhs);
---------------------------------------------------------------------------------------------
Node.cpp
--------------------------------------------------
#include "Node.h"
Node::Node(string newData)
{
mData = newData;
mpLeft = nullptr;
mpRight = nullptr;
}
Node::Node(Node ©)
{
mData = copy.mData;
mpLeft = copy.mpLeft;
mpRight = copy.mpRight;
}
Node::~Node()
{
}
//setters
void Node::setMpLeft(Node *&newMpLeft)
{
mpLeft = newMpLeft;
}
void Node::setMpRight(Node *&newMpRight)
{
mpRight = newMpRight;
}
void Node::setData(const string newData)
{
mData = newData;
}
//getters
Node *& Node::getMpLeft()
{
return mpLeft;
}
Node *& Node::getMpRight()
{
return mpRight;
}
string Node::getData() const
{
return mData;
}
void Node::printData()
{
cout << mData << endl;
}
----------------------------------------------------------------------------------------------------
Node.h
-------------------------------------------------
#include "Node.h"
Node::Node(string newData)
{
mData = newData;
mpLeft = nullptr;
mpRight = nullptr;
}
Node::Node(Node ©)
{
mData = copy.mData;
mpLeft = copy.mpLeft;
mpRight = copy.mpRight;
}
Node::~Node()
{
}
//setters
void Node::setMpLeft(Node *&newMpLeft)
{
mpLeft = newMpLeft;
}
void Node::setMpRight(Node *&newMpRight)
{
mpRight = newMpRight;
}
void Node::setData(const string newData)
{
mData = newData;
}
//getters
Node *& Node::getMpLeft()
{
return mpLeft;
}
Node *& Node::getMpRight()
{
return mpRight;
}
string Node::getData() const
{
return mData;
}
void Node::printData()
{
cout << mData << endl;
}
--------------------------------------------------------------------------------------
TransactionNode.cpp
----------------------------------------------------
#include "TransactionNode.h"
TransactionNode::TransactionNode(int newUnits, string newData) : Node(newData)
{
mUnits = newUnits;
}
TransactionNode::~TransactionNode()
{
}
void TransactionNode::setUnits(const int newUnits)
{
mUnits = newUnits;
}
int TransactionNode::getUnits() const
{
return mUnits;
}
void TransactionNode::printData()
{
cout << "Type: " << mData << endl << "Units: " << mUnits << endl;
}
----------------------------------------------------------------------------------------
TransactionNode.h
---------------------------------------------------
#pragma once
#include "Node.h"
class TransactionNode : public Node
{
int mUnits;
public:
TransactionNode(int newUnits = 0, string newData = "");
~TransactionNode();
//setters
void setUnits(const int newUnits);
//getters
int getUnits() const;
//pure virtual
void printData();
};
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.