1
00:00:00,210 --> 00:00:10,140
Welcome back to what should be the final video in this Avielle three series part of the course here.

2
00:00:11,120 --> 00:00:13,580
So we're going to finish out our.

3
00:00:15,390 --> 00:00:18,480
A rail project here and sea lion.

4
00:00:19,050 --> 00:00:29,190
We're going to add a couple of functions that do a level order traversal and print out the values so

5
00:00:29,190 --> 00:00:31,860
we can verify our tree's structure.

6
00:00:33,080 --> 00:00:40,100
And we'll, of course, have to put some stuff in Maine to run the whole program, you know, have some

7
00:00:40,100 --> 00:00:40,790
client code.

8
00:00:41,720 --> 00:00:47,410
So we're going to do that and along the way, I'm going to go over an example input.

9
00:00:47,480 --> 00:00:50,720
I already have this input file here that I've made.

10
00:00:50,720 --> 00:00:54,860
That's pretty small, but it has all the rotations, I believe.

11
00:00:55,910 --> 00:00:58,670
You have like be right, right?

12
00:01:00,230 --> 00:01:02,000
I think a left left.

13
00:01:03,590 --> 00:01:07,220
Rotation and left right and right left should be.

14
00:01:08,870 --> 00:01:13,010
Should be all of them, I believe that's right.

15
00:01:13,430 --> 00:01:19,310
It might there might be a few missing or no, it has an ancillary list as well.

16
00:01:20,300 --> 00:01:22,450
Yeah, so I double checking.

17
00:01:22,720 --> 00:01:24,890
I have a little drawing here.

18
00:01:24,890 --> 00:01:27,980
I made, but yeah, I made some slides.

19
00:01:27,980 --> 00:01:32,090
So we're going to walk through that and verify if that RV actually works in all that.

20
00:01:32,450 --> 00:01:38,420
So let's go ahead and just get started with adding these other functions to print it out.

21
00:01:39,230 --> 00:01:48,310
So I'm just going to put some prototypes here in the header, so I'm going to call this level order

22
00:01:48,770 --> 00:01:56,930
down because what it's going to do is go in order, not in order, by numbers, in order traversal,

23
00:01:56,930 --> 00:02:00,500
but it's going to traverse like level by level and print them out.

24
00:02:01,920 --> 00:02:11,100
So this is going to be a function is called from Maine, and then I'm going to have a private version

25
00:02:11,370 --> 00:02:16,680
of this that is also level ordered out,

26
00:02:20,490 --> 00:02:22,560
but it's going to take A..

27
00:02:22,800 --> 00:02:27,360
And it's going to take the level.

28
00:02:27,360 --> 00:02:35,390
So in one function, I am going to basically loop for the amount of the height of the tree, so like

29
00:02:35,400 --> 00:02:36,780
through all the levels.

30
00:02:38,490 --> 00:02:40,020
And then I'm going to pass.

31
00:02:40,020 --> 00:02:48,180
I'm going to call this other function in that loop and pass the level and we're actually going to.

32
00:02:50,180 --> 00:02:57,230
Use that to have like a base case and then go left and right and printed out in the right order, and

33
00:02:57,230 --> 00:03:04,010
I'll explain that once we are implementing that, but you know, let's go ahead and put this first function

34
00:03:04,010 --> 00:03:05,060
in there and then we'll do this.

35
00:03:06,410 --> 00:03:06,890
Next one.

36
00:03:08,100 --> 00:03:19,230
So I'm going to avoid a real tree level or down, and I'm going to a for loop here, some say, and

37
00:03:19,230 --> 00:03:20,550
I equals one.

38
00:03:21,420 --> 00:03:29,130
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

39
00:03:29,130 --> 00:03:30,630
say Root.

40
00:03:31,830 --> 00:03:40,530
So that is going to be, you know, our actual root root height, not the height of say.

41
00:03:42,120 --> 00:03:42,570
Yeah.

42
00:03:42,570 --> 00:03:47,190
Or they're going to be or hate groups.

43
00:03:47,610 --> 00:03:50,520
Yeah, because I made their height function, right?

44
00:03:50,800 --> 00:03:51,840
Yes, that.

