So guys, now let us take one more example.
Suppose we want to do a round lookup for the IP address?
1.2.3.5.
So convert this IP address into its equal and minor reform.
Take up the stack.
And we will going to start our search from the root node.
So the don't care child of the root node is four.
So just push the entry into the stack.
The node number is four and the total number of bits of the input that has been parsed is zero.
So here zero means the beginning of this input string.
So now let us begin our search from the root of this and try to add a structure.
The first bit of the input binary is string a zero.
So we will take the path along the zero child of the root node and we land at node number two.
The prefix land of the node number two is eight.
Solvable, going to match the eight bits of the input string with the eight bits of the effective prefix
of the node two and the matches.
So because the matches therefore push the don't care children of the node two into the stack, which
is the node in the bottom and the total number of bits that have been successfully parsed.
Is it all right?
And we will continue our search.
So the next bit of the input, the string is zero.
So we will take the part along the zero child of the node do and we will land.
And the node number nine, the perfect slant of the node number nine is 24.
Therefore match the quantified bits of the effective prefix of the node nine with the 24 bits of the
input string.
And sadly the do not matches now because there do not matches.
Therefore we will going to shift our subs from Node nine to Node down by popping the top element from
the stack.
The top element from the stack sees resume.
We are size from the northern and bottom and the total number of bits of the input.
The string that has been parsed is eight.
All right.
So we are at this position and are in for the string and we are at the bottom.
Now prefixed land of the north.
Number ten is 24.
Therefore match the bits of the effective prefix of the Norden with the 24 bits of the input string
and the matches.
All right.
Because the effective prefix of the time is all don't care.
Therefore, Norden matches.
And now after this match, the total number of bits of our for the string has been exhausted.
Therefore, we stop our results here at not number ten.
So the round of interest that we are looking for is the root 1.0.0.0 slash it.
So this is the root which will be used by a router in order to forward the traffic, which is just trying
for IP address.
1.2.3.5.
In other words, we see that this is the road which matters best with this IP address as per the longest
prefix maths principle.
And of course, once the rout is located successfully and this rule took up a lot of time, we will
destroy our stack.
Now note that as long as in your MTI data structure, you have this default out installed.
So it is not possible that for a given anti random IP address, if you could not find the root ask for
the longest prefix match principle then at the least the default around zero slice zero will going to
match with any random IP address as per the longest prefix match principle.
The law number four is the bottom most point in the stack and when this will pop out of the stack,
you will shift your search to node number four.
And when you shift your suggestion or number for the effective prefix of the node, number four is all
don't care.
So it means that whatever your IP address is, it will suddenly only going to match with this root,
which is zero zero.
We actually call this allowed with a special name called Default Prompt.
So this was the IP out lookup algorithm.
You practice it more for different, different IP addresses and tried to look up those IP addresses
in the same tried to structure.
So I leave it to you to practice yourself.
So now let us summarize what we have learned in this course so far.
We learned the data structure called and try, which is a tree like a structure.
Each node is a prefix offer its children.
All right, so just like you have a name.
Let's see.
Abhishek Sharma.
So Abhishek will go in the parent and Sharma will go in the trial or something like that.
Such that each node contains the data, which is a prefix of its children.
This is the property of the same tribunal structure.
And for this reason, the drive families of data structure is also called prefix treat.
All right.
They are also called Perfect three, because each note contains the prefix offered to children.
In other words, every children contains the suffix offered spitting.
And we learned about the drought in such an allotted time would certainly got a term root look up a
lot of time and allowed the additional water time.
All of that takes order of care time where key is the number of bricks and then put a string.
So for IPV four address is equal to 32.
So essentially I'm trying to add a structure gives you constant time complexity.