1
00:00:02,290 --> 00:00:03,040
Hi, everyone.

2
00:00:03,070 --> 00:00:09,250
So in this lesson we will see completed by Nutri, we will see you complete minor details and we will

3
00:00:09,250 --> 00:00:10,720
also see its implementation.

4
00:00:11,560 --> 00:00:17,890
So if you remember in the last lesson we discussed, that balance best is the best data structure that

5
00:00:17,890 --> 00:00:20,050
we have to implement the priority queue.

6
00:00:20,710 --> 00:00:24,010
But there were two problems associated with the balance bisdee.

7
00:00:24,280 --> 00:00:29,560
So that's why we discussed and designed a new data structure called Help to implement our priorities.

8
00:00:30,640 --> 00:00:33,320
Now let's discuss those two problems again.

9
00:00:33,640 --> 00:00:39,030
So first of all, I was basically so we have to always ensure that our best is balanced and that is

10
00:00:39,190 --> 00:00:39,670
overhead.

11
00:00:40,180 --> 00:00:44,920
And the second problem was basically of storing BSD is a very complex thing.

12
00:00:46,580 --> 00:00:49,280
Because there will be a lot of a lot of binders to handle.

13
00:00:50,330 --> 00:00:56,390
And now let's try to understand how he will help us to solve these two properties, these two problems

14
00:00:56,390 --> 00:00:57,830
of Balestra based.

15
00:00:59,650 --> 00:01:01,570
So firstly, just try to find out.

16
00:01:02,760 --> 00:01:05,099
What is the height of a complete by nutri?

17
00:01:07,000 --> 00:01:11,980
So what will be the height of a bid by Nutri so for finding out the height of a complete by Niddrie?

18
00:01:12,920 --> 00:01:18,440
We have to find out Tuvalu's and basically it will involve a lot of mathematical calculation.

19
00:01:19,220 --> 00:01:21,880
So first, let us try to find out these two values.

20
00:01:22,220 --> 00:01:28,180
So what is the minimum number of nodes in a complete binary tree of high tech?

21
00:01:30,170 --> 00:01:37,150
And the second thing that we have to find out is the maximum number of nodes in a computer binary of

22
00:01:37,160 --> 00:01:37,840
eight each.

23
00:01:38,210 --> 00:01:40,550
So we have to find out these two values.

24
00:01:41,530 --> 00:01:44,470
Before finding out the height of a computer by Nutri.

25
00:01:46,460 --> 00:01:48,570
So let's find out these two values.

26
00:01:49,340 --> 00:01:55,810
So first, let us try to find out the number of nodes in our computer by Niddrie of each.

27
00:01:56,480 --> 00:01:58,160
So let's do some match.

28
00:02:00,130 --> 00:02:07,150
So I want to find out the minimum number of nodes, so let's take an example, so let's say the height

29
00:02:07,150 --> 00:02:08,740
of complete binary tree is for.

30
00:02:10,060 --> 00:02:11,410
Now, let's go, secretary.

31
00:02:12,610 --> 00:02:15,840
So this is accompanied by Niddrie, this is a complete by Nedry.

32
00:02:15,880 --> 00:02:17,300
This is a computer by Nutri.

33
00:02:17,680 --> 00:02:19,040
This is a computer by Niddrie.

34
00:02:19,420 --> 00:02:20,630
This is a complete Binetti.

35
00:02:20,650 --> 00:02:21,520
So this is.

36
00:02:22,480 --> 00:02:31,110
CBT with Haiti now, what do I want I want to I want a CBT of aid for so basically I will add only one

37
00:02:31,120 --> 00:02:31,330
or.

38
00:02:32,350 --> 00:02:38,050
I will add only one or not, this is a complete binary of eight four and the notes are minimum.

39
00:02:38,810 --> 00:02:44,770
Obviously I can add many nodes, I can add nodes here, but we have to find out the minimum number of

40
00:02:44,770 --> 00:02:45,100
nodes.

41
00:02:45,310 --> 00:02:47,740
So that's why I will add only one node.

42
00:02:48,040 --> 00:02:50,590
So this is actually a complete by nutri.

43
00:02:50,590 --> 00:02:53,110
This is a valid, complete binary with hateful.

44
00:02:54,120 --> 00:02:56,500
Now, let us calculate how many number of nodes are there.

45
00:02:56,910 --> 00:03:02,990
So at this level, one node, so I can say to the power zero nodes at this level, two to the power

46
00:03:03,140 --> 00:03:06,270
nodes at this level, so two to the power to nodes.

