1
00:00:00,210 --> 00:00:09,960
Welcome to a nother lecture on anvil trees in this lecture, we will be doing some implementation of

2
00:00:09,960 --> 00:00:18,330
the code and I will not be going over a theoretical things in this portion.

3
00:00:18,750 --> 00:00:29,460
But when we do a second part of our implementation, I will refer back to some images that we've looked

4
00:00:29,460 --> 00:00:35,580
at some slides just so we can get a better grasp of what it is that we're doing and kind of switch back

5
00:00:35,580 --> 00:00:39,660
and forth so we can see why we're writing the code that we're writing.

6
00:00:40,590 --> 00:00:48,680
And so if you were if you're still actually a little bit confused about the rotations and things and

7
00:00:48,690 --> 00:00:53,400
movement of the pointers and restructuring the tree, don't worry about it.

8
00:00:53,400 --> 00:01:00,210
We will look even in more detail when we are writing the code for these rotations.

9
00:01:00,210 --> 00:01:05,940
I will include some slides that show exactly what we're doing when we're writing this line of code.

10
00:01:06,690 --> 00:01:07,710
So don't worry about that.

11
00:01:07,710 --> 00:01:13,290
If it's still a little confusing, we kind of just took a general look at that tree and there were some

12
00:01:13,290 --> 00:01:16,640
arrows and stuff, but it might still be unclear.

13
00:01:16,650 --> 00:01:22,110
So hopefully I can clear that up for you in the next lecture.

14
00:01:22,110 --> 00:01:27,270
But today we're just going to do kind of a little bit of a scaffolding for what we're going to need

15
00:01:27,270 --> 00:01:30,840
for the real tree, some helper functions and things like that.

16
00:01:32,040 --> 00:01:35,970
So I went ahead and made a new project.

17
00:01:37,140 --> 00:01:39,150
You see, it's a real tree record.

18
00:01:39,510 --> 00:01:43,590
If you would like to, you can kind of piggyback off of your binary search tree, and that's totally

19
00:01:43,590 --> 00:01:44,040
fine.

20
00:01:44,430 --> 00:01:49,650
I went ahead and already made a few files, so I have a header file for my node class.

21
00:01:50,130 --> 00:01:56,880
I have a header file for the actual Avielle tree class and then an implementation for each class.

22
00:01:57,450 --> 00:02:02,340
And you're probably wondering unless you've already done something like this, why is there no implementation

23
00:02:02,340 --> 00:02:03,390
for the node class?

24
00:02:03,390 --> 00:02:08,610
And we will see that right here, and it's because I'm going to actually do the implementation in the

25
00:02:08,610 --> 00:02:09,120
header.

26
00:02:09,750 --> 00:02:16,760
So a few things I'm going to show in this lecture that you may or may not have seen before.

27
00:02:16,770 --> 00:02:19,440
They're just kind of style and syntax things.

28
00:02:20,580 --> 00:02:23,310
I kind of want my node class to be compact in the header.

29
00:02:23,310 --> 00:02:28,380
So I'm just going to put the implementation there, since the implementations are very simple for these

30
00:02:28,380 --> 00:02:28,830
functions.

31
00:02:28,830 --> 00:02:35,280
So I will have it kind of prototyped and implemented in the same area in the class.

32
00:02:36,060 --> 00:02:40,530
So that's another way of writing code and C++ if you haven't done that before.

33
00:02:40,540 --> 00:02:46,410
If you have, you can just ignore what I'm saying, and I'm also going to go over a tune things that

34
00:02:46,410 --> 00:02:53,880
might be new in C++ for you if you haven't gone over them before and the previous portion of this course

35
00:02:53,880 --> 00:02:55,950
or just in your own studies.

36
00:02:56,550 --> 00:03:01,380
And that'll be initialization lists and ternary operator.

37
00:03:01,390 --> 00:03:03,300
So or sorry ternary statements.

38
00:03:03,300 --> 00:03:07,320
So I will go ahead and get started then.

39
00:03:07,860 --> 00:03:14,670
So what I'm going to do is actually commit to using namespace STD.

40
00:03:15,330 --> 00:03:19,530
And I'm going to, I think, increase the size a little bit in this video.

41
00:03:19,530 --> 00:03:25,380
I'm hoping that the previous recordings weren't too small, but from now on, I'm going to try and write

42
00:03:25,380 --> 00:03:31,950
code kind of like in the biggest size that's usable for me, just so it's as visible as possible.

