1
00:00:00,790 --> 00:00:07,150
OK, so we're going to go ahead and pick up where we left off last, which was right before doing our

2
00:00:07,150 --> 00:00:15,220
insert function, so we're going to get into doing that insert function in this lecture and do all the

3
00:00:15,220 --> 00:00:17,070
rotations and all that good stuff.

4
00:00:17,080 --> 00:00:24,580
And I will be going along with some visuals as we work through it, so it'll helpfully help explain

5
00:00:24,580 --> 00:00:25,570
it well enough.

6
00:00:25,840 --> 00:00:28,480
So let's go ahead and get started.

7
00:00:29,380 --> 00:00:34,420
So I'm going to go ahead and make this public facing function here.

8
00:00:37,150 --> 00:00:41,140
The I think I made them make them both.

9
00:00:44,310 --> 00:00:48,720
Yeah, I made them actually both public.

10
00:00:49,170 --> 00:00:54,390
I should probably have this one be a private function, actually.

11
00:00:55,620 --> 00:00:59,970
So yeah, I mean to kind of put that here.

12
00:01:01,890 --> 00:01:02,250
All right.

13
00:01:02,550 --> 00:01:07,350
Yeah, I guess these probably should actually be private as well.

14
00:01:08,280 --> 00:01:12,890
So I'm going to go ahead and put these in there.

15
00:01:15,320 --> 00:01:21,320
All right, so let's go ahead and do that, one that will call from the client file, which will pass

16
00:01:21,320 --> 00:01:29,750
the value, and I'm just actually going to be resetting this the route here.

17
00:01:31,370 --> 00:01:35,930
So what I might do is just to route equals

18
00:01:38,450 --> 00:01:43,520
local insert and I'll pass the route and devalue.

19
00:01:43,640 --> 00:01:45,800
So that's all we're going to be doing in this function.

20
00:01:48,560 --> 00:01:48,900
All right.

21
00:01:48,920 --> 00:02:00,440
So let's go ahead and do the actual function with the work, so, so be it the lottery and then local.

22
00:02:04,260 --> 00:02:08,760
Oh, do you actually know what it is?

23
00:02:08,940 --> 00:02:10,230
This should be no.

24
00:02:12,300 --> 00:02:13,280
No pointer.

25
00:02:15,010 --> 00:02:17,460
Yeah, all agree.

26
00:02:18,220 --> 00:02:18,550
All right.

27
00:02:19,120 --> 00:02:21,520
So let's go ahead and get started.

28
00:02:22,320 --> 00:02:28,860
So this is actually going to be a recursive function, and I'm trying to explain it the best I can.

29
00:02:28,930 --> 00:02:34,480
It might sound a little confusing, but what we're going to do is a traditional kind of insertion function

30
00:02:34,480 --> 00:02:41,350
for a binary search tree kind of where we're checking to see if the.

31
00:02:43,510 --> 00:02:44,020
Route.

32
00:02:46,850 --> 00:02:53,360
Kind of keep going down in like traversing the tree based on like comparing the value at the roots.

33
00:02:53,360 --> 00:02:56,300
So we'll get we'll use that get value function from our node class.

34
00:02:56,900 --> 00:03:00,740
And of course, you know, if the value is greater, we'll go to the right as a value.

35
00:03:00,740 --> 00:03:01,940
Celeste will go to the left.

36
00:03:01,940 --> 00:03:03,200
So we're going to do that.

37
00:03:03,200 --> 00:03:11,600
But we're also going to have to do the whole balance factor thing and call the functions that do rotations.

38
00:03:11,600 --> 00:03:17,090
And so basically, what we're going to do is that traditional binary search, tree insertion part.

39
00:03:18,350 --> 00:03:25,550
And then we're also like below that, we're going to have to be doing calculating balance factors,

40
00:03:25,550 --> 00:03:28,790
kind of checking the condition where we check the balance factor.

41
00:03:30,130 --> 00:03:38,410
Of the node that will be rotating about and then we're going to actually have to return like a call

42
00:03:38,410 --> 00:03:48,400
to one of those rotation functions because that rotation function will actually return like.

43
00:03:49,470 --> 00:03:55,200
The no, the sub trying to organize the submarine or return the root note of that sub tree, and that's