47
00:03:06,270 --> 00:03:08,940
And this is one also plus one.

48
00:03:10,350 --> 00:03:12,510
Now, how many nodes are there, so if you will add.

49
00:03:15,020 --> 00:03:16,430
Go to the Power-One, then.

50
00:03:18,170 --> 00:03:18,620
So.

51
00:03:19,860 --> 00:03:25,170
The value of height is actually four, so this value is actually higher to minus two.

52
00:03:25,980 --> 00:03:27,330
So for minus two is to.

53
00:03:28,380 --> 00:03:34,410
So what will happen, if you will add all these items, so our last item will be true to the power height

54
00:03:34,410 --> 00:03:36,510
minus two and this one.

55
00:03:37,110 --> 00:03:37,680
Plus one.

56
00:03:38,820 --> 00:03:41,010
So these are the minimum number of Nords.

57
00:03:42,200 --> 00:03:44,450
In a complete by of High-Tech.

58
00:03:46,250 --> 00:03:53,480
Now, this storm is actually a dramatic progression, so if you remember the formula, so the formula

59
00:03:53,480 --> 00:03:58,080
is very simple after the power and minus one divided by our minus one.

60
00:03:58,430 --> 00:04:00,640
So it is easy to do the power to zero.

61
00:04:01,160 --> 00:04:02,450
So do the power zero.

62
00:04:02,450 --> 00:04:05,300
Then add is to what is the total number of times.

63
00:04:05,300 --> 00:04:14,150
So the total number of items is each minus one to each minus one then minus one and ah is to minus one.

64
00:04:14,720 --> 00:04:18,940
So this is actually due to the power minus one, minus one.

65
00:04:20,180 --> 00:04:21,950
And then we have plus one here.

66
00:04:22,460 --> 00:04:23,720
So I will write plus one.

67
00:04:23,990 --> 00:04:26,870
So plus and minus one will cancel out each other.

68
00:04:27,170 --> 00:04:34,280
So I know the minimum number of nodes, we know number of nodes in a complete binary tree of each is

69
00:04:34,280 --> 00:04:36,470
actually due to the power each minus one.

70
00:04:40,610 --> 00:04:44,430
Now, we also have to find out the maximum number of nodes.

71
00:04:44,840 --> 00:04:48,260
So now let's try to find out the maximum number of nodes.

72
00:04:49,810 --> 00:04:50,470
So let us.

73
00:04:51,710 --> 00:04:53,570
So let's say my height is.

74
00:04:54,870 --> 00:05:01,910
For so whatever the maximum number of rules, so this is a complete by of how to complete by of five

75
00:05:01,930 --> 00:05:02,370
three.

76
00:05:04,620 --> 00:05:10,710
Now, this is a complete by Nutri, this is a valid complete by any real fight for, but we have to

77
00:05:10,710 --> 00:05:12,490
find out the maximum number of nodes.

78
00:05:12,810 --> 00:05:15,870
So what I will do, I will completely fill this level.

79
00:05:20,300 --> 00:05:25,280
And now let us do the calculations of how many number of nodes that isn't at this level bruited about

80
00:05:25,290 --> 00:05:27,200
zero to the Power-One.

81
00:05:27,200 --> 00:05:30,560
So this is due to the power to and this is due to the power three.

82
00:05:31,370 --> 00:05:32,630
So what is three?

83
00:05:32,630 --> 00:05:35,290
Three is actually height minus one.

84
00:05:35,300 --> 00:05:37,790
So it is four for minus, honestly.

85
00:05:38,770 --> 00:05:46,430
Now, let us add all these nodes, so the maximum number of nodes is actually the addition of all this.

86
00:05:46,440 --> 00:05:50,890
So to the biocidal, then two to the power, one, then to the power two.

87
00:05:51,100 --> 00:05:52,210
So it will go on.

88
00:05:52,210 --> 00:05:55,690
And the last is true to the power each minus one.

89
00:05:56,260 --> 00:05:58,600
Now, again, this is a dramatic progression.

90
00:05:59,530 --> 00:06:00,790
The formula is very simple.

91
00:06:01,030 --> 00:06:04,190
Out of the power in minus one, divided by R minus one.

92
00:06:04,540 --> 00:06:07,920
So it is true that the power of zero R is two.

93
00:06:08,140 --> 00:06:10,220
So how many total, how many times are there?

94
00:06:10,240 --> 00:06:11,760
So there are total items.

95
00:06:11,770 --> 00:06:16,000
So each minus one divided by two minus one.

