Let us refer to the difference between the height as just the slope, so we have intuitively in our pictures. So, if it is unbalance then things are treated, so we could have till this way or till this way, so we call this the slope. So, we let us say this slope is height of the left minus height, so the height of the left is less than the height of the right, then you have a positive slope. If the height of the left is bigger than the height of the right, then you have right, left is smaller than right you have negative slope, left is bigger than right you are positive slope.

In a balanced tree since the height difference absolute value must be 1, you can only have three possible slopes throughout the tree, either there is no slope they are exactly the same or it is minus 1 or plus 1.

Now, if you can argue very easily that if the current value is of the slope some minus 1 plus 1, when you delete a node, you can reduce one of the heights by 1. So, the height difference can go from 1 to 2 or when you increase you can make the height difference, again go from 1 to 2. So, the new slope after a single insert or a single delete can be at most minus 1 or plus 2, minus 2 or plus 2. So, what we will end up to do what we will try to do is that whenever we do an insert or a delete we will immediately try to rebalance the tree.

So, we would have a single disturbance from minus 2 or plus 2 it will never become very badly unbalance and we will immediately restore the balance to within minus 1 to plus 1. So, you will do this rebalancing we will also do this rebalancing bottom up, so what happens we will do an insert, if you remember is that we go down and we find a place to insert. So, this point we add a new node, so therefore now at this point that could be some imbalance, so we fix it, then we will go back to the up this path and we will go there and we will fix the path here, but at this point you will assume that the tree below has been balanced.

So, now since the left has height h plus 2, it has height at least 2, h can be at most at least smallest h can be 0, so it has height at least 2, so there at least 1 node here. I mean 2 means that there are at least 2 nodes here, so we have at least 1 node in particular. So, we will expand this by exposing its root and the root will have in general 2 sub trees, so now this whole thing has height h plus 2.

So, we take this tree and we kind of hang it out by y and we reattach things. So, in this rotation when you hang it out by y, x comes down and now we look at this sub trees, so we have the 3 sub trees, we have TLL, TLR and TR. So, if you go there we find that TR is to the right of x and it is also to the right of y, so it is the right of both, TLR is to the left of x to the right of y, TLL is to left of y, left of x.

If you go there we find that TR is to the right of both, TLR is to the left of x right of y and TLL is to the left of both. So, we hang up these trees, so now all the values we can verify will be currently organized as a search tree issue.