In this lecture, we are going to begin implementing in our binary search tree.
So the first thing that we need to do is create a struct called binary search tree and we'll make it
of type T and something that we're going to do.
And this data structure is we're going to make sure that our T type implements the Ord tree, which
is short for ordering because ordering is important in a binary search tree and we'll see where it comes
into play and some later lectures.
So some of the fields that we're going to have are value and then we're going to have our left node
and our right node.
So our value is going to be of type option T, and then our left and right node are actually going to
be the same type since they are both nodes and they're going to be option box, binary search, tree
of type T, So we can now copy this and paste it down for the right side.
So we use an option because our value, our node can either be none or some and then we use a box.
That way we have a definable and representative type or size on the heap.
So if we look at what happens when we remove a box and then we run cargo build, we see that we see
that the recursive type has an infinite size and the compiler is actually telling us that, hey, we
need to insert some indirection so that we can make the binary search tree struct rep presentable.
And that has a couple of recommendations for us.
So I went with box that way we are represented easily and very well on the heap.
So now that we have our struct set up.
And also, just in case you were wondering, for section 23, I ran cargo, new lib, Section 23.
That way we have a new library for us to work in because we are going to do our test cases again.
So again, now that we have our struct defined, we can begin implementing in some methods on it.
But before we do that I want to implement in the default trait for our binary search tree.
And default is going to be our default behavior when we call our binary search tree.
So say we call our binary search tree, but we don't provide a method with it.
It's going to default to the what we define here inside of our default method, which in this case we
are going to call our new method.
So what that's calling our new method, we know that we need to call or create a new method and our
actual implementation block for our binary search tree.
So we can do that right now.
So we'll say pub F in new and with it being a new binary search tree, we know that we want to return
a binary search tree and when we create a new binary search tree are new is actually going to create
our root node for us.
So when we return this struct of our binary search tree, this is going to be our root node and we just
give the default values of none for everything.
It's an empty root node, but when we begin inserting in values, we no longer will have an empty root
node.
So now we're going to begin inserting in values.
So we'll create a public method called INSERT.
And since we are changing the values inside of our beast, we need to make it a mutable reference to
ourself and we want to pass in value of type T.
So the first check that we're going to do is we want to say if the self dot value
dot is none,
then that's where we want to insert our value
for.
Our four hour insert method.
So if if the node is none, then we want to insert some value there.
Otherwise, we need to do a little bit more work.
So we want to match on our self value.
And if our value is none, then we don't have anything to do.
Otherwise, we have some work to do.
And remember, we need to account for are we traversing the tree left or right, or are we going left,
right, left, left or left, right, right, left, whatever it may be.
So we have to have some logic in here to to make sure we know where our value is correctly supposed
to go.
And if you remember in the previous lecture.
It looked like some recursive calls were going in when we were calling our or when we were inserting
values because we always started at the root node.
And then we worked our way down to see kind of where we were going.
So we'll take that approach and we are actually going to do some recursive ness inside of this method
by calling our insert
method from within our insert method.
So in here we will say let target node equals if our value is less than our key and we want to reference
our key.
That way we can get the actual value inside of it.
Then if we are less than we want to make it our left node.
Otherwise we want to make it our right node because here we are less than.
But here this means we are greater than.
So now that we got that situated, now we need to match on our target node.
Now that we have figured out what our target node is going to be.
And so we want to say some and then if we have a ref mutable node.
Then what we want to do here is we want to call our insert method again on our value.
And if we are none,
then we want to say let mute node equals a new binary search tree.
So we want to create a new sub tree and we want to insert our value.
And so we're calling our insert again, and now we want to set our target node is equal to some box
new node.
And we want to close this.
Let's run a cargo format to make sure that we are looking good.
All right.
So now we are set up.
So let's go over this again.
So again, if our self value is none, then we want to set our value to some value.
Now we want to match on our value.
And if it's none, we have nothing to do.
Otherwise we need to figure out if we're going to go to the left.
Or to the right with our target node and then on our target nodes.
So we now know that we went left or right.
So now if we know we went left or right, we're going to match on that value and then we're going to
insert again.
So insert we'll go back up here and it's going to say, are we going left or are we going right?
And then assuming that there is not another node connected to it.
Well, now we can create our node call insert again and we know that it will go either to the left or
to the right.
So now that we have our insert method set up, let's start fleshing out some of our test cases because
we know that we definitely need to test this to make sure everything is working correctly.
So we will say use super.
That way we can bring it into our scope and we are going to create a new tree and I'm actually going
to return a new binary search tree here.
Because as you're going to see, we are going to use this function in our other test cases.
That way, we don't spend time constantly creating new trees.
We can use the same tree over and over again in our test cases for a simplified setup on our test cases.
So we're going to insert a good bit of values here.
That way we have a pretty well populated tree that we can work against.
And so we'll insert a few more values.
We'll go 27, insert we'll go 34.
In our last value, we will go 15.
And now we can return our tree.
So notice I did not give it a test attribute above it.
By doing this with this actually returning our tree here, we can't test against it.
If you try to, you will get an error.
But if we run our test here, let's see.
And it's because I held left wrong.
It helps.
Or I spelled right wrong.
There we go.
So now let's just make sure everything compiles happily.
So we got everything compiled.
Happily, we have created our insert method.
So now in our next lecture, we are going to create some additional methods as well as their test cases,
to make sure that our tree is being set up and working properly.
So I will see you in the next lecture.