96
00:06:16,570 --> 00:06:19,810
So this is nothing but two to the power each minus one.

97
00:06:20,870 --> 00:06:27,920
So the maximum number of nodes makes a number of nodes in a complete binary of height, it is actually

98
00:06:28,190 --> 00:06:29,960
true to the power each minus one.

99
00:06:33,980 --> 00:06:37,970
So now we know the number of nodes and we know the number of nodes.

100
00:06:39,340 --> 00:06:42,670
So these are the minimum number of nodes and these are the maximum number of nodes.

101
00:06:48,280 --> 00:06:55,450
So minimum number of nodes is actually due to the power each minus one and the maximum number of nodes

102
00:06:55,450 --> 00:07:00,370
is actually to the power each minus one in a complete binary tree.

103
00:07:01,500 --> 00:07:04,470
Of height, edge of height, edge.

104
00:07:06,720 --> 00:07:13,200
So basically, can I say that my and and is actually a number of not so total number of nodes in the

105
00:07:13,200 --> 00:07:19,860
computer by Nutri will be less than or equal to the power minus one and will be greater than or equal

106
00:07:19,860 --> 00:07:22,260
to two to the power each minus one.

107
00:07:24,990 --> 00:07:26,730
So is this statement valid?

108
00:07:28,040 --> 00:07:32,620
So obviously, the statement is valid because any if it were the number of nodes in a binary tree,

109
00:07:32,930 --> 00:07:37,170
so these are the maximum number of nodes possible and these are the number of nodes possible.

110
00:07:37,400 --> 00:07:39,240
So obviously, this relation is valid.

111
00:07:40,040 --> 00:07:41,840
Now, let us try to solve the solution.

112
00:07:41,840 --> 00:07:44,660
So let us try to solve this one first.

113
00:07:45,110 --> 00:07:50,340
So the solution is to reduce our H minus one is less than close to one.

114
00:07:51,020 --> 00:07:52,940
Now apply log on both sides.

115
00:07:52,940 --> 00:07:55,250
Take log with the base to on both the sides.

116
00:07:55,850 --> 00:07:59,810
So this is log to then we have to do the power each minus one.

117
00:08:00,770 --> 00:08:09,740
Less than three to log two, and now there is a formula of log that log into the power B, so B will

118
00:08:09,740 --> 00:08:10,520
come out, friend.

119
00:08:10,550 --> 00:08:11,960
So this will become blog.

120
00:08:12,680 --> 00:08:13,580
So what will happen?

121
00:08:13,760 --> 00:08:15,890
So this H.M.S. will come out, friend.

122
00:08:18,440 --> 00:08:20,750
So this will be H minus one.

123
00:08:23,310 --> 00:08:31,790
Then log to Whitby's to is less than articles to log in Bisto, and this really is actually one.

124
00:08:32,570 --> 00:08:33,150
This is one.

125
00:08:34,289 --> 00:08:35,610
So what is my formula?

126
00:08:35,640 --> 00:08:44,820
So H minus one is less than what it costs to log and Bisto or I can say H is less likely to log and

127
00:08:44,820 --> 00:08:45,450
B to.

128
00:08:48,090 --> 00:08:50,490
And Blessin sorry I forgot this one.

129
00:08:50,850 --> 00:08:52,140
So this will be plus one.

130
00:08:54,820 --> 00:08:56,800
Now, let us try to solve the solution.

131
00:08:58,270 --> 00:09:02,830
So this is and is literally close to true to the power edge minocin.

132
00:09:03,870 --> 00:09:09,330
So take one this side, so this will be end plus one last night, it close to two to the power edge

133
00:09:10,230 --> 00:09:12,420
and now the log on both the sides.

134
00:09:13,260 --> 00:09:16,650
So log and plus one base to.

135
00:09:17,590 --> 00:09:22,700
Is less than our to log to the power edge Bisto.

136
00:09:23,530 --> 00:09:25,300
So this is it and this is an.

137
00:09:26,670 --> 00:09:30,950
Now, again, it will come out front, so this is Hetch.

138
00:09:32,040 --> 00:09:40,110
Log to be to and this is log off and plus one Bisto, so this will lose again when.

139
00:09:41,320 --> 00:09:45,730
This is one so each is good and our goal is to.

140
00:09:46,950 --> 00:09:49,200
Lagarto and plus one.

141
00:09:50,360 --> 00:09:51,440
And now it will do.

142
00:09:53,690 --> 00:09:57,980
So this is my second relation, and this is this is first.

143
00:09:58,340 --> 00:09:59,380
This is second conclusion.