43
00:03:32,430 --> 00:03:35,700
So hopefully that hasn't been an issue till now and that it's been big enough.

44
00:03:35,700 --> 00:03:38,400
But you know, I'm trying to increase the size for sure.

45
00:03:39,240 --> 00:03:39,600
All right.

46
00:03:39,690 --> 00:03:47,130
So let's go ahead and make our class name for Node and I'll do a public section.

47
00:03:47,130 --> 00:03:50,160
And this is one of the things that I was talking about, right?

48
00:03:50,160 --> 00:03:51,630
The constructor here.

49
00:03:51,630 --> 00:03:56,640
And it's not just going to be a prototype, it's going to be the implementation as well.

50
00:03:56,640 --> 00:04:00,630
And I'm going to do it in the form of what is called an initialization list.

51
00:04:00,640 --> 00:04:04,530
So it's just a more compact syntax for writing and constructor.

52
00:04:04,980 --> 00:04:06,300
And that looks like this.

53
00:04:06,300 --> 00:04:10,440
So it's you write, what would you normally write for the prototype, something like this node?

54
00:04:11,250 --> 00:04:17,310
And then you put a colon and then you're basically going to write a list of the things to be initialized

55
00:04:17,310 --> 00:04:19,080
and use parentheses for it like this.

56
00:04:19,710 --> 00:04:25,290
So I haven't written my private members yet, so it's probably going to be underlined in red for sure.

57
00:04:25,290 --> 00:04:30,240
Will be, but I'm just going to start writing that right now and now implement them after I write this.

58
00:04:30,870 --> 00:04:32,760
Sorry, I'll declare them in the private section.

59
00:04:33,450 --> 00:04:37,770
So I'm going to have a left pointer off my node, just like binary search tree.

60
00:04:37,770 --> 00:04:40,410
And I'm initialize that and no pointer and like this.

61
00:04:40,860 --> 00:04:46,410
So I say left and then in parentheses, I put no pointer and then a comma, and we continue our list.

62
00:04:47,040 --> 00:04:47,970
I'm going to have a right.

63
00:04:49,170 --> 00:04:54,780
I do know pointer like that, and then I'm going to have the value for the data, and I just can call

64
00:04:54,780 --> 00:04:58,740
that underscore value and initialize that to zero.

65
00:04:59,070 --> 00:04:59,400
And then we.

66
00:04:59,590 --> 00:05:06,700
Finish it off with just some empty brackets here, and they don't have to be empty and they can actually

67
00:05:06,700 --> 00:05:07,390
have.

68
00:05:08,670 --> 00:05:13,710
Things inside of this like more implementation inside here, but I don't need that, so I'm just putting

69
00:05:13,710 --> 00:05:14,610
an empty right there.

70
00:05:16,200 --> 00:05:16,560
All right.

71
00:05:16,830 --> 00:05:23,280
So since I don't like that underline now I'm going to go ahead and just write this year, so we have

72
00:05:23,280 --> 00:05:25,200
a no pointer called left.

73
00:05:25,800 --> 00:05:27,890
We have A. pointer and call right.

74
00:05:28,530 --> 00:05:31,680
And we have an integer on a core value.

75
00:05:32,670 --> 00:05:34,320
So that way it's not underlined anymore.

76
00:05:35,220 --> 00:05:41,280
I'm going to make another constructor that gets past the value to initialize them and do the same thing

77
00:05:41,280 --> 00:05:42,840
with my initialization list here.

78
00:05:43,620 --> 00:05:45,690
I'm going to have left a no pointer.

79
00:05:46,290 --> 00:05:47,110
In fact, you know what?

80
00:05:47,160 --> 00:05:50,310
I will just copy the.

81
00:05:51,960 --> 00:06:02,940
Rest of this office, and I'm going to have this value be in, which is passed there.

82
00:06:05,630 --> 00:06:13,220
OK, so now I have another constructor there, then I'm going to do my setters and getters for these

83
00:06:13,220 --> 00:06:17,450
nodes so we can set the sub trees and I'm going to call this left sub tree.

84
00:06:18,950 --> 00:06:21,890
This will be the getter, so it turns left.

85
00:06:23,630 --> 00:06:35,150
And another thing for right some tree we saw in Karen's right, then I'll have the setters that get

86
00:06:35,150 --> 00:06:40,370
passed and node pointer and this will be left.

87
00:06:40,370 --> 00:06:45,680
And since I'm putting left in here, I'm going to have something like this.

88
00:06:45,780 --> 00:06:49,310
This uses the calling object with the keyword.

