Binary tree with duplicate values
Introduction
Assignment #4 used a linked list, whereas assignment #5 used a binary search tree.
The only difference to the user between the two programs is if the user entered a bribe amount that someone already had paid. With a linked list, you “broke the tie” by “first come, first served.” However, since binary search trees cannot contain duplicate values, there was no addition to the tree. Instead, the user was advised that this bribe amount had already been paid, after which the application continued by displaying the menu.
LA School has decided to implement a variant of the bribe program to manage student enrollment in courses. Students are added to a class based on the bribe amount. The higher the bribe, the higher on the list. If two students offered the same bribe, whoever offered the bribe first would be higher on the list. The order in which students appeared on the list for a course could make a difference if more students wanted to take the course than the enrollment limit for the course.
Assumed Changes in Code
You may assume additional code was written to make three changes to the code you wrote for Assignment #s 4 and 5. You do not have to write code to make these changes.
The first change is made only to the binary search tree, to permit it, like the linked list, tohave duplicate bribe values. One member variable (data type int) would be added to thePersonRec The variable’s initial value will be 1. For each successive student whooffers the same bribe amount, the value of the variable would be incremented by 1. Thus, thevalue of the member variable for the second student who offers the same bribe amount wouldbe 2, for the third student 3, and so forth.
The second change would be made to both the linked list and the binary search tree. Afunction would be added to enable the user to search for a specified name or bribe amount.
The third change also would be made to both the linked list and the binary search tree. Y Afunction would be added to enable the user to delete a student, based on the name or the bribeamount.
Your job
You’ve been hired as an assistant to the head of IT at LA School. She has asked you to recommend, based on a comparison of algorithmic efficiency, whether the college should use a linked list or a binary search tree to write the bribe program to manage student course enrollment, and to explain (justify) your recommendation.
Algorithmic efficiency would arise in at least these contexts:
Adding a student to the course.
Deleting a student from a course.
Looking up if one or more students had a given name or had paid a given bribe amount.
Assginment_4 key
personlist.cpp
#include “personlist.h”
#include
usingstd::cout; using std::cin; using std::endl;
// Default Constructor
PersonList::PersonList() : head(nullptr) { }
// Destructor
PersonList::~PersonList() {
PersonRec *temp = head;
while (!isEmpty()) {
temp = head->link;
delete head;
head = temp;
}
}
// Prints a list of all the “donors”
voidPersonList::ViewList() {
PersonRec *currPtr = head;
if (isEmpty())
std::cout<< “\nList is empty\n”;
else {
cout<< “\n# Name Contribution\n”;
cout.width(40); cout.fill(‘=’); cout<< “\n”; // Formatting
// Print until end of list is reached
for (int i{ 1 }; !endOfList(currPtr); i++) {
cout<< i << ” ” <name << ” $” <bribe <
currPtr = currPtr->link;
}
}
}
voidPersonList::AddToList() {
// prevPtr is used for insertion, currPtr for iterating, temp for user input
PersonRec *prevPtr, *currPtr, *temp = new PersonRec;
bool loop;
cout<< “\nEnter the person’s name: “;
cin.getline(temp->name, 20);
cout<< “\nEnter the person’s contribution: “;
cin>> temp->bribe;
// If not empty, check bribe amounts and insert accordingly
if (!isEmpty()) {
currPtr = head;
do {
loop = false;
// If temp bribe equals current bribe
if (temp->bribe == currPtr->bribe) {
// Advance the iterators until temp bribe != current bribe
while (!(endOfList(currPtr)) && (temp->bribe == currPtr->bribe)) {
advance(prevPtr, currPtr);
}
// Insert the PersonRec after equal bribes and before lesser bribes
insert(temp, prevPtr);
}
// Else if temp bribe is greater than current bribe
else if (temp->bribe >currPtr->bribe) {
// Special condition in which ‘head’ needs to be changed
if (currPtr == head) {
temp->link = currPtr;
head = temp;
}
// Otherwise link previous to temp and temp to current
else {
insert(temp, prevPtr);
}
}
// Else if none of the above conditions are satisfied, iterate the pointers
else {
advance(prevPtr, currPtr);
// If end of list is reached, insert at the end
if (endOfList(currPtr))
insert(temp, prevPtr);
else
loop = true;
}
// End Loop
} while (loop);
}
// Else List is empty, insert in the first position
else {
temp->link = nullptr;
head = temp;
}
}
boolPersonList::isEmpty() const {
return head == nullptr;
}
boolPersonList::endOfList(PersonRec *currPtr) const {
returncurrPtr == nullptr;
}
voidPersonList::advance(PersonRec *&prevPtr, PersonRec *&currPtr) const {
//Make sure currPtr->link assignment will be valid
if (currPtr != nullptr) {
prevPtr = currPtr;
currPtr = currPtr->link;
}
}
voidPersonList::insert(PersonRec *&temp, PersonRec *&prevPtr) {
temp->link = prevPtr->link;
prevPtr->link = temp;
}
personlist.h
#ifndef PERSON_H
#define PERSON_H
structPersonRec {
char name[20]; //Char array containing person’s name
int bribe; //Amount of bribe (assumed to be whole number)
PersonRec *link;//Pointer to next PersonRec node (or to NULL if no next node)
};
classPersonList {
public:
PersonList();
~PersonList();
voidViewList();
voidAddToList();
private:
PersonRec *head;
//Additional private functions
boolisEmpty() const;
boolendOfList(PersonRec*) const;
void advance(PersonRec*&, PersonRec*&) const;
void insert(PersonRec*&, PersonRec*&);
};
#endif //PERSON_H
test.cpp
#include “personlist.h”
#include
using namespace std;
intdisplayMenu(void);
voidprocessChoice(int, PersonList&);
int main() {
intnum;
PersonListmyList;
do {
num = displayMenu();
if (num != 3)
processChoice(num, myList);
} while (num != 3);
return 0;
}
intdisplayMenu(void) {
int choice;
cout<< “\nMenu\n”;
cout<< “==============================\n\n”;
cout<< “1. Add student to waiting list\n”;
cout<< “2. View waiting list\n”;
cout<< “3. Exit program\n\n”;
cout<< “Please enter choice: “;
cin>> choice;
cin.ignore();
return choice;
}
voidprocessChoice(int choice, PersonList& p) {
switch (choice) {
case 1: p.AddToList();
break;
case 2: p.ViewList();
break;
}
}
Assigment #5_key
test.cpp
#include
#include
#include “tree.h”
using namespace std;
intdisplayMenu(void);
voidprocessChoice(int, CTree&);
int main(void) {
intnum;
CTreect;
do {
num = displayMenu();
if (num != 3)
processChoice(num, ct);
} while (num != 3);
return 0;
}
intdisplayMenu(void) {
int choice;
cout<< “\nMenu\n”;
cout<< “==============================\n\n”;
cout<< “1. Add student to waiting list\n”;
cout<< “2. View waiting list\n”;
cout<< “3. Exit program\n\n”;
cout<< “Please enter choice: “;
cin>> choice;
return choice;
}
voidprocessChoice(int choice, CTree&myTree) {
switch (choice) {
case 1: myTree.Add(); break;
case 2: myTree.View(); break;
}
}
tree.cpp
#include “tree.h”
#include
#include
#include
usingstd::cout; using std::cin; using std::endl;
// PersonRec Constructor
PersonRec::PersonRec(const char *name, constint&bribe, PersonRec *left, PersonRec *right)
: _bribe(bribe), _left(left), _right(right) {
if(name != nullptr)
// Use strncat to copy the argument safely (using a size parameter)
strncat(_name, name, SIZE_OF_NAME);
}
// CTree Destructor
CTree::~CTree() {
postorderDelete(_root);
_root = nullptr;
}
voidCTree::Add() {
charaName[SIZE_OF_NAME];
intaBribe;
cin.ignore();
cout<< “\nEnter the person’s name: “;
cin.getline(aName, SIZE_OF_NAME, ‘\n’);
cout<< “\nEnter the person’s contribution: “;
cin>>aBribe;
// Recursive Insertion
insert(_root, aName, aBribe);
}
// Recursive Printing
voidCTree::descendingOrderPrint(PersonRec *&root) const {
// This variable is used to keep count of the printed items
staticint counter = 0;
if (root != nullptr) {
descendingOrderPrint(root->_right); // Rightward Recursion
cout<< ++counter << ‘ ‘ << root->_name << ” $” << root->_bribe <
descendingOrderPrint(root->_left); // Leftward Recursion
}
// Reset static counter after all items are printed
if (root == _root)
counter = 0;
}
// Recursive Insertion
voidCTree::insert(PersonRec *&root, const char *name, constint&bribe) {
// If not null, keep iterating
if (root != nullptr) {
// Rightward Iteration
if (bribe > root->_bribe)
insert(root->_right, name, bribe);
// Leftward Iteration
else if (bribe < root->_bribe)
insert(root->_left, name, bribe);
// Base case for when the bribes are equal
else
cout<< “Oops, another ‘donor’ has already donated that amount.\n”;
}
// Else if root <- null and tree !<- full, create new node in place
else if (!isFull())
root = new PersonRec(name, bribe);
}
boolCTree::isEmpty() const {
return (_root == nullptr);
}
boolCTree::isFull() const {
// Check if additional heap memory is available
try {
PersonRec *temp = new PersonRec;
delete temp;
return false;
}
// Return (full <- true) if unable to allocate
catch (std::bad_alloc err) {
return true;
}
}
// Recursive postorder deletion
voidCTree::postorderDelete(PersonRec *&root) {
if (root != nullptr) {
postorderDelete(root->_left);
postorderDelete(root->_right);
delete root;
}
}
voidCTree::View() {
if (isEmpty())
cout<< “\nList is empty\n”;
else {
cout<< “\n# Name Contribution\n”;
cout.width(40); cout.fill(‘=’); cout<< “\n”; // Formatting
descendingOrderPrint(_root);
}
}
tree.h
// See definitions in tree.cpp for additional comments
#ifndef TREE_H
#define TREE_H
#pragma once
// For PersonRec char array
constint SIZE_OF_NAME = 20;
structPersonRec {
char _name[SIZE_OF_NAME]{ ‘\0’ };
int _bribe{ 0 };
PersonRec *_left{nullptr };
PersonRec *_right{nullptr };
PersonRec(const char * = nullptr, constint& = 0, PersonRec * = nullptr, PersonRec * = nullptr);
};
classCTree {
public:
CTree::CTree() : _root(nullptr) { }
~CTree();
boolisEmpty() const;
boolisFull() const;
void Add();
void View();
private:
PersonRec *_root;
void insert(PersonRec *&, const char *, constint&);// recursive insertion
voidpostorderDelete(PersonRec *&); // recursive deletion
voiddescendingOrderPrint(PersonRec *&) const; // recursive printing
};
#endif // !TREE_H
Solution
Algorithms Recommendation
Based on the two algorithms presented and data types (Binary Search Trees, referred ahead as BST’s, and Linked Lists, referred ahead as LL’s), used to store the information of the bribes and students whom made them, we shall study the algorithms “Search”, “Insert” and “Remove” according to the size of the BST’s/LL’s (which have the same size for the same number of elements) and we’ll use N to represent its value.
Also, we’ll use the “Big O(Ο)”, “Big Omega (Ω)” and “Big Theta(Θ)” notations to refer to the “worst case”, “best case”, “for all cases” (if it’s the case) of each algorithm.
“Insert” Algorithm (I(n)):
BST’s
I(n) = Ω (1);
I(n) = Ο (N);
(The best-case scenario in this implementation is when the tree is totally unbalanced to the right or left and the element we want to insert is less or bigger than the first element of the tree, respectively. The worst-case scenario is when the roles are inversed and for a right sided tree the element to input is the smaller. On average though, as we go through the tree we usually ignore half of it resulting in a division by 2 for each branch of the tree, thus resulting in log2(N) (instants of time).)
LL’s
I(n) = Ω (1);
I(n) = Ο (N);
(The best-case scenario in this implementation is when the element you want to insert is less than the first element of the list. The worst-case scenario is when the element we want to insert is bigger than any present in the list. On average, it takes N/2 (instants of time) to insert the element on an LL.)
“Remove” Algorithm (R(n)):
BST’s
- R(n) = Ω (1);
- R(n) = Ο (N);
(The best-case scenario in this implementation is when the tree is totally unbalanced to the right or left and the element we want to remove is less or bigger than the first element of the tree, respectively. The worst-case scenario is when the roles are inversed and for a right sided tree the element to input is the smaller. On average it’s also the same, as we go through the tree we usually ignore half of it resulting in a division by 2 for each branch of the tree, thus resulting in log2(N) (instants of time). The remove algorithm for the BST’s has the same complexity as the insert one as we can tell.)
LL’s
- R(n) = Ω (1);
- R(n) = Ο (N);
(The best-case scenario in this implementation is when the element you want to remove is the first element (the smaller) of the list. The worst-case scenario is when the element we want to remove is the last one or it’s not even in the list (the biggest or bigger than all). On average it’s all the same again, we got that it takes N/2 (instants of time) to remove the element on an LL. The remove algorithm in the LL’s is has also the same complexity of the insert one for the same structure.)
“Search” Algorithm (S(n)):
BST’s
- S(n) = Ω (1);
- S(n) = Ο (N);
(The best-case scenario in this implementation is when theelement we seek is the head of the tree. The worst-case scenario is when the tree is totally unbalanced and the element we seek is the leaf of the tree or isn’t even in it. On average it’s also the same, as we go through the tree we usually ignore half of it resulting in a division by 2 for each branch of the tree, thus resulting in log2(N) (instants of time). As we can see thesearch algorithm for the BST’s has the same complexity as the insert and the remove ones too. )
LL’s
- S(n) = Ω (1);
- S(n) = Ο (N);
(The best-case scenario in this implementation is when the element we seek is the first element (the smaller) of the list. The worst-case scenario is when the element we seek is the last one or it’s not even in the list (the biggest or bigger than all).On average, we got that it takes N/2 (instants of time) to remove the element on an LL. Again, in terms of complexity it’s the same as the insert/remove algorithms. )
Summing up, if we look only to the best-case and worst-case scenarios the algorithms look pretty similar to the naked eye, but if we look at them in probabilistic terms we’ll see that the BST implementation for the data structure is a better one as it less time in general for the three tasks. Let’s imagine we have a data structure of 1024 elements and that for each element we “see” it takes 1 second. If we implemented a LL we’d get on average a time of 512 seconds to insert, remove or search an element whereas with a BST implementation it would take only 10 seconds. That’s a ratio of more than 5:1 and with bigger sizes the ratio increases exponentially. With that said, the logical approach is to implement a Binary Search Tree instead of a Linked List.