Data Analysis using Binary Search Trees For this assignment you are implementing
ID: 3763249 • Letter: D
Question
Data Analysis using Binary Search Trees
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 ();
Now I have this:
#include
#include
#include
#include
using namespace std;
#ifndef Header_h
#define Header_h
class Node
{
public:
Node(string newData) //This is constructor to node class.
{
mData = newData;
mpLeft = nullptr;
mpRight = nullptr;
}
virtual ~Node(){} //This is virtual destructor to node class.
//--> These are the setters functions.
void setData (string newData) //This is a setter function for mData.
{
mData = newData;
}
void setLeft (Node *newLeft) //This is a setter function for mpLeft.
{
mpLeft = newLeft;
}
void setRight (Node *newRight) //This is a setter function for mpRight.
{
mpRight = newRight;
}
//--> These are the getters functions.
string getData () //This is a getter function for mData.
{
return mData;
}
Node *& getLeft () //This is a getter function for mpLeft.
{
return mpLeft;
}
Node *& getRghit () //This is a getter function for mpRghit.
{
return mpRight;
}
virtual void printData () = 0; //This is the virtual printData function.
protected:
string mData;
Node* mpLeft;
Node* mpRight;
};
//This is the TransactionNode class
class TransactionNode : public Node
{
public:
TransactionNode (int newUnits, string newData) : Node (newData) //This is constructor to TransactionNode class.
{
mUnits = newUnits;
}
~TransactionNode () //This is destructor to TransactionNode class.
{
cout << "This is the TransactionNode's destructor" << endl;
}
void setUnits (int newUnits) //This is a setter function for mUnits.
{
mUnits = newUnits;
}
int getUnits () //This is a getter function for mUnits.
{
return mUnits;
}
void printData () //This is overriding the printData() function in Node
{
cout << "number of units: " << mUnits << " string: " << this->mData << endl;
}
private:
int mUnits;
};
class BST
{
public:
BST (){} //This is constructor to BST class.
~BST () //This is destructor to BST class.
{
destroyTree(mpRoot);
}
void setRoot (Node* newRoot) //This is a setter function for mpRoot.
{
mpRoot = newRoot;
}
Node *& getRoot () //This is a getter function for mpRoot.
{
return mpRoot;
}
void insert ()
{
insertPrivate (mpRoot);
}
private:
Node* mpRoot;
void destroyTree (Node *deleteNode)
{
if (deleteNode != NULL)
{
destroyTree(deleteNode->Node::getLeft());
destroyTree(deleteNode->Node::getRghit());
delete deleteNode;
}
}
void insertPrivate (Node* data);
}
Explanation / Answer
Node.h
---------------------------------------
#ifndef NODE_H_
#define NODE_H_
using namespace std;
#include <iostream>
class Node {
//data members
protected:
string mData;
Node* mpLeft;
Node* mpRight;
public:
Node(string); //constructor
virtual ~Node(); //destructor
//--> These are the setters functions.
void setData (string); //This is a setter function for mData.
void setLeft (Node*); //This is a setter function for mpLeft.
void setRight (Node*); //This is a setter function for mpRight.
//--> These are the getters functions.
string getData(); //This is a getter function for mData.
Node* getLeft(); //This is a getter function for mpLeft.
Node* getRghit(); //This is a getter function for mpRghit.
virtual void printData () = 0; //This is the virtual printData function
};
#endif /* NODE_H_ */
---------------------------------
Node.cpp
#include "Node.h"
Node::Node(string newData) {
mData = newData;
mpLeft = NULL;
mpRight = NULL;
}
Node::~Node() {
// TODO Auto-generated destructor stub
}
void Node::setData (string newData) //This is a setter function for mData.
{
mData = newData;
}
void Node::setLeft(Node* newLeft) //This is a setter function for mpLeft.
{
mpLeft = newLeft;
}
void Node::setRight (Node* newRight) //This is a setter function for mpRight.
{
mpRight = newRight;
}
//--> These are the getters functions.
string Node::getData() //This is a getter function for mData.
{
return mData;
}
Node* Node::getLeft() //This is a getter function for mpLeft.
{
return mpLeft;
}
Node* Node::getRghit() //This is a getter function for mpRghit.
{
return mpRight;
}
--------------------------------
TransactionNode.h:
-----------------------------------
#ifndef TRANSACTIONNODE_H_
#define TRANSACTIONNODE_H_
#include "Node.h"
class TransactionNode: public Node {
private:
int mUnits; //units sold or brought
public:
TransactionNode(int, string); //Constructor
~TransactionNode(); //Destructor
//setter and getter functions
void setUnits(int); //This is a setter function for mUnits.
int getUnits(); //This is a getter function for mUnits.
void printData(); //This is overriding the printData() function in Node
};
#endif /* TRANSACTIONNODE_H_ */
-----------------------------------------------------
TransactionNode.cpp:
------------------------------------------
#include "TransactionNode.h"
TransactionNode::TransactionNode(int newUnits, string newData):Node(newData) //This is constructor to TransactionNode class.
{
mUnits = newUnits;
}
TransactionNode::~TransactionNode() {
}
//setter and getter functions
void TransactionNode::setUnits(int newUnits) //This is a setter function for mUnits.
{
mUnits = newUnits;
}
int TransactionNode::getUnits() //This is a getter function for mUnits.
{
return mUnits;
}
void TransactionNode::printData() //This is overriding the printData() function in Node
{
cout<<"Product:"<<this->getData()<<", Units:"<<this->getUnits()<<endl;
}
----------------------------------------------
BST.h:
-----------------------------------------
#ifndef BST_H_
#define BST_H_
using namespace std;
#include <iostream>
#include "TransactionNode.h"
class BST {
private:
Node* mpRoot; //Root of BST
void destroyTree (Node* deleteNode)
{
if (deleteNode!= NULL)
{
destroyTree(deleteNode->Node::getLeft());
destroyTree(deleteNode->Node::getRghit());
delete deleteNode;
}
}
void insertPrivate(Node* pT)
{
TransactionNode* temp=(TransactionNode*)pT;
TransactionNode* root=(TransactionNode*)mpRoot;
if(root==NULL)
{
root=temp;
}
else if(root->getUnits()>=temp->getUnits())
{
insertPrivate(root->getLeft());
}
else
{
insertPrivate(root->getRghit());
}
}
void inOrderTraversal(Node* pT) //in-order traversal of tree
{
TransactionNode* temp=(TransactionNode*)pT;
if(temp!=NULL)
{
inOrderTraversal(temp->getLeft());
temp->printData();
inOrderTraversal(temp->getRghit());
}
}
TransactionNode* findSmallest(Node* pT)
{
TransactionNode* temp=(TransactionNode*)pT;
TransactionNode* smallest=temp;
while(smallest->getLeft()!=NULL)
{
smallest=(TransactionNode*)smallest->getLeft();
}
return smallest;
}
TransactionNode* findLargest(Node* pT)
{
TransactionNode* temp=(TransactionNode*)pT;
TransactionNode* largest=temp;
while(largest->getRghit()!=NULL)
{
largest=(TransactionNode*)largest->getRghit();
}
return largest;
}
public:
BST();
~BST();
//setter and getter functions
void setRoot(Node*); //This is a setter function for mpRoot.
Node* getRoot(); //This is a getter function for mpRoot.
void insert(string, int); //inserts a node into BST
void inOrderTraversal(); //in-order traversal of the tree
TransactionNode* findSmallest(); //returns node with smallest units
TransactionNode* findLargest(); //returns node with largest units
};
#endif /* BST_H_ */
---------------------------------------
BST.cpp:
-----------------------------------
#include "BST.h"
BST::BST() {
mpRoot=NULL;
}
BST::~BST() {
destroyTree(mpRoot);
}
//setter and getter functions
void BST::setRoot (Node* newRoot) //This is a setter function for mpRoot.
{
mpRoot = newRoot;
}
Node* BST::getRoot() //This is a getter function for mpRoot.
{
return mpRoot;
}
//insert function
void BST::insert(string data, int units)
{
Node* newNode=new TransactionNode(units, data);
insertPrivate(newNode);
}
void BST::inOrderTraversal()
{
inOrderTraversal(mpRoot);
}
TransactionNode* BST::findSmallest()
{
TransactionNode* smallest=NULL;
smallest=findSmallest(mpRoot);
return smallest;
}
TransactionNode* BST::findLargest()
{
TransactionNode* largest=NULL;
largest=findLargest(mpRoot);
return largest;
}
--------------------------------
Note:
1. Any sample of .csv file, need that for further implementation.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.