89
00:06:49,310 --> 00:06:53,690
This and I see this arrow left equals the path to left.

90
00:07:00,410 --> 00:07:02,390
Same thing for their right.

91
00:07:04,970 --> 00:07:06,350
So that's right.

92
00:07:06,350 --> 00:07:08,480
And I forgot the semicolon there.

93
00:07:09,440 --> 00:07:10,700
So let's finish that.

94
00:07:12,170 --> 00:07:13,370
Then we'll get all right.

95
00:07:13,370 --> 00:07:18,770
We'll do a getter accessory for our value.

96
00:07:20,840 --> 00:07:25,700
So I have that there and then I'll do a setter to set value.

97
00:07:28,850 --> 00:07:34,610
I should probably continue the camel case here, so I'll do that.

98
00:07:37,580 --> 00:07:39,440
Well, yeah, this will be on.

99
00:07:39,440 --> 00:07:46,730
I'll pass the contest and now and I'll just say value equals style.

100
00:07:48,400 --> 00:07:48,710
Oops.

101
00:07:50,770 --> 00:07:55,810
OK, so that's be pretty much it for our Noad class.

102
00:07:58,580 --> 00:07:58,910
Yeah.

103
00:08:00,600 --> 00:08:08,070
So let's go ahead and head over to our email tree.

104
00:08:08,620 --> 00:08:23,910
Header file So for this, I'm going to want to include the let's see what I include my class and then

105
00:08:23,940 --> 00:08:26,520
I think, yeah, it's all wrinkly right now.

106
00:08:27,970 --> 00:08:29,460
Put that in there for the sake of it.

107
00:08:29,820 --> 00:08:32,550
Let's say class Avielle Tree

108
00:08:35,340 --> 00:08:37,070
of Public section.

109
00:08:37,080 --> 00:08:47,820
I'm going to have a basic constructor then and I'm going to have a function.

110
00:08:47,820 --> 00:08:54,130
We're going to need a function, actually, so we can calculate our balance factors and stuff.

111
00:08:54,150 --> 00:08:59,160
We're going to need a function that helps facilitate that card height.

112
00:09:00,060 --> 00:09:02,000
And I'll be explaining this a little bit.

113
00:09:02,010 --> 00:09:09,140
I'm not going to be showing a visualization of this lake, but it will be a recursive function and I'm

114
00:09:09,150 --> 00:09:13,470
trying to explain it to the best of my ability, the implementation when we're doing it.

115
00:09:14,490 --> 00:09:20,340
But this is something that I recommend you trying to see if you can figure out how to write on yourself

116
00:09:21,120 --> 00:09:26,250
by yourself and try and figure out what you would do for a recursive function to find the height of

117
00:09:26,250 --> 00:09:27,300
a binary search tree.

118
00:09:28,260 --> 00:09:32,760
So I will be implementing it and explaining it, but it would be good practice to see if you can implement

119
00:09:32,760 --> 00:09:34,320
it before I explain it.

120
00:09:35,010 --> 00:09:40,380
Also going to have the balance factor, of course, that will return the balance factor.

121
00:09:40,710 --> 00:09:45,420
I'm actually going to go back there and continue the camel case.

122
00:09:46,260 --> 00:09:50,130
This will be passed a route to find the balance factor of.

123
00:09:52,530 --> 00:09:57,150
And then I'm going to prototype my other functions here, but I'm not going to implement them in this

124
00:09:57,150 --> 00:10:02,700
lecture, but I'm going to have all the rotations and these are going to return a node.

125
00:10:02,700 --> 00:10:17,250
So I'm going to say L-l rotation and I'm going to call this in real life movie and we'll do L-R rotation

126
00:10:24,510 --> 00:10:27,570
with this, our location

127
00:10:30,900 --> 00:10:36,840
and our El rotation.

128
00:10:40,500 --> 00:10:40,900
OK.

129
00:10:41,220 --> 00:10:46,320
And then I'm, of course, going to want some functions to insert into the tree.

130
00:10:47,250 --> 00:10:48,000
So.

131
00:10:49,290 --> 00:10:51,150
Yeah, we want to call this

132
00:10:56,460 --> 00:11:02,190
insert the value that this will be kind of the public facing one and then I'll have and local one that

133
00:11:02,190 --> 00:11:14,250
returns and then I call that local and state and that gets passed a root node to start at and p value.

134
00:11:15,660 --> 00:11:15,990
OK.

135
00:11:15,990 --> 00:11:21,720
And then in my private section, I'm pretty much only having the root of the tree right now.

