Hello all and welcome back.
So in this video I would like to talk about the balancing in our BST.
So till now we have of course done a lot of discussion on trees starting from the generic trees, then
moving to BST binary trees, and finally the binary search tree in each and every tree.
We discussed that how the overall desirable structure of my tree is something which is balanced, the
one which is on my left side right now.
In the last video, we saw that how the operations in my BST are big O of H.
Okay, so each and every operation was coming out to be order of height.
The height in a balanced BST is of the order of log n, so this will transform to big O of log N here.
Okay, but will be big O of N in the right skewed tree.
Okay.
So the overall idea is that we now know what Balanced Tree is, right?
So we know that the height of left and right should be less than one.
In an ideal scenario, we would not like that our tree is skewed okay.
We want our balance.
We want our tree to be balanced so that all the operations can be done off.
Done in the order of log n okay.
So what happened that we have now created some different types so that we can just make sure that our
tree always remain balanced.
Now it is not required to go in a lot of depth or even I would suggest do these particular types because
they normally are not asked in an interview.
Plus it becomes a lot complex.
Okay.
So the orders here are a lot complex in terms of the implementation.
And majorly it is not a topic which is asked that much, but I personally believe that one should have
an idea because we are talking about everything with respect to a balanced tree.
The best case scenario.
Okay, that is what we take.
So few of the types which I can write down is.
So let's say if we see BST types.
So the first one is two for three.
Then we have red black tree.
We also have something known as AVL tree.
Now the basic idea here is to make sure that once we have the property, how can we maintain the overall
balanced structure of our tree.
I can give you an idea about AVL tree as well.
And maybe we can see the same.
What happens in an AVL tree is so let's say if you have a tree something like this where you have added
element.
Now this tree is balanced as of now okay.
But now it is in unbalanced.
What happened here.
AVL tree says that okay.
To keep it balanced let me just rotate it.
Okay.
Let me just rotate it a little bit on let's say this particular node.
Once you do this your tree is going to become something like this.
And now it is balanced okay.
So it tries that always your tree can be balanced out.
Similarly red black trees.
It tries to maintain nodes with red and black color.
Now don't need to go a lot in the implementation for the AVL tree.
You can still try to just read about it a little bit.
I can show you the overall working of AVL tree as well.
So this was one of the tree which we saw everyone.
Now let us go and see for the AVL tree.
Okay.
Let me zoom in a little bit.
So let's say I enter ten.
This is entered.
Now let's say I enter 20.
This is again enter.
So 20 is going to enter here.
Now let's say I enter 30.
Okay.
Once I will enter 30 it is going to go here which is going to make my overall tree imbalance which is
not overall desired property.
Right.
So if I keep on adding in a normal BST, we can see that how the length will keep on increasing on this
side, which is big O of N in terms of any operation.
But once I add it here.
Right.
Once I add 30 here it is going to get added normally.
But after adding we will see that some kind of a balancing happens.
So it is just checking.
And now see it has rotated your tree.
And now your tree is balanced right.
So that's the basic idea.
Now pretty sure that via visualization some things will be clear.
Let us try to add 40 as well.
It's going to add here 40 because it's not a problem.
We know that the height is still maintained.
Again if there will be a problem with respect to the balancing thing, then we will try to again just
rotate and make sure that I'm able to keep it balanced so that all my operations are a lot optimized.
Okay, so that's the basic idea.
Now we have talked a lot about how balanced one are, the desirable one, and there are just few types
which make sure that this property is not compromised with.
If we are making a tree again, it is not required to go a lot in depth of them as of now.
But you should have an idea, okay, because if you are talking so much about the balanced tree with
respect to every operation, if you are maintaining or assuming that yes, our a trivial, majorly B
balance.
Then we should know that yes, there are some implementation which makes sure of that thing.
Okay, so yeah, that was the basic idea which I wanted to discuss.
Now honestly, we have discussed these in a lot depth.
So instead of jumping onto these trees, I would first expect and suggest you to just do all the questions,
everything which you have discussed with respect to the generic binary and binary search trees, because
that will be more than enough for any interview, any exam.
Once.
Let's say you feel that, okay, you are confident and your curiosity gets the best out of you.
You can of course, just try to read about these trees as well.
Okay, so great everyone.
I'm pretty sure that you like the idea that how we have expanded more upon Bsts to make sure that the
desirable property of balance is maintained via making some different types.
So yeah, that was the major idea behind this class.
Now, I will expect that you will just make sure that you have a full command on trees, each and every
operation, as well as do all the assignments which have been shared with you.
Okay.