OK, so in this lecture, we are going to be talking about something called Avielle trees.
So to do that, we're going to take a look back at the binary search tree stuff that we've been doing.
So one of the major issues that we had with the binary search tree was the worst case input into it.
So that was when we had something in descending, sorted order or ascending sorted order.
And if you remember back to that, it caused a minor search tree to basically become an imbalanced tree
to the point of it just being a linked list, which wasn't good because one of the good things about
the binary search she was its structure that gave us that log in search time.
But when it was a linked list, we had to basically abide by the time complexity of the link list because
it was the same size of the input, so it was linear time.
So let's go ahead and just recap on that right here.
We're going to have these two examples of descending and descending sorted order input just to show
you once again what we're talking about.
So we start out here with this input five, four three two one.
So the route now will be five.
The four comes in, it becomes the left child because it's less than five.
Three comes in.
It's less than five and four.
So we have another left child and so on and so forth down to one.
So you notice this is just like completely left leaning.
And so it's essentially a linked list at this point.
So if we do it the other way we start with one is the rule.
Two is greater than one.
Three is greater than one or two and so on and so forth.
Now we just have a right leaning tree that's basically a linked list as well.
So that's kind of what we're talking about with the issue with standard binary search tree.
The Avielle tree fixes this problem.
By self-balancing, so it belongs to a class of trees that we refer to as self-balancing.
There are some other trees and I'm not going to go over that can do similar things like red black trees
might be one of them, but I'm not going to cover that.
I'm just going to go over one of them and I pick the real tree.
So that's what we'll be looking at.
How does it achieve this?
Well, what it does is it actually assigns a special number to each node that is referred to as the
balance factor.
The balance factor for a certain node is decided by subtracting the height of the rights of tree coming
off that node from the left some tree, so we do less of tree from that node minus rates of tree.
If you're thinking about the height, you basically just follow the path from that node to the left.
To get the height of the last century, you would find the biggest path down to a root node from that
initial left pointer.
So if you're at a node, head to the left, go down the longest path to the bottom of the tree, and
that will be your height.
Then same thing for the rights of Tree, of course, the height of the wrath of tree.
And after all, these balance factors are assigned to each specific node.
We then are going to check to see if any of those balance factors are greater than one or less than
negative one.
You can also think of this as just taking the absolute value of the balance factor.
And if it is greater than or equal to one or sorry, if it is greater than one, then that is a problem.
So in the case that it is greater than one, we will need to perform something we call a rotation on
that subject area and that will rebalance the trees so we can get that time complexity that we want
and maintain the structure of the tree.
That's ideal.
So I'm I go over just some examples of rotations, but first, we're just going to calculate the balance
factors of these four different scenarios that we'll be running into, where each one will require different
rotations.
So let's just look at the balance factors first.
So let's start on this one over on the left.
This is going to be like a tree example just has three nodes.
Let's go ahead and look at this bottom one.
So bottom node, we have a height of zero minus a height of zero.
So that's zero.
The next one.
Let's head down the last century.
We have one, so the height of the century is one minus zero for the rates of tree is one.
So balance factor of one.
One to four, the last century, zero four, the rates of trade, so to minus zero is two.
And that is a problem.
That's why I've highlighted in red.
So we said that if it's greater than one, that is an issue, if the absolute value is greater than
one, that is an issue.
So let's go ahead and do this other example, zero for the bottom.
Then we have zero minus one that's minus one.
Then we have zero minus one two, which is going to be minus two.
Once again, that's an issue.
It is less than negative one.
Or if you're thinking about the absolute value, it is greater than one.
The absolute value of this is two, which is greater than one.
So let's see this other one.
We have zero again.
Then we have zero minus one, so minus one.
Then we have one two minus zero, so that gives us two.
Zero down here on this one.
Then we have one one two zero one and we have zero minus one two, so that's going to be minus two zero
minus two.
OK, so let's start on the left again.
And now we're going to go through some different slides where we talk about these actual rotations that
we're going to have to do to balance these four different scenarios.
So let's look at this one first.
That one is going to be called an El Al rotation, which stands for the left left.
And so it's essentially the turns that we are making.
So we're taking the left and a left from the violating node.
But technically, we can just say the imbalance is due to the height of a sub tree.
That is the left child of the left child.
So that is going to be our legal rotation, the violation notice here when we're going down to get our
height from there, we went left and left to get that height.
So that was one to minus zero.
So we're considering this height.
That was problematic to give us this bounce factor here.
And to do that due to the rotation, you see this yellow arrow.
We're taking this node and we're actually bringing it just down to here, right here.
So the three is going to go here and the two is going to be pointing to the three.
The three will be the right child at the two.
So let's look at that.
Just like that, the three came down here and became the right child of the two.
So that was a left left rotation.
And the left left is not for the rotation that we're doing it because it's it's named after the fact
that it's a left turn and a left turn made this the violating node.
The problem with the height.
So let's look at a right right rotation.
So that is just the opposite of the left left.
So we have, you know, a right turn and a right turn here to get our height and the fact that this
has zero and this was to me to have this imbalanced balance factor here.
Same thing.
We're going to bring it down here.
Take this note, and we're going to send it right here and the two is going to have a left child of
one now.
So we see that right here now, we're all balanced after we do that rotation, so that is a right right
rotation.
A left right rotation, just like it sounds and just like we saw before, we have a left turn and a
right turn for our problematic height issue with the balance factor for this one, though, there's
kind of like two steps, like there's a couple sub steps, we'll still consider it one rotation as far
as when we're going to implement this in code, but we actually are going to have to do two little mini
steps.
The first step is going to be to take the low air node here and bring that up in between these two nodes
here.
So we're taking this lower note, bring it up in between here, that gives us something like this.
So now we have three and then two and then one.
And what we're going to do at that point is we're going to do what we did for that left left rotation.
We're going to take this three up here and move that three down here.
So it's two little steps here.
We took the two, put it in here, then we took the three and we're bringing it down here, and that
gives us a nice balance again.
So you can break it.
It's a little easier, I think, to break into two steps.
But if you want to just think about it in one rotation.
An analogy I kind of like to think of is like, you know, little spheres or what have you with strings
on them.
And so I imagine that I had some type of, you know, the thing that I'm moving from the bottom right
here.
Like, if I had this and there was a string going here and a string going here and we had gravity and
I took this and brought it up through here, then it would basically be, you know, if I brought the
two and I brought it like way up here.
The strings that connected to here and here would be pointing down to the three there and to the one
just like this.
So if you want to think about the rotation in that sense that you grab this and just bring it up through
here and then you draw lines down like this.
That's another way you can think of it, but it's kind of nice to break it in the steps, as we'll see
in the near future here, because when you have, you know, bigger sub trees where there's more nodes
coming off of these nodes down here, like larger centuries, it gets a little confusing when you're
trying to think about changing pointers and things like that.
So that's why I think the two step idea is a little bit better, but totally up to you.
Right, Leffler wrote rotation, so let's let's think the opposite of the last one, we're going right
and then left.
For the balance factor issue.
That's why it's called right left rotation, same thing, we're going to take this, bring it up through
here and then we're going to take this one and bring it back down.
So we do that first.
We took the two, put it in between these two and then the ones coming back down here to be the left
sub three of the two.
Just like that.
OK, so now I'm going to go over some bigger examples just so you know how to do it with a more realistic
tree.
So I already have some balance factors here that I forgot to feed in, so let's go ahead and populate
it with the balance factors.
So I already left those two there so that they can anti-climactic intro to this, but we have zero here,
one for this, you know, zero here, this is not a problem.
One two minus one, that's just one.
This was zero.
But this is going to be an issue here because we have one to three minus one gives us to appear.
So this is a situation in which we are going to have to do a left left rotation because if we look at
the violating, no.
If we go down this direction.
Towards where it was, the height was problematic, we have a left left.
And so this is where we're going to have to basically think about the fact that we're going to just
be talking about three nodes essentially all the time because you take two turns like two pointers that's
going to connect you with three nodes.
So it start on this one, the violin and Owen, and then we take a left and a left.
So we're always going to be talking about three nodes that we're going to do a rotation on.
So, you know, the height was one to three.
We're only going to perform the rotation on these three nodes here.
We're not going to do anything with this fourth, as far as the type of rotation we're doing and the
movements we're doing.
So just keep that in mind, like the turns are, you know, two pointers because we're going to be rotating
three nodes there.
So let's see how we would do this.
So just like our left left examples we've gone through before.
What we're going to do is we're actually going to take our tin up here and we're going to bring it down
as the right cemetery of eight.
But there is an issue, and that is that we have this 9:00 right here is already there.
So this already has a right century.
So what are we going to do with that?
Well, since it is part of this sub tree, we're actually going to just be able to connect it.
So let's go ahead and look at that.
Let's move the nine out of the way for a second.
We bring the tin down, and since nine was part of that left some tree initially.
So let's go back here.
Nine was on the in the last century of 10, when we break 10 of 10 has a right century here that we're
leaving on there 18.
But when we detach this from the eight, this point right here, it's just doesn't really have anything
that it's pointing to.
So what we're going to do when we bring this down here, we're going to have this left pointer point
to this sub tree right here.
So that's what we do.
We move the ten down here.
The ten is right here and then we connect the nine to this 10 right here.
And then we have a tree that no longer has any problems if you calculate the balance factors again.
You will see that this tree is no longer problematic.
So that was a left left rotation.
So now we're going to look in a bigger example of a right right rotation.
So let's go ahead and check that out.
So what will this look like?
We'll start with our balance factors, so zero zero.
Zero for this one minus one.
It's go out of this leaf that zero.
This is here as well.
This is serious, well, this is minus one because zero minus one.
This is one one minus zero.
This is one minus one to.
This is one two minus one to three.
But this is problematic because it's one to minus one to three four.
So this is going to be an interesting one because we're actually rotating with the note on a pretty
big tree here, so.
Let's go ahead and walk through it.
So this is a right, right, because if we're going down the direction that you know, the larger hype
that caused this imbalance, we would take a right and a right.
So remember, we're talking about those three notes.
That's why we're just doing right and right for this right, right?
Location rotation and thinking about these three a.m.
This note up here is actually going to come down just like we talked about before.
We're going to bring it down and it's going to be right here.
But once again, we have this sub tree right here that we're going to need to connect to.
So let's take a look.
So things kind of moved out of the way, but what I did there was I took the 10 and I moved it over
here.
So we started like this and I took this and I moved out here so we could look at this section.
So that's what we're doing.
I still have the place we were going to want to put the 10 with this arrow here, but we're going to
need to think about this one.
So what do you think is going to happen with this 12?
Or if we think back to the previous example of left left and we're just thinking about it, the inverse
situation here.
We broke the tin off and it has this sub tree over here connected.
But now it has nothing connected here.
So just like the last time, we're going to take this and fill that void with this sub tree here since
we need to move the tender to here.
And that's what we will do, so now we put 10 in the place that we needed to.
We brought it down here and then the fact that it had this kind of empty pointer here that was previously
pointing to something we're going to take this country.
That was the one that was right here, and we're going to attach it to this right.
So three of the 10.
OK, so now we have a balanced view.
And brought it up here just to make it look a little bit better.
Now let's look at left, right and a bigger example.
So we have zero.
We have one here, zero kindness going randomly now to fill these balance factors.
But you can do all the Leafs first and do it level by level if you wanted.
We have zero here.
You kind of want to count up from the bottom, though that is an important point because you want to
if you encounter a balance factor somewhere here in this sub tree, you'll want to do a rotation on
that first.
You want like, you know, if you when you encounter a problematic balance factor like down here, like
you would do that rotation without necessarily thinking about.
The bigger ones, you know, you're rotating it in that type of way.
So we have minus one here, this is one minus two.
One to one to three, that's minus one zero.
That's a leaf of zero because it's a leaf zero, because it's one on one.
Then this is two because we have one two three and then we have one to.
So actually, that's not three one to three four is the maximum, and then we have one two, so four
minus two gives us two.
So remember back to the left right rotation, we're doing left right because this was the direction
that had for that threw off the balance factor, and I did not tell her that read apologies for that.
I would only just have this read because it is the violating balance factor.
The violating, no.
So just for 10 minutes.
Read my apologies.
We're going to take this further left right rotation because it was the direction of the violating hate
that caused the problem.
And we're going to take this A..
Move it up between these for the first step, so we'll have 10, 12 and 18.
And then we're going to take this and move it down here, this 18 will come down here.
So that is how we're going to perform this rotation.
So let's look at what we did right here.
We have the 18 and the 10.
We kind of broke it apart because we're going to move the 12 in here.
So we have this section in this section that took this section right here and this section right here
and split them apart.
And then we have this coming up here.
So.
We initially moved the 10 to this, because if we think about it, we're moving, we've brought this
tent away and we're moving this 12, that's leaving this thing hanging.
So we're going to need to connect this 11 to it.
So that's why we did that.
And so now we have this point where we're connecting the 12 to here and 18 to the 12.
So the 11 was initially on the 12, but now it's going off to the 10 because we lost attending in there.
And so that's what it looks like, completed after the first step.
The next thing is to bring this.
Eighteen up here, down below the 12, so this is basically another left left rotation to the second
part of it is basically the same as the left left rotation, just like we talked about before.
So to do that, things like shifting a little bit here.
But let's look, let's look back at that took the 18 and just moved it down here.
So this whole 18 century got moved down when you need to put it right here.
So this got left hanging here after 18.
So that's why we're going to take this sub tree, which is the area we want to move the 18 to and we're
going to attach it to the left sub tree of the 18.
So that's what we do, we attach this and we end up with a tree like this.
So our balance factors are no longer an issue in this tree.
All right, now, let's look at a right left example.
So let's do our balance factors.
We have zero one zero.
One here.
One two one two one zero zero zero one one.
And then right here we have a problem because it's one and then we have a one to three.
So one minus three is negative two, so I think this balance factor up there, but this is the one that
is problematic right now because as the balance factor that is the absolute value is greater than one.
So.
We have right left for this rotation because we're going down to the height that was the offender,
so what we're going to do is move this note up.
So think about the last example we have.
This is basically the inverse of that.
We're taking this note right here or moving it up between this 18 and this 26.
And then the next thing we'll do is we will move the 18 down to here, so into this spot right here
where this 25 was.
So let's do that.
We break these apart right here and we move to 25 in between.
So we have those right there.
And we connected those, and now we need to move the 18 down to here.
So we're going to do that and move the 18 down to here.
And then that 23 is going to connect because of we move, the 18, 20 three was connected to this 25,
but only move the 18 is left hanging right here.
And so now we're going to take that twenty three and connect it to here.
Another way to think of it is that twenty three was part of 18th right century, and since we need to
move 18 to this spot and push twenty three out of the way, we will still keep it as the right cemetery.
So that's why we put it here on the right cemetery.
OK, and now we can just connect this whole thing back up.
And we have a balanced three, you know, balance enough, not violated any more.
OK, so hopefully that explained all of the rotations.
I might try and include some links to some visualizations and animations you can look at online.
It's really just kind of practicing these.
She go through insert a bunch of values into a binary search tree with examples and just draw it out
on paper or something like that is probably the easiest and make the rotations as you're inserting.
So each time you insert a new node, recalculate all the balance factors from the bottom up.
And then basically the second you have a violating node that you notice like you should definitely go
through and perform a rotation on that before you insert anything else.
So you can maintain the balance tree throughout the insertion process.
OK.
So with that, I'll see you in the next lecture and we'll be looking at how to write some code to implement
this.