Instructions
Objective
Write a C++ assignment program to implement a binary search tree with balancing methods.
Requirements and Specifications
Your assignment is to implement a binary search tree with balancing methods.
For this project, you are provided with the skeleton .h and .cpp files and a sample driver:
streak.h – Interface for the Tiger and Streak classes.
streak.cpp – A skeleton for the implementation of the class Streak.
driver.cpp – a sample driver program. (Note: this file is provided to show a typical usage. Since the project is not implemented, trying to compile and run this driver program will not generate the sample output in driver.txt. Once you develop your project, you should be able to generate the same output as driver.txt by running this driver program.)
driver.txt – a sample output produced by driver.cpp
Source Code
#include
using namespace std;
struct Pair {
public:
Pair(int key, string value) {
_key = key;
_value = value;
}
int getKey() {
return _key;
}
string getValue() {
return _value;
}
private:
int _key;
string _value;
};
class Heap {
public:
Heap(int n) {
arr = new Pair*[n];
capacity = n;
size = 0;
}
~Heap() {
for (int i = 0; i delete arr[i];
}
delete[] arr;
}
void insert(int key, string value) {
if (size == capacity) {
return;
}
Pair* p = new Pair(key, value);
size++;
arr[size-1] = p;
upHeap(size-1);
}
string removeMin() {
if (size == 0) {
return "";
}
string value = arr[0]->getValue();
arr[0] = arr[size-1];
size--;
downHeap(0);
return value;
}
void upHeap(int anIndex) {
if (anIndex == 0) {
return;
}
int parentIndex = (anIndex - 1)/2;
if (arr[parentIndex]->getKey() > arr[anIndex]->getKey()) {
Pair* sw = arr[parentIndex];
arr[parentIndex] = arr[anIndex];
arr[anIndex] = sw;
upHeap(parentIndex);
}
}
void downHeap(int anIndex) {
if (2*anIndex +1 >= size) {
return;
}
int i = 2*anIndex + 1;
if (2*anIndex + 2 < size) {
i = arr[2*anIndex + 1]->getKey() < arr[2*anIndex + 2]->getKey() ? 2*anIndex+1 : 2*anIndex + 2;
}
if (arr[anIndex]->getKey() > arr[i]->getKey()) {
Pair* sw = arr[i];
arr[i] = arr[anIndex];
arr[anIndex] = sw;
downHeap(i);
}
}
void print() {
// for (int i = 0; i // cout << arr[i]->getKey() << " ";
// }
// cout << endl;
}
private:
int size;
int capacity;
Pair** arr;
};
int main() {
Heap h(100);
h.insert(5, "a");
h.print();
h.insert(4, "b");
h.print();
h.insert(7, "i");
h.print();
h.insert(1, "d");
h.print();
cout << h.removeMin() << endl;
h.print();
h.insert(3, "j");
h.print();
h.insert(6, "c");
h.print();
cout << h.removeMin() << endl;
h.print();
cout << h.removeMin() << endl;
h.print();
h.insert(8, "g");
h.print();
cout << h.removeMin() << endl;
h.print();
h.insert(2, "h");
h.print();
cout << h.removeMin() << endl;
h.print();
cout << h.removeMin() << endl;
h.print();
}
/**
* UserTree.h
* Implementation for the UTree class.
*/
#include "utree.h"
/**
* Destructor, deletes all dynamic memory.
*/
UTree::~UTree() {
clear();
}
/**
* Sources a .csv file to populate Account objects and insert them into the UTree.
* @param infile path to .csv file containing database of accounts
* @param append true to append to an existing tree structure or false to clear before importing
*/
void UTree::loadData(string infile, bool append) {
std::ifstream instream(infile);
string line;
char delim = ',';
const int numFields = 5;
string fields[numFields];
/* Check to make sure the file was opened */
if(!instream.is_open()) {
std::cerr << __FUNCTION__ << ": File " << infile << " could not be opened or located" << endl;
exit(-1);
}
/* Should we append or clear? */
if(!append) this->clear();
/* Read in the data from the .csv file and insert into the UTree */
while(std::getline(instream, line)) {
std::stringstream buffer(line);
/* Quick check to make sure each line is formatted correctly */
int delimCount = 0;
for(unsigned int c = 0; c < buffer.str().length(); c++) if(buffer.str()[c] == delim) delimCount++;
if(delimCount != numFields - 1) {
throw std::invalid_argument("Malformed input file detected - ensure each line contains 5 fields deliminated by a ','");
}
/* Populate the account attributes -
* Each line always has 5 sections of data */
for(int i = 0; i < numFields; i++) {
std::getline(buffer, line, delim);
fields[i] = line;
}
Account newAcct = Account(fields[0], std::stoi(fields[1]), std::stoi(fields[2]), fields[3], fields[4]);
this->insert(newAcct);
}
}
/**
* Dynamically allocates a new UNode in the tree and passes insertion into DTree.
* Should also update heights and detect imbalances in the traversal path after
* an insertion.
* @param newAcct Account object to be inserted into the corresponding DTree
* @return true if the account was inserted, false otherwise
*/
bool UTree::insert(Account newAcct)
{
if (_root == nullptr)
{
_root = new UNode();
_root->getDTree()->insert(newAcct);
_root->_height = 0;
return true;
}
if (!insertNode(_root, nullptr, false, newAcct))
return false;
updateHeight(_root);
return true;
}
/**
* Removes a user with a matching username and discriminator.
* @param username username to match
* @param disc discriminator to match
* @param removed DNode object to hold removed account
* @return true if an account was removed, false otherwise
*/
bool UTree::removeUser(string username, int disc, DNode*& removed) {
UNode* node = retrieve(username);
if (node != nullptr)
return node->_dtree->remove(disc, removed);
removed = nullptr;
return false;
}
/**
* Retrieves a set of users within a UNode.
* @param username username to match
* @return UNode with a matching username, nullptr otherwise
*/
UNode* UTree::retrieve(string username) {
if (_root == nullptr)
return nullptr;
return retrieveNode(_root, username);
}
UNode* UTree::retrieveNode(UNode *node, string username) {
if (node->getUsername() == username)
return node;
else if (node->getUsername() < username)
return retrieveNode(node->_right, username);
else
return retrieveNode(node->_left, username);
}
/**
* Retrieves the specified Account within a DNode.
* @param username username to match
* @param disc discriminator to match
* @return DNode with a matching username and discriminator, nullptr otherwise
*/
DNode* UTree::retrieveUser(string username, int disc) {
UNode* node = retrieve(username);
if (node != nullptr) {
return node->getDTree()->retrieve(disc);
}
return nullptr;
}
/**
* Returns the number of users with a specific username.
* @param username username to match
* @return number of users with the specified username
*/
int UTree::numUsers(string username) {
UNode* node = retrieve(username);
if (node != nullptr) {
return node->getDTree()->getNumUsers();
}
return 0;
}
/**
* Helper for the destructor to clear dynamic memory.
*/
void UTree::clear() {
if (_root != nullptr)
{
clearNode(_root);
_root = nullptr;
}
}
/**
* Prints all accounts' details within every DTree.
*/
void UTree::printUsers() const {
if (_root != nullptr)
printUsersNode(_root);
}
/**
* Dumps the UTree in the '()' notation.
*/
void UTree::dump(UNode* node) const {
if(node == nullptr) return;
cout << "(";
dump(node->_left);
cout << node->getUsername() << ":" << node->getHeight() << ":" << node->getDTree()->getNumUsers();
dump(node->_right);
cout << ")";
}
/**
* Updates the height of the specified node.
* @param node UNode object in which the height will be updated
*/
void UTree::updateHeight(UNode* node) {
int lHeight = -1, rHeight = -1;
if (node->_left != nullptr) {
updateHeight(node->_left);
lHeight = node->_left->_height;
}
if (node->_right != nullptr) {
updateHeight(node->_right);
rHeight = node->_right->_height;
}
node->_height = (lHeight > rHeight ? lHeight : rHeight) + 1;
}
/**
* Checks for an imbalance, defined by AVL rules, at the specified node.
* @param node UNode object to inspect for an imbalance
* @return (can change) returns true if an imbalance occured, false otherwise
*/
int UTree::checkImbalance(UNode* node) {
int lHeight = -1, rHeight = -1;
if (node->_left != nullptr)
lHeight = node->_left->_height;
if (node->_right != nullptr)
rHeight = node->_right->_height;
return lHeight - rHeight;
}
//----------------
/**
* Begins and manages the rebalance procedure for an AVL tree (pass by reference)
* @param node UNode object where an imbalance occurred
*/
void UTree::rebalance(UNode*& node) {
int balance = checkImbalance(node);
int lHeight = 0, rHeight = 0;
if (balance > 1) {
if (node->_left->_left != nullptr)
lHeight = node->_left->_left->_height;
if (node->_left->_right != nullptr)
rHeight = node->_left->_right->_height;
if (rHeight > lHeight)
node->_left = leftRotate(node->_left);
node = rightRotate(node);
}
else if (balance < -1) {
if (node->_right->_right != nullptr)
rHeight = node->_right->_right->_height;
if (node->_right->_left != nullptr)
lHeight = node->_right->_left->_height;
if (lHeight > rHeight)
node->_right = rightRotate(node->_right);
node = leftRotate(node);
}
}
bool UTree::insertNode(UNode* node, UNode* parentNode, bool isLeft, Account acct)
{
if (node->getUsername() == acct.getUsername())
return node->getDTree()->insert(acct);
else if (node->getUsername() < acct.getUsername())
{
if (node->_right == nullptr)
{
node->_right = new UNode();
node->_right->getDTree()->insert(acct);
return true;
}
if (insertNode(node->_right, node, false, acct))
{
updateHeight(node);
rebalance(node);
if (parentNode == nullptr)
_root = node;
else {
if (isLeft)
parentNode->_left = node;
else
parentNode->_right = node;
}
return true;
}
else
return false;
}
else {
if (node->_left == nullptr) {
node->_left = new UNode();
node->_left->getDTree()->insert(acct);
return true;
}
if (insertNode(node->_left, node, true, acct))
{
updateHeight(node);
rebalance(node);
if (parentNode == nullptr)
_root = node;
else {
if (isLeft)
parentNode->_left = node;
else
parentNode->_right = node;
}
return true;
}
else
return false;
}
}
void UTree::clearNode(UNode *node) {
if (node->_left != nullptr)
clearNode(node->_left);
if (node->_right != nullptr)
clearNode(node->_right);
delete node;
}
void UTree::printUsersNode(UNode *node) const {
printUsersNode(node->_left);
node->_dtree->printAccounts();
printUsersNode(node->_right);
}
UNode* UTree::leftRotate(UNode* node) {
UNode *rNode = node->_right;
UNode *rlNode = rNode->_left;
rNode->_left = node;
node->_right = rlNode;
updateHeight(node);
updateHeight(rNode);
return rNode;
}
UNode* UTree::rightRotate(UNode* node) {
UNode *lNode = node->_left;
UNode *lrNode = lNode->_right;
lNode->_right = node;
node->_left = lrNode;
updateHeight(node);
updateHeight(lNode);
return lNode;
}