45
00:03:54,320 --> 00:03:55,370
Should be.

46
00:03:55,460 --> 00:04:00,380
Yeah, so we'll get the height of the root node arm data, remember?

47
00:04:02,980 --> 00:04:05,320
And I told you I was worse.

48
00:04:07,110 --> 00:04:18,040
And then in here, I'm going to just call level or jump, which is going to be our other one.

49
00:04:18,330 --> 00:04:24,580
And I'm going to pass it the root and high school.

50
00:04:25,200 --> 00:04:26,910
So let's go do that.

51
00:04:26,910 --> 00:04:28,710
Other level watered down that takes the notes.

52
00:04:28,720 --> 00:04:31,260
So this is going to be

53
00:04:35,910 --> 00:04:39,060
military level or down that one.

54
00:04:40,020 --> 00:04:41,310
And so.

55
00:04:42,640 --> 00:04:51,400
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

56
00:04:51,400 --> 00:04:56,170
if it's an old pointer for the absolute best case, in which case we'll just return.

57
00:04:57,310 --> 00:05:05,220
And then I put another case here, and I'm going to say else if level equals one.

58
00:05:08,110 --> 00:05:17,590
Then we're going to see out the notes and values, so we'll do it now, get value and in line.

59
00:05:20,200 --> 00:05:31,210
And so the reason we're going to do this is because it's basically going to do a left recursion and

60
00:05:31,210 --> 00:05:38,770
a right recursion, and we're going to subtract one another, recursive calls each time from a level.

61
00:05:39,130 --> 00:05:51,550
And since we're passing a specific level, we basically want to know when it gets down to one because

62
00:05:51,550 --> 00:05:55,690
that's kind of like the first level of children of a specific route.

63
00:05:58,300 --> 00:06:01,510
And if that if that's the case, then we're going to want to print it out.

64
00:06:02,350 --> 00:06:10,510
So I'm going to do a level or jump and to the left some tree.

65
00:06:11,500 --> 00:06:19,660
And then I would do level minus one and then I'll do the same thing for the race tree.

66
00:06:25,410 --> 00:06:29,520
So basically, once it gets down to.

67
00:06:30,860 --> 00:06:36,920
One then we know that we want to print out the value.

68
00:06:37,890 --> 00:06:42,060
So that's why we are putting this extra base case out here.

69
00:06:43,440 --> 00:06:49,050
So it's another function, you know, where you could go ahead and draw this out, you know, the recursive

70
00:06:49,050 --> 00:06:56,790
calls and the dry the tree out on like the minor surgery drain on paper and kind of see what's happening

71
00:06:56,790 --> 00:06:57,030
here.

72
00:06:57,030 --> 00:07:00,270
You know, when we go all the way down, we're calling this left.

73
00:07:01,560 --> 00:07:07,170
Recursion and we go all the way down, you know, and then return here.

74
00:07:07,560 --> 00:07:09,220
Then you know, what's happening?

75
00:07:09,450 --> 00:07:17,280
So you can go through some examples with both these functions and see see how it works, but I'm just

76
00:07:17,280 --> 00:07:19,170
doing this for printing purposes.

77
00:07:19,770 --> 00:07:27,300
You can go back and look at mortgage reversals to get a better understanding, in-depth understanding

78
00:07:27,300 --> 00:07:27,810
of them.

79
00:07:27,930 --> 00:07:30,000
We talked about a few, but this is.

80
00:07:31,720 --> 00:07:36,250
An extra one level order, I'm just doing it so we can look at the structure of the tree because I want

81
00:07:36,250 --> 00:07:43,180
to make sure that, you know, our tree structure aligns with what we predict the not what we predict,

82
00:07:43,180 --> 00:07:47,590
but we'll go through the rotations and our tree should have a certain structure at the end.

83
00:07:47,590 --> 00:07:49,690
And that's how we're going to verify this by doing this.

84
00:07:51,860 --> 00:07:59,290
OK, so that is all I'm going to have, actually, and here and so I'm actually going to head over to

85
00:07:59,570 --> 00:08:00,380
Main.