44
00:03:55,200 --> 00:04:02,760
actually what we're going to be setting as our like our values and stuff.

45
00:04:02,760 --> 00:04:07,770
You know, like if you set a sub tree, if you like, do the rotation on the sub tree, you know, you'll

46
00:04:07,770 --> 00:04:11,550
be like pointing to some given route.

47
00:04:11,550 --> 00:04:13,770
So that's why we're going to be doing it that way.

48
00:04:15,570 --> 00:04:19,350
So, yeah, sorry, if that didn't make sense, we'll get more into it in just one second.

49
00:04:19,350 --> 00:04:22,140
So I'm going to make a base case here.

50
00:04:22,380 --> 00:04:24,900
Of course, our traditional if is null pointer.

51
00:04:27,240 --> 00:04:33,090
So this is, of course, checking to see if we're at the base node of a tree in which we want to create

52
00:04:33,090 --> 00:04:34,720
a new node in that case.

53
00:04:34,740 --> 00:04:45,180
So I'm going to say node pointer in in for new node equals new node and we'll use that constructor where

54
00:04:45,180 --> 00:04:47,130
we pass the value right away.

55
00:04:47,220 --> 00:04:55,270
So and then I'm actually, yeah, I just do return new node.

56
00:04:56,970 --> 00:04:57,390
So.

57
00:04:59,300 --> 00:05:00,530
Yeah, that'll be.

58
00:05:02,350 --> 00:05:14,170
The case in which we can just add it to the end there, so otherwise I'm going to do if the value is

59
00:05:14,170 --> 00:05:17,780
greater than the value at the current rate.

60
00:05:17,790 --> 00:05:19,780
So that's good value.

61
00:05:22,540 --> 00:05:28,720
In this case, I will do that left sub three recursion.

62
00:05:29,650 --> 00:05:33,460
So what I'm going to I'm actually right out here to the left.

63
00:05:33,640 --> 00:05:34,720
So you.

64
00:05:37,210 --> 00:05:40,210
So we left sub three.

65
00:05:40,510 --> 00:05:47,220
And what I'm going to do for this is, Oh, actually, I did this wrong.

66
00:05:47,230 --> 00:05:47,720
I'm sorry.

67
00:05:47,740 --> 00:05:51,280
This is if the value is greater than the value.

68
00:05:51,280 --> 00:05:55,930
So this should be a race sub tree.

69
00:05:59,050 --> 00:05:59,700
My bad?

70
00:05:59,710 --> 00:06:01,360
Sorry about that too, right?

71
00:06:01,750 --> 00:06:03,160
So tree recursion.

72
00:06:03,790 --> 00:06:09,310
And so I'm going to recursively set this right sub tree.

73
00:06:09,670 --> 00:06:10,270
So.

74
00:06:11,670 --> 00:06:13,500
Basically going to.

75
00:06:16,030 --> 00:06:22,390
Do a recursive call, so hopefully this isn't too confusing, but I'm going to do a recursive call to

76
00:06:22,390 --> 00:06:28,840
local insert past the left sub tree and the value.

77
00:06:29,170 --> 00:06:34,390
And so basically this is going to go all the way down, of course, telecast this base case and it's

78
00:06:34,390 --> 00:06:39,100
going to add a new node so you can think about it.

79
00:06:39,100 --> 00:06:45,040
It initially gets passed like the root node and then so it can start at the top and then it gets past

80
00:06:45,040 --> 00:06:45,820
the value.

81
00:06:46,660 --> 00:06:52,840
It's basically going to compare it go all the way down the tree using this type of thing right here.

82
00:06:53,560 --> 00:07:00,490
So it'll keep setting the right sub tree in this case to hide it.

83
00:07:00,490 --> 00:07:03,970
I put the left sub tree in there again.

84
00:07:04,570 --> 00:07:07,180
Very sorry, I keep putting the wrong things in there.

85
00:07:07,480 --> 00:07:09,180
So we want to call the right symmetry.

86
00:07:09,190 --> 00:07:10,780
I'm sorry for putting the left sub tree.

87
00:07:10,780 --> 00:07:17,410
That must've been confusing, so we'll want to recursively call with the right sub tree and kind of

