Hello, everyone, welcome to this brand new video.
So in this video, we are going to learn Venuti, the structure, which is called tri.
So before moving on and learning what is try, first of all, let's try to understand why do we need
this new researcher?
So, for example, we are given a list of words.
This is our words.
And if I want to search one word and this words area, for example, if I want to search the world news,
then how I will search whether this news word is present in this world or not.
The approach is very simple, right?
You will Etretat what these words are and you will compare the given word with the words which are present
in this word today, for example, first of all, you will compare whether there are equals to news
on Earth.
Then we will compare this word and you will compare this word and you will keep comparing the word.
And finally, you will be able to find the word news and then you will report your answer.
Yes, the given word is basically present in the words that, for example, if the what is not present,
then when word is not present in this words, very.
But what do you need to do in order to find out this?
You will iterate over the complete words, Eddie, and you will compare each word with the given word
and you will not be able to find the given word when in this words that end they will report your answer.
No, the word is not present in the words.
So this approach is not good at all for each word.
You need to get rid of this words adding and to compare each word with the given word.
So what do want to do?
We want to optimize this.
We want to optimise our searching process and try to the structure will help us do that.
So how actually will help us?
So let's start.
So try to first of all, we will have a start node or we can say a root node, just like they are treated
as a teacher.
So we have the start node or the we can say it is a root node and what will do?
We will insert all the words.
We will insert all these words in our new structure, which is called try.
Now let's see how you will insert words.
So first, let's first let me draw some Overlordship, some nodes, basically.
Yep, so let's try to insert first word, what with the process and how we will be able to insert the
word, so I want to insert this word or so I will go to the root node and I will see whether the character
is whether a node corresponding to is present or not.
No, there is no node corresponding to correctly.
So I will create one node and I will store it here and I will make the connection.
I will make this connection.
Now go to the next word.
Ah, so I am standing at this node, I am standing at Node A and I will see whether there is a node
where the or not there is no node with character.
So you will create one node and you will store are here and they will make this connection.
Now go to the next character.
So next character is e you are standing at this node and you will see whether there is a node with the
correctly or not.
No, there is no node.
So I will create one node and you restore it here and you will make this connection.
So now our word is basically over.
So what we will do, we will highlight the last node.
So we will highlight we will make this node a bold in order.
We will basically highlight this node so that we can represent that ad correctly.
One word is ending here.
So e r e is one, correct?
Sorry, it's one word.
And we are highlighting to indicate that this is a given word.
This is the and this is the end.
Correct.
For a given word.
Now let's move on to the second word which you want to insert.
So again, we will see here that e so you are standing at the root node.
You are inserting one more word.
You are standing at the root and you will see whether it is present or not.
Yes, we have it.
So I will reach here.
Then I will check whether S is present or not.
No s is not present.
So what you will do, you will create one node and you will store s here and you will make this connection.
And now, as is the end character for the government, since this is the end character, you will basically
highlight this and you will say this is basically terminal.
All right.
This node is not terminal.
This node is known terminal this nor the terminal, not by terminal node.
I mean that the given word is ending here.
This is the end goal for a given word.
Similarly, this is the end character of one of the word.
So this is our terminal node.
Now, let's move on to the next word that we want to insert.
We want to insert do so.
Let me create some nodes first.
OK, so I want to insert the word do so, first of all, I will check whether this is present or not.
So I am standing at the root node and I want to check the present or not is not present.
So you will create one node and it will be here and you will make this connection.
Now move on to the second character, which is all.
So you are standing at this node and you will see whether there is a node with character or not.
No, there is no word.
So you will make a node and you will store all here.
You will make this connection and all is basically the last character for the given word.
So you will basically highlight this node will make this node as terminal node to indicate that this
is the end.
Correct.
Therefore, a given word, a word is basically ending at character.
Now let's move on to the next word, which we want to insert.
So the next word that we want to insert is basically dot.
So I'm standing at the root node.
I will see whether correctly this present or not.
Yes.
Correctly is present.
So come here next.
Check whether character is present or not.
Yes, character is present.
So you will come here now to check whether character to present or not.
B is not present.
So you will make a node and you will still be in that node and it will make this connection.
And since P is basically the last character of a word, so you will highlight this node, we will make
this node a terminal.
All right.
Now let's move on to the new word which you want to insert.
So I want to insert the word new.
So let me create a few nodes here.
So let's start.
So I want to insert the word new, I'm standing at the root node and there is no character, no node
which is storing the character.
And so I will create one node and it will store the character in and I will make this connection.
Now, the next character is E!
So I am standing at this node.
I am standing at this node and there is no node with the character E, so I will make this node and
I will make this connection one thing.
Do not confuse that E is present here.
So why I am creating new node.
So basically I will check for each character.
Right for and there is no node present downward often.
Right.
So it is basically downward of are not downward of end.
Right.
That's why you need to create new node.
So I will, I'm standing here and I will see whether is pointing towards any node which is containing
you or not.
OK, so I need to see downward for each character.
So it is not present.
I have created E and I have made this connection.
Now I am standing at E.
I will see whether the word W is present or not.
So downward of it.
There is no node with which is storing W.
So I will create one node and it was was the blue in it and it will make this connection.
And since this is the terminal word sorry, since this is the terminal character, we will highlight
this word, we will highlight this node.
Sorry.
So we are highlighting this node via because one word is ending at this character.
Fine.
Now let's try to insert new character.
Sorry, let's try to insert news.
So we're trending at the root node, see whether any is present or not.
Yes.
And this present.
So go to N now check e presenta n is present so go to check whether W is present or NSW is present.
So go to the blue check whether S.
S present or not.
No s is not present in the down side of the blue.
So what you will do, you will create one node and you will store as here you will make this connection.
And since this is the last character, you will also highlight this.
So I will also highlight this.
Now, let's try to insert the remaining words in our trial subject, so let me create notes here.
OK, now let's move.
So I want to insert this word.
So the first character is and I am standing at the root node and I have a node which is storing.
And so I will come here basically.
And from here what I will do.
So I will check whether the next word no is pleasant or not.
So all in the downside of and I have only I do not have.
Oh so what I will do, I will create one node and this node will store all and I will make the connection.
And I will come at this node, so I am standing at this node and always basically the last character.
So what you will do, you will also highlight that this node is basically the last character.
Now, I want to insert this word not so again.
You are standing at the root node.
There is a node which is storing and so you will come here now the next characteris or so there is a
node which is storing the character.
So you will come here now the next characteristic.
So all is not pointing to any node which is storing piece of it.
You will do, you will create one new node and you will still be here.
You will make this connection.
And since this is the last character for a while, you will make this node as terminal node.
And now our trial structure is complete, so our trial, a structure is complete now, and let's see
how this trial structure will improve our searching.
Let's try to find out, for example, if I want to search the world news, if I want to search the world
news, what I will do, go to the root node.
Now, check whether there is a node with character and or not.
Yes, there is a word with character.
And so go to this node.
I am standing here next characteris E to check whether there is an order registering.
Yes, there is an order which is storing e so come here next connector is W so e pointing towards the
blue.
Yes, there is an order which is storing the blue.
So come here.
I am standing here.
Check as whether there is an order which is an NDA character, which there is an order which is storing
is now the word is over.
Now the wait is over.
So check whether this note is a terminal or not.
Yes, this is a terminal.
So my output will be yes, my output will be yes.
We have optimized our searching because in this case, what is the time, complexity, time?
Complexity is basically begal for wifehood because there are four characters.
Right.
So this is simply because for now, for this word, when you are standing at the root node, you will
see whether there is an order restoring the blue or not.
No, there is no node which is storing the blue.
We are we have a deep and and there is no node which are storing the blue.
I will return answer no.
So in just one comparison, in just one comparison, I am able to find out that this node is not present.
OK, so basically for any given word, for any given time, complexity, in the worst case time complexity
will be big off and and is basically the number of characters present in the world and is the number
of characters, for example, in this case news, there are four characters.
So time complexity is big, all four.
So this is the time complexity big off and is the number of characters in the given word.
So you can see we have.
Optimized our searching with the help of private sector search, private sector basically helps us in
searching.
Right now, let's take one more example, so we're taking the.
So what you can do, for example, we have a dictionary, right, we have dictionary.
Dictionary is containing basically a list of words in a dictionary.
We have a list of words, for example, given a word, you want to check whether the given word is present
in dictionary or not.
So what will be the very naive approach, very brute force approach?
It will be basically go through the list of words in the dictionary and check each word of a given word.
But that will be a lot of a lot of time, so best approach will be what you do.
You will insert all the words of dictionary into a try.
You will make a try.
You will build a try.
So we will build a tri of dictionary words.
We will build a tri of dictionary word, and this will be a one time.
Once we have built a tri of all the words the dictionary, then if you want to search any word in the
dictionary, what you will do, you will search and try.
We will search and try and in private, as the searching, searching is basically big often.
And that's how Trai is used in dictionary, right, and repeating myself, but will do.
This is a one time hard work that what we need to do, we need to insert all the words of a try in a
dictionary.
And once we have inserted all the words now for searching our time, complexity will be Gulfam.
So we have optimized our searching.
Let me give you one more example of trying.
So have you heard of so there is one app, which is Truecaller.
Now, what Truecaller does is you provide the number, for example, this is the number and the Truecaller
app from a given number.
It will give you the name of the person.
It will give you the name of the person to whom this number belongs.
So how Truecaller app works.
So basically, it builds a try.
It builds a trial phone number, for example.
Let me take a few examples here.
So this is another number.
Let's say this is another number.
Let's say these are few numbers and each number has a name associated with it, so each number has a
name, let's say the name for this is basically ABC four.
This is something else.
Let's name it.
The name for this is basically then this is B, C, D, E, D, and this is E, so these are the name
of the person's right.
So how how Truecaller works is basically it creates a triangle phone number.
So let's create very fast.
So I have this root node.
Now, insert this word sunshine, create an order for the nine again, create next nine, then one,
then seven to create nine, then I have one and then I have seven.
Next is basically nine nine one eight, so nine nine one and eight, so for eight.
Next is nine nine nine, so nine nine one and then nine.
Next is nine nine nine nine, so nine, then again nine, then we have nine here, so we have nine here
and then again nine.
So this is nine, Nexus nine, nine, two and seven.
So nine, then nine.
Then I have to here and then I have seven.
So all the terminal nodes seven is a terminal node, so four, what I will do, I was told, hear the
name of the person.
So this is our terminal node and this terminal node is storing one more information, which is the name
of the person.
So I will told the name of the person in this node, last node basically for nine, when I restore the
name of the person, the name of the person is B, this is our terminal load.
Nine nine one nine, so this is, again, a terminal node and a terminal load is going to store the
name of the person.
So the name of the person is C nine nine nine nine.
So I want to be here and this is our terminal node again, nine nine to seven.
So I was told the name of the person here and this is our terminal node.
So Truecaller app makes a tri of all the phone numbers and terminal node.
It's the name of the person.
Now, if you if you want to search one number, for example, let's say I want to search nine nine nine
nine, I am giving the input nine nine nine nine.
And I want to search what is the name of the person for this number.
So what I will do, go to nine, then go to nine, then go to nine, then go to nine.
And I will reach the terminal node, I will reach the terminal node and I will check the name of the
person inside.
So I will return.
My answer is the simple right now let's see if a number does not belong or a number is not present in
a try.
For example, this number is not present in tray.
Basically Truecaller.
Truecaller does not have information of this number.
So I will search in the tray.
So nine then.
I don't have it.
I don't have it here.
So I will say that we do not have the information.
We do not have the either the phone number is wrong in this phone number is wrong.
This is not a valid phone number or the Truecaller.
I will say I do not have the information for this number.
So it will say no information.
Right.
So this is how Truecaller works, and if this is a valid number, then Truecaller will insert this valid
number into it and it will store the corresponding name also.
So that is the that is the basically that is the practical implementation of the private sector.
So in next, we do what we will do.
We will implement our own private sector.
So this is it from this video.
Guys, I will see you in the next one.
And in the next video, we are going to implement our private sector.
So this is it.
Thank you, guys.