visual garnet
Hi! so this is an assignment im working on and it requires an implementation of a RBT insertion of HotelBookings
My main concern is how to actually apply the given pseudocode. I have just been following the pseudocode for other functions so I'm not very knowledgeable on how the 100% correct implementation of this should look like. I also don't know all of the cases for insertion for a Red Black Tree but I will provide them just in case and study them meanwhile.
dry coralBOT
visual garnet
this is the pseudocode im following
void RedBlackTree::insertNode(Node *node)
{
Node *y = NULL;
Node *x = root;
while (x != NULL)
{
y = x;
if (node->key < x->key)
{
x = x->leftChild;
}
else
{
x = x->rightChild;
}
}
node->parent = y;
if (y == NULL)
{
root = node;
}
else if (node->key < y->key)
{
y->leftChild = node;
}
else if (node->key > y->key)
{
y->rightChild = node;
}
else //duplicated node. Not added
{
node -> leftChild = NULL;
node -> rightChild = NULL;
node -> color = "Red";
cout << "Duplicated node. NOT added" << endl;
return;
}
}
this is what i have so far
the key is basically a hotelName + arrivalDate + confirmationNumber
so it compares them and sees where in the RBT it should be inserted
ok so from what im seeing x (the pointer to the root node) travels down until it finds a place where the node can be inserted
inside this while loop im pretty sure that i can check if x->key == node->key and imediately return since we have a duplicated node
hmm i think that is the only issue i had lmao
muted pond
You should really use more descriptive names than node, x and y
I know you're just following the slides, but descriptive names make understanding code so much easier
Good thing your IDE should support renaming every instance of a variable (just google what the shortcut is for your IDE)
visual garnet
okk yeah because my brain is just coding automatically
im not really deeply understanding what is going on but thanks for that
i do think i answered my own question kind of
muted pond
i do think i answered my own question kind of
well, keep the question open until you've tried to implement it.
From my own experience I can say that you often come up with an idea that you're super convinced will work, only for it to turn out to be completely wrong.
visual garnet
yeah that might happen
muted pond
*Not saying that you're not on the right track though (neither am I saying you am)
visual garnet
and like ive only coded like 5/20 functions
its super hard to tell it'll work
it's basically a CLI program that takes letters as input, lets say D
and then asks for a hotel name, arrival date, confirm Num, and then looks for it and deletes it from the RBT
or input = I and it inserts a booking in RBT
thats the gist of it
dry coralBOT
@visual garnet Has your question been resolved? If so, type !solved :)
muted pond
its super hard to tell it'll work
I would start with implementing the most basic functions that are super easy or are simply required (almost) everywhere else.
Then you implement the first function that will actually allow you to do something (e.g. the constructor to create a new empty tree). You then test that functionality, see if it works, see if all variables are set how they should be.
Then you make the next most fundamental function, which would be the insert.
You don't make the entire insert at once, you only want to focus on a single part of it. Then test it with inputs that will always trigger only that part of the code. See if it works as expected. Then test it with inputs that would trigger other parts of the code and observe if it expectedly fails.
Then you go to the next part of that insert function. And so on and so on.
The key is testing. Testing, testing and testing.
Every single change you make to your code you'll need to test with inputs that will trigger that code, then observe if it worked as expected.
As time goes on you'll get a better understanding for how everything works which enables you to judge if a certain thing needs to be tested or not, but as a beginner for the first few weeks you'll want to radically test everything.
visual garnet
yeah so my first mistake was thinking i could just code every function and then test my whole program 💀
okk ill stop doing that rn
muted pond
yeah so my first mistake was thinking i could just code every function and then ...
That worked exactly once for me. It was a truly glorious day.
visual garnet
im trying to be like you 🫡
alright so basically work on the CLI first
make sure it prints stuff on the console 💀
muted pond
alright so basically work on the CLI first
what?
visual garnet
i mean the input output stuff
muted pond
You can just hardcode the test cases. You don't have to manually type them in by hand every time
muted pond
Wait, you already have tests?
muted pond
okay, yeah. that makes my whole entire essay about testing kinda obsolete then
visual garnet
#include "RedBlackTree.h"
using namespace std;
//This function used to get the info. of a HotelBooking object
void getBookingInfo(string oneLine, string& hotelName, string& arrivalDate, int& confirmNum);
int main()
{
string hotelName, arrivalDate ;
int confirmNum;
string command, oneLine;
string delimiter = ",";
int pos = 0;
//Create a RedBlackTree object here, use it throughout the program
//----
do
{
getline(cin, oneLine);
pos = oneLine.find(delimiter);
command = oneLine.substr(0, pos);
oneLine.erase(0, pos + delimiter.length());
if(command.compare("quit")==0)
{
cout << "\nCommand: quit" << endl;
//call the relevant function on the red black tree
//----
break;
}
else if(command.compare("tree_preorder")==0)
{
cout << "\nCommand: tree_preorder" << endl;
//call the relevant function on the red black tree
//----
}
else if(command.compare("tree_inorder")==0)
{
cout << "\nCommand: tree_inorder" << endl;
//call the relevant function on the red black tree
//----
}
else if(command.compare("tree_postorder")==0)
{
cout << "\nCommand: tree_postorder" << endl;
//call the relevant function on the red black tree
//----
}
else if(command.compare("tree_minimum")==0)
{
cout << "\nCommand: tree_minimum" << endl;
//call the relev
the class is already premade
muted pond
Okay? But like this you still need to manually type them in every time
visual garnet
oh yeah i mean i havent typed them in yet
but there is input
cases
sorry i know what you mean
muted pond
But actually it's not that bad because we can just replace std::cin by another file input stream.
I.e. we can just create a text file, write all the input we want to test in there and are good to go
visual garnet
i usually use a c++ compiler online for this 💀
and we are not supposed to use the IDE for it
we are supposed to use SSH
muted pond
Do you have a C++ compiler locally?
visual garnet
yeah
muted pond
Or yeah, you could use the SSH
visual garnet
vscode
muted pond
Yeah, that's a compiler
muted pond
gcc for C
g++ for C++
It's kinda obvious when you look at the language names
visual garnet
oh yeah it gives me the option for g++, clang++
muted pond
g++ and clang++ are both C++ compilers and arguably the two most widespread ones (except for Windows)
visual garnet
yeah i just use g++
muted pond
Okay, then test it locally on your computer
muted pond
Best with the file replacement for std::cin so you don't have to type/copy it in manually every time you test.
visual garnet
i put the you have quit there
muted pond
Funnily enough I don't think you used g++ there.
I think you used MinGW
visual garnet
so you are saying i can do this (from online compiler) in vscode
visual garnet
Funnily enough I don't think you used `g++` there.
I think you used `MinGW`
youre right 💀
i literally pressed run with g++
muted pond
so you are saying i can do this (from online compiler) in vscode
Yes.
Btw, how do you handle having multiple files (header and source file) on the same online compiler instance?
What online compiler do you use?
muted pond
Interesting.
Then I guess you can just keep on doing that.
I always use godbolt as my online compiler of choice and there I haven't found such an option yet
visual garnet
yupp i looked for that option in some online compilers but only this one had it
maybe replit lets you do that too i think
im gonna test my insert function real quick 🙏
muted pond
Btw, I just realized we're in #1013104018739974194 , not in #1013107104678162544
visual garnet
💀
visual garnet
!solved
dry coralBOT