88
00:07:17,410 --> 00:07:22,960
keep going down and setting it, setting that sub tree correctly, you know, as we go down.

89
00:07:23,800 --> 00:07:29,160
So it's kind of, you know, interesting way of doing it, but hopefully that makes sense to you.

90
00:07:30,360 --> 00:07:30,900
So.

91
00:07:32,160 --> 00:07:42,600
Yeah, I might just, uh, yeah, let me just put normally that in the brackets here and let's see,

92
00:07:42,600 --> 00:07:46,440
did not put a semicolon on there, so that's why it is red.

93
00:07:47,670 --> 00:07:54,620
So then we want to say else if it's less than and this will actually be the last century.

94
00:07:57,480 --> 00:08:05,340
So if value is less than real, give value, then we will, as the left, said Tree.

95
00:08:06,030 --> 00:08:18,690
OK, and so we will set the less arbitrary to this, you know, recursively going down and passing the

96
00:08:18,840 --> 00:08:23,400
left sub tree as long as the value is less.

97
00:08:25,590 --> 00:08:26,010
So.

98
00:08:29,820 --> 00:08:34,500
It's kind of our traditional like building tree, you know, insertion, but then now we need to accommodate

99
00:08:34,500 --> 00:08:39,870
for these imbalances, you know, so we're going to call our balance factor function and then we're

100
00:08:39,870 --> 00:08:41,230
going to have to do some rotations.

101
00:08:41,250 --> 00:08:56,190
So one I say, if there is a left left in balance and now I want to hop over to some drawings of these

102
00:08:56,190 --> 00:09:02,460
things because I want to explain what I'm about to do with this with this code here.

103
00:09:03,870 --> 00:09:10,830
So right here we have a left left rotation for this left left imbalance.

104
00:09:11,760 --> 00:09:15,750
And you can think about that also like we talked before.

105
00:09:17,550 --> 00:09:19,800
About, you know.

106
00:09:21,140 --> 00:09:29,270
The imbalance is coming from a the direction of the greatest height or whatever, so we have this left

107
00:09:29,270 --> 00:09:30,530
left imbalance.

108
00:09:30,530 --> 00:09:37,610
So the path that was calling it causing that imbalance for us to do it left left rotation was left left,

109
00:09:37,610 --> 00:09:38,840
you know, it went this way.

110
00:09:40,090 --> 00:09:48,580
You notice here that we have this like one to three and we're subtracting one from up here, and that's

111
00:09:48,580 --> 00:09:49,390
making it to.

112
00:09:51,180 --> 00:09:57,060
So we the way that we're going to be able to look at the balance factor.

113
00:09:58,540 --> 00:10:00,970
And know what type of rotation to do.

114
00:10:02,080 --> 00:10:11,020
Is based on the looking at the route, the current node that we're on.

115
00:10:12,480 --> 00:10:18,360
And also, these combinations of.

116
00:10:20,750 --> 00:10:23,780
It's like less of a tree or write some tree.

117
00:10:24,350 --> 00:10:31,310
So you notice in this left left rotation scenario, we have two right here for our balance factor.

118
00:10:32,500 --> 00:10:36,970
And then we look at this left some tree of fruit.

119
00:10:37,780 --> 00:10:47,290
So you've noticed that I put, ah, four root and then right here I put RL in that stands for root left.

120
00:10:48,710 --> 00:10:50,390
So routes left Sudbury.

121
00:10:51,440 --> 00:10:55,490
We have a two here, and then we have a one right here.

122
00:10:57,700 --> 00:11:06,730
And we have a one right here, because of course, if the left sub tree, you know, we had left left

123
00:11:07,090 --> 00:11:07,960
and this was.

124
00:11:09,310 --> 00:11:12,280
This direction right here was what was causing that imbalance.

125
00:11:12,640 --> 00:11:19,840
When we go down to this node right here, we see that we have two right here and one right here.

126
00:11:19,870 --> 00:11:24,070
So left some tree minus three, some tree two minus one is one.

127
00:11:25,550 --> 00:11:34,430
These two numbers kind of give us an idea of what type of rotation we have to do and we can rely on

128
00:11:34,430 --> 00:11:43,850
them to be, you know, within the range of negative two to two because once we start building our tree,