144
00:09:59,660 --> 00:10:01,340
Now combine these two illusion.

145
00:10:01,850 --> 00:10:02,660
What will I get?

146
00:10:03,950 --> 00:10:04,880
So each.

147
00:10:05,960 --> 00:10:08,000
Is greater than articles to.

148
00:10:10,050 --> 00:10:19,250
Log to Anderson and each is less than ideal to this one, so this is log 210 plus one.

149
00:10:19,950 --> 00:10:22,250
So this is my computer, Luciane.

150
00:10:23,710 --> 00:10:31,030
Now, in terms of begal, in terms of time, complexity, so each is less than nightclothes do, so

151
00:10:31,030 --> 00:10:34,290
in terms of time, complexity, we can avoid this plus one.

152
00:10:34,660 --> 00:10:36,280
So this will be big of.

153
00:10:37,530 --> 00:10:45,000
Log and similarly, in terms of time, complexity, we can avoid this lesson, so it is basically denied

154
00:10:45,070 --> 00:10:45,510
close to.

155
00:10:46,730 --> 00:10:47,510
Lock and.

156
00:10:48,610 --> 00:10:53,650
Now, see, Edge is less than ideal slogan, it is good slogan.

157
00:10:53,680 --> 00:10:55,930
So that means it is actually Logan.

158
00:11:00,190 --> 00:11:06,650
You analyze this relationship, so each is less than a slogan, which is a good slogan.

159
00:11:06,670 --> 00:11:10,120
So this implies that height is always log-in.

160
00:11:11,050 --> 00:11:17,470
So in complete binary tree, my height is always log of N.

161
00:11:19,420 --> 00:11:26,230
My height is always logoff and you can consider best case, worst case, basically, any case, average

162
00:11:26,230 --> 00:11:34,000
based versus my height in a complete binary tree will always be logged, often without doing anything.

163
00:11:35,170 --> 00:11:36,100
Now, if you will see.

164
00:11:38,070 --> 00:11:42,540
My height in a complete binary tree is always log in.

165
00:11:44,130 --> 00:11:46,860
And we are not doing anything to maintain our hate.

166
00:11:48,290 --> 00:11:54,350
So in Vélez Bisdee, we have to do a lot of calculation so that our height remains log-in, so that

167
00:11:54,350 --> 00:12:00,710
our body remains balanced, so that our height remains log-in but incomplete by nutri height is always

168
00:12:00,710 --> 00:12:02,710
Logan without us doing anything.

169
00:12:03,960 --> 00:12:06,270
So this solves our first problem.

170
00:12:07,450 --> 00:12:12,740
Now, the second problem, so the second problem was storing BSG is really, really difficult.

171
00:12:12,760 --> 00:12:16,700
It is very complicated because there will be a lot of lot of points to deal with.

172
00:12:17,200 --> 00:12:19,890
Now, let's see how he will help us.

173
00:12:21,000 --> 00:12:23,850
To solve this second problem associated with violence.

174
00:12:24,600 --> 00:12:27,140
So let's discuss how we will store our help.

175
00:12:27,990 --> 00:12:34,740
So no balancing required since the height is always Logan, we will not do anything and I will always

176
00:12:34,740 --> 00:12:35,160
be Logan.

177
00:12:35,180 --> 00:12:37,200
So no balancing required.

178
00:12:39,160 --> 00:12:43,780
And now let's discuss how we will store our complete by Nutri.

179
00:12:48,100 --> 00:12:50,950
So we know that saving bisdee.

180
00:12:53,250 --> 00:12:55,170
Is actually a very complex process.

181
00:12:56,540 --> 00:13:02,490
Saving Beiste is a very complex process, so let us discuss how we will store complete by Niddrie.

182
00:13:04,130 --> 00:13:05,900
So this is my computer by Niddrie.

183
00:13:11,170 --> 00:13:17,590
Now, I want to insert an element, let's say I want to insert element to it, so the only option.

184
00:13:17,590 --> 00:13:18,700
The only position.

185
00:13:20,070 --> 00:13:26,070
Available to me is this one I can only insert it here, I cannot insert it anywhere else, I cannot

186
00:13:26,070 --> 00:13:32,010
insert here, I cannot insert here, and similarly, I cannot insert any at any of the position.

187
00:13:32,220 --> 00:13:36,780
So this is the only position available for me to insertion is very easy.

188
00:13:37,140 --> 00:13:38,840
Now, let's say you want to insert nine.

189
00:13:39,300 --> 00:13:42,090
So the only option available for inserting nine is this one.

