Hi, everyone.
So in this lesson we will see completed by Nutri, we will see you complete minor details and we will
also see its implementation.
So if you remember in the last lesson we discussed, that balance best is the best data structure that
we have to implement the priority queue.
But there were two problems associated with the balance bisdee.
So that's why we discussed and designed a new data structure called Help to implement our priorities.
Now let's discuss those two problems again.
So first of all, I was basically so we have to always ensure that our best is balanced and that is
overhead.
And the second problem was basically of storing BSD is a very complex thing.
Because there will be a lot of a lot of binders to handle.
And now let's try to understand how he will help us to solve these two properties, these two problems
of Balestra based.
So firstly, just try to find out.
What is the height of a complete by nutri?
So what will be the height of a bid by Nutri so for finding out the height of a complete by Niddrie?
We have to find out Tuvalu's and basically it will involve a lot of mathematical calculation.
So first, let us try to find out these two values.
So what is the minimum number of nodes in a complete binary tree of high tech?
And the second thing that we have to find out is the maximum number of nodes in a computer binary of
eight each.
So we have to find out these two values.
Before finding out the height of a computer by Nutri.
So let's find out these two values.
So first, let us try to find out the number of nodes in our computer by Niddrie of each.
So let's do some match.
So I want to find out the minimum number of nodes, so let's take an example, so let's say the height
of complete binary tree is for.
Now, let's go, secretary.
So this is accompanied by Niddrie, this is a complete by Nedry.
This is a computer by Nutri.
This is a computer by Niddrie.
This is a complete Binetti.
So this is.
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
or.
I will add only one or not, this is a complete binary of eight four and the notes are minimum.
Obviously I can add many nodes, I can add nodes here, but we have to find out the minimum number of
nodes.
So that's why I will add only one node.
So this is actually a complete by nutri.
This is a valid, complete binary with hateful.
Now, let us calculate how many number of nodes are there.
So at this level, one node, so I can say to the power zero nodes at this level, two to the power
nodes at this level, so two to the power to nodes.
And this is one also plus one.
Now, how many nodes are there, so if you will add.
Go to the Power-One, then.
So.
The value of height is actually four, so this value is actually higher to minus two.
So for minus two is to.
So what will happen, if you will add all these items, so our last item will be true to the power height
minus two and this one.
Plus one.
So these are the minimum number of Nords.
In a complete by of High-Tech.
Now, this storm is actually a dramatic progression, so if you remember the formula, so the formula
is very simple after the power and minus one divided by our minus one.
So it is easy to do the power to zero.
So do the power zero.
Then add is to what is the total number of times.
So the total number of items is each minus one to each minus one then minus one and ah is to minus one.
So this is actually due to the power minus one, minus one.
And then we have plus one here.
So I will write plus one.
So plus and minus one will cancel out each other.
So I know the minimum number of nodes, we know number of nodes in a complete binary tree of each is
actually due to the power each minus one.
Now, we also have to find out the maximum number of nodes.
So now let's try to find out the maximum number of nodes.
So let us.
So let's say my height is.
For so whatever the maximum number of rules, so this is a complete by of how to complete by of five
three.
Now, this is a complete by Nutri, this is a valid complete by any real fight for, but we have to
find out the maximum number of nodes.
So what I will do, I will completely fill this level.
And now let us do the calculations of how many number of nodes that isn't at this level bruited about
zero to the Power-One.
So this is due to the power to and this is due to the power three.
So what is three?
Three is actually height minus one.
So it is four for minus, honestly.
Now, let us add all these nodes, so the maximum number of nodes is actually the addition of all this.
So to the biocidal, then two to the power, one, then to the power two.
So it will go on.
And the last is true to the power each minus one.
Now, again, this is a dramatic progression.
The formula is very simple.
Out of the power in minus one, divided by R minus one.
So it is true that the power of zero R is two.
So how many total, how many times are there?
So there are total items.
So each minus one divided by two minus one.
So this is nothing but two to the power each minus one.
So the maximum number of nodes makes a number of nodes in a complete binary of height, it is actually
true to the power each minus one.
So now we know the number of nodes and we know the number of nodes.
So these are the minimum number of nodes and these are the maximum number of nodes.
So minimum number of nodes is actually due to the power each minus one and the maximum number of nodes
is actually to the power each minus one in a complete binary tree.
Of height, edge of height, edge.
So basically, can I say that my and and is actually a number of not so total number of nodes in the
computer by Nutri will be less than or equal to the power minus one and will be greater than or equal
to two to the power each minus one.
So is this statement valid?
So obviously, the statement is valid because any if it were the number of nodes in a binary tree,
so these are the maximum number of nodes possible and these are the number of nodes possible.
So obviously, this relation is valid.
Now, let us try to solve the solution.
So let us try to solve this one first.
So the solution is to reduce our H minus one is less than close to one.
Now apply log on both sides.
Take log with the base to on both the sides.
So this is log to then we have to do the power each minus one.
Less than three to log two, and now there is a formula of log that log into the power B, so B will
come out, friend.
So this will become blog.
So what will happen?
So this H.M.S. will come out, friend.
So this will be H minus one.
Then log to Whitby's to is less than articles to log in Bisto, and this really is actually one.
This is one.
So what is my formula?
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
B to.
And Blessin sorry I forgot this one.
So this will be plus one.
Now, let us try to solve the solution.
So this is and is literally close to true to the power edge minocin.
So take one this side, so this will be end plus one last night, it close to two to the power edge
and now the log on both the sides.
So log and plus one base to.
Is less than our to log to the power edge Bisto.
So this is it and this is an.
Now, again, it will come out front, so this is Hetch.
Log to be to and this is log off and plus one Bisto, so this will lose again when.
This is one so each is good and our goal is to.
Lagarto and plus one.
And now it will do.
So this is my second relation, and this is this is first.
This is second conclusion.
Now combine these two illusion.
What will I get?
So each.
Is greater than articles to.
Log to Anderson and each is less than ideal to this one, so this is log 210 plus one.
So this is my computer, Luciane.
Now, in terms of begal, in terms of time, complexity, so each is less than nightclothes do, so
in terms of time, complexity, we can avoid this plus one.
So this will be big of.
Log and similarly, in terms of time, complexity, we can avoid this lesson, so it is basically denied
close to.
Lock and.
Now, see, Edge is less than ideal slogan, it is good slogan.
So that means it is actually Logan.
You analyze this relationship, so each is less than a slogan, which is a good slogan.
So this implies that height is always log-in.
So in complete binary tree, my height is always log of N.
My height is always logoff and you can consider best case, worst case, basically, any case, average
based versus my height in a complete binary tree will always be logged, often without doing anything.
Now, if you will see.
My height in a complete binary tree is always log in.
And we are not doing anything to maintain our hate.
So in Vélez Bisdee, we have to do a lot of calculation so that our height remains log-in, so that
our body remains balanced, so that our height remains log-in but incomplete by nutri height is always
Logan without us doing anything.
So this solves our first problem.
Now, the second problem, so the second problem was storing BSG is really, really difficult.
It is very complicated because there will be a lot of lot of points to deal with.
Now, let's see how he will help us.
To solve this second problem associated with violence.
So let's discuss how we will store our help.
So no balancing required since the height is always Logan, we will not do anything and I will always
be Logan.
So no balancing required.
And now let's discuss how we will store our complete by Nutri.
So we know that saving bisdee.
Is actually a very complex process.
Saving Beiste is a very complex process, so let us discuss how we will store complete by Niddrie.
So this is my computer by Niddrie.
Now, I want to insert an element, let's say I want to insert element to it, so the only option.
The only position.
Available to me is this one I can only insert it here, I cannot insert it anywhere else, I cannot
insert here, I cannot insert here, and similarly, I cannot insert any at any of the position.
So this is the only position available for me to insertion is very easy.
Now, let's say you want to insert nine.
So the only option available for inserting nine is this one.
You can only insert nine here.
So basically how we will be able to find out at which position I will be able to insert so you have
to rule on a traversal, so will tell us this level, then you will try this level, then you will traverse
this level, and then you will traverse this level.
And as soon as you find an empty position, as soon as you find out a position at which there is no
node, then at that position you can insert the element.
For example, if you want doing certain, then you will do traversal to find out an empty position and
then you will be able to store that value there.
So this is very, very bad because for finding out an empty position, so for finding out an empty position,
we have to do level order traversal in complete binary tree and level traversal will take big off End-Time.
So far, just finding the empty position, we are going to go find them and that is very, very bad.
So that means I have to do something about it.
I cannot do Learoyd just to find out the empty position at which I have to insert my node.
So the easy way and the best way to store.
Complete by Nutri is actually using an eddy.
So I'm repeating myself, the easiest way to store a complete binary tree is basically with the help
of NATO.
Now let's see how.
So first, let us consider a complete binary tree.
So this is a complete by nutri.
Now what we do.
We will take a..
And we will fill this area.
So how we will fill this area, we will just do the Illinois traversal.
So just to the level that I was a landfill, Daryn, so it will be one, then two, then three, then
four, five, six and seven.
And these are indexes zero, one, two, three, four, five and six, so I will store my complete by
Niddrie inside and very simple.
Now let's see suppose.
My parent is two and four and five, so there is two sorto and jailer's, basically four.
For the left child and five is the left child, so to speak, and the next one.
So next one, it left child is present and the next three years, right child is present at the next
food.
Let's consider one more element.
So let's consider element one.
So this is element one.
So it's left child is two and it's right child is three.
So it's right child three to four and six zero zero.
It's left child is present at the next one.
And it's Rachel is present at next to let's take one more example, let's take three.
So for three, the left jail is six and seven, so left six very six present.
So this is three and six is present here.
And for three weeks, I told presenter Rachel Besant at Disembarks, so the index of three is two,
so next to the left child is six.
It is better under the next five and right child is present at next six.
So this this is my index A.
You can say and say, can we observe a relationship?
So basically, if this is a the left child is at the way plus one and right child is present at the
table plus to.
You can see the value of Razvan, so to weigh plus one, it will become three to weigh plus two.
So it will become for.
Similarly, the value of a zero, so the Y plus one, two times zero plus one is fun.
Similarly to ableist also to.
So the all important relationship that if the index is the parent index, then the left child will group
at the next Y plus one and right child will be present at the next wageless to.
So this is our mathematical observation, I'm repeating myself so you can see two is actually my parent,
too, is actually parent index.
So this is parent index.
In order to find out the left child index, you will apply this formula to way plus one.
In order to find out the right index, you will apply this formula to plus two.
Simple.
Now, let's take one more example.
So this is then then let's say I have five.
Well, this is a complete by Niddrie.
This is a complete binary.
And.
So what we will do, we will store our complete binary trinary, but we will always be Julys as if it
is a tree and we're not available.
So then then five.
So we are doing or traversal to fill that six, eight and zero.
And these are indexes zero, one, two, three, four and five.
Now, what I want to do, so suppose I want to insert an element handed.
I want to insert an element and so on that will be inserted at the last position.
This is very obvious.
So it will be inserted at the last portion in next No.6.
So this is the only option available for under.
So that this really means a complete binary tree logic so far.
Twelve hundred is the right subtree, so wastrels or 12 is presented next to.
So I the value of AI is two and one hundred is the Rachel and Rachel formalize the way plus two to in
order to find out the right index.
So applied this formula.
So this is doing two, two plus two.
So it came out to be six you can see and there is present at index six.
So our formula is working fine.
Now suppose you want to insert one more element.
Suppose you want to insert element ninety.
So the only option available for 90 is this one, so that this really means a complete binary tree and
it will be inserted at the last position.
So this is 90.
The Nexus seven, so six is the parent of 90, what is the index of six?
Three, so the index is three and ninety is the left child so left child formula is the way plus one,
you put the value of a three, so it will game out to be seven.
Now you can see at index seven, the left child of six is on the left.
I love six is present at index seven.
So basically, our formulas are working fine.
So basically, this is my parent, I is the index of the parent, then the child will be present at
the next, Alison and Rachel will be present at the next duopolies to simple.
No point does required just one simple Eddie, so that's how it will solve our problem.
It will solve our second problem.
So our second problem is also solved, we are able to store complete binary tree in just one simple
very.
No point does required.
OK, I'm repeating myself, we are storing our complete binary in just one simple area, and there are
no point pointers required, just one simple area.
And one more thing.
What do you think will be the same complexity for insertion?
It is outdraw when we are just inserting at the right, we are just inserting at the last index.
So suppose this is the next index, the index that which I have to insert my element.
So I will just maintain my next index variable and I will start at Konstantine for insertion in computer
based insertion in CBT is constant.
You can see such a simple implementation.
Very easy implementation.
Now suppose you want to delete an element.
Suppose you want to delete an element, so obviously we can only delete the last element, we can only
delete 90 in this case.
So that means what I will do.
So for the leading an element, I will do next index, next minus minus.
So next index will come here at index number seven.
So the value of next index will become seven because initially it was eight.
So next next represent the index at which I have to insert element so I will lose him and I next index
minus minus deletion is constant.
You can see we just have to do a minus minus, so we are deleting in question time, we are inserting
in Question Time simple.
Now, let's do let's take one more example.
So let's take one more example.
So this is my complete by Nutri, so again, I'm repeating myself.
I restored the complete binary in an array, but we will visualize it like a tree.
So these are the values.
These are the indexes.
Zero.
One, two, three.
For five, now, let's insert some elements, so initially the next index is here, so next index is
zero.
Now, what I want to do so that in certain values or in certain certain will be inserted and I will
draw Maitri here.
So the value of Nexen next will become one.
Now I want to insert, let's say 15, so 15 will be inserted next year and next will become two and
15 will become the left child.
Now, let's say I want to insert five.
So five will be inserted next.
Next will become three and five will become the right child.
Now, let's say I want to insert seven.
So seven will be inserted next.
Next will become four and seven will be inserted here.
Now, let's say I want to insert it so it will be inserted next year.
Next will become five and it will be inserted here.
So that's how all this thing will work.
We are storing the complete binary tree in an array, but we will visualize it as if it is a tree.
Simple.
Now we know that if I is the parent index, so in order to find out the left index, I will do the lesson.
And in order to find out the right index, I want to, I will do two plus two.
I want to do the reverse given the way plus one given the child index.
I want to find out the parent index.
So given the right index, I want to find out the index.
So I just want to do the reverse.
So what will be our formula?
So this is left early next twip lesson.
So if you will divide it by two, if you will divide the left index by two.
So it came out to be a.
So they will be in 22 division.
So integer integer is going to be an integer.
But if you will divide the right next to this is my right next to a plus two.
So if you will divide the right index by two, so it will come out to be a plus one.
And obviously this is wrong.
So what we can do to solve this problem, so we will subtract the one from the child index and then
we will divide by two.
So this is the left next to a plus one.
What we will look we will subtract the minus one and then we will divide by two.
So it will come out to be a similarly what I will do.
This is right index.
First I will subtract one from the index and then I will divide by two.
So this will come out to be I.
So this is the parent index.
So what we have to do so paint the next, if you want to find out the paint index, this is very simple.
You take the child index so child index can be left index, right index.
It doesn't matter.
Then you will subtract minus one and then you will divide by two.
So formula is very simple.
Next, subtract minus one divided by two, and you will be able to find out the parent index symbol,
if you have a confusion, you can take an example.
And if this is the index, in order to find our index, you will do two times of page index plus one
in order to find out right index, you will do two times of index plus two.
So basically this one.
So basically, you have to remember to formulas this formula.
To find out, banned index from the child index and this formula to find out the left and right index
given brand index so we will learn more about complete minidress in our next videos.
I will see in the next one by.