129
00:11:43,850 --> 00:11:51,170
we're constantly checking these balance factors, you know, so we don't really let it get outside of

130
00:11:51,170 --> 00:11:52,010
that range.

131
00:11:52,340 --> 00:11:59,930
And that is why we can rely on looking at the balance factor of the root node and the balance factors

132
00:11:59,930 --> 00:12:03,890
of either here or here coming from the root node.

133
00:12:04,040 --> 00:12:06,170
And that is how we are going to write our code.

134
00:12:07,100 --> 00:12:14,660
And so I wanted to explain that before we just write our insert stuff here, even before we go into

135
00:12:14,660 --> 00:12:17,120
the actual implementation of the balance factor functions.

136
00:12:18,020 --> 00:12:19,730
So let's think about that.

137
00:12:20,180 --> 00:12:23,060
We have a left left rotation.

138
00:12:23,570 --> 00:12:30,430
We notice that the root node is going to be two and the roots left some trees.

139
00:12:30,440 --> 00:12:35,900
Balance factor is going to be one, and that means we need to do a left left rotation.

140
00:12:38,190 --> 00:12:39,780
So we're going to go ahead and do that.

141
00:12:40,260 --> 00:12:56,010
I'm going to say if the balance factor of the route is equal to two and the balance factor of the routes

142
00:12:56,610 --> 00:13:00,630
left, some tree is equal to one.

143
00:13:03,540 --> 00:13:07,170
What about that then?

144
00:13:07,170 --> 00:13:13,080
In this case, we are absolutely not going to need those because we're just going to do the turn left

145
00:13:13,080 --> 00:13:19,470
left rotation and we're going to pass the current node, which will be.

146
00:13:20,710 --> 00:13:27,370
This root node, we're going to pass that to the left left rotation function to do this rotation right

147
00:13:27,370 --> 00:13:28,900
here, which I'll get into in a moment.

148
00:13:28,900 --> 00:13:31,840
But right now we're just going to right the first calls to our.

149
00:13:33,170 --> 00:13:36,140
Rotation functions in this local insert function.

150
00:13:38,030 --> 00:13:40,760
All right, so let's head on to the next one.

151
00:13:41,150 --> 00:13:48,290
Say if there is a left right imbalance.

152
00:13:48,650 --> 00:13:57,830
So if there is a left right and balance.

153
00:13:59,690 --> 00:14:01,160
So let's take a look at that.

154
00:14:04,400 --> 00:14:05,960
I have the.

155
00:14:07,100 --> 00:14:08,300
Left, right, right here.

156
00:14:10,590 --> 00:14:23,160
So you notice that in this first picture here we have a negative two as the rude because we are going

157
00:14:23,160 --> 00:14:24,930
one to.

158
00:14:25,850 --> 00:14:31,480
And then, you know, one to and then like three, whatever you want to consider it, you know, three

159
00:14:31,490 --> 00:14:36,590
or three this way we have this one to three.

160
00:14:36,590 --> 00:14:43,280
You know this high of the left sub tree from Root is three and a high of the rates of tree is one.

161
00:14:43,290 --> 00:14:45,860
So three minus one is negative two.

162
00:14:47,190 --> 00:14:50,810
You know, this can be taken away or this can be taken away and we do the same thing.

163
00:14:51,590 --> 00:15:00,110
And then we have, you know, since it's a left right violation, we're going to go ahead and look at

164
00:15:00,110 --> 00:15:03,530
this one and then we're going to look at the next node.

165
00:15:03,820 --> 00:15:07,460
You know, this is the left and then this one has the right.

166
00:15:07,730 --> 00:15:11,000
So we're going to take this node into consideration as well.

167
00:15:12,800 --> 00:15:20,720
And you notice that this balance factor here is one for this left right rotation.

168
00:15:20,870 --> 00:15:23,360
So we have, you know, it's left.

169
00:15:23,360 --> 00:15:30,560
Some tree is one and the height of the right is two.

170
00:15:31,460 --> 00:15:31,910
So.

171
00:15:34,810 --> 00:15:39,490
We actually yeah, that should be yeah, that's actually incorrect.

