1 00:00:02,070 --> 00:00:02,790 Hi, everyone. 2 00:00:02,820 --> 00:00:07,160 So in this video, we are going to learn a new tactic to keep. 3 00:00:07,920 --> 00:00:15,000 So if you remember in the last video we discussed that balanced body was the best option for implementing 4 00:00:15,240 --> 00:00:22,560 ridiculous because the time complexity was in Logan and all other leaders were giving us and skirt time 5 00:00:22,560 --> 00:00:23,250 complexity. 6 00:00:23,970 --> 00:00:26,830 But balanced bisdee has some issues. 7 00:00:26,850 --> 00:00:29,090 So there are some problems with Belen's reused. 8 00:00:29,670 --> 00:00:32,729 So the first problem is basically the balancing factor. 9 00:00:33,880 --> 00:00:38,290 So what we have to do, so we have to write code in such a way that our trees are always balanced. 10 00:00:38,620 --> 00:00:41,340 So this is overhead for us. 11 00:00:41,770 --> 00:00:47,050 Now, the second problem with balanced Vista is basically the storing is very complicated. 12 00:00:49,730 --> 00:00:50,930 So in balance, Misty. 13 00:00:52,400 --> 00:00:55,980 The way you insert the elements, so it is going to be very, very complicated. 14 00:00:56,330 --> 00:01:03,620 So instead of using balanced for implementing vertical, so we have designed a new researcher called 15 00:01:03,620 --> 00:01:06,960 Heap and we will use Hipp for implementing Veridical. 16 00:01:07,790 --> 00:01:10,990 So let us now try to understand, what is he? 17 00:01:12,530 --> 00:01:17,720 First of all, we know he is a researcher, so there are some he properties. 18 00:01:18,200 --> 00:01:22,460 And what are those properties that make it suitable for implementing vertical? 19 00:01:23,030 --> 00:01:26,660 So the first he properties actually it is a complete binary tree. 20 00:01:29,290 --> 00:01:37,690 So he is I think it is just a complete by nutri, in short, we rated CBT complete by CBT, not a second 21 00:01:37,690 --> 00:01:43,880 property is basically it has something called border property, which we will study in some time. 22 00:01:45,070 --> 00:01:48,890 So because of these two properties, he is suitable for implementing VERIDICAL. 23 00:01:50,440 --> 00:01:57,740 So first, now let us discuss what is a complete by Nuti CBT so we all know what is a binary tree by 24 00:01:57,880 --> 00:02:04,300 trees, a tree which will have maksym to jalon zero one or two so maksym a. can have two general in 25 00:02:04,300 --> 00:02:04,990 binary tree. 26 00:02:07,310 --> 00:02:14,990 So let us discuss what is complete by Niddrie so incomplete Minuti, it has only one property sorry 27 00:02:14,990 --> 00:02:18,470 to property, so first properties will be first properties. 28 00:02:18,470 --> 00:02:21,490 All levels are completely full except the last level. 29 00:02:22,670 --> 00:02:26,120 So all levels are completely full except last one. 30 00:02:30,560 --> 00:02:32,600 So consider one example, suppose. 31 00:02:35,730 --> 00:02:38,520 This is a binding treaty, so it's this binary CBT. 32 00:02:39,160 --> 00:02:43,640 Now, this property, so all levels are completely filled except the last level. 33 00:02:43,950 --> 00:02:46,840 So remove the last level now at all levels are filled. 34 00:02:47,160 --> 00:02:48,630 So, yes, it is a CBT. 35 00:02:51,440 --> 00:02:52,880 Now, consider this example. 36 00:02:55,240 --> 00:02:58,130 So is this by nutri acerbity or not? 37 00:02:58,360 --> 00:02:59,350 So if we'll see. 38 00:03:01,110 --> 00:03:06,060 We can't ignore the last level because we can accept the last level, all levels should be completely 39 00:03:06,060 --> 00:03:09,030 full, but this level is not full, you can see. 40 00:03:09,210 --> 00:03:12,720 So this node has a left children, but this node doesn't have children. 41 00:03:12,960 --> 00:03:15,980 So this node, this level is not completely filled. 42 00:03:16,170 --> 00:03:18,240 So that's why this is not a subsidy. 43 00:03:19,820 --> 00:03:27,050 Now, the second property of Sebti is basically we have to fill the levels from left to right, so from 44 00:03:27,050 --> 00:03:28,060 left to right. 45 00:03:28,100 --> 00:03:29,630 So what is the meaning of Left-to-right? 46 00:03:29,870 --> 00:03:33,360 So Nords will be inserted from left to right. 47 00:03:33,890 --> 00:03:35,060 So, for example. 48 00:03:39,160 --> 00:03:40,420 So this is a celebrity. 49 00:03:42,660 --> 00:03:43,470 Perfectly fine. 50 00:03:45,110 --> 00:03:46,400 This is also a celebrity. 51 00:03:47,650 --> 00:03:49,390 Now, is this a acerbity? 52 00:03:50,630 --> 00:03:53,210 So is this a CBD of going by this definition? 53 00:03:54,470 --> 00:03:58,370 You consider this definition to all levels are completely failed at this level is completely. 54 00:03:58,740 --> 00:04:02,300 This level is completely full, but this level is not completely full. 55 00:04:02,300 --> 00:04:03,770 But that is an exception. 56 00:04:04,110 --> 00:04:10,070 So according to this definition, they should be Sebti, but we have to also apply this definition. 57 00:04:10,460 --> 00:04:13,490 So the nodes have to be filled from left to right. 58 00:04:13,820 --> 00:04:15,570 So the meaning is basically. 59 00:04:15,590 --> 00:04:22,280 So this node has a left node, but this node doesn't have a right node, so it should be filled from 60 00:04:22,280 --> 00:04:23,030 left to right. 61 00:04:23,030 --> 00:04:24,380 So this node is missing. 62 00:04:24,680 --> 00:04:26,720 So that's why this is not a CBT. 63 00:04:28,100 --> 00:04:29,260 This is not a CBD. 64 00:04:29,430 --> 00:04:30,480 I'm repeating myself. 65 00:04:31,910 --> 00:04:33,470 This is a city, correct? 66 00:04:34,410 --> 00:04:39,810 Then if you want to insert one more note, you have to insert at the left, because we have to insert 67 00:04:39,810 --> 00:04:40,820 Nordström from left, right. 68 00:04:41,040 --> 00:04:42,300 So this is also a celebrity. 69 00:04:42,720 --> 00:04:49,050 But as soon as you insert this node, if you will insert this note, then it is not a Sebti, right? 70 00:04:49,150 --> 00:04:51,860 This is not a celebrity because you missed this node. 71 00:04:52,560 --> 00:04:53,790 You are missing this node. 72 00:04:54,060 --> 00:04:56,140 We have to insert the node from left to right. 73 00:04:56,730 --> 00:04:58,090 So this is not a celebrity. 74 00:04:59,130 --> 00:05:00,780 Now, let us consider some example. 75 00:05:01,780 --> 00:05:06,430 And now let's try to decide what is a subsidy or which is not CBT. 76 00:05:09,600 --> 00:05:10,470 It is a celebrity. 77 00:05:11,850 --> 00:05:12,840 This is Sebti. 78 00:05:13,950 --> 00:05:20,390 It is also Sabeti again, this is a by Nutri again, this is a computer by Nutri. 79 00:05:20,970 --> 00:05:22,590 This is also a computer by Nutri. 80 00:05:23,620 --> 00:05:25,270 This is also committed by Nutri. 81 00:05:26,550 --> 00:05:28,110 This is also accompanied by Nutri. 82 00:05:29,280 --> 00:05:31,020 This is also committed by the military. 83 00:05:32,040 --> 00:05:33,550 This is also committed by Niddrie. 84 00:05:34,350 --> 00:05:35,970 This is also committed by Nutri. 85 00:05:38,030 --> 00:05:39,590 Now, this is not a celebrity. 86 00:05:41,310 --> 00:05:46,770 This is not a celebrity, so going by the first definition, all levels are completely full except the 87 00:05:46,770 --> 00:05:47,390 last level. 88 00:05:47,520 --> 00:05:48,560 So that's not an issue. 89 00:05:48,720 --> 00:05:51,930 But going by the second definition, you missed the left. 90 00:05:51,950 --> 00:05:55,010 And so I have to fill from left to right. 91 00:05:55,020 --> 00:05:56,640 I have to fill from left, right. 92 00:05:56,820 --> 00:05:58,910 So that's why this note is not there. 93 00:05:59,160 --> 00:06:01,070 So this is not a CBD anymore. 94 00:06:02,830 --> 00:06:04,370 Now, let's take one more example. 95 00:06:05,110 --> 00:06:08,160 Now let's see how we can insert or delete from a CBT. 96 00:06:09,540 --> 00:06:10,260 From a complete. 97 00:06:11,330 --> 00:06:13,240 So this is my complete Pinetree. 98 00:06:13,290 --> 00:06:14,620 Let's take one example. 99 00:06:14,630 --> 00:06:14,910 So. 100 00:06:18,970 --> 00:06:23,320 Now, this is a complete by nutri, all levels are completely full except the last level. 101 00:06:24,490 --> 00:06:30,400 And we are feeling from left to right, so one more thing, when I'm saying all levels are completely 102 00:06:30,400 --> 00:06:31,690 full except the last level. 103 00:06:33,350 --> 00:06:35,360 So that means this is also somebody. 104 00:06:36,330 --> 00:06:38,820 If all levels are filled, that is also CBD. 105 00:06:39,180 --> 00:06:41,560 So this is a CBD, all levels are filled. 106 00:06:41,610 --> 00:06:43,020 Last year also fell. 107 00:06:47,510 --> 00:06:52,340 Now, consider this example, so this is a celebrity because all the levels are filled and we are feeling 108 00:06:52,340 --> 00:06:53,180 from left to right. 109 00:06:53,540 --> 00:06:54,510 So this is a celebrity. 110 00:06:55,370 --> 00:06:57,140 Now I want to insert some nodes. 111 00:06:57,890 --> 00:07:04,290 So, for example, if I want to insert Ben so Ben can be inserted so that this really means somebody. 112 00:07:04,310 --> 00:07:07,220 So the only position available to me is basically this one. 113 00:07:08,490 --> 00:07:14,910 So this is the only position available for inserting then, so that the tree remains CBT complete by 114 00:07:14,910 --> 00:07:15,260 Nutri. 115 00:07:16,260 --> 00:07:17,570 Now I want to Insurgentes. 116 00:07:17,580 --> 00:07:19,940 So the only option available to me is this one. 117 00:07:20,640 --> 00:07:22,730 Now I want to insert, let's say, 25. 118 00:07:23,070 --> 00:07:25,770 So only option available to me is this one. 119 00:07:26,140 --> 00:07:27,780 I want to insert TOTY. 120 00:07:28,050 --> 00:07:31,350 So the only position available to me is this one left of five. 121 00:07:32,310 --> 00:07:34,710 OK, so we are inserting from left to right. 122 00:07:35,950 --> 00:07:42,490 So that mystery remains a complete by Nutri, and I suppose I want to delete some notes. 123 00:07:43,870 --> 00:07:51,580 I want to delete some notes, so can I delete six, so if it will delete node six, this tree is not 124 00:07:51,580 --> 00:07:54,600 Sabitha anymore because this level is not completely filled. 125 00:07:55,090 --> 00:07:56,430 So you cannot delete six. 126 00:07:57,440 --> 00:08:02,960 We cannot delay tax, so can we delay it for no, we cannot lead for it because if we will delay it 127 00:08:02,960 --> 00:08:03,290 for. 128 00:08:04,390 --> 00:08:07,960 OK, so instead of let's make it then, so can we delete them? 129 00:08:08,620 --> 00:08:13,650 No, we cannot let them, because then then this level is not completely full. 130 00:08:15,400 --> 00:08:23,530 So consider this liberty, so this is a complete binary three, four, five and six, so this is complete 131 00:08:23,530 --> 00:08:24,040 by Nutri. 132 00:08:25,210 --> 00:08:27,430 Now tell me which in I can delete. 133 00:08:28,590 --> 00:08:36,960 So that mystery remains a computer by nutri, so I can only delete the last node, which is six, so 134 00:08:36,960 --> 00:08:42,900 deleting means you can only delete the last element of the last level. 135 00:08:43,169 --> 00:08:45,360 You can delete the last element of the last level. 136 00:08:45,360 --> 00:08:46,880 So we can only delete six. 137 00:08:48,090 --> 00:08:51,000 Now, after deleting six, we can only delete five. 138 00:08:51,300 --> 00:08:53,880 So that distri remains a complete binary. 139 00:08:54,150 --> 00:08:58,860 After deleting five, I can delete four after four, for I can only military. 140 00:08:59,040 --> 00:09:01,560 Then I can only do a little and then I can delete one. 141 00:09:02,710 --> 00:09:06,460 So I hope you understood what is the meaning, how we can insert and how we can delete. 142 00:09:07,460 --> 00:09:13,040 So we have to start from left to right and we can delete from right to left. 143 00:09:14,130 --> 00:09:21,600 Simple from the last level, so we will discuss more about complete minidress in our next video, I 144 00:09:21,600 --> 00:09:23,040 will turn the next one, but by.