I have read many posts on BST and duplicates and I understand it isn't very possible / no clean way to allow duplicates especially for a complex type which I am using. So I need some help on how / if it's possible to implement a BST with duplicates with my scenario.
My scenario: I am using a Transaction class as my node keys, and the main data I am comparing is the 'amount' in the transaction class, so my binary search tree can allow you to enter an amount and output any transactions with its 'toString()' function to the user, that matches the search amount. However, now I face the issue that I won't be able to have a duplicate transaction amount. How could I resolve this? Could anyone provide an example? thank you.
Code to reproduce the problem to solve:
#include<iostream>
using namespace std;
#include <algorithm>
#include <cctype>
#include <string>
#include <memory>
// Complex type used for the BST
class Transaction
{
private:
std::string desc;
time_t timestamp;
std::string value;
bool isWithdrawal;
public:
Transaction(const std::string& value, std::string reason = "None.")
: desc(reason), timestamp(time(nullptr)), value(value) { // timestamp is current date/time based on current system
// Lambda to convert reason to lower to we can identify elements easier
std::transform(reason.begin(), reason.end(), reason.begin(),
[](unsigned char c) { return std::tolower(c); });
this->isWithdrawal = (reason.find("withdrawal") != std::string::npos) ? true : false;
}
std::string toString() const {
// convert timestamp to string form
const char* string_timestamp = ctime(×tamp);
if(this->isWithdrawal) { return "-- " desc ": -£" value " on " string_timestamp;}
else {return "-- " desc ": £" value " on " string_timestamp;}
}
// Gets the amount, converts it to a double and returns it
double getAmount() const {
return std::stod(this->value);
}
};
// The binary search tree implementation
class BST {
struct node {
std::shared_ptr<Transaction> data;
node* left;
node* right;
};
node* root;
node* makeEmpty(node* t) {
if(t == NULL)
return NULL;
{
makeEmpty(t->left);
makeEmpty(t->right);
delete t;
}
return NULL;
}
node* insert(std::shared_ptr<Transaction> x, node* t)
{
if(t == NULL)
{
t = new node;
t->data = x;
t->left = t->right = NULL;
}
else if(x->getAmount() < t->data->getAmount())
t->left = insert(x, t->left);
else if(x->getAmount() > t->data->getAmount())
t->right = insert(x, t->right);
return t;
}
node* findMin(node* t)
{
if(t == NULL)
return NULL;
else if(t->left == NULL)
return t;
else
return findMin(t->left);
}
node* findMax(node* t) {
if(t == NULL)
return NULL;
else if(t->right == NULL)
return t;
else
return findMax(t->right);
}
void inorder(node* t) {
if(t == NULL)
return;
inorder(t->left);
cout << t->data->getAmount() << " ";
inorder(t->right);
}
node* find(node* t, double x) {
if(t == NULL)
return NULL;
else if(x < t->data->getAmount())
return find(t->left, x);
else if(x > t->data->getAmount())
return find(t->right, x);
else
return t;
}
public:
BST() {
root = NULL;
}
~BST() {
root = makeEmpty(root);
}
void insert(std::shared_ptr<Transaction> x) {
root = insert(x, root);
}
void display() {
inorder(root);
cout << endl;
}
std::string search(double x) {
node* result = find(root, x);
if(result != NULL) { return result->data->toString(); }
else { return "N/A"; }
}
};
int main() {
BST t;
t.insert(std::make_shared<Transaction>("1500.50", "Deposit"));
t.insert(std::make_shared<Transaction>("1600.98", "Deposit"));
t.insert(std::make_shared<Transaction>("1400", "Withdrawal"));
t.insert(std::make_shared<Transaction>("1400.59", "Deposit"));
t.display();
std::cout << t.search(1500.50);
return 0;
}
CodePudding user response：
I have read many posts on BST and duplicates and I understand it isn't very possible / no clean way to allow duplicates especially for a complex type which I am using.
This is incorrect you can use multimap or multiset for this case.
For example, cppreference
Multimap is an associative container that contains a sorted list of key-value pairs, while permitting multiple entries with the same key. Sorting is done according to the comparison function Compare, applied to the keys. Search, insertion, and removal operations have logarithmic complexity.
You just need to supply as a template parameter a Compare functor which says that for two equivalent keys, none is smaller than the other.
CodePudding user response：
You can associate a BST node with multiple values by making your data member a container, for example, change:
std::shared_ptr<Transaction> data;
into
std::list<std::shared_ptr<Transaction>> data;
This is the same thing as associating a key with multiple values. In essence, this is what std::multimap and std::multiset do. You will have to update tree operations/iterator as well. You will have to zip individual std::lists together, when doing container traversal, for example.
EDIT:
An easy alternative would be to use std::multiset<std::tuple<std::string, time_t, std::string, bool>>.
CodePudding user response：
A binary search tree lets you store keys and associated records. It allows efficient searches for a given key (with the purpose of retrieving the associated information).
As it also supports enumeration in sorted order, it allows retrieving all keys in a given range, and duplicate keys are not a problem.
CodePudding user response：
As other answers indicate, there is no problem with putting duplicates, or items with duplicate keys, in a BST.
It does make it annoying (and sometimes slow!) to then find any particular item that you're looking for, in order to remove it or change its key.
I suggest that for, your use case, you don't need to store duplicates at all. Your BST stores pointers to Transactions, and you want to sort them by price. You should probably use the actual pointer value (the Transaction address) to break ties.
That way, your BST is still sorted by price, but every Transaction has a unique key, and any particular transaction can be located or removed in O(log N) time.