172
00:15:40,060 --> 00:15:46,450
I'm just noticing, yeah, so this should be one minus one two, so that should be negative one.

173
00:15:46,460 --> 00:15:51,610
So I should actually correct that I will correct that right now.

174
00:15:54,300 --> 00:15:56,400
Yeah, sorry, I make some mistakes sometimes.

175
00:15:56,730 --> 00:15:59,790
But, you know, I guess as long as I catch them, hopefully it's OK.

176
00:16:00,180 --> 00:16:08,100
So yeah, this is a left this one minus one to four, the race increase, so one minus two is negative

177
00:16:08,100 --> 00:16:08,430
one.

178
00:16:09,330 --> 00:16:10,920
So that's what we're going to be

179
00:16:13,260 --> 00:16:17,130
using for for this, actually.

180
00:16:18,600 --> 00:16:22,880
So this and actually this shouldn't be negative to I don't know why I put that to.

181
00:16:22,950 --> 00:16:24,060
I made another mistake here.

182
00:16:24,420 --> 00:16:25,380
So this is.

183
00:16:26,560 --> 00:16:30,930
Two sorry about that, I'm getting that super super mixed up.

184
00:16:30,970 --> 00:16:31,570
Sorry about that.

185
00:16:32,020 --> 00:16:35,860
So yeah, we have one to three minus one is two.

186
00:16:36,490 --> 00:16:38,740
So I made that correction right there.

187
00:16:38,960 --> 00:16:39,880
Apologies again.

188
00:16:40,750 --> 00:16:43,510
So these are the numbers that we're going to use for the left, right and balance.

189
00:16:43,510 --> 00:16:52,000
Then we're going to be checking to see whether the balance factor is to for the route and whether the

190
00:16:52,030 --> 00:16:55,030
left symmetry of the route is minus one.

191
00:16:56,140 --> 00:16:57,280
So let's go ahead and check for that.

192
00:16:58,360 --> 00:17:17,650
So I must say, if the balance factor of route equals two and the balance factor of the route left century

193
00:17:19,510 --> 00:17:29,170
equals negative one, then we will do you a return left right.

194
00:17:29,470 --> 00:17:31,660
But it's a great rotation.

195
00:17:32,110 --> 00:17:34,210
And of course, passing the just like before.

196
00:17:36,310 --> 00:17:46,120
OK, so let's do if there is a right, right and balance.

197
00:17:47,350 --> 00:17:56,460
So I'm going to say OK, if balance factor route equals and what would this be?

198
00:17:56,470 --> 00:17:57,220
Let's take a look.

199
00:17:58,000 --> 00:18:02,920
Hopefully, I don't have a ton more mistakes, but definitely possible.

200
00:18:02,920 --> 00:18:04,680
So we're doing right, right?

201
00:18:08,010 --> 00:18:09,630
Looks like this one is correct, sir.

202
00:18:10,140 --> 00:18:19,560
Thankfully, I did not mess up the numbers here, so we have one for the last century and one to three

203
00:18:19,560 --> 00:18:22,050
for the rights of trees, so that is minus two.

204
00:18:22,980 --> 00:18:25,680
And let's see this one right here.

205
00:18:25,710 --> 00:18:32,430
We have one for the left cemetery and one two for the right cemetery, so that's minus one.

206
00:18:33,570 --> 00:18:37,730
So this is a scenario in which we'd have the right right rotation.

207
00:18:37,740 --> 00:18:42,090
The imbalance is in this direction.

208
00:18:42,660 --> 00:18:48,650
And even though we could have trees that were different than this, you know, there might be more values

209
00:18:48,660 --> 00:18:49,140
over here.

210
00:18:50,190 --> 00:18:54,900
We're talking about the case in which whatever values are over here, you know, there is an imbalance

211
00:18:54,900 --> 00:19:02,580
that has happened suddenly from this direction being, you know, larger than the notes over here.

212
00:19:03,540 --> 00:19:08,430
In which case the I'm talking about the height of the trees over here, in which case we would have

213
00:19:08,430 --> 00:19:14,880
to perform this right, right, OK, rotation and we since we are following this formula from the beginning,

214
00:19:14,880 --> 00:19:19,860
with that range of negative two to two, you know, we're not going to be carrying her values.

