Hello all and welcome back.
So in this video let us now move forward and try to find out what is the complexity of different operations
which we have done in our BST class.
So in the last couple of videos we have implemented the methods such as insert, search and delete in
our BST class, which we saw are the major methods or operation which we have to perform.
Right.
So in the visualization as well, different visualization, which we saw there were these three methods
available.
Right.
Because these are the only three methods which you mainly are required to do.
Along with that, of course it can be traverse checking if it is BST, but that is something which you
have already done.
Now coming to these main operations okay, so let us take them one by one.
Let's say first one is search.
Now for search.
Let us assume that our tree is something like this okay.
So let me copy this note and let us make multiple notes.
See, I'm getting my tree, which is almost maybe I would say balanced.
Right.
So not taking a degenerate overall let's say this is my tree.
Let me just connect the notes real quick.
Also everyone please make sure that you download these notes.
They will be very much helpful to you in revising and before any interview as well.
Great.
Now, if my tree is not skewed and say I'm getting a tree like this, what used to happen exactly?
We used to go to a node based on the value of the root.
We used to take a decision whether to go right or to go left.
Then we used to go to say right then to this position overall, to do all this thing right, to do all
this different, different steps.
I am effectively traversing o h where h is my height.
I am not going to each and every node.
Okay, so height of tree.
It is in order of the height, whatever is the height.
In binary trees.
We used to go to each and every node to, let's say search for a particular node or value, which I'm
finding right here.
That is not the case because I am going one either on the left side or on the right side.
That will effectively come out to be what is the height of my tree.
Now, in case if it is skewed, then we know how the height is n right?
If it is not skewed then we majorly have seen that height will be equal to log n, right?
So around log n is where height is for the tree where I have this particular skewed tree, we know that
it is not a desirable tree right.
It is as good as a linked list.
And we know in searching in a linked list, the overall complexity is O of n only.
Great.
So that is with respect to search.
Now let us see for insert.
Similarly for insert.
Okay.
So if I just scroll down a little bit and let me copy this particular tree as well.
Maybe we can use the same one only.
Now for insert.
Actually the whole process is exactly same right.
So I go to the root.
Then I see where I have to insert.
Let's say I go right then on the left let's say it's saying go to the left and I'm inserting the node
here.
Okay.
So the whole process again is very much similar.
So the complexity becomes again Big-O of h right.
Where h again is the height of my tree.
Now in a very good case, in a case of perfect binary search tree, it will be log n in our tree, which
is skewed.
It will be o of n, end, right?
But majorly in major cases if we are making a tree, right?
Not a linked list.
We will try that.
Our tree is going towards where it is balanced, right where the height of each side is not a lot high
like there is no much difference.
So normally we say that we are able to do things in o log n time, which we know is a very good advantage
over o of n, so o log n is very good as compared to O of n something which we have seen right when
we compared binary search with a linear search.
Great.
So pretty sure that these will be clear.
Now let us move forward and talk about height or delete.
So third operation is delete which of course was a little bit tricky.
But let us see that one by one everyone.
So again I will be just copying this tree only it is a good tree to work on.
And maybe we will add some nodes here.
Great.
So this is our tree let's say which we have everyone.
Now what I'm doing is I am adding, say, another node here.
And even let's say one more should be fine.
Okay, great.
So now pay attention.
What exactly is going to happen.
Let's say I want to delete this particular root.
Okay.
Let's say I want to delete root only.
Now what is going to happen for deleting root or let's say any other if let's say even I want to delete
this particular node.
The first operation is the very first part is going to that node going or finding node we want to delete.
Let's say we find it at H1 height okay.
So let's say this is at h1 height.
What effectively I am saying let us say if you want to delete this particular node, this particular
node, let's say you find it at H1 Right now your node can be something this as well if it is a very
big tree.
Okay, when many elements are there.
But let's say we are able to find it at h1 height.
Great.
If we have to delete this then what's the second work we do?
Find replacement.
For replacement, let's say we find the replacement at some H2 height.
Okay so what I effectively mean everyone.
Let's say this is my overall tree where I find H1 and say I'm changing it with this particular node.
Okay, so I am changing it with this node.
Maybe we can take the example or say for this particular node we are one second.
It's not the vanishing pin.
So it should be fine here.
For this particular node.
Let's say I will be finding this at H2 okay.
You will see one thing for sure that h1 h2 okay in case it can be equal to H, right?
It will not be greater than h because some point you have find the node which you want to delete.
And based on that you are now finding the replacement.
The last work used to be delete the replacement.
Now in deleting the replacement we will not be making another call.
The reason is that replacement for sure left or right is going to be null.
So it will also be in H two level.
So what I effectively mean by that let's say you have to find a replacement for this node.
You will go here and keep on going left until this is none.
Now if this is none and let's say it has a right subtree, we are just going to make this as my new
node here, right?
So we will just correct this connection here.
This is something which we discussed.
It will not be making a call again because we know that one side of this replacement is going to be
done so at H2.
Overall we will be able to work this out.
Okay.
So let me just explain it a little bit again.
Let's say at some height you have to delete your tree that is H1.
Okay.
You find the node at h1.
Then at some height you will find that okay.
What you can replace it with.
So that let's say is H2.
Along with this we will have to make sure that we delete the replacement as well.
So this will also be H2.
Now your replacement because it will have of course one of the side.
None either the left or the right.
Okay.
Because that is the condition on which we find replacement for getting the min node.
We used to keep on going left until the left is not null.
Right everyone.
So if in a way we just see that visually it will always be less than two h, right?
It will always be less than two h.
Because this is let's say h.
In worst case it is proper h and then h2 will be some part of my height.
So what I can say.
Pay attention everyone.
H1 plus h2 plus h2.
It will be less than two h, right?
If that's the case now, I hope all of you remember N2N.
The complexity overall still gets to Big-O of H, right?
So if I'm able to get a very good balanced tree out.
Right.
If I'm able to get a very good balanced tree.
Okay.
And I'm not talking about these trees, the skewed one because again, we know that the skewed one,
they are not the ideal tree which we want.
So if this is the tree then it's a problem.
So for a balanced tree we are able to see that all these operations can be performed in big O of log
N time.
Right.
Because the height is around log n, we can say that if a tree is balanced and the balanced tree, we
already know where the left and the right subtree have a height difference which is less than or equal
to one.
Okay, so this is the complexity.
Let me write that down as well.
This is the major conclusion for a balanced.
BST, which is the overall tree which we want.
All operations.
Are big O of log n.
Now comparing that to let's say a list or an array, if we have a sorted list or an array.
Right.
Because the nodes are continuous one after the other, another, not the nodes, the values there we
have to do the shifting right there.
We have to make the space.
If we are deleting, then also we have to do the shifting.
So all that actually makes used to make the complexity big O of N, just by using trees and making sure
that they are balanced, we are able to increase that complexity overall to a level which is big O of
log N, and we know that how good of a overall Improvement.
That is okay.
Again, that will depend a lot on the tree structure.
But if we make sure that when we are making the tree, we are keeping it balanced.
So there are different ways or different trees which are defined for this particular overall aim as
well, that we want that our tree should remain balanced.
Okay.
So which we are going to just touch upon in the next video.
But the basic idea is that by using T properly, I can have things all these operations in big O of
log N from big O of N, which again is a very, very good improvement which we have made.
So I'm pretty sure now all the operations how exactly they are doing.
Okay.
It is fine.
If someone asks you about the overall complexity, you should always say big o of H, not n big O of
log n, but yes, for a balanced BST it is big O of log n like of the order of log n.
Okay, so cool everyone.
I'm pretty sure that the complexity part will be clear.
Now let's meet in the next video where we will see some ways or touch upon some ways.
This is actually handled.