86
00:08:01,410 --> 00:08:10,860
And here we're just going to write some basic clan code to get this stuff going, so let's go ahead

87
00:08:11,190 --> 00:08:13,670
and have our stream in here.

88
00:08:13,680 --> 00:08:15,430
I'm going to want.

89
00:08:16,470 --> 00:08:17,610
Actually, no, I don't need that.

90
00:08:17,760 --> 00:08:18,360
I don't need that.

91
00:08:18,570 --> 00:08:20,520
We're going to need actually like a stream.

92
00:08:21,900 --> 00:08:32,070
So I'm going to include stream because I'm going to need to open that file and then I actually want

93
00:08:32,070 --> 00:08:35,040
to go for that doesn't run on that or whatever.

94
00:08:35,040 --> 00:08:40,860
But I want to include the Avielle to be able to see that h.

95
00:08:41,100 --> 00:08:46,470
And then I'm going to add my number of args.

96
00:08:46,470 --> 00:08:52,770
I see and then the entire ARG B because we have command line arguments.

97
00:08:53,550 --> 00:09:00,950
I'm going to get rid of this, do my standard check to see if there hasn't been an argument provided.

98
00:09:00,960 --> 00:09:06,090
And I need to say, you know, this is how you use it.

99
00:09:06,990 --> 00:09:08,610
Yeah, I do want that.

100
00:09:08,610 --> 00:09:13,170
In that case, then I anyone ask Jane, you know, I got rid of that.

101
00:09:15,590 --> 00:09:21,810
So we'll say, you know, usage is key.

102
00:09:22,220 --> 00:09:22,420
All right.

103
00:09:22,890 --> 00:09:25,250
Zero, just the file name and then.

104
00:09:30,330 --> 00:09:34,500
Name, brand, image, file.

105
00:09:36,060 --> 00:09:42,600
So just tells us to have the name of the executable and then the name of the Empire file as well, so.

106
00:09:43,730 --> 00:09:49,580
And actually, this like I traditionally just had like an exit here as well.

107
00:09:51,800 --> 00:09:57,650
So this will be, you know, like I said, what's a problem?

108
00:09:57,770 --> 00:09:59,660
Exit code, negative phone or something like that?

109
00:10:00,500 --> 00:10:07,250
OK, so I'm going to do an input file stream and call this file and.

110
00:10:09,360 --> 00:10:18,570
And when I opened it, this will be ugly, one will be the input file name.

111
00:10:19,800 --> 00:10:22,560
I'm going to make an Avielle tree object.

112
00:10:23,610 --> 00:10:26,200
So a real tree, I'm just going to call this tree.

113
00:10:26,220 --> 00:10:38,430
People knew a real tree and I'm going to have this integer versus a variable so I can read into it.

114
00:10:39,870 --> 00:10:45,690
And then here's where we're going to insert into the tree and all the while loop.

115
00:10:45,690 --> 00:10:50,910
And I'll just say, well, file and read into the.

116
00:10:53,420 --> 00:11:01,970
Three and I will say three in search value.

117
00:11:04,220 --> 00:11:08,960
And then here I will say tree level or down to printed out.

118
00:11:09,530 --> 00:11:11,960
So should be.

119
00:11:14,260 --> 00:11:16,250
Printed out in that specific order.

120
00:11:17,560 --> 00:11:18,280
So.

121
00:11:20,540 --> 00:11:23,240
Yeah, and then I have my return zero down here.

122
00:11:26,360 --> 00:11:29,960
I think we should be all good to go.

123
00:11:30,500 --> 00:11:34,580
So I've already done my edit configurations.

124
00:11:35,030 --> 00:11:37,610
It may or may not run right now, so we'll just have to you.

125
00:11:38,630 --> 00:11:39,350
Double check.

126
00:11:39,770 --> 00:11:42,080
But I have my input file here.

127
00:11:44,000 --> 00:11:44,990
With these numbers.

128
00:11:45,590 --> 00:11:51,590
And so, first of all, I'd like to do is just have us walk through building the tree with these numbers

129
00:11:51,590 --> 00:11:53,510
and then we will verify that it works.

130
00:11:54,320 --> 00:11:56,530
So let's go ahead and walk through that.