136
00:11:24,090 --> 00:11:26,130
And that should be good.

137
00:11:26,490 --> 00:11:30,270
So, yeah, let's go ahead and move over to the implementation file.

138
00:11:32,850 --> 00:11:43,620
So we're going to definitely need to include our header files, so I'm going to include a real tree

139
00:11:43,770 --> 00:11:45,390
and I'll include my node

140
00:11:50,400 --> 00:11:51,720
in each.

141
00:11:53,510 --> 00:12:00,950
And I know at some point I'm going to be writing a function to print out the tree in some order.

142
00:12:01,490 --> 00:12:08,780
We're using like one of those reversals and printing out, and so I'm going to include extreme,

143
00:12:13,610 --> 00:12:17,030
but that and then left to our constructor.

144
00:12:20,840 --> 00:12:25,880
So I'm not going to do an initialization list for this and just going to do a basic one.

145
00:12:31,340 --> 00:12:34,700
But you can definitely do an edit initialization list if you'd like.

146
00:12:35,660 --> 00:12:38,300
So let's talk about this height function now.

147
00:12:39,530 --> 00:12:40,130
So.

148
00:12:43,930 --> 00:12:49,270
How do we find the height of a binary search tree, so I definitely think that it's a good idea to see

149
00:12:49,270 --> 00:12:53,170
if you can figure this out on your own and if it's too crazy and you get stuck, don't worry.

150
00:12:53,920 --> 00:12:57,160
But definitely, you know, congratulations if you're able to figure it out.

151
00:12:58,390 --> 00:13:00,260
Go ahead and pass the video if you want to do that.

152
00:13:00,280 --> 00:13:01,780
Otherwise, I'm going to explain it right now.

153
00:13:03,710 --> 00:13:10,970
So if you think about the height of a binary search tree and how to figure that out, we basically need

154
00:13:10,970 --> 00:13:20,210
to count the nodes during the recursive process so we go all the way down to a leaf node, whether that

155
00:13:20,210 --> 00:13:22,910
be, you know, taking whatever path.

156
00:13:24,350 --> 00:13:28,880
We want to go all the way down to all the leaf nodes and explore.

157
00:13:28,970 --> 00:13:36,590
And we're talking about when we say the height, we're talking about the max depth.

158
00:13:36,590 --> 00:13:39,830
That's kind of another way that you could call this function.

159
00:13:40,430 --> 00:13:44,540
We want to have the longest path from a given node.

160
00:13:45,780 --> 00:13:48,560
You know, the node route that's being passed is an argument.

161
00:13:49,520 --> 00:13:53,670
That's one of the parameters from that node, any given node.

162
00:13:53,690 --> 00:14:00,890
We want to find the longest path, you know, whether that's taking whatever combination of left and

163
00:14:00,890 --> 00:14:05,000
right turns from the route to go down to Alif node.

164
00:14:06,790 --> 00:14:07,870
And so how do we do that?

165
00:14:07,900 --> 00:14:11,770
Well, since we need to count during that recursive process?

166
00:14:13,140 --> 00:14:23,430
We basically need to dig down to each left sub tree, and even though I talked about not really using

167
00:14:23,430 --> 00:14:29,190
local variables inside of a function, we are in fact going to be able to use that and leverage that

168
00:14:29,190 --> 00:14:30,390
somehow in this function.

169
00:14:30,390 --> 00:14:37,980
And we're going to need to save the height of each left sub tree and the height of each right sub tree.

170
00:14:38,760 --> 00:14:41,460
Then we're going to want to find which one is bigger.

171
00:14:42,580 --> 00:14:49,060
And basically, you know, if one is bigger, if the left is bigger than the right, we're going to

172
00:14:49,060 --> 00:14:56,740
want to return the left value plus one during our recursive phase.

173
00:14:57,050 --> 00:15:02,200
Is it going to be adding one each time we come up from a non null?

174
00:15:04,360 --> 00:15:11,110
No, you know, and otherwise, you know, we'll return there to the right one plus one, so it's basically

175
00:15:11,110 --> 00:15:13,990
like finding which one is a larger path.

176
00:15:14,260 --> 00:15:19,600
So you can think about it as we dig all the way to the bottom of all these like past recursively.

177
00:15:19,990 --> 00:15:26,530
And then as we come up in the recursive phase, we're going to be adding one each time if it's not null,

178
00:15:26,860 --> 00:15:32,080
if it's no, our base case is just going to be to return to zero, so we won't add anything.

