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.