190
00:13:42,090 --> 00:13:43,710
You can only insert nine here.

191
00:13:45,510 --> 00:13:51,990
So basically how we will be able to find out at which position I will be able to insert so you have

192
00:13:51,990 --> 00:13:57,270
to rule on a traversal, so will tell us this level, then you will try this level, then you will traverse

193
00:13:57,330 --> 00:13:59,760
this level, and then you will traverse this level.

194
00:13:59,760 --> 00:14:06,060
And as soon as you find an empty position, as soon as you find out a position at which there is no

195
00:14:06,060 --> 00:14:10,000
node, then at that position you can insert the element.

196
00:14:10,030 --> 00:14:15,930
For example, if you want doing certain, then you will do traversal to find out an empty position and

197
00:14:15,930 --> 00:14:18,570
then you will be able to store that value there.

198
00:14:19,860 --> 00:14:27,990
So this is very, very bad because for finding out an empty position, so for finding out an empty position,

199
00:14:27,990 --> 00:14:35,370
we have to do level order traversal in complete binary tree and level traversal will take big off End-Time.

200
00:14:35,580 --> 00:14:40,740
So far, just finding the empty position, we are going to go find them and that is very, very bad.

201
00:14:40,980 --> 00:14:43,610
So that means I have to do something about it.

202
00:14:44,040 --> 00:14:48,980
I cannot do Learoyd just to find out the empty position at which I have to insert my node.

203
00:14:50,160 --> 00:14:53,400
So the easy way and the best way to store.

204
00:14:54,910 --> 00:14:57,910
Complete by Nutri is actually using an eddy.

205
00:14:59,230 --> 00:15:05,440
So I'm repeating myself, the easiest way to store a complete binary tree is basically with the help

206
00:15:05,440 --> 00:15:05,920
of NATO.

207
00:15:05,980 --> 00:15:06,960
Now let's see how.

208
00:15:07,390 --> 00:15:10,300
So first, let us consider a complete binary tree.

209
00:15:14,080 --> 00:15:15,930
So this is a complete by nutri.

210
00:15:16,330 --> 00:15:17,160
Now what we do.

211
00:15:17,500 --> 00:15:18,450
We will take a..

212
00:15:22,600 --> 00:15:23,820
And we will fill this area.

213
00:15:24,160 --> 00:15:27,340
So how we will fill this area, we will just do the Illinois traversal.

214
00:15:27,580 --> 00:15:33,070
So just to the level that I was a landfill, Daryn, so it will be one, then two, then three, then

215
00:15:33,070 --> 00:15:35,530
four, five, six and seven.

216
00:15:38,580 --> 00:15:44,970
And these are indexes zero, one, two, three, four, five and six, so I will store my complete by

217
00:15:44,970 --> 00:15:48,510
Niddrie inside and very simple.

218
00:15:49,620 --> 00:15:52,020
Now let's see suppose.

219
00:15:53,290 --> 00:16:00,520
My parent is two and four and five, so there is two sorto and jailer's, basically four.

220
00:16:01,600 --> 00:16:06,350
For the left child and five is the left child, so to speak, and the next one.

221
00:16:06,880 --> 00:16:14,170
So next one, it left child is present and the next three years, right child is present at the next

222
00:16:14,170 --> 00:16:14,440
food.

223
00:16:15,550 --> 00:16:17,100
Let's consider one more element.

224
00:16:17,530 --> 00:16:19,370
So let's consider element one.

225
00:16:20,110 --> 00:16:21,280
So this is element one.

226
00:16:21,730 --> 00:16:26,980
So it's left child is two and it's right child is three.

227
00:16:26,980 --> 00:16:32,080
So it's right child three to four and six zero zero.

228
00:16:32,080 --> 00:16:34,510
It's left child is present at the next one.

229
00:16:35,500 --> 00:16:41,640
And it's Rachel is present at next to let's take one more example, let's take three.

230
00:16:42,580 --> 00:16:49,400
So for three, the left jail is six and seven, so left six very six present.

231
00:16:49,870 --> 00:16:53,560
So this is three and six is present here.

232
00:16:55,170 --> 00:17:01,200
And for three weeks, I told presenter Rachel Besant at Disembarks, so the index of three is two,

233
00:17:02,010 --> 00:17:05,300
so next to the left child is six.

234
00:17:05,310 --> 00:17:10,380
It is better under the next five and right child is present at next six.

235
00:17:11,400 --> 00:17:13,560
So this this is my index A.