215
00:19:19,860 --> 00:19:22,590
We can rely on these two numbers to tell us the type of rotation.

216
00:19:22,590 --> 00:19:24,120
So just want to reiterate that.

217
00:19:24,780 --> 00:19:32,520
So the negative two and negative one will be the values that we're using, and that is the root in the

218
00:19:32,520 --> 00:19:34,910
root rate sub tree.

219
00:19:35,850 --> 00:19:37,610
So let's go ahead and do that.

220
00:19:37,620 --> 00:19:48,780
So balance factor equals negative two and the balance factor of the risk, right?

221
00:19:48,780 --> 00:19:53,310
So tree equals negative one

222
00:19:57,030 --> 00:19:58,380
e are.

223
00:20:04,060 --> 00:20:06,740
He goes and he's another parentheses there.

224
00:20:06,760 --> 00:20:10,660
Sorry about that, um.

225
00:20:10,930 --> 00:20:12,160
And that doesn't mean there.

226
00:20:15,320 --> 00:20:21,830
OK, so we will return the right great rotation period.

227
00:20:25,190 --> 00:20:34,240
OK, and then let's check our final one, which if there is a right left, I believe, yeah, right

228
00:20:36,050 --> 00:20:37,910
left in the balance.

229
00:20:40,490 --> 00:20:48,470
And so if the balance factor of the route equals, let's go look at this.

230
00:20:50,230 --> 00:20:51,970
So right, left.

231
00:20:53,030 --> 00:21:00,850
Let's double check to make sure I haven't messed up the values again, so this looks good and yeah,

232
00:21:00,860 --> 00:21:01,960
this looks good, OK?

233
00:21:02,120 --> 00:21:08,570
It looked like that was the only one that I messed up was that that final slide there for the left right?

234
00:21:09,410 --> 00:21:13,040
So we have one minus one to three or three.

235
00:21:13,550 --> 00:21:15,620
So that would be negative two.

236
00:21:15,620 --> 00:21:20,120
And then we have one, two or two minus one makes it one.

237
00:21:20,870 --> 00:21:27,980
So we're looking at the route to be negative two and the roots right to be one for this scenario, which

238
00:21:27,980 --> 00:21:29,120
we perform a right left.

239
00:21:31,700 --> 00:21:32,870
So let's go ahead and do that.

240
00:21:33,110 --> 00:21:41,390
We have the route is negative two and the balance factor of the route, right?

241
00:21:41,390 --> 00:21:47,690
So tree is equal to one case.

242
00:21:47,690 --> 00:21:51,260
We return right left rotation at the root.

243
00:21:55,170 --> 00:21:55,650
OK.

244
00:21:57,480 --> 00:21:58,440
Perfect.

245
00:21:59,930 --> 00:22:08,570
So we performed the rotation there, and then what we're going to do is just like we were returning

246
00:22:08,570 --> 00:22:09,920
the route.

247
00:22:14,690 --> 00:22:16,820
We're turning the new node right here.

248
00:22:17,240 --> 00:22:23,630
What we're going to do is return the root in this case, so.

249
00:22:26,910 --> 00:22:35,340
Will add a new node will need to return that will need to perform those rotations if necessary, after

250
00:22:35,430 --> 00:22:43,770
adding that new node, if it becomes an imbalance and then regardless of the situation, we are going

251
00:22:43,770 --> 00:22:55,740
to return the root so current node that they're on for us to return.

252
00:22:55,740 --> 00:22:56,970
Someone put that down there.

253
00:22:58,830 --> 00:23:00,630
OK, so let's get into these.

254
00:23:02,350 --> 00:23:05,170
Balance factor functions.

255
00:23:05,560 --> 00:23:15,790
And for this, I think I'm actually going to maybe stop the video right here and start a another video

256
00:23:15,790 --> 00:23:20,230
so we can actually just focus focus on those.

257
00:23:20,560 --> 00:23:24,730
So yeah, we got this insert out of the way.

258
00:23:24,780 --> 00:23:30,820
In the next lecture, I will go ahead and go over these those images again, and we will do each of

259
00:23:30,820 --> 00:23:32,310
these rotation functions.

260
00:23:32,310 --> 00:23:32,960
So CNN.