1
00:00:07,160 --> 00:00:12,410
In this lecture, we are going to begin implementing in our binary search tree.

2
00:00:13,610 --> 00:00:20,690
So the first thing that we need to do is create a struct called binary search tree and we'll make it

3
00:00:20,690 --> 00:00:24,200
of type T and something that we're going to do.

4
00:00:24,200 --> 00:00:32,390
And this data structure is we're going to make sure that our T type implements the Ord tree, which

5
00:00:32,390 --> 00:00:39,200
is short for ordering because ordering is important in a binary search tree and we'll see where it comes

6
00:00:39,200 --> 00:00:42,530
into play and some later lectures.

7
00:00:43,040 --> 00:00:48,230
So some of the fields that we're going to have are value and then we're going to have our left node

8
00:00:48,230 --> 00:00:50,030
and our right node.

9
00:00:50,960 --> 00:00:57,860
So our value is going to be of type option T, and then our left and right node are actually going to

10
00:00:57,860 --> 00:01:05,420
be the same type since they are both nodes and they're going to be option box, binary search, tree

11
00:01:05,420 --> 00:01:12,590
of type T, So we can now copy this and paste it down for the right side.

12
00:01:13,250 --> 00:01:23,060
So we use an option because our value, our node can either be none or some and then we use a box.

13
00:01:23,060 --> 00:01:29,210
That way we have a definable and representative type or size on the heap.

14
00:01:29,300 --> 00:01:41,270
So if we look at what happens when we remove a box and then we run cargo build, we see that we see

15
00:01:42,110 --> 00:01:48,260
that the recursive type has an infinite size and the compiler is actually telling us that, hey, we

16
00:01:48,260 --> 00:01:54,890
need to insert some indirection so that we can make the binary search tree struct rep presentable.

17
00:01:55,550 --> 00:01:58,130
And that has a couple of recommendations for us.

18
00:01:58,220 --> 00:02:07,040
So I went with box that way we are represented easily and very well on the heap.

19
00:02:08,180 --> 00:02:13,850
So now that we have our struct set up.

20
00:02:15,580 --> 00:02:24,930
And also, just in case you were wondering, for section 23, I ran cargo, new lib, Section 23.

21
00:02:24,940 --> 00:02:29,830
That way we have a new library for us to work in because we are going to do our test cases again.

22
00:02:31,090 --> 00:02:37,120
So again, now that we have our struct defined, we can begin implementing in some methods on it.

23
00:02:38,080 --> 00:02:44,200
But before we do that I want to implement in the default trait for our binary search tree.

24
00:02:45,040 --> 00:02:55,240
And default is going to be our default behavior when we call our binary search tree.

25
00:02:55,240 --> 00:02:58,870
So say we call our binary search tree, but we don't provide a method with it.

26
00:02:59,020 --> 00:03:09,100
It's going to default to the what we define here inside of our default method, which in this case we

27
00:03:09,100 --> 00:03:12,490
are going to call our new method.

28
00:03:13,600 --> 00:03:20,710
So what that's calling our new method, we know that we need to call or create a new method and our

29
00:03:20,710 --> 00:03:27,190
actual implementation block for our binary search tree.

30
00:03:28,900 --> 00:03:31,660
So we can do that right now.

31
00:03:31,660 --> 00:03:39,970
So we'll say pub F in new and with it being a new binary search tree, we know that we want to return

32
00:03:39,970 --> 00:03:49,660
a binary search tree and when we create a new binary search tree are new is actually going to create

33
00:03:49,720 --> 00:03:52,030
our root node for us.

34
00:03:52,750 --> 00:04:04,840
So when we return this struct of our binary search tree, this is going to be our root node and we just

35
00:04:05,560 --> 00:04:08,920
give the default values of none for everything.

36
00:04:08,920 --> 00:04:16,090
It's an empty root node, but when we begin inserting in values, we no longer will have an empty root

37
00:04:16,090 --> 00:04:16,600
node.