236
00:17:14,720 --> 00:17:18,329
You can say and say, can we observe a relationship?

237
00:17:18,680 --> 00:17:25,520
So basically, if this is a the left child is at the way plus one and right child is present at the

238
00:17:25,550 --> 00:17:26,210
table plus to.

239
00:17:27,530 --> 00:17:33,610
You can see the value of Razvan, so to weigh plus one, it will become three to weigh plus two.

240
00:17:33,620 --> 00:17:34,640
So it will become for.

241
00:17:35,740 --> 00:17:41,080
Similarly, the value of a zero, so the Y plus one, two times zero plus one is fun.

242
00:17:41,530 --> 00:17:43,340
Similarly to ableist also to.

243
00:17:44,700 --> 00:17:51,750
So the all important relationship that if the index is the parent index, then the left child will group

244
00:17:52,080 --> 00:17:57,780
at the next Y plus one and right child will be present at the next wageless to.

245
00:18:01,540 --> 00:18:09,100
So this is our mathematical observation, I'm repeating myself so you can see two is actually my parent,

246
00:18:09,820 --> 00:18:11,320
too, is actually parent index.

247
00:18:11,360 --> 00:18:12,490
So this is parent index.

248
00:18:12,940 --> 00:18:17,470
In order to find out the left child index, you will apply this formula to way plus one.

249
00:18:17,770 --> 00:18:21,760
In order to find out the right index, you will apply this formula to plus two.

250
00:18:22,180 --> 00:18:22,780
Simple.

251
00:18:24,140 --> 00:18:25,670
Now, let's take one more example.

252
00:18:30,520 --> 00:18:34,450
So this is then then let's say I have five.

253
00:18:35,000 --> 00:18:36,660
Well, this is a complete by Niddrie.

254
00:18:37,180 --> 00:18:38,520
This is a complete binary.

255
00:18:38,560 --> 00:18:39,920
This is a complete binary.

256
00:18:40,600 --> 00:18:41,980
This is a complete binary.

257
00:18:41,980 --> 00:18:42,520
And.

258
00:18:44,030 --> 00:18:49,670
So what we will do, we will store our complete binary trinary, but we will always be Julys as if it

259
00:18:49,670 --> 00:18:52,810
is a tree and we're not available.

260
00:18:52,830 --> 00:18:54,820
So then then five.

261
00:18:55,160 --> 00:18:58,910
So we are doing or traversal to fill that six, eight and zero.

262
00:19:00,520 --> 00:19:03,940
And these are indexes zero, one, two, three, four and five.

263
00:19:05,720 --> 00:19:10,820
Now, what I want to do, so suppose I want to insert an element handed.

264
00:19:12,120 --> 00:19:16,840
I want to insert an element and so on that will be inserted at the last position.

265
00:19:16,860 --> 00:19:17,720
This is very obvious.

266
00:19:17,740 --> 00:19:20,850
So it will be inserted at the last portion in next No.6.

267
00:19:22,610 --> 00:19:25,370
So this is the only option available for under.

268
00:19:26,940 --> 00:19:30,970
So that this really means a complete binary tree logic so far.

269
00:19:31,020 --> 00:19:35,940
Twelve hundred is the right subtree, so wastrels or 12 is presented next to.

270
00:19:36,780 --> 00:19:43,890
So I the value of AI is two and one hundred is the Rachel and Rachel formalize the way plus two to in

271
00:19:43,890 --> 00:19:45,390
order to find out the right index.

272
00:19:45,720 --> 00:19:46,920
So applied this formula.

273
00:19:47,220 --> 00:19:49,610
So this is doing two, two plus two.

274
00:19:49,620 --> 00:19:54,590
So it came out to be six you can see and there is present at index six.

275
00:19:56,100 --> 00:19:57,820
So our formula is working fine.

276
00:19:58,530 --> 00:20:00,690
Now suppose you want to insert one more element.

277
00:20:00,690 --> 00:20:02,780
Suppose you want to insert element ninety.

278
00:20:03,120 --> 00:20:09,030
So the only option available for 90 is this one, so that this really means a complete binary tree and

279
00:20:09,030 --> 00:20:10,750
it will be inserted at the last position.

280
00:20:10,770 --> 00:20:11,730
So this is 90.

281
00:20:12,980 --> 00:20:18,020
The Nexus seven, so six is the parent of 90, what is the index of six?

282
00:20:18,030 --> 00:20:25,570
Three, so the index is three and ninety is the left child so left child formula is the way plus one,