179
00:15:33,060 --> 00:15:35,610
And we're checking when we add one.

180
00:15:35,970 --> 00:15:42,000
We're only adding one to whatever the biggest number is so far, whether it was coming from the right

181
00:15:42,000 --> 00:15:43,230
or coming from the left.

182
00:15:44,390 --> 00:15:45,560
So that's how we're going to do this.

183
00:15:46,110 --> 00:15:53,030
Some must start out with that base case, and I must say if the route is well, not is no point.

184
00:15:53,330 --> 00:15:57,950
The route is, you know, Poyner can't spell right now.

185
00:15:59,060 --> 00:16:02,840
Go ahead and just return zero because we're not going to add anything in that case.

186
00:16:03,230 --> 00:16:10,370
Then we're going to say I've put a variable here instead of equal to so this can be left into a recursive

187
00:16:10,370 --> 00:16:10,880
call.

188
00:16:11,960 --> 00:16:20,690
It goes to the left so left tree and then we're going to do a recursive call that goes to the right

189
00:16:22,910 --> 00:16:25,820
and that's going to be the right century.

190
00:16:27,500 --> 00:16:28,660
And then we do our check here.

191
00:16:28,670 --> 00:16:36,800
So if left is greater than right, then return left +1.

192
00:16:36,980 --> 00:16:47,720
So we're going to keep that number that's been recursively returned to the X frame that we're at and

193
00:16:47,720 --> 00:16:49,070
we'll add another one to it.

194
00:16:49,070 --> 00:16:54,770
And it will return back up to its parent node, which is also, you know, the previous stack frame

195
00:16:55,280 --> 00:16:56,690
that was calling it before.

196
00:16:56,690 --> 00:17:03,680
So, you know, and then the other case, if it's not, then we want to instead return, right?

197
00:17:03,680 --> 00:17:10,580
Plus one, because that contains that means that right contains the longest path like the count of the

198
00:17:10,580 --> 00:17:13,460
longest path so far, coming back up recursively from the bottom.

199
00:17:15,540 --> 00:17:17,160
And it's as simple as that, actually.

200
00:17:17,520 --> 00:17:18,330
That's all I need.

201
00:17:18,780 --> 00:17:25,740
So if you want to, you can go ahead and make a small example for this function and draw it out on paper,

202
00:17:25,740 --> 00:17:30,840
draw the recursive tree, the tree of the records of calls or just a binary search tree, you know?

203
00:17:33,570 --> 00:17:39,210
You know, they're kind of synonymous in the case of binary search tree and recursive tree, you know,

204
00:17:39,210 --> 00:17:45,510
because we can think of the actual nodes that we're at since we're just traversing the tree recursively,

205
00:17:45,510 --> 00:17:49,950
the nose kind of double as the stack frames, which you've probably noticed so far since I've been talking

206
00:17:49,950 --> 00:17:50,760
about it in that way.

207
00:17:51,630 --> 00:17:56,730
So go ahead and draw that out and just kind of see if you can make sense of a small example of a tree

208
00:17:56,730 --> 00:18:03,540
where you come back up and kind of add values to left and right and keep track of that recursive process

209
00:18:03,750 --> 00:18:06,270
that'll definitely help you understand it and visualize it.

210
00:18:07,770 --> 00:18:08,010
All right.

211
00:18:08,010 --> 00:18:12,600
So now that we got that out of the way, let's go ahead and write the code for our balance factor functions.

212
00:18:13,920 --> 00:18:20,850
So this is going to be a real tree, and I'm going to say, oops, not capital balance factor.

213
00:18:21,600 --> 00:18:26,820
And for the balance factor, I'm going to need the height of the left and the height of the right,

214
00:18:26,820 --> 00:18:32,610
because remember, we get our balance factor by subtracting the height of the right from the left.

215
00:18:33,210 --> 00:18:37,560
So I'm going to say age left and age right.

216
00:18:38,910 --> 00:18:46,830
And what I'm going to say actually is I'm going to say if Root, which is basically just seen, if it's

217
00:18:46,830 --> 00:18:55,560
not if the roots, not null pointer and if it's not null pointer, then I'm going to say if the sub

218
00:18:55,560 --> 00:19:03,740
tree is not no, then set the left or right height to the sub tree.

219
00:19:03,750 --> 00:19:07,920
Otherwise we're going to set it to zero.

220
00:19:08,760 --> 00:19:13,590
And so that is going to I'm going to actually do this in the form of a ternary.

