1
00:00:00,000 --> 00:00:07,700
[No Audio]

2
00:00:07,701 --> 00:00:09,866
Welcome back again in the course. The

3
00:00:09,867 --> 00:00:11,966
problems that we are going to investigate in

4
00:00:11,967 --> 00:00:13,966
the remaining of this section are going to be

5
00:00:13,967 --> 00:00:16,166
based on the use of smart pointers that we

6
00:00:16,167 --> 00:00:18,633
covered in the previous section.

7
00:00:19,800 --> 00:00:21,533
In this particular tutorial, we are

8
00:00:21,566 --> 00:00:23,766
going to consider a business, where there are

9
00:00:23,767 --> 00:00:26,966
many products available for purchase. The

10
00:00:26,967 --> 00:00:28,966
customers are frequently interested in

11
00:00:28,967 --> 00:00:31,333
determining the products, which are in some

12
00:00:31,334 --> 00:00:33,566
price range. Since there are too many

13
00:00:33,567 --> 00:00:35,500
products with lots and lots of data,

14
00:00:35,933 --> 00:00:38,300
the company wants to quickly retrieve this

15
00:00:38,333 --> 00:00:40,633
information, therefore, they would like to

16
00:00:40,634 --> 00:00:42,700
have a suitable data structure for storing

17
00:00:42,701 --> 00:00:45,333
the product price information, which will

18
00:00:45,334 --> 00:00:47,666
enable quick retrieval of the requested

19
00:00:47,700 --> 00:00:51,666
information. As consultants of the business,

20
00:00:51,866 --> 00:00:54,000
we will recommend the use of binary search

21
00:00:54,001 --> 00:00:56,600
trees which will enable efficient storage and

22
00:00:56,601 --> 00:01:00,000
quick retrieval. Let us start coding this problem.

23
00:01:00,001 --> 00:01:02,100
[No Audio]

24
00:01:02,101 --> 00:01:04,033
First, we will declare a vector

25
00:01:04,034 --> 00:01:06,033
which will contain the product_prices.

26
00:01:06,034 --> 00:01:15,200
[No Audio]

27
00:01:15,201 --> 00:01:17,366
Next, we will define binary search tree

28
00:01:17,466 --> 00:01:19,600
which will be used to store the values of the

29
00:01:19,601 --> 00:01:22,500
product. Before implementing this, let us see

30
00:01:22,501 --> 00:01:24,733
what is a binary search tree and how it will

31
00:01:24,734 --> 00:01:27,266
store the values. A tree is a collection of

32
00:01:27,300 --> 00:01:30,533
entities called nodes. Nodes are connected by

33
00:01:30,534 --> 00:01:34,000
edges. Each node contains a value or data.

34
00:01:34,800 --> 00:01:37,033
The first node of the tree is called the

35
00:01:37,034 --> 00:01:41,200
root. This is an example tree. The first node

36
00:01:41,201 --> 00:01:43,766
in the tree which is not being pointed to by

37
00:01:43,767 --> 00:01:46,500
any other node, and is at the top is called

38
00:01:46,501 --> 00:01:49,600
the root node. The value associated with this

39
00:01:49,601 --> 00:01:53,666
node is the value 2. Each node may or may not

40
00:01:53,667 --> 00:01:57,000
have child nodes. The nodes which are being

41
00:01:57,001 --> 00:02:00,200
pointed to by a certain node are its child

42
00:02:00,201 --> 00:02:03,100
nodes. The child's of the root node in this

43
00:02:03,101 --> 00:02:05,600
case are the child's having the value of

44
00:02:05,601 --> 00:02:09,032
7 and 5. The root having a value 2 is

45
00:02:09,033 --> 00:02:10,900
said to be the parent of the nodes with a

46
00:02:10,901 --> 00:02:13,000
value of 7 and 5 in this case.

47
00:02:13,900 --> 00:02:16,833
The nodes with no children are also sometimes

48
00:02:16,834 --> 00:02:20,066
called as leaf nodes. The tree has some

49
00:02:20,067 --> 00:02:22,333
similarity with that of a Linked List type,

50
00:02:22,366 --> 00:02:26,300
that we covered earlier. In contrast to

51
00:02:26,301 --> 00:02:28,033
the Linked List, where the elements are