131
00:11:58,660 --> 00:12:00,070
So here's our list right here.

132
00:12:00,310 --> 00:12:02,440
We insert 12.

133
00:12:04,780 --> 00:12:13,390
And so we're putting that of the route go to the next, we insert twenty one and now I'm not writing

134
00:12:13,390 --> 00:12:21,280
the balance factors on here, but let's just check them left minus right zero zero minus one is negative

135
00:12:21,280 --> 00:12:21,660
one.

136
00:12:21,670 --> 00:12:22,860
Everything's fine there.

137
00:12:25,790 --> 00:12:26,470
Here we have a problem.

138
00:12:26,470 --> 00:12:32,650
We add thirty three and we have, you know, zero for this negative one for this one.

139
00:12:32,860 --> 00:12:36,310
And then we have a zero minus one to its negative two.

140
00:12:36,520 --> 00:12:37,900
So we have right right.

141
00:12:37,900 --> 00:12:40,600
We need to do a right rate rotation.

142
00:12:41,380 --> 00:12:48,460
So if we do that right, right rotation, we just bring this one down and then we have this so zero,

143
00:12:48,460 --> 00:12:49,690
zero and zero now.

144
00:12:52,150 --> 00:12:58,440
So now we add 24 into the mix and we should begin, this is zero.

145
00:12:58,460 --> 00:13:00,130
And then we have one more serious one.

146
00:13:01,600 --> 00:13:05,040
This is zero and then we have one minus one to its negative one.

147
00:13:05,050 --> 00:13:05,890
So that's fine.

148
00:13:08,080 --> 00:13:10,210
And we add twenty nine and we have a problem.

149
00:13:10,220 --> 00:13:11,230
This is zero.

150
00:13:12,530 --> 00:13:13,700
This is a negative one.

151
00:13:15,120 --> 00:13:18,770
And this is, too, because we have one to minus zero is two.

152
00:13:18,870 --> 00:13:20,970
So this is a left right.

153
00:13:21,270 --> 00:13:24,120
So we're going to have to rotate this.

154
00:13:24,660 --> 00:13:31,200
So the 29 is going to cut up through here and then it'll branch off its right around thirty three and

155
00:13:31,200 --> 00:13:32,510
left child 24.

156
00:13:33,960 --> 00:13:37,380
So twenty nine came up, left child, 24, right child, 33.

157
00:13:38,850 --> 00:13:48,390
So while balance now we add twenty six and we have a problem again up here, so it's zero zero minus

158
00:13:48,390 --> 00:13:49,380
one minus one.

159
00:13:51,030 --> 00:13:52,020
This is zero.

160
00:13:52,260 --> 00:13:55,830
We have one to minus one that is going to be one.

161
00:13:56,730 --> 00:14:00,190
And then this is zero and then we have one minus one two three.

162
00:14:00,450 --> 00:14:01,650
So that's negative two.

163
00:14:01,660 --> 00:14:03,660
So we need to rotate about this.

164
00:14:04,620 --> 00:14:08,610
So let's go ahead and do that.

165
00:14:08,620 --> 00:14:12,810
So, you know, we're going to bring that 24 of through here.

166
00:14:14,570 --> 00:14:23,480
And the I believe the 26 is going to be attaching to here and then 24 will become the new route.

167
00:14:24,730 --> 00:14:25,180
Yes.

168
00:14:25,330 --> 00:14:27,070
So 24 is a new route.

169
00:14:28,360 --> 00:14:34,540
Let's just go through that again, 24 comes up through here and then branches up to 21 and then 29.

170
00:14:34,810 --> 00:14:37,120
And then this guy gets attached to the 29.

171
00:14:39,850 --> 00:14:45,910
OK, so let's go ahead and to this one, we add our final number three and now we have an imbalance

172
00:14:45,910 --> 00:14:48,190
over here, so this is zero.

173
00:14:48,640 --> 00:14:54,960
And then this is one of my series one and then one two minus zero is actually two.

174
00:14:54,970 --> 00:14:59,390
I keep messing up these numbers all the time.

175
00:14:59,410 --> 00:14:59,980
I'm sorry.