38
00:04:18,130 --> 00:04:21,640
So now we're going to begin inserting in values.

39
00:04:22,090 --> 00:04:28,540
So we'll create a public method called INSERT.

40
00:04:29,110 --> 00:04:35,050
And since we are changing the values inside of our beast, we need to make it a mutable reference to

41
00:04:35,050 --> 00:04:39,970
ourself and we want to pass in value of type T.

42
00:04:43,120 --> 00:04:47,740
So the first check that we're going to do is we want to say if the self dot value

43
00:04:50,170 --> 00:04:51,400
dot is none,

44
00:04:55,990 --> 00:04:59,860
then that's where we want to insert our value

45
00:05:02,170 --> 00:05:02,980
for.

46
00:05:04,320 --> 00:05:07,440
Our four hour insert method.

47
00:05:07,980 --> 00:05:12,390
So if if the node is none, then we want to insert some value there.

48
00:05:13,710 --> 00:05:16,530
Otherwise, we need to do a little bit more work.

49
00:05:16,830 --> 00:05:21,030
So we want to match on our self value.

50
00:05:21,780 --> 00:05:28,170
And if our value is none, then we don't have anything to do.

51
00:05:29,640 --> 00:05:33,510
Otherwise, we have some work to do.

52
00:05:35,130 --> 00:05:42,090
And remember, we need to account for are we traversing the tree left or right, or are we going left,

53
00:05:42,090 --> 00:05:46,860
right, left, left or left, right, right, left, whatever it may be.

54
00:05:46,860 --> 00:05:53,250
So we have to have some logic in here to to make sure we know where our value is correctly supposed

55
00:05:53,250 --> 00:05:53,820
to go.

56
00:05:54,480 --> 00:05:56,820
And if you remember in the previous lecture.

57
00:05:58,610 --> 00:06:04,430
It looked like some recursive calls were going in when we were calling our or when we were inserting

58
00:06:04,430 --> 00:06:07,040
values because we always started at the root node.

59
00:06:07,040 --> 00:06:10,340
And then we worked our way down to see kind of where we were going.

60
00:06:10,970 --> 00:06:18,620
So we'll take that approach and we are actually going to do some recursive ness inside of this method

61
00:06:18,620 --> 00:06:20,360
by calling our insert

62
00:06:22,790 --> 00:06:25,190
method from within our insert method.

63
00:06:25,760 --> 00:06:35,120
So in here we will say let target node equals if our value is less than our key and we want to reference

64
00:06:35,120 --> 00:06:35,840
our key.

65
00:06:36,050 --> 00:06:39,740
That way we can get the actual value inside of it.

66
00:06:39,920 --> 00:06:44,810
Then if we are less than we want to make it our left node.

67
00:06:45,410 --> 00:06:52,880
Otherwise we want to make it our right node because here we are less than.

68
00:06:52,880 --> 00:06:57,220
But here this means we are greater than.

69
00:06:59,300 --> 00:07:05,060
So now that we got that situated, now we need to match on our target node.

70
00:07:05,810 --> 00:07:09,950
Now that we have figured out what our target node is going to be.

71
00:07:10,430 --> 00:07:16,820
And so we want to say some and then if we have a ref mutable node.

72
00:07:19,350 --> 00:07:25,380
Then what we want to do here is we want to call our insert method again on our value.

73
00:07:28,500 --> 00:07:29,880
And if we are none,

74
00:07:32,850 --> 00:07:37,410
then we want to say let mute node equals a new binary search tree.

75
00:07:38,070 --> 00:07:46,620
So we want to create a new sub tree and we want to insert our value.

76
00:07:47,460 --> 00:07:56,610
And so we're calling our insert again, and now we want to set our target node is equal to some box

77
00:07:57,720 --> 00:08:00,300
new node.

78
00:08:03,690 --> 00:08:05,400
And we want to close this.

79
00:08:05,430 --> 00:08:09,010
Let's run a cargo format to make sure that we are looking good.

80
00:08:09,030 --> 00:08:09,540
All right.