52
00:02:28,066 --> 00:02:30,266
arranged in a linear fashion one after

53
00:02:30,267 --> 00:02:32,533
another, the tree provides a different way of

54
00:02:32,534 --> 00:02:35,100
arranging the elements. In this case, each

55
00:02:35,101 --> 00:02:38,433
node has a single pointer that is pointing to

56
00:02:38,434 --> 00:02:42,000
it, and that is, is the parent node.

57
00:02:43,400 --> 00:02:46,500
However, each node may have multiple nodes to which it

58
00:02:46,501 --> 00:02:49,600
may points to, and they are referred to as

59
00:02:49,601 --> 00:02:53,000
their children. There can be different types

60
00:02:53,001 --> 00:02:56,033
of trees. We will be exploring a special type

61
00:02:56,034 --> 00:02:58,900
of tree called binary search tree. In binary

62
00:02:58,901 --> 00:03:01,400
search tree, each node may have utmost two

63
00:03:01,401 --> 00:03:03,833
children called the left child and the right

64
00:03:03,834 --> 00:03:07,700
child. The tree part which is connected with

65
00:03:07,701 --> 00:03:10,400
the left child is called the left subtree, and

66
00:03:10,401 --> 00:03:12,266
the tree part which is connected with the

67
00:03:12,267 --> 00:03:15,000
right child is called the right subtree. The

68
00:03:15,001 --> 00:03:16,933
essential requirement in the binary search

69
00:03:16,934 --> 00:03:18,766
tree is that, the left subtree of a node

70
00:03:18,767 --> 00:03:21,166
contains only nodes with values lesser than

71
00:03:21,167 --> 00:03:23,766
the node's value. In the same way, the right

72
00:03:23,767 --> 00:03:26,500
subtree of a node contains only nodes with

73
00:03:26,501 --> 00:03:28,366
values greater than the nodes value.

74
00:03:28,533 --> 00:03:31,733
Moreover, the left and right subtree, each for

75
00:03:31,734 --> 00:03:34,233
the left and right subtree each must also be

76
00:03:34,234 --> 00:03:36,033
a binary search tree themselves.

77
00:03:37,333 --> 00:03:39,933
Let us see how the tree is being built step wise.

78
00:03:40,000 --> 00:03:42,566
Consider the following list of numbers that

79
00:03:42,567 --> 00:03:44,866
we will use to store in a binary search tree.

80
00:03:45,266 --> 00:03:47,400
The first value in the list will be the first

81
00:03:47,401 --> 00:03:50,200
root of the binary search tree, the next value

82
00:03:50,201 --> 00:03:52,166
will be matched with the value of the root,

83
00:03:52,500 --> 00:03:55,233
and if it is lesser, then we will move to the

84
00:03:55,234 --> 00:03:58,533
left subtree and merge it with the nodes value.

85
00:03:59,200 --> 00:04:01,800
If the left subtree is empty, then we

86
00:04:01,801 --> 00:04:04,233
will make an order and initialize it from the

87
00:04:04,234 --> 00:04:07,566
value. If the value after matching with the

88
00:04:07,567 --> 00:04:09,900
root is greater than, is greater than the

89
00:04:09,901 --> 00:04:12,200
root, we will move to the right subtree and

90
00:04:12,201 --> 00:04:15,300
we'll match it to the node there. Again if

91
00:04:15,301 --> 00:04:17,632
the right subtree is empty, then we will make

92
00:04:17,633 --> 00:04:19,933
an node there and initialize it from the value.

93
00:04:20,233 --> 00:04:22,800
This algorithm will continue until all the

94
00:04:22,801 --> 00:04:25,033
values are being inserted into the tree.

95
00:04:25,966 --> 00:04:27,900
Since it is lesser in this case, therefore,

96
00:04:27,901 --> 00:04:29,766
we will add it to the left of the root,

97
00:04:29,833 --> 00:04:31,833
because there is nothing already there.

98
00:04:31,834 --> 00:04:34,933
The next value is greater, so therefore, we will

99
00:04:34,934 --> 00:04:38,300
add it to the right of the node. Going this

100
00:04:38,301 --> 00:04:40,533
way, the next value is 20, which is greater

101
00:04:40,534 --> 00:04:43,166
than the root value, so we will therefore,

102
00:04:43,167 --> 00:04:45,500
move to the right and match it against the

