OK, so we're going to go ahead and pick up where we left off last, which was right before doing our
insert function, so we're going to get into doing that insert function in this lecture and do all the
rotations and all that good stuff.
And I will be going along with some visuals as we work through it, so it'll helpfully help explain
it well enough.
So let's go ahead and get started.
So I'm going to go ahead and make this public facing function here.
The I think I made them make them both.
Yeah, I made them actually both public.
I should probably have this one be a private function, actually.
So yeah, I mean to kind of put that here.
All right.
Yeah, I guess these probably should actually be private as well.
So I'm going to go ahead and put these in there.
All right, so let's go ahead and do that, one that will call from the client file, which will pass
the value, and I'm just actually going to be resetting this the route here.
So what I might do is just to route equals
local insert and I'll pass the route and devalue.
So that's all we're going to be doing in this function.
All right.
So let's go ahead and do the actual function with the work, so, so be it the lottery and then local.
Oh, do you actually know what it is?
This should be no.
No pointer.
Yeah, all agree.
All right.
So let's go ahead and get started.
So this is actually going to be a recursive function, and I'm trying to explain it the best I can.
It might sound a little confusing, but what we're going to do is a traditional kind of insertion function
for a binary search tree kind of where we're checking to see if the.
Route.
Kind of keep going down in like traversing the tree based on like comparing the value at the roots.
So we'll get we'll use that get value function from our node class.
And of course, you know, if the value is greater, we'll go to the right as a value.
Celeste will go to the left.
So we're going to do that.
But we're also going to have to do the whole balance factor thing and call the functions that do rotations.
And so basically, what we're going to do is that traditional binary search, tree insertion part.
And then we're also like below that, we're going to have to be doing calculating balance factors,
kind of checking the condition where we check the balance factor.
Of the node that will be rotating about and then we're going to actually have to return like a call
to one of those rotation functions because that rotation function will actually return like.
The no, the sub trying to organize the submarine or return the root note of that sub tree, and that's
actually what we're going to be setting as our like our values and stuff.
You know, like if you set a sub tree, if you like, do the rotation on the sub tree, you know, you'll
be like pointing to some given route.
So that's why we're going to be doing it that way.
So, yeah, sorry, if that didn't make sense, we'll get more into it in just one second.
So I'm going to make a base case here.
Of course, our traditional if is null pointer.
So this is, of course, checking to see if we're at the base node of a tree in which we want to create
a new node in that case.
So I'm going to say node pointer in in for new node equals new node and we'll use that constructor where
we pass the value right away.
So and then I'm actually, yeah, I just do return new node.
So.
Yeah, that'll be.
The case in which we can just add it to the end there, so otherwise I'm going to do if the value is
greater than the value at the current rate.
So that's good value.
In this case, I will do that left sub three recursion.
So what I'm going to I'm actually right out here to the left.
So you.
So we left sub three.
And what I'm going to do for this is, Oh, actually, I did this wrong.
I'm sorry.
This is if the value is greater than the value.
So this should be a race sub tree.
My bad?
Sorry about that too, right?
So tree recursion.
And so I'm going to recursively set this right sub tree.
So.
Basically going to.
Do a recursive call, so hopefully this isn't too confusing, but I'm going to do a recursive call to
local insert past the left sub tree and the value.
And so basically this is going to go all the way down, of course, telecast this base case and it's
going to add a new node so you can think about it.
It initially gets passed like the root node and then so it can start at the top and then it gets past
the value.
It's basically going to compare it go all the way down the tree using this type of thing right here.
So it'll keep setting the right sub tree in this case to hide it.
I put the left sub tree in there again.
Very sorry, I keep putting the wrong things in there.
So we want to call the right symmetry.
I'm sorry for putting the left sub tree.
That must've been confusing, so we'll want to recursively call with the right sub tree and kind of
keep going down and setting it, setting that sub tree correctly, you know, as we go down.
So it's kind of, you know, interesting way of doing it, but hopefully that makes sense to you.
So.
Yeah, I might just, uh, yeah, let me just put normally that in the brackets here and let's see,
did not put a semicolon on there, so that's why it is red.
So then we want to say else if it's less than and this will actually be the last century.
So if value is less than real, give value, then we will, as the left, said Tree.
OK, and so we will set the less arbitrary to this, you know, recursively going down and passing the
left sub tree as long as the value is less.
So.
It's kind of our traditional like building tree, you know, insertion, but then now we need to accommodate
for these imbalances, you know, so we're going to call our balance factor function and then we're
going to have to do some rotations.
So one I say, if there is a left left in balance and now I want to hop over to some drawings of these
things because I want to explain what I'm about to do with this with this code here.
So right here we have a left left rotation for this left left imbalance.
And you can think about that also like we talked before.
About, you know.
The imbalance is coming from a the direction of the greatest height or whatever, so we have this left
left imbalance.
So the path that was calling it causing that imbalance for us to do it left left rotation was left left,
you know, it went this way.
You notice here that we have this like one to three and we're subtracting one from up here, and that's
making it to.
So we the way that we're going to be able to look at the balance factor.
And know what type of rotation to do.
Is based on the looking at the route, the current node that we're on.
And also, these combinations of.
It's like less of a tree or write some tree.
So you notice in this left left rotation scenario, we have two right here for our balance factor.
And then we look at this left some tree of fruit.
So you've noticed that I put, ah, four root and then right here I put RL in that stands for root left.
So routes left Sudbury.
We have a two here, and then we have a one right here.
And we have a one right here, because of course, if the left sub tree, you know, we had left left
and this was.
This direction right here was what was causing that imbalance.
When we go down to this node right here, we see that we have two right here and one right here.
So left some tree minus three, some tree two minus one is one.
These two numbers kind of give us an idea of what type of rotation we have to do and we can rely on
them to be, you know, within the range of negative two to two because once we start building our tree,
we're constantly checking these balance factors, you know, so we don't really let it get outside of
that range.
And that is why we can rely on looking at the balance factor of the root node and the balance factors
of either here or here coming from the root node.
And that is how we are going to write our code.
And so I wanted to explain that before we just write our insert stuff here, even before we go into
the actual implementation of the balance factor functions.
So let's think about that.
We have a left left rotation.
We notice that the root node is going to be two and the roots left some trees.
Balance factor is going to be one, and that means we need to do a left left rotation.
So we're going to go ahead and do that.
I'm going to say if the balance factor of the route is equal to two and the balance factor of the routes
left, some tree is equal to one.
What about that then?
In this case, we are absolutely not going to need those because we're just going to do the turn left
left rotation and we're going to pass the current node, which will be.
This root node, we're going to pass that to the left left rotation function to do this rotation right
here, which I'll get into in a moment.
But right now we're just going to right the first calls to our.
Rotation functions in this local insert function.
All right, so let's head on to the next one.
Say if there is a left right imbalance.
So if there is a left right and balance.
So let's take a look at that.
I have the.
Left, right, right here.
So you notice that in this first picture here we have a negative two as the rude because we are going
one to.
And then, you know, one to and then like three, whatever you want to consider it, you know, three
or three this way we have this one to three.
You know this high of the left sub tree from Root is three and a high of the rates of tree is one.
So three minus one is negative two.
You know, this can be taken away or this can be taken away and we do the same thing.
And then we have, you know, since it's a left right violation, we're going to go ahead and look at
this one and then we're going to look at the next node.
You know, this is the left and then this one has the right.
So we're going to take this node into consideration as well.
And you notice that this balance factor here is one for this left right rotation.
So we have, you know, it's left.
Some tree is one and the height of the right is two.
So.
We actually yeah, that should be yeah, that's actually incorrect.
I'm just noticing, yeah, so this should be one minus one two, so that should be negative one.
So I should actually correct that I will correct that right now.
Yeah, sorry, I make some mistakes sometimes.
But, you know, I guess as long as I catch them, hopefully it's OK.
So yeah, this is a left this one minus one to four, the race increase, so one minus two is negative
one.
So that's what we're going to be
using for for this, actually.
So this and actually this shouldn't be negative to I don't know why I put that to.
I made another mistake here.
So this is.
Two sorry about that, I'm getting that super super mixed up.
Sorry about that.
So yeah, we have one to three minus one is two.
So I made that correction right there.
Apologies again.
So these are the numbers that we're going to use for the left, right and balance.
Then we're going to be checking to see whether the balance factor is to for the route and whether the
left symmetry of the route is minus one.
So let's go ahead and check for that.
So I must say, if the balance factor of route equals two and the balance factor of the route left century
equals negative one, then we will do you a return left right.
But it's a great rotation.
And of course, passing the just like before.
OK, so let's do if there is a right, right and balance.
So I'm going to say OK, if balance factor route equals and what would this be?
Let's take a look.
Hopefully, I don't have a ton more mistakes, but definitely possible.
So we're doing right, right?
Looks like this one is correct, sir.
Thankfully, I did not mess up the numbers here, so we have one for the last century and one to three
for the rights of trees, so that is minus two.
And let's see this one right here.
We have one for the left cemetery and one two for the right cemetery, so that's minus one.
So this is a scenario in which we'd have the right right rotation.
The imbalance is in this direction.
And even though we could have trees that were different than this, you know, there might be more values
over here.
We're talking about the case in which whatever values are over here, you know, there is an imbalance
that has happened suddenly from this direction being, you know, larger than the notes over here.
In which case the I'm talking about the height of the trees over here, in which case we would have
to perform this right, right, OK, rotation and we since we are following this formula from the beginning,
with that range of negative two to two, you know, we're not going to be carrying her values.
We can rely on these two numbers to tell us the type of rotation.
So just want to reiterate that.
So the negative two and negative one will be the values that we're using, and that is the root in the
root rate sub tree.
So let's go ahead and do that.
So balance factor equals negative two and the balance factor of the risk, right?
So tree equals negative one
e are.
He goes and he's another parentheses there.
Sorry about that, um.
And that doesn't mean there.
OK, so we will return the right great rotation period.
OK, and then let's check our final one, which if there is a right left, I believe, yeah, right
left in the balance.
And so if the balance factor of the route equals, let's go look at this.
So right, left.
Let's double check to make sure I haven't messed up the values again, so this looks good and yeah,
this looks good, OK?
It looked like that was the only one that I messed up was that that final slide there for the left right?
So we have one minus one to three or three.
So that would be negative two.
And then we have one, two or two minus one makes it one.
So we're looking at the route to be negative two and the roots right to be one for this scenario, which
we perform a right left.
So let's go ahead and do that.
We have the route is negative two and the balance factor of the route, right?
So tree is equal to one case.
We return right left rotation at the root.
OK.
Perfect.
So we performed the rotation there, and then what we're going to do is just like we were returning
the route.
We're turning the new node right here.
What we're going to do is return the root in this case, so.
Will add a new node will need to return that will need to perform those rotations if necessary, after
adding that new node, if it becomes an imbalance and then regardless of the situation, we are going
to return the root so current node that they're on for us to return.
Someone put that down there.
OK, so let's get into these.
Balance factor functions.
And for this, I think I'm actually going to maybe stop the video right here and start a another video
so we can actually just focus focus on those.
So yeah, we got this insert out of the way.
In the next lecture, I will go ahead and go over these those images again, and we will do each of
these rotation functions.
So CNN.