1 00:00:01,080 --> 00:00:03,300 Hi, everyone, welcome to this new video. 2 00:00:03,330 --> 00:00:09,640 So in this video, what we are going to do is we are going to build one try of dictionary. 3 00:00:11,280 --> 00:00:14,000 We are going to build one tree of dictionary. 4 00:00:14,010 --> 00:00:15,450 And this is my dictionary. 5 00:00:15,690 --> 00:00:21,690 So correctly, dictionary is containing these words and I need to build one tree out of it. 6 00:00:22,530 --> 00:00:22,930 Right. 7 00:00:23,100 --> 00:00:25,830 So we have discussed how that will look like. 8 00:00:26,040 --> 00:00:34,620 So first I will have the root node and then basically also create a node with data and then create a 9 00:00:34,620 --> 00:00:38,220 node with a data R and create a node with data. 10 00:00:38,760 --> 00:00:44,110 And since E is the last node, so what we will do, you will also highlight this node. 11 00:00:45,660 --> 00:00:48,870 So we need to insert all these words. 12 00:00:48,870 --> 00:00:54,540 We need to insert all these words in our trade as actual simple. 13 00:00:54,540 --> 00:00:54,900 Right. 14 00:00:55,800 --> 00:00:59,850 So what we need to do, first of all, we need to define what is this node? 15 00:01:00,840 --> 00:01:01,680 What is this node? 16 00:01:01,860 --> 00:01:07,200 So basically this let's say the name of the node is try node. 17 00:01:08,490 --> 00:01:14,820 So we're destroying all this, containing it will contain data, some data and the data is off type 18 00:01:14,820 --> 00:01:15,410 character. 19 00:01:15,690 --> 00:01:18,420 So I will have something like character data. 20 00:01:19,850 --> 00:01:28,010 What else it will contain, so it will contain like whether the given node is a terminal node or not. 21 00:01:28,790 --> 00:01:29,180 Right. 22 00:01:29,180 --> 00:01:31,540 But given all is a terminal or not. 23 00:01:31,940 --> 00:01:36,730 So it will contain something, a ball type ball, whether terminal or not. 24 00:01:36,740 --> 00:01:37,760 So is terminal. 25 00:01:40,060 --> 00:01:49,470 What else it will contain, so see for a how many possibilities, how many trials can be there? 26 00:01:50,170 --> 00:01:51,790 So currently I have one child. 27 00:01:51,970 --> 00:01:56,920 If I insert this character, this word, sorry, so I will have one more node. 28 00:01:57,490 --> 00:02:01,000 So now it has to child it has two child otterness. 29 00:02:01,000 --> 00:02:03,590 So that makes how many trials can be delayed. 30 00:02:04,000 --> 00:02:08,889 So I think at the max there can be 26 trials because we have 26 alphabet's. 31 00:02:08,889 --> 00:02:09,240 Right. 32 00:02:09,880 --> 00:02:13,990 So what we need to do, we need to create one area of trials also. 33 00:02:14,950 --> 00:02:19,670 So array of trials basically and trial is of type. 34 00:02:19,690 --> 00:02:23,220 So this is a trial and jail is also a trial. 35 00:02:23,230 --> 00:02:24,670 All right. 36 00:02:24,880 --> 00:02:26,940 This trial is also a.. 37 00:02:27,250 --> 00:02:34,240 And notice basically to astronaut and this this node is appointed to this node. 38 00:02:34,450 --> 00:02:36,670 So that's a appointer to trial. 39 00:02:37,480 --> 00:02:38,800 And how many trials? 40 00:02:38,950 --> 00:02:40,220 26 trials. 41 00:02:41,170 --> 00:02:44,830 So what I'm trying to say here is how the node will look like. 42 00:02:45,550 --> 00:02:47,260 So it will look like this. 43 00:02:47,260 --> 00:02:48,550 This is a.. 44 00:02:49,900 --> 00:02:52,380 It is containing whether this is terminal or not. 45 00:02:52,660 --> 00:02:56,370 So for the node A, this is known terminal. 46 00:02:57,100 --> 00:03:04,060 So this Norn terminal, since this is known, it will store false value and there will be a re. 47 00:03:06,050 --> 00:03:07,460 Offsiders, 26. 48 00:03:11,780 --> 00:03:18,980 And this will contain the pointer to the next and similarly, this will contain pointer to the next 49 00:03:18,980 --> 00:03:20,390 node and so on. 50 00:03:22,450 --> 00:03:26,080 And if there are no pointers, then this will store null value. 51 00:03:27,920 --> 00:03:28,670 Simple, right? 52 00:03:28,700 --> 00:03:31,490 If there are no pointers, then I will null value. 53 00:03:31,910 --> 00:03:40,190 And in fact, since we have this, Eddie, I don't think we need this data member. 54 00:03:41,210 --> 00:03:42,710 We don't need to store study. 55 00:03:42,860 --> 00:03:43,300 Why? 56 00:03:43,520 --> 00:03:44,690 How will I story. 57 00:03:44,870 --> 00:03:47,410 So it will correspond to the 08 index. 58 00:03:47,750 --> 00:03:51,280 Similarly, characters will correspond to index 25. 59 00:03:51,950 --> 00:03:54,740 So there is no need for this data type. 60 00:03:55,020 --> 00:03:57,140 We only need these two data types. 61 00:03:58,110 --> 00:03:58,540 Right. 62 00:04:00,250 --> 00:04:05,980 So let's do one thing, let's start implementing this, and then I will explain you step by step. 63 00:04:06,010 --> 00:04:09,820 OK, so first start implementing this private sector. 64 00:04:10,180 --> 00:04:11,740 Let's start writing the code. 65 00:04:18,519 --> 00:04:27,100 OK, so as we have decided, first of all, we need to define what is an old so class trying, or you 66 00:04:27,100 --> 00:04:28,540 can simply write a.. 67 00:04:29,320 --> 00:04:35,020 So let's simply write a note or you can write Prysner one and the same thing doesn't matter. 68 00:04:35,030 --> 00:04:40,590 Just name and let's define some data members. 69 00:04:40,610 --> 00:04:45,590 So for but as we have discussed is whether it is terminal or not. 70 00:04:45,850 --> 00:04:47,020 So is terminal. 71 00:04:49,340 --> 00:04:52,990 And second thing that we discussed is basically, uh. 72 00:04:54,990 --> 00:05:01,860 We will have a. can have at most 26 children, so I was told point to my 26 children. 73 00:05:04,140 --> 00:05:14,250 So my child, at the most I can have told the child this is very similar to the like we have implemented 74 00:05:14,250 --> 00:05:16,170 trees, we have implemented by new trees. 75 00:05:16,200 --> 00:05:17,730 This is very similar to that only. 76 00:05:19,620 --> 00:05:21,780 And let's also have a constructor. 77 00:05:23,260 --> 00:05:29,860 So in constructor, what we're going to do is so in constructor Istomin, let's set the value system 78 00:05:30,070 --> 00:05:30,860 to be false. 79 00:05:31,360 --> 00:05:38,090 So initially, no node is basically a terminal node and let's set the value for this for my child. 80 00:05:38,380 --> 00:05:41,200 So initially, I don't have any of a child. 81 00:05:41,740 --> 00:05:42,760 I have no child. 82 00:05:42,760 --> 00:05:45,190 Since I have no child, I will. 83 00:05:45,190 --> 00:05:51,850 Sternhell here point as I'm going to stonewall because currently I don't have a child. 84 00:05:53,170 --> 00:05:55,840 So child of I will be storing them. 85 00:06:01,590 --> 00:06:02,420 Simple, right? 86 00:06:04,640 --> 00:06:09,480 OK, so this is our Todd, so what do we need here? 87 00:06:10,370 --> 00:06:20,060 So I think we need two functions where two functions that we need we need a function and what this function 88 00:06:20,570 --> 00:06:21,050 will do. 89 00:06:21,200 --> 00:06:23,300 So it will contain it will take. 90 00:06:23,300 --> 00:06:26,120 Which do you want to insert inside the tray? 91 00:06:27,590 --> 00:06:27,980 Right. 92 00:06:28,220 --> 00:06:30,280 This add function will take two things. 93 00:06:31,160 --> 00:06:35,450 What is the word and in which tray you want to insert this word simple. 94 00:06:35,450 --> 00:06:35,810 Right? 95 00:06:36,080 --> 00:06:38,820 And the second function that we need will be search. 96 00:06:40,580 --> 00:06:46,340 So in search it will take which what do you want to search and then which you want to search. 97 00:06:46,340 --> 00:06:46,820 This one. 98 00:06:47,210 --> 00:06:47,840 Simple, right. 99 00:06:47,870 --> 00:06:52,190 So we need to write the definition for these two function, add and such. 100 00:06:52,430 --> 00:06:55,730 So let's first write this add function. 101 00:06:55,730 --> 00:07:00,270 We will add all the words of our dictionary in our tray. 102 00:07:00,710 --> 00:07:02,600 So first, let us do that. 103 00:07:07,220 --> 00:07:11,090 So let's create. 104 00:07:12,090 --> 00:07:12,750 I try. 105 00:07:15,700 --> 00:07:21,870 And this is our dictionary try or you can say it as rude, it's it's optional, right? 106 00:07:21,880 --> 00:07:27,520 You can you can Delimiter Dictionary, our dictionary of Trie basically try your dictionary words or 107 00:07:27,520 --> 00:07:29,030 you can simply write rude. 108 00:07:29,440 --> 00:07:30,280 It doesn't matter. 109 00:07:30,610 --> 00:07:32,260 So this is new Trenorden. 110 00:07:32,290 --> 00:07:33,380 Sorry, you know. 111 00:07:35,150 --> 00:07:42,350 OK, so the spelling of note will be Smolen or let's make it capitaland class A.. 112 00:07:48,950 --> 00:07:51,030 It's right, Naude hair and. 113 00:07:52,190 --> 00:07:53,440 Let's right not here. 114 00:07:54,910 --> 00:07:56,340 OK, so this is a.. 115 00:08:00,380 --> 00:08:09,800 So what is the impact of this line, what this line will do, it will create when node and this node 116 00:08:09,800 --> 00:08:11,340 is terminal will be false. 117 00:08:12,170 --> 00:08:14,870 So it's terminal is basically false. 118 00:08:17,040 --> 00:08:19,050 And it has an area, 119 00:08:22,110 --> 00:08:29,760 and since it has no child, so these all the pointers, all these pointers are basically starting. 120 00:08:30,610 --> 00:08:35,820 OK, so this area, this area of 26 size is basically pointing towards. 121 00:08:37,679 --> 00:08:41,289 Right, and this is my root node, so this is my root node. 122 00:08:42,299 --> 00:08:44,250 Now I have my priority. 123 00:08:44,910 --> 00:08:46,070 I have my priority. 124 00:08:46,080 --> 00:08:50,920 I need to write the function and it will take word and try. 125 00:08:51,000 --> 00:08:52,120 So this is my try. 126 00:08:52,960 --> 00:08:57,660 OK, so let's start writing the code for their function. 127 00:09:03,730 --> 00:09:07,810 So this area function will not return anything. 128 00:09:09,210 --> 00:09:17,430 This ad function will take the world, which you want to insert, and it will take that right in which 129 00:09:17,430 --> 00:09:18,340 you want to insert. 130 00:09:19,320 --> 00:09:21,600 So let's name it right here. 131 00:09:24,530 --> 00:09:28,950 Simple, so now, as we discussed, how do we insert the word? 132 00:09:28,970 --> 00:09:30,210 It's very, very simple. 133 00:09:30,230 --> 00:09:35,720 For example, if I want to insert A.R.T., so I have this root node. 134 00:09:40,620 --> 00:09:49,110 So I want to insert Aadi, what I will do, I will I trade over this string, I will try to the string, 135 00:09:49,110 --> 00:09:51,290 I will check whether it is pleasant or not. 136 00:09:51,300 --> 00:09:55,650 So this is a is basically corresponding to the zero index. 137 00:09:55,860 --> 00:09:57,960 It is pointing towards NUL, right. 138 00:09:58,190 --> 00:09:59,540 It is pointing towards Nele. 139 00:09:59,880 --> 00:10:08,640 So I will create one node and this null will basically point towards this node basically to make this 140 00:10:08,640 --> 00:10:11,580 connection right. 141 00:10:12,330 --> 00:10:16,980 And then you will come to this node and then you will come to this node. 142 00:10:25,770 --> 00:10:29,820 So what we need to do, we need to irritate or whatever, so intense. 143 00:10:32,400 --> 00:10:33,540 Verdant cites. 144 00:10:37,380 --> 00:10:44,550 And what you need to do now is you need to get rid of this word so it equals zero, i.e. less than N. 145 00:10:45,730 --> 00:10:46,720 I plumpness. 146 00:10:51,890 --> 00:10:59,320 And here you here, first of all, we need to check whether L.A., which is touring, is present or 147 00:10:59,330 --> 00:10:59,670 not. 148 00:10:59,930 --> 00:11:01,280 So let's first check. 149 00:11:01,310 --> 00:11:18,140 So if a child, child and the given character is basically void of IHI and the sensitises, uh, capital 150 00:11:18,170 --> 00:11:18,550 E.. 151 00:11:18,590 --> 00:11:23,490 So I need to subtract capitally to get the value so it corresponds to zero. 152 00:11:24,680 --> 00:11:29,660 So if this is basically null, that means the note does not exist. 153 00:11:30,290 --> 00:11:34,440 So if the note does not exist, then you need to create one node. 154 00:11:35,930 --> 00:11:37,190 So let's create the node. 155 00:11:46,070 --> 00:11:50,690 So we need to create this node so there will be new, not simply. 156 00:11:52,650 --> 00:11:59,970 And remember, after creating the world, after we have created the world, after we have created this 157 00:11:59,970 --> 00:12:04,890 node, what we need to do, we need to go to this node, we need to go to this node. 158 00:12:04,890 --> 00:12:07,290 So therefore, I will check this node. 159 00:12:07,830 --> 00:12:08,290 Right. 160 00:12:08,310 --> 00:12:09,750 We need to go to this node. 161 00:12:09,750 --> 00:12:15,870 And how I will go to this not simply means I have made actually I have made this connection with the 162 00:12:15,870 --> 00:12:17,430 help of this new node. 163 00:12:17,430 --> 00:12:18,920 Now I want to go here. 164 00:12:19,230 --> 00:12:20,250 I am standing here. 165 00:12:21,120 --> 00:12:22,500 I want to go here. 166 00:12:25,390 --> 00:12:31,840 So for doing that, what we need to do, we need to update our try and this will be tricolours. 167 00:12:34,770 --> 00:12:40,200 Right off child of the given ward. 168 00:12:42,620 --> 00:12:43,520 Minus. 169 00:12:45,560 --> 00:12:46,360 And that's it. 170 00:12:48,740 --> 00:12:55,550 So that's it, this our function book, so let me explain you from the starting. 171 00:13:02,130 --> 00:13:08,760 See, what's happening here is I want to insert this area I am passing by. 172 00:13:09,240 --> 00:13:15,780 So currently this is my train is terminal is basically false. 173 00:13:17,520 --> 00:13:23,000 And I have this, Eddie, and this ad is them. 174 00:13:25,570 --> 00:13:32,770 Ed, after the exercise, now the government is basically party, so I'm first finding out, like, 175 00:13:32,770 --> 00:13:34,510 as we have discussed, what we need to do. 176 00:13:34,510 --> 00:13:36,160 I need to I over this thing. 177 00:13:36,460 --> 00:13:39,960 So I am I doing with this thing now I am checking for correctly. 178 00:13:40,360 --> 00:13:44,100 So this is word of eye, which is character E, so E minus eight zero. 179 00:13:44,320 --> 00:13:46,870 I told you I represent index zero. 180 00:13:47,200 --> 00:13:49,770 Similarly Z present index 25. 181 00:13:50,770 --> 00:13:54,490 So I am checking whether the child which is this. 182 00:13:55,060 --> 00:13:56,700 So this is an all or not. 183 00:13:56,710 --> 00:13:57,010 Yes. 184 00:13:57,010 --> 00:14:00,550 This is null since the system then you will create a new node. 185 00:14:00,730 --> 00:14:02,350 So create a new node. 186 00:14:04,190 --> 00:14:09,940 And we are making the connection, so instead of Nele, it will store the address of this node. 187 00:14:10,220 --> 00:14:15,230 So we have made this connection and after making the connection, as you remember, we have to come 188 00:14:15,230 --> 00:14:16,250 to this node also. 189 00:14:16,520 --> 00:14:17,520 I am standing here. 190 00:14:17,720 --> 00:14:24,620 So this private label, I am standing at this node, but I want to reach additional because in the loop 191 00:14:24,650 --> 00:14:25,810 next character will be out. 192 00:14:25,880 --> 00:14:29,180 So I need to stand here and for standing here. 193 00:14:29,180 --> 00:14:30,230 What I will do, I will. 194 00:14:30,340 --> 00:14:31,650 This index will help us. 195 00:14:32,000 --> 00:14:34,070 So now I am standing here. 196 00:14:35,360 --> 00:14:41,000 Similarly for this not also new node will call the constructor and it will set the value of its terminal 197 00:14:41,000 --> 00:14:44,780 to be false and its 26 size at every store. 198 00:14:44,780 --> 00:14:47,060 All the values and all right. 199 00:14:47,060 --> 00:14:48,410 All the value I stored. 200 00:14:48,440 --> 00:14:50,870 And then now the next character is basically ah. 201 00:14:51,140 --> 00:14:54,010 So I will check whether are essential or not. 202 00:14:54,020 --> 00:14:56,000 So in this area I need to check. 203 00:14:56,000 --> 00:14:56,390 Right. 204 00:14:56,390 --> 00:14:57,380 Not in this area. 205 00:14:58,520 --> 00:14:59,480 Not in this area. 206 00:14:59,630 --> 00:15:00,560 In this area. 207 00:15:00,560 --> 00:15:01,420 I need to check. 208 00:15:01,700 --> 00:15:05,270 That's why this code is important for standing here. 209 00:15:05,900 --> 00:15:06,590 So I will check. 210 00:15:06,600 --> 00:15:07,150 Yes it is. 211 00:15:07,150 --> 00:15:10,040 And since it is null you will create a new node. 212 00:15:10,370 --> 00:15:13,610 So you will create a new node with the help of this index. 213 00:15:14,090 --> 00:15:20,750 And similarly, its terminal will be false because I will call the constructor and then it's during 214 00:15:20,750 --> 00:15:23,510 this exercise area is going to stall. 215 00:15:23,810 --> 00:15:27,470 And similarly, the are the index, I think. 216 00:15:27,740 --> 00:15:29,660 I don't remember what will be the index of. 217 00:15:29,660 --> 00:15:34,610 Ah, so you can subtract it and you will be able to find out the index and that index will store the 218 00:15:35,420 --> 00:15:36,970 will point towards this node. 219 00:15:37,430 --> 00:15:40,850 Similarly, you will be able to create one in order for E. 220 00:15:41,540 --> 00:15:42,440 So for R. 221 00:15:44,550 --> 00:15:51,570 Index, I think index is basically four or five, so if it is five, then at index five instead of starting, 222 00:15:51,570 --> 00:15:54,470 then I will store the address to this node. 223 00:15:54,840 --> 00:16:01,230 And finally, the last thing that we need to do is basically the last character is basically our terminal 224 00:16:01,230 --> 00:16:01,880 character. 225 00:16:02,190 --> 00:16:04,430 So we need to highlight this node. 226 00:16:05,220 --> 00:16:11,300 We need to highlight this node and for highlighting this node we have a variable is terminal. 227 00:16:11,520 --> 00:16:15,600 So initially that is terminal for this node is basically false. 228 00:16:15,990 --> 00:16:17,360 We need to make through. 229 00:16:17,970 --> 00:16:24,430 So after reaching after coming out of the after coming out of the vial, after coming out of this for 230 00:16:24,450 --> 00:16:25,770 loop, I am standing here. 231 00:16:26,370 --> 00:16:27,340 I am standing here. 232 00:16:27,360 --> 00:16:32,940 So what I need to do instead of false, I need to make it true so that I can highlight that this is 233 00:16:32,940 --> 00:16:34,090 a terminal node. 234 00:16:34,110 --> 00:16:35,570 This is a terminal character. 235 00:16:36,690 --> 00:16:38,630 So let's do the highlighting part. 236 00:16:39,120 --> 00:16:43,970 So in highlighting part, what we need to do, we need to set the value. 237 00:16:44,490 --> 00:16:46,890 So try arrow child. 238 00:16:49,280 --> 00:16:52,100 Sorry, Triguero Estopinal. 239 00:16:55,070 --> 00:16:56,890 Will be true and that. 240 00:16:59,830 --> 00:17:00,620 And that's it. 241 00:17:00,850 --> 00:17:09,160 So this air function will work, so that's it, guys, our air function will work properly and how you 242 00:17:09,160 --> 00:17:16,180 will call the air function, it's very simple since we need to insert all the words in the dictionary. 243 00:17:16,450 --> 00:17:18,700 So I will trade over the dictionary. 244 00:17:22,920 --> 00:17:24,750 Dictionary says. 245 00:17:29,690 --> 00:17:37,640 And for each word, for each word, what we need to do, we need to call this our function, so add 246 00:17:38,480 --> 00:17:47,030 I get word of the dictionary and in which try and destroy root, even if this name is confusing you, 247 00:17:47,030 --> 00:17:48,500 you can name it as a dictionary. 248 00:17:48,510 --> 00:17:49,840 Also in dictionary try. 249 00:17:50,090 --> 00:17:52,940 I am I am inserting a yet word. 250 00:17:53,990 --> 00:17:54,740 So that's it. 251 00:17:55,520 --> 00:17:57,310 So now your tribe is ready. 252 00:17:58,220 --> 00:17:59,550 So our tribe is ready. 253 00:17:59,570 --> 00:18:03,380 So how the tribe will look like again. 254 00:18:03,390 --> 00:18:13,040 So this is the start node or basically the root node and then we will have a we will have ah we will 255 00:18:13,040 --> 00:18:16,840 have East and Eastern Time in L.A. So this will be highlighted. 256 00:18:17,030 --> 00:18:26,060 Similarly, I have said and this will this will be highlighted and similarly I have D then I have O 257 00:18:26,660 --> 00:18:28,190 and all will be highlighted. 258 00:18:28,370 --> 00:18:34,100 Similarly I have B here and this will be highlighted and similarly rest of the words. 259 00:18:34,100 --> 00:18:36,170 So I will try is basically right now. 260 00:18:36,740 --> 00:18:39,560 So I would add function is done now. 261 00:18:39,560 --> 00:18:42,380 All we need to do, we need to write the code for search function. 262 00:18:42,980 --> 00:18:46,820 So in next we do, we are going to write the code for the search function. 263 00:18:47,060 --> 00:18:52,440 We will give one word and we will check whether the word is present in this trial or not. 264 00:18:52,630 --> 00:18:52,990 Right. 265 00:18:53,240 --> 00:18:55,120 So this is it from this device. 266 00:18:55,130 --> 00:18:56,610 I will see you in the next one. 267 00:18:56,900 --> 00:18:57,440 Thank you.