283
00:20:25,850 --> 00:20:29,100
you put the value of a three, so it will game out to be seven.

284
00:20:29,480 --> 00:20:34,890
Now you can see at index seven, the left child of six is on the left.

285
00:20:34,910 --> 00:20:37,310
I love six is present at index seven.

286
00:20:38,520 --> 00:20:41,010
So basically, our formulas are working fine.

287
00:20:42,760 --> 00:20:48,440
So basically, this is my parent, I is the index of the parent, then the child will be present at

288
00:20:48,460 --> 00:20:53,590
the next, Alison and Rachel will be present at the next duopolies to simple.

289
00:20:54,640 --> 00:21:00,850
No point does required just one simple Eddie, so that's how it will solve our problem.

290
00:21:01,380 --> 00:21:02,980
It will solve our second problem.

291
00:21:04,280 --> 00:21:10,950
So our second problem is also solved, we are able to store complete binary tree in just one simple

292
00:21:10,970 --> 00:21:11,260
very.

293
00:21:13,810 --> 00:21:15,160
No point does required.

294
00:21:16,120 --> 00:21:22,720
OK, I'm repeating myself, we are storing our complete binary in just one simple area, and there are

295
00:21:22,740 --> 00:21:25,600
no point pointers required, just one simple area.

296
00:21:26,320 --> 00:21:27,250
And one more thing.

297
00:21:28,150 --> 00:21:31,570
What do you think will be the same complexity for insertion?

298
00:21:31,990 --> 00:21:37,430
It is outdraw when we are just inserting at the right, we are just inserting at the last index.

299
00:21:37,450 --> 00:21:41,860
So suppose this is the next index, the index that which I have to insert my element.

300
00:21:42,100 --> 00:21:49,330
So I will just maintain my next index variable and I will start at Konstantine for insertion in computer

301
00:21:49,330 --> 00:21:53,290
based insertion in CBT is constant.

302
00:21:53,380 --> 00:21:56,360
You can see such a simple implementation.

303
00:21:56,950 --> 00:21:58,540
Very easy implementation.

304
00:21:59,020 --> 00:22:01,240
Now suppose you want to delete an element.

305
00:22:02,320 --> 00:22:08,350
Suppose you want to delete an element, so obviously we can only delete the last element, we can only

306
00:22:08,350 --> 00:22:09,900
delete 90 in this case.

307
00:22:10,330 --> 00:22:11,890
So that means what I will do.

308
00:22:12,040 --> 00:22:15,970
So for the leading an element, I will do next index, next minus minus.

309
00:22:16,150 --> 00:22:19,180
So next index will come here at index number seven.

310
00:22:19,570 --> 00:22:24,280
So the value of next index will become seven because initially it was eight.

311
00:22:24,670 --> 00:22:32,500
So next next represent the index at which I have to insert element so I will lose him and I next index

312
00:22:32,500 --> 00:22:36,580
minus minus deletion is constant.

313
00:22:38,230 --> 00:22:44,680
You can see we just have to do a minus minus, so we are deleting in question time, we are inserting

314
00:22:44,680 --> 00:22:46,990
in Question Time simple.

315
00:22:49,600 --> 00:22:52,450
Now, let's do let's take one more example.

316
00:22:55,210 --> 00:22:56,680
So let's take one more example.

317
00:22:56,710 --> 00:23:00,640
So this is my complete by Nutri, so again, I'm repeating myself.

318
00:23:00,640 --> 00:23:05,980
I restored the complete binary in an array, but we will visualize it like a tree.

319
00:23:06,190 --> 00:23:07,900
So these are the values.

320
00:23:08,740 --> 00:23:09,550
These are the indexes.

321
00:23:09,550 --> 00:23:09,850
Zero.

322
00:23:09,850 --> 00:23:10,870
One, two, three.

323
00:23:13,760 --> 00:23:22,400
For five, now, let's insert some elements, so initially the next index is here, so next index is

324
00:23:22,430 --> 00:23:22,820
zero.

325
00:23:23,630 --> 00:23:29,810
Now, what I want to do so that in certain values or in certain certain will be inserted and I will

326
00:23:29,810 --> 00:23:30,740
draw Maitri here.

327
00:23:31,810 --> 00:23:33,790
So the value of Nexen next will become one.

328
00:23:33,940 --> 00:23:39,850
Now I want to insert, let's say 15, so 15 will be inserted next year and next will become two and

329
00:23:39,850 --> 00:23:41,410
15 will become the left child.

330
00:23:42,130 --> 00:23:44,310
Now, let's say I want to insert five.