221
00:19:13,680 --> 00:19:18,590
So if you haven't done turn areas before, don't worry, I'm going to explain them right now.

222
00:19:18,600 --> 00:19:23,400
If you have, then you know, this is going to be nothing new to you, but it set a variable.

223
00:19:23,400 --> 00:19:32,530
We have our height left, which is an integer, and I'm basically going to say, OK, so if the left

224
00:19:32,530 --> 00:19:40,830
sub tree is not know which, all I have to do is say if root left sub tree.

225
00:19:41,130 --> 00:19:46,470
So that's basically, you know, asking, you know, is it null or not?

226
00:19:46,470 --> 00:19:49,860
You can just put it as a condition there, just like we did with f root.

227
00:19:50,550 --> 00:19:57,540
And then I put a question mark and then I say, OK, you know, if it's not, no.

228
00:19:57,750 --> 00:20:06,450
If Root left some tree, then I'm going to call the hate function and pass it the left sub tree.

229
00:20:08,730 --> 00:20:13,560
Otherwise, you know, if it is null, I'm just going to say to zero.

230
00:20:14,310 --> 00:20:18,510
And so, you know, if this evaluates to true right here.

231
00:20:19,620 --> 00:20:22,080
Then it's going to take this value.

232
00:20:23,600 --> 00:20:29,450
So this is kind of like the what the question symbolizes and, you know, if it's like the else is kind

233
00:20:29,450 --> 00:20:34,310
of what comes after the colon, which is zero so zero will get put in here.

234
00:20:34,680 --> 00:20:38,390
You know, if it's the condition, this will get put into this variable.

235
00:20:38,390 --> 00:20:45,860
If it's the, you know, if the if is satisfied, if this condition satisfied and you can actually turn

236
00:20:45,860 --> 00:20:52,100
it back and forth here, like, let's see if I can get it to pop up here.

237
00:20:52,790 --> 00:20:58,880
So you notice I click on a little light bulb, it says replace this turn area with, if else so that

238
00:20:58,880 --> 00:21:03,620
basically this is what it would look like as an if else.

239
00:21:04,190 --> 00:21:10,340
And then I kind of can go back to here to this light bulb and I'll return it back to turn so you can

240
00:21:10,340 --> 00:21:13,310
toggle back and forth with C Line, which is kind of nice.

241
00:21:14,930 --> 00:21:18,950
But I just like it, it's kind of a more compact thing, just like the initialization list, so I just

242
00:21:18,950 --> 00:21:21,200
want to mention it in case people didn't know it already.

243
00:21:21,320 --> 00:21:26,480
Let's go ahead and do it for the right century then or sorry, our right value.

244
00:21:28,070 --> 00:21:31,130
So let's do it right.

245
00:21:31,130 --> 00:21:31,860
Some tree.

246
00:21:32,900 --> 00:21:35,620
Question mark height.

247
00:21:36,260 --> 00:21:36,760
Fruit.

248
00:21:37,850 --> 00:21:38,840
Right century.

249
00:21:40,130 --> 00:21:41,540
Otherwise zero.

250
00:21:43,650 --> 00:21:44,160
Cool.

251
00:21:44,370 --> 00:21:49,260
And then, of course, our balance factor is going to, you know, we're getting the height and saving

252
00:21:49,260 --> 00:21:52,980
it in these variables and then we're going to return the difference.

253
00:21:53,100 --> 00:22:02,340
So from each left, we actually specifically want the height of the left sub tree minus the high rates

254
00:22:02,340 --> 00:22:02,730
of tree.

255
00:22:05,650 --> 00:22:06,730
So pretty simple there.

256
00:22:07,810 --> 00:22:11,020
That's all we got for our balance factor function.

257
00:22:12,840 --> 00:22:17,100
And I am actually going to cut the video off here.

258
00:22:17,130 --> 00:22:28,200
I think the next video is going to be all about inserting and doing the rotations, so we're going to

259
00:22:28,200 --> 00:22:33,420
cover all those functions, and I kind of want just a full video dedicated to that.

260
00:22:33,430 --> 00:22:39,630
I'm going to bring up some visualizations that are actually a little more fine tuned in detail than

261
00:22:39,630 --> 00:22:43,110
what we went over in that theoretical first lecture about real trees.

262
00:22:43,440 --> 00:22:51,750
And so I'm hoping it'll really help you clear up any misunderstandings or confusion you might have had

263
00:22:51,750 --> 00:22:52,680
with it so far.

264
00:22:53,340 --> 00:22:55,590
OK, so with that, I will see you in the next video.