81
00:08:09,540 --> 00:08:14,370
So now we are set up.

82
00:08:14,370 --> 00:08:15,660
So let's go over this again.

83
00:08:15,660 --> 00:08:22,320
So again, if our self value is none, then we want to set our value to some value.

84
00:08:23,460 --> 00:08:27,510
Now we want to match on our value.

85
00:08:27,510 --> 00:08:29,610
And if it's none, we have nothing to do.

86
00:08:29,880 --> 00:08:33,630
Otherwise we need to figure out if we're going to go to the left.

87
00:08:34,900 --> 00:08:40,510
Or to the right with our target node and then on our target nodes.

88
00:08:40,510 --> 00:08:42,810
So we now know that we went left or right.

89
00:08:42,820 --> 00:08:47,680
So now if we know we went left or right, we're going to match on that value and then we're going to

90
00:08:47,680 --> 00:08:48,520
insert again.

91
00:08:48,520 --> 00:08:54,010
So insert we'll go back up here and it's going to say, are we going left or are we going right?

92
00:08:54,370 --> 00:09:00,230
And then assuming that there is not another node connected to it.

93
00:09:00,250 --> 00:09:07,090
Well, now we can create our node call insert again and we know that it will go either to the left or

94
00:09:07,090 --> 00:09:07,870
to the right.

95
00:09:09,960 --> 00:09:20,130
So now that we have our insert method set up, let's start fleshing out some of our test cases because

96
00:09:20,130 --> 00:09:25,680
we know that we definitely need to test this to make sure everything is working correctly.

97
00:09:25,680 --> 00:09:28,920
So we will say use super.

98
00:09:28,950 --> 00:09:35,940
That way we can bring it into our scope and we are going to create a new tree and I'm actually going

99
00:09:35,940 --> 00:09:40,170
to return a new binary search tree here.

100
00:09:41,760 --> 00:09:48,990
Because as you're going to see, we are going to use this function in our other test cases.

101
00:09:49,110 --> 00:09:54,070
That way, we don't spend time constantly creating new trees.

102
00:09:54,120 --> 00:10:04,170
We can use the same tree over and over again in our test cases for a simplified setup on our test cases.

103
00:10:04,560 --> 00:10:07,560
So we're going to insert a good bit of values here.

104
00:10:07,620 --> 00:10:12,150
That way we have a pretty well populated tree that we can work against.

105
00:10:13,800 --> 00:10:17,370
And so we'll insert a few more values.

106
00:10:19,410 --> 00:10:26,160
We'll go 27, insert we'll go 34.

107
00:10:27,690 --> 00:10:32,040
In our last value, we will go 15.

108
00:10:33,000 --> 00:10:35,040
And now we can return our tree.

109
00:10:36,140 --> 00:10:42,110
So notice I did not give it a test attribute above it.

110
00:10:42,410 --> 00:10:52,310
By doing this with this actually returning our tree here, we can't test against it.

111
00:10:52,880 --> 00:10:54,740
If you try to, you will get an error.

112
00:10:54,740 --> 00:10:57,860
But if we run our test here, let's see.

113
00:10:57,860 --> 00:11:01,640
And it's because I held left wrong.

114
00:11:01,640 --> 00:11:02,660
It helps.

115
00:11:02,660 --> 00:11:04,160
Or I spelled right wrong.

116
00:11:06,500 --> 00:11:07,310
There we go.

117
00:11:07,310 --> 00:11:11,240
So now let's just make sure everything compiles happily.

118
00:11:11,240 --> 00:11:13,320
So we got everything compiled.

119
00:11:13,340 --> 00:11:17,630
Happily, we have created our insert method.

120
00:11:18,370 --> 00:11:26,830
So now in our next lecture, we are going to create some additional methods as well as their test cases,

121
00:11:26,830 --> 00:11:31,960
to make sure that our tree is being set up and working properly.

122
00:11:31,960 --> 00:11:34,390
So I will see you in the next lecture.