Welcome back to what should be the final video in this Avielle three series part of the course here.
So we're going to finish out our.
A rail project here and sea lion.
We're going to add a couple of functions that do a level order traversal and print out the values so
we can verify our tree's structure.
And we'll, of course, have to put some stuff in Maine to run the whole program, you know, have some
client code.
So we're going to do that and along the way, I'm going to go over an example input.
I already have this input file here that I've made.
That's pretty small, but it has all the rotations, I believe.
You have like be right, right?
I think a left left.
Rotation and left right and right left should be.
Should be all of them, I believe that's right.
It might there might be a few missing or no, it has an ancillary list as well.
Yeah, so I double checking.
I have a little drawing here.
I made, but yeah, I made some slides.
So we're going to walk through that and verify if that RV actually works in all that.
So let's go ahead and just get started with adding these other functions to print it out.
So I'm just going to put some prototypes here in the header, so I'm going to call this level order
down because what it's going to do is go in order, not in order, by numbers, in order traversal,
but it's going to traverse like level by level and print them out.
So this is going to be a function is called from Maine, and then I'm going to have a private version
of this that is also level ordered out,
but it's going to take A..
And it's going to take the level.
So in one function, I am going to basically loop for the amount of the height of the tree, so like
through all the levels.
And then I'm going to pass.
I'm going to call this other function in that loop and pass the level and we're actually going to.
Use that to have like a base case and then go left and right and printed out in the right order, and
I'll explain that once we are implementing that, but you know, let's go ahead and put this first function
in there and then we'll do this.
Next one.
So I'm going to avoid a real tree level or down, and I'm going to a for loop here, some say, and
I equals one.
So we're going to start off with like the first level I is less than or equal to you and I'm going to
say Root.
So that is going to be, you know, our actual root root height, not the height of say.
Yeah.
Or they're going to be or hate groups.
Yeah, because I made their height function, right?
Yes, that.
Should be.
Yeah, so we'll get the height of the root node arm data, remember?
And I told you I was worse.
And then in here, I'm going to just call level or jump, which is going to be our other one.
And I'm going to pass it the root and high school.
So let's go do that.
Other level watered down that takes the notes.
So this is going to be
military level or down that one.
And so.
What I'm going to, of course, need to do if we always do is I have this note in and I'm going to check
if it's an old pointer for the absolute best case, in which case we'll just return.
And then I put another case here, and I'm going to say else if level equals one.
Then we're going to see out the notes and values, so we'll do it now, get value and in line.
And so the reason we're going to do this is because it's basically going to do a left recursion and
a right recursion, and we're going to subtract one another, recursive calls each time from a level.
And since we're passing a specific level, we basically want to know when it gets down to one because
that's kind of like the first level of children of a specific route.
And if that if that's the case, then we're going to want to print it out.
So I'm going to do a level or jump and to the left some tree.
And then I would do level minus one and then I'll do the same thing for the race tree.
So basically, once it gets down to.
One then we know that we want to print out the value.
So that's why we are putting this extra base case out here.
So it's another function, you know, where you could go ahead and draw this out, you know, the recursive
calls and the dry the tree out on like the minor surgery drain on paper and kind of see what's happening
here.
You know, when we go all the way down, we're calling this left.
Recursion and we go all the way down, you know, and then return here.
Then you know, what's happening?
So you can go through some examples with both these functions and see see how it works, but I'm just
doing this for printing purposes.
You can go back and look at mortgage reversals to get a better understanding, in-depth understanding
of them.
We talked about a few, but this is.
An extra one level order, I'm just doing it so we can look at the structure of the tree because I want
to make sure that, you know, our tree structure aligns with what we predict the not what we predict,
but we'll go through the rotations and our tree should have a certain structure at the end.
And that's how we're going to verify this by doing this.
OK, so that is all I'm going to have, actually, and here and so I'm actually going to head over to
Main.
And here we're just going to write some basic clan code to get this stuff going, so let's go ahead
and have our stream in here.
I'm going to want.
Actually, no, I don't need that.
I don't need that.
We're going to need actually like a stream.
So I'm going to include stream because I'm going to need to open that file and then I actually want
to go for that doesn't run on that or whatever.
But I want to include the Avielle to be able to see that h.
And then I'm going to add my number of args.
I see and then the entire ARG B because we have command line arguments.
I'm going to get rid of this, do my standard check to see if there hasn't been an argument provided.
And I need to say, you know, this is how you use it.
Yeah, I do want that.
In that case, then I anyone ask Jane, you know, I got rid of that.
So we'll say, you know, usage is key.
All right.
Zero, just the file name and then.
Name, brand, image, file.
So just tells us to have the name of the executable and then the name of the Empire file as well, so.
And actually, this like I traditionally just had like an exit here as well.
So this will be, you know, like I said, what's a problem?
Exit code, negative phone or something like that?
OK, so I'm going to do an input file stream and call this file and.
And when I opened it, this will be ugly, one will be the input file name.
I'm going to make an Avielle tree object.
So a real tree, I'm just going to call this tree.
People knew a real tree and I'm going to have this integer versus a variable so I can read into it.
And then here's where we're going to insert into the tree and all the while loop.
And I'll just say, well, file and read into the.
Three and I will say three in search value.
And then here I will say tree level or down to printed out.
So should be.
Printed out in that specific order.
So.
Yeah, and then I have my return zero down here.
I think we should be all good to go.
So I've already done my edit configurations.
It may or may not run right now, so we'll just have to you.
Double check.
But I have my input file here.
With these numbers.
And so, first of all, I'd like to do is just have us walk through building the tree with these numbers
and then we will verify that it works.
So let's go ahead and walk through that.
So here's our list right here.
We insert 12.
And so we're putting that of the route go to the next, we insert twenty one and now I'm not writing
the balance factors on here, but let's just check them left minus right zero zero minus one is negative
one.
Everything's fine there.
Here we have a problem.
We add thirty three and we have, you know, zero for this negative one for this one.
And then we have a zero minus one to its negative two.
So we have right right.
We need to do a right rate rotation.
So if we do that right, right rotation, we just bring this one down and then we have this so zero,
zero and zero now.
So now we add 24 into the mix and we should begin, this is zero.
And then we have one more serious one.
This is zero and then we have one minus one to its negative one.
So that's fine.
And we add twenty nine and we have a problem.
This is zero.
This is a negative one.
And this is, too, because we have one to minus zero is two.
So this is a left right.
So we're going to have to rotate this.
So the 29 is going to cut up through here and then it'll branch off its right around thirty three and
left child 24.
So twenty nine came up, left child, 24, right child, 33.
So while balance now we add twenty six and we have a problem again up here, so it's zero zero minus
one minus one.
This is zero.
We have one to minus one that is going to be one.
And then this is zero and then we have one minus one two three.
So that's negative two.
So we need to rotate about this.
So let's go ahead and do that.
So, you know, we're going to bring that 24 of through here.
And the I believe the 26 is going to be attaching to here and then 24 will become the new route.
Yes.
So 24 is a new route.
Let's just go through that again, 24 comes up through here and then branches up to 21 and then 29.
And then this guy gets attached to the 29.
OK, so let's go ahead and to this one, we add our final number three and now we have an imbalance
over here, so this is zero.
And then this is one of my series one and then one two minus zero is actually two.
I keep messing up these numbers all the time.
I'm sorry.
That must be annoying for you guys.
But this is too too much, too serious, too.
We're going to have to do this rotation here, so that is just going to be the 12 coming up and the
21 coming down will be 12 to three to 21 like that.
And now we have finished our tree, so we expect it to look like this.
The level order dump should be something like 24, 12, 29, three, 21, 26, 33, something like that.
So let's see if this actually works.
Let's go ahead and run it.
OK, so.
24, 12, 29.
Yeah.
Twenty four, then 12, then 29, then it should be three, 21, 26, 33.
Three, twenty one, twenty six, thirty three.
OK, so seems to all match up.
All right.
So that was a lot of, uh, a lot of information.
A real trees are.
Kind of difficult, a little bit tricky.
An interesting thing, I might have already mentioned this in the lecture, but I'm sorry if I'm repeating
myself.
When we were doing the hash tables.
A neat thing that you may or may not have covered yet is unordered map in C++, which is a steel type
that is something that uses hashing.
I believe it uses something kind of like chaining that we were using instead of the unordered map and
then a map, just a normal steel map type in C++.
It's another thing that you can have keys like put in a key and get a value out of.
It's a key value pairs that type of data structure, but that actually uses a self-balancing tree.
I'm pretty sure it's not an evil tree.
I think it's a red black tree.
But you know, that's something I just wanted to point out.
It's quite efficient compared to the unaltered map, actually.
So if you'd like to learn more about that, you can go look up the C++ map and C++ unordered map, and
you can read about how those are implemented.
The map should be a balanced tree, I believe is how they did it.
And then an ordered map is some type of hashing, which I believe is not as chaining instead of some
type of training instead of like another probing one or something like that.
So, yeah, some you know, that was just an example I wanted to give of a usage of a real tree.
It's already kind of in place, you know, with the C++ language.
Well, it's not any real true, but a self-balancing tree, you know, a usage of a self-balancing tree
like we've done here.
OK, so I hope you enjoy that and we'll see you for the next topic.