[No Audio]
Welcome back again in the course. The
problems that we are going to investigate in
the remaining of this section are going to be
based on the use of smart pointers that we
covered in the previous section.
In this particular tutorial, we are
going to consider a business, where there are
many products available for purchase. The
customers are frequently interested in
determining the products, which are in some
price range. Since there are too many
products with lots and lots of data,
the company wants to quickly retrieve this
information, therefore, they would like to
have a suitable data structure for storing
the product price information, which will
enable quick retrieval of the requested
information. As consultants of the business,
we will recommend the use of binary search
trees which will enable efficient storage and
quick retrieval. Let us start coding this problem.
[No Audio]
First, we will declare a vector
which will contain the product_prices.
[No Audio]
Next, we will define binary search tree
which will be used to store the values of the
product. Before implementing this, let us see
what is a binary search tree and how it will
store the values. A tree is a collection of
entities called nodes. Nodes are connected by
edges. Each node contains a value or data.
The first node of the tree is called the
root. This is an example tree. The first node
in the tree which is not being pointed to by
any other node, and is at the top is called
the root node. The value associated with this
node is the value 2. Each node may or may not
have child nodes. The nodes which are being
pointed to by a certain node are its child
nodes. The child's of the root node in this
case are the child's having the value of
7 and 5. The root having a value 2 is
said to be the parent of the nodes with a
value of 7 and 5 in this case.
The nodes with no children are also sometimes
called as leaf nodes. The tree has some
similarity with that of a Linked List type,
that we covered earlier. In contrast to
the Linked List, where the elements are
arranged in a linear fashion one after
another, the tree provides a different way of
arranging the elements. In this case, each
node has a single pointer that is pointing to
it, and that is, is the parent node.
However, each node may have multiple nodes to which it
may points to, and they are referred to as
their children. There can be different types
of trees. We will be exploring a special type
of tree called binary search tree. In binary
search tree, each node may have utmost two
children called the left child and the right
child. The tree part which is connected with
the left child is called the left subtree, and
the tree part which is connected with the
right child is called the right subtree. The
essential requirement in the binary search
tree is that, the left subtree of a node
contains only nodes with values lesser than
the node's value. In the same way, the right
subtree of a node contains only nodes with
values greater than the nodes value.
Moreover, the left and right subtree, each for
the left and right subtree each must also be
a binary search tree themselves.
Let us see how the tree is being built step wise.
Consider the following list of numbers that
we will use to store in a binary search tree.
The first value in the list will be the first
root of the binary search tree, the next value
will be matched with the value of the root,
and if it is lesser, then we will move to the
left subtree and merge it with the nodes value.
If the left subtree is empty, then we
will make an order and initialize it from the
value. If the value after matching with the
root is greater than, is greater than the
root, we will move to the right subtree and
we'll match it to the node there. Again if
the right subtree is empty, then we will make
an node there and initialize it from the value.
This algorithm will continue until all the
values are being inserted into the tree.
Since it is lesser in this case, therefore,
we will add it to the left of the root,
because there is nothing already there.
The next value is greater, so therefore, we will
add it to the right of the node. Going this
way, the next value is 20, which is greater
than the root value, so we will therefore,
move to the right and match it against the
value there. It is again greater than the
value of 14, so we will move again to the
right. And since there is nothing there, so
therefore, we will create a new node with a
value of 20 over there. The next value is
less than the root, so we will to the left,
and it is also lesser than the value of 6,
so again we will move to the left, and then
we will insert it over there. Going this way,
the next value of 30 will be inserted to the
right of 20. The next value is 8, which
is lesser than 9, so we will move to the
left and match it against 6. We may note
that it is greater than 6, so we will move
to the right and insert it there. The idea is
to keep on matching until we reach an empty node.
The next value of 17 will be inserted
in the same way to the left of 20. Finally,
the value of 5 will be inserted to the left of 8.
Once all the values are populated in the tree,
there are nice properties of the tree. For each
node, all the nodes in the left side tree
are lesser than its value, and all the nodes
in its right subtree are greater than its value.
For instance, for the value 9,
all the values in this part
of the tree are lesser than 9, and all the
values in this part are greater than 9.
This is true for any subtree of this bigger
tree. This means that, checking for some
interval will be easy and fast in this case,
because we are not required to look for all
the data all the times. For instance, if we
want to retrieve all the values in the range
of 6 to 15, so it can be done using three
conditions. First, we will check a node, if
its value is in between the two ranges, then
we will add it to the result. We may only
find a value within a given range in the left
subtree, if the value of the node is greater
than or equal to the value 6. For instance,
if the value at this node happens to have a
value such as the value 5, which is not
greater than 6, then from the property of
the binary search tree, we know that all the
nodes in the left subtree would have values
lesser than 5. And therefore, we will be
unable to find any value within the given
range in the left subtree in this case.
Finally, we will only take in the right
subtree, if the value at the node is lesser
than or equal to 15. This is again due to the
property of the binary search tree, which
ensure that all the values in the right
subtree will always be greater than the value
of the node. These three conditions will be
checked recursively for each and every node.
If the value of the node is in the range,
then we will add it to the result. We will
investigate the left subtree for the three
cases if the value is greater than or equal
to the value 6. If it is less than or equal
to the upper limit, then we will investigate
the right subtree for the three cases again.
Let us look a bit deeper at how the three
cases are being checked recursively, and how
the recursion will work. We will start with
the node of, with the node of value 9.
It satisfies the first if condition, and is
therefore being added to the result. Next, it
also satisfies the second if condition, and we
will therefore move to the left subtree.
Please note that it also satisfies the third
if condition, but we will return to that once
we are done with the left subtree. This node
also satisfies the first condition, so it
will be added to the result. It also
satisfies the second condition. So therefore,
we will move to the left again. This node now
does not satisfy any of the given conditions.
So therefore, we will return back to the
upper level node. Now this node also
satisfies the third condition, so we will
check its right node. It satisfies the first
condition, so we will add it to the list. The
left of this does not satisfies the condition
and is not right, so therefore, we will
return back to the root, because all the three
conditions for the node 6 has already been checked.
This time now, we will check the
right of the root, it satisfies the first if
condition, so therefore we will add it to the
list. It does not have left, so we will check
the third condition. The third condition is
also not matched, so therefore, we will return
the result and we are done. We will look at
the implementation of the same in the next
tutorial. Do come back again for learning
that and until then happy Rust programming.
[No Audio]