103
00:04:45,501 --> 00:04:48,333
value there. It is again greater than the

104
00:04:48,334 --> 00:04:50,666
value of 14, so we will move again to the

105
00:04:50,667 --> 00:04:53,066
right. And since there is nothing there, so

106
00:04:53,067 --> 00:04:55,566
therefore, we will create a new node with a

107
00:04:55,567 --> 00:04:58,466
value of 20 over there. The next value is

108
00:04:58,467 --> 00:05:00,733
less than the root, so we will to the left,

109
00:05:01,133 --> 00:05:03,900
and it is also lesser than the value of 6,

110
00:05:03,901 --> 00:05:06,966
so again we will move to the left, and then

111
00:05:06,967 --> 00:05:09,700
we will insert it over there. Going this way,

112
00:05:09,866 --> 00:05:12,033
the next value of 30 will be inserted to the

113
00:05:12,034 --> 00:05:15,333
right of 20. The next value is 8, which

114
00:05:15,334 --> 00:05:17,200
is lesser than 9, so we will move to the

115
00:05:17,201 --> 00:05:20,600
left and match it against 6. We may note

116
00:05:20,601 --> 00:05:23,166
that it is greater than 6, so we will move

117
00:05:23,167 --> 00:05:25,766
to the right and insert it there. The idea is

118
00:05:25,767 --> 00:05:28,300
to keep on matching until we reach an empty node.

119
00:05:28,633 --> 00:05:30,800
The next value of 17 will be inserted

120
00:05:30,801 --> 00:05:33,233
in the same way to the left of 20. Finally,

121
00:05:33,234 --> 00:05:35,833
the value of 5 will be inserted to the left of 8.

122
00:05:36,733 --> 00:05:39,433
Once all the values are populated in the tree,

123
00:05:39,434 --> 00:05:42,400
there are nice properties of the tree. For each

124
00:05:42,401 --> 00:05:44,700
node, all the nodes in the left side tree

125
00:05:44,701 --> 00:05:47,500
are lesser than its value, and all the nodes

126
00:05:47,600 --> 00:05:50,633
in its right subtree are greater than its value.

127
00:05:51,100 --> 00:05:52,933
For instance, for the value 9,

128
00:05:52,934 --> 00:05:54,433
all the values in this part

129
00:05:54,434 --> 00:05:57,000
of the tree are lesser than 9, and all the

130
00:05:57,001 --> 00:05:59,366
values in this part are greater than 9.

131
00:05:59,900 --> 00:06:02,966
This is true for any subtree of this bigger

132
00:06:02,967 --> 00:06:05,367
tree. This means that, checking for some

133
00:06:05,368 --> 00:06:08,000
interval will be easy and fast in this case,

134
00:06:08,001 --> 00:06:10,100
because we are not required to look for all

135
00:06:10,101 --> 00:06:12,533
the data all the times. For instance, if we

136
00:06:12,534 --> 00:06:14,300
want to retrieve all the values in the range

137
00:06:14,301 --> 00:06:16,833
of 6 to 15, so it can be done using three

138
00:06:16,834 --> 00:06:20,500
conditions. First, we will check a node, if

139
00:06:20,501 --> 00:06:23,166
its value is in between the two ranges, then

140
00:06:23,167 --> 00:06:26,000
we will add it to the result. We may only

141
00:06:26,001 --> 00:06:28,833
find a value within a given range in the left

142
00:06:28,834 --> 00:06:31,266
subtree, if the value of the node is greater

143
00:06:31,267 --> 00:06:33,733
than or equal to the value 6. For instance,

144
00:06:33,833 --> 00:06:36,033
if the value at this node happens to have a

145
00:06:36,034 --> 00:06:38,400
value such as the value 5, which is not

146
00:06:38,401 --> 00:06:40,666
greater than 6, then from the property of

147
00:06:40,667 --> 00:06:42,533
the binary search tree, we know that all the

148
00:06:42,534 --> 00:06:44,533
nodes in the left subtree would have values

149
00:06:44,534 --> 00:06:46,900
lesser than 5. And therefore, we will be

150
00:06:46,901 --> 00:06:49,033
unable to find any value within the given

151
00:06:49,034 --> 00:06:51,033
range in the left subtree in this case.

152
00:06:52,100 --> 00:06:53,900
Finally, we will only take in the right

153
00:06:53,901 --> 00:06:56,100
subtree, if the value at the node is lesser

154
00:06:56,101 --> 00:06:59,533
than or equal to 15. This is again due to the

155
00:06:59,534 --> 00:07:01,800
property of the binary search tree, which

156
00:07:01,801 --> 00:07:03,600
ensure that all the values in the right

157
00:07:03,601 --> 00:07:05,700
subtree will always be greater than the value

158
00:07:05,701 --> 00:07:09,000
of the node. These three conditions will be

159
00:07:09,001 --> 00:07:11,433
checked recursively for each and every node.

160
00:07:11,434 --> 00:07:13,600
If the value of the node is in the range,

161
00:07:13,800 --> 00:07:16,200
then we will add it to the result. We will

162
00:07:16,201 --> 00:07:18,466
investigate the left subtree for the three

163
00:07:18,467 --> 00:07:21,300
cases if the value is greater than or equal

164
00:07:21,301 --> 00:07:24,000
to the value 6. If it is less than or equal

165
00:07:24,001 --> 00:07:25,866
to the upper limit, then we will investigate

166
00:07:25,867 --> 00:07:28,133
the right subtree for the three cases again.

167
00:07:29,166 --> 00:07:31,766
Let us look a bit deeper at how the three

168
00:07:31,767 --> 00:07:34,266
cases are being checked recursively, and how

169
00:07:34,267 --> 00:07:36,900
the recursion will work. We will start with

170
00:07:36,901 --> 00:07:39,233
the node of, with the node of value 9.

171
00:07:39,433 --> 00:07:42,300
It satisfies the first if condition, and is

172
00:07:42,301 --> 00:07:44,800
therefore being added to the result. Next, it

173
00:07:44,833 --> 00:07:47,600
also satisfies the second if condition, and we

174
00:07:47,601 --> 00:07:50,300
will therefore move to the left subtree.

175
00:07:50,833 --> 00:07:53,100
Please note that it also satisfies the third

176
00:07:53,101 --> 00:07:55,800
if condition, but we will return to that once

177
00:07:55,801 --> 00:07:58,800
we are done with the left subtree. This node

178
00:07:58,801 --> 00:08:01,066
also satisfies the first condition, so it

179
00:08:01,067 --> 00:08:03,033
will be added to the result. It also

180
00:08:03,066 --> 00:08:05,200
satisfies the second condition. So therefore,

181
00:08:05,201 --> 00:08:08,700
we will move to the left again. This node now

182
00:08:08,701 --> 00:08:11,333
does not satisfy any of the given conditions.

183
00:08:11,334 --> 00:08:13,933
So therefore, we will return back to the

184
00:08:13,934 --> 00:08:16,733
upper level node. Now this node also

185
00:08:16,734 --> 00:08:19,566
satisfies the third condition, so we will

186
00:08:19,567 --> 00:08:23,233
check its right node. It satisfies the first

187
00:08:23,266 --> 00:08:27,033
condition, so we will add it to the list. The

188
00:08:27,034 --> 00:08:29,366
left of this does not satisfies the condition

189
00:08:29,400 --> 00:08:32,133
and is not right, so therefore, we will

190
00:08:32,166 --> 00:08:35,700
return back to the root, because all the three

191
00:08:35,701 --> 00:08:38,200
conditions for the node 6 has already been checked.

192
00:08:39,633 --> 00:08:42,265
This time now, we will check the

193
00:08:42,299 --> 00:08:45,000
right of the root, it satisfies the first if

194
00:08:45,001 --> 00:08:46,900
condition, so therefore we will add it to the

195
00:08:46,901 --> 00:08:50,200
list. It does not have left, so we will check

196
00:08:50,201 --> 00:08:53,166
the third condition. The third condition is

197
00:08:53,167 --> 00:08:56,433
also not matched, so therefore, we will return

198
00:08:56,434 --> 00:08:59,166
the result and we are done. We will look at

199
00:08:59,167 --> 00:09:00,866
the implementation of the same in the next

200
00:09:00,867 --> 00:09:02,766
tutorial. Do come back again for learning

201
00:09:02,767 --> 00:09:05,766
that and until then happy Rust programming.

202
00:09:05,767 --> 00:09:10,533
[No Audio]