176
00:14:59,980 --> 00:15:01,780
That must be annoying for you guys.

177
00:15:03,150 --> 00:15:05,200
But this is too too much, too serious, too.

178
00:15:05,220 --> 00:15:11,580
We're going to have to do this rotation here, so that is just going to be the 12 coming up and the

179
00:15:11,580 --> 00:15:16,170
21 coming down will be 12 to three to 21 like that.

180
00:15:16,860 --> 00:15:20,160
And now we have finished our tree, so we expect it to look like this.

181
00:15:20,460 --> 00:15:29,640
The level order dump should be something like 24, 12, 29, three, 21, 26, 33, something like that.

182
00:15:30,330 --> 00:15:31,920
So let's see if this actually works.

183
00:15:32,340 --> 00:15:33,990
Let's go ahead and run it.

184
00:15:40,670 --> 00:15:41,870
OK, so.

185
00:15:45,940 --> 00:15:48,160
24, 12, 29.

186
00:15:50,410 --> 00:15:50,650
Yeah.

187
00:15:50,680 --> 00:15:56,950
Twenty four, then 12, then 29, then it should be three, 21, 26, 33.

188
00:15:58,320 --> 00:16:01,320
Three, twenty one, twenty six, thirty three.

189
00:16:02,910 --> 00:16:05,400
OK, so seems to all match up.

190
00:16:07,530 --> 00:16:07,870
All right.

191
00:16:08,040 --> 00:16:12,450
So that was a lot of, uh, a lot of information.

192
00:16:12,930 --> 00:16:14,700
A real trees are.

193
00:16:16,080 --> 00:16:18,300
Kind of difficult, a little bit tricky.

194
00:16:19,620 --> 00:16:25,050
An interesting thing, I might have already mentioned this in the lecture, but I'm sorry if I'm repeating

195
00:16:25,050 --> 00:16:25,560
myself.

196
00:16:26,280 --> 00:16:28,440
When we were doing the hash tables.

197
00:16:30,220 --> 00:16:39,370
A neat thing that you may or may not have covered yet is unordered map in C++, which is a steel type

198
00:16:40,240 --> 00:16:45,140
that is something that uses hashing.

199
00:16:45,430 --> 00:16:54,640
I believe it uses something kind of like chaining that we were using instead of the unordered map and

200
00:16:54,640 --> 00:17:01,600
then a map, just a normal steel map type in C++.

201
00:17:02,620 --> 00:17:08,230
It's another thing that you can have keys like put in a key and get a value out of.

202
00:17:08,230 --> 00:17:16,090
It's a key value pairs that type of data structure, but that actually uses a self-balancing tree.

203
00:17:16,570 --> 00:17:18,400
I'm pretty sure it's not an evil tree.

204
00:17:18,400 --> 00:17:20,050
I think it's a red black tree.

205
00:17:20,200 --> 00:17:23,940
But you know, that's something I just wanted to point out.

206
00:17:24,190 --> 00:17:29,150
It's quite efficient compared to the unaltered map, actually.

207
00:17:29,200 --> 00:17:37,420
So if you'd like to learn more about that, you can go look up the C++ map and C++ unordered map, and

208
00:17:37,690 --> 00:17:40,320
you can read about how those are implemented.

209
00:17:40,330 --> 00:17:43,810
The map should be a balanced tree, I believe is how they did it.

210
00:17:43,810 --> 00:17:51,820
And then an ordered map is some type of hashing, which I believe is not as chaining instead of some

211
00:17:51,820 --> 00:17:56,110
type of training instead of like another probing one or something like that.

212
00:17:56,110 --> 00:18:01,810
So, yeah, some you know, that was just an example I wanted to give of a usage of a real tree.

213
00:18:03,170 --> 00:18:06,260
It's already kind of in place, you know, with the C++ language.

214
00:18:06,990 --> 00:18:11,690
Well, it's not any real true, but a self-balancing tree, you know, a usage of a self-balancing tree

215
00:18:11,930 --> 00:18:13,160
like we've done here.

216
00:18:13,490 --> 00:18:17,540
OK, so I hope you enjoy that and we'll see you for the next topic.