331
00:23:44,380 --> 00:23:46,830
So five will be inserted next.

332
00:23:46,890 --> 00:23:49,750
Next will become three and five will become the right child.

333
00:23:50,500 --> 00:23:53,050
Now, let's say I want to insert seven.

334
00:23:53,440 --> 00:23:55,300
So seven will be inserted next.

335
00:23:55,330 --> 00:23:58,030
Next will become four and seven will be inserted here.

336
00:23:58,510 --> 00:24:02,620
Now, let's say I want to insert it so it will be inserted next year.

337
00:24:02,690 --> 00:24:05,420
Next will become five and it will be inserted here.

338
00:24:05,740 --> 00:24:07,530
So that's how all this thing will work.

339
00:24:08,230 --> 00:24:14,050
We are storing the complete binary tree in an array, but we will visualize it as if it is a tree.

340
00:24:14,710 --> 00:24:15,310
Simple.

341
00:24:16,690 --> 00:24:23,410
Now we know that if I is the parent index, so in order to find out the left index, I will do the lesson.

342
00:24:24,040 --> 00:24:27,900
And in order to find out the right index, I want to, I will do two plus two.

343
00:24:28,330 --> 00:24:32,920
I want to do the reverse given the way plus one given the child index.

344
00:24:32,920 --> 00:24:34,580
I want to find out the parent index.

345
00:24:34,930 --> 00:24:38,310
So given the right index, I want to find out the index.

346
00:24:38,320 --> 00:24:40,070
So I just want to do the reverse.

347
00:24:40,330 --> 00:24:41,740
So what will be our formula?

348
00:24:42,640 --> 00:24:45,450
So this is left early next twip lesson.

349
00:24:45,730 --> 00:24:50,580
So if you will divide it by two, if you will divide the left index by two.

350
00:24:50,920 --> 00:24:53,350
So it came out to be a.

351
00:24:53,440 --> 00:24:55,870
So they will be in 22 division.

352
00:24:55,880 --> 00:24:58,330
So integer integer is going to be an integer.

353
00:24:58,930 --> 00:25:05,290
But if you will divide the right next to this is my right next to a plus two.

354
00:25:05,770 --> 00:25:10,090
So if you will divide the right index by two, so it will come out to be a plus one.

355
00:25:10,600 --> 00:25:12,050
And obviously this is wrong.

356
00:25:12,970 --> 00:25:18,880
So what we can do to solve this problem, so we will subtract the one from the child index and then

357
00:25:18,880 --> 00:25:20,030
we will divide by two.

358
00:25:20,440 --> 00:25:23,110
So this is the left next to a plus one.

359
00:25:23,470 --> 00:25:26,980
What we will look we will subtract the minus one and then we will divide by two.

360
00:25:27,760 --> 00:25:31,460
So it will come out to be a similarly what I will do.

361
00:25:32,560 --> 00:25:33,850
This is right index.

362
00:25:33,970 --> 00:25:37,980
First I will subtract one from the index and then I will divide by two.

363
00:25:38,260 --> 00:25:39,930
So this will come out to be I.

364
00:25:40,960 --> 00:25:42,970
So this is the parent index.

365
00:25:45,210 --> 00:25:50,630
So what we have to do so paint the next, if you want to find out the paint index, this is very simple.

366
00:25:50,640 --> 00:25:55,260
You take the child index so child index can be left index, right index.

367
00:25:55,260 --> 00:25:56,130
It doesn't matter.

368
00:25:56,700 --> 00:25:59,860
Then you will subtract minus one and then you will divide by two.

369
00:26:01,290 --> 00:26:03,810
So formula is very simple.

370
00:26:05,670 --> 00:26:13,270
Next, subtract minus one divided by two, and you will be able to find out the parent index symbol,

371
00:26:13,810 --> 00:26:16,210
if you have a confusion, you can take an example.

372
00:26:17,310 --> 00:26:24,630
And if this is the index, in order to find our index, you will do two times of page index plus one

373
00:26:25,170 --> 00:26:29,880
in order to find out right index, you will do two times of index plus two.

374
00:26:30,330 --> 00:26:31,380
So basically this one.

375
00:26:34,040 --> 00:26:38,540
So basically, you have to remember to formulas this formula.

376
00:26:39,930 --> 00:26:47,880
To find out, banned index from the child index and this formula to find out the left and right index

377
00:26:48,120 --> 00:26:54,420
given brand index so we will learn more about complete minidress in our next videos.

378
00:26:54,600 --> 00:26:55,970
I will see in the next one by.