So guys, now let us begin with the root search algorithm.
So you can see that we have an MRI it out structure on the right hand side.
And at this point of time, these five rules have already been inserted into this and tried it out structure.
So it simply means that we have inserted five rules.
It means this MRI data structure would have five leaves.
Now we will going to discuss how to search a particular out and this and try to add a structure.
So when I say searching a particular route, it means that given around, let's see, 128.120 8.0.0
slash 16.
I need to come up with the answer yes or no whether this route is present in the central data structure
or not.
So our search algorithm is based on exact match bit by bit, including the don't care.
So for example, if I am looking to compare that with 1010 with the bid pattern, 101x and if I ask
you the question whether these two bid patterns are equal or not, or whether these two bid patterns
exactly matches or not, the answer is that that they do not matches.
And the reason is simple.
The last word here is zero.
And here the last bit is a drawn care bit.
So exact match means that each bid between the two bid patterns which are being masked must exactly
match even the don't care but has to match exactly with the don't care.
But on the other side.
So for example, let's say another example, we have a bit pattern here 101x does it exactly match with
the pattern?
101x and the answer is yes.
All right.
So exact match means that even don't care but has to match exactly with the complimentary don't care
bid on the other side against which the comparison is being done.
Having said that.
Now let us see whether.
We are able to search the Route 128 or 120 8.0.0 slash 16.
So the very first thing that we need to do is to compute the effective prefix of this route.
So the following is the effective prefix of this route.
Now road search algorithm begins with the route node.
Again, the very bit the very first bit of the effective prefix is one.
So I will take a part along the one at the child of the route node and I will land at the node number
three.
The node number three has a prefix length eight.
So I will going to compare the eight bits of the effective prefix with the eight bit.
Of the effective effects of the note three and they exactly matches.
All right so if the exactly matches then I will continue to traverse the and try downwards.
Now the next bit in the effective prefix is one.
So I will take the part along the one at trend of the node three and I will land at the node number
eight.
And the node number eight has a prefix length of 24.
So I will going to compare the next 24 bits of the effective prefix of the input route with the 24 bits
of the effective prefix of the node eight.
And I see the exactly matches.
All right.
And my entire 32 bits of the input effect, the prefix has been exhausted.
So I will stop my search here.
All right.
So it simply means that the number eight is a matching node and it corresponds to around 128 or 130
8.0.06.
Less extreme, which is this one.
All right.
So this is how eyes such are out in the AM trial, so I will return to that.
Such a drought as president, drought and table.
Let us execute the drought science algorithm for another example.
So for example, let's suppose that I want to solve this drought and the same tried it out structure.
So again, convert this drought into effective prefix.
Now start your search from the root node again, since the first bit of this effective prefix is one
I will take apart along the one at the child of the root node and I will land at node number three.
The prefix length of the node number three is eight.
So I was going to match it bits.
Of the route that is being served with the aid Brits of the.
Of the effect, the prefix of the node three and the exactly matches.
So I will continue my so it's down the tree.
The next bit in the input of active prefix is zero.
So I will take the part along the zero to child.
Of the three and I would land at No.
Number seven.
The No.
Number seven has the prefix length of eight.
So I will try to match the next eight bits of the input effect, the prefix with the next with the eight
bits of the effective prefix of the node seven.
And I find that the exactly matches.
So I will continue my journey downwards the next bit.
And the effective prefix of the input is don't care.
So I will take the part along the don't care child of the Lord seven and I will land at Lord Number
six.
Now the prefix length of the Lord number six is 16.
So I will going to compare the 16 bits on the input round with the 16 words of the effective prefix
of the Lord.
Six.
All right.
And the exactly.
Matches and my input.
In fact, the prefix has been completely exhausted.
So I will stop at number six.
So it simply means that the root is present in the right in a structure.
And the node which holds the data corresponding to this root is the Lord number six.
All right.
Similarly, if I want to search the 128, 120 8.0.2 slash 32, then again, compute the effect the profits
of the set out and start your assess from the root note of the and try it since the first bit of this
prefix is one.
So I will take apart along the one at the end of the root node and I will land at nought.
Number three Whose prefix length is it?
So I was going to compare the eight bits of the input effective prefix with the aid, which is on the
current nought which matches.
All right.
So I will inspect the next bit of the input prefix, which is one.
So I will try to traverse down the tree along the one, a child of the north tree, but the one that
child of the north tree is null.
There is no part.
So it simply means that this particular root is not present in the same in structure at any point during
the traversal in the add a structure starting from the root mode down the tree towards the leaf.
If you ever find that you have nowhere to go, then it means that that particular root is not present.
And the same title structure.
All right.
Here, I cannot descend down the MTI data structure further because the one at the child of the Node
three is null.
And I cannot reach to the leaf node of the triangular structure.
All right.
So it means that this particular root is not present.
And this I'm in a structure as simple as that.
So you can see that searching around that I'm trying to do a structure that's very simple and straightforward.
You just keep on comparing the bits of the effective prefix of the input route with the effective prefixes
of the nodes as we traverse down the and try to add a structure.
And it is mandatory that you should end up with some leaf node in the and try to add a structure.
By the time we are effective, prefix is completely exhausted.
Then only we see that only that particular leaf node is the matching node corresponding to your root
which is being sourced.