17.1.5. Slope and Rebalancing

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.

The concept of 'slope' in a tree refers to the difference in height between the left and right subtrees. A positive slope means the left subtree is shorter than the right, while a negative slope indicates the left subtree is taller. In a balanced tree, the absolute value of this slope must be 1, allowing for three possibilities: equal heights (slope 0), the left subtree being taller (slope -1), or the right one being taller (slope +1). Anything beyond these slopes indicates an imbalance.

Imagine a seesaw on a playground. If both sides are equal, the seesaw is balanced (slope 0). If one side is heavier (taller), it tips down (negative or positive slope). Just like you adjust kids' placements on a seesaw to keep it balanced, we adjust our tree when it becomes unbalanced.

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.

When performing insertions or deletions in a balanced tree, a change in height can result in a slope that exceeds the acceptable range. Each operation may swing the slope from -1, 0, or +1 to -2 or +2. To prevent imbalance, after each insertion or deletion, we must check the tree and perform rebalancing operations to bring the slope back within the allowed range, effectively ensuring the tree remains efficient for future operations.

Think of a stack of books on a shelf. If you add or remove a book, the stack may lean to one side. To keep it straight and stable, you would adjust it immediately after each change. Similarly, in a tree, we must ensure it stays balanced after each addition or removal.

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.

The rebalancing process occurs from the bottom up following an operation (insert or delete). When a node is added or removed, it might cause a notable imbalance, represented by the slope exceeding ±2. The immediate objective is to restore balance within the range of ±1. By adjusting the nodes upwards from where the insertion or deletion occurred, we assume the lower subtrees are already balanced, effectively ensuring the entire tree remains operationally efficient after every modification.

Imagine a game of Jenga where removing or adding a block might make the tower wobbly. To stabilize it, you would carefully reposition blocks underneath to maintain overall balance. In the same way, after each tree modification, we adjust the structure from the bottom layers up to maintain stability.

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.

In a situation where we have an unbalanced node with a height difference, we analyze the heights of subtrees. If one side is much taller (e.g., height h + 2), we can deduce there must be at least one node on that side, which allows us to reorganize the tree structure. By exposing the root of the taller subtree, we create new connections and reorganize the nodes to restore balance.

Think of a person lifting a heavy box (the unbalanced node). If one side (the left) is much heavier than the other, you have to adjust how you hold the box, possibly moving some items around or shifting how you carry it to stabilize it and prevent dropping it.

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.

When rebalancing, we often employ rotations—specifically right or left rotations. By pivoting around a specific node, we can reposition the tree's structure. For instance, in a right rotation around node y, node x takes y's place, and we rearrange the subtrees around them, which helps maintain the structure of the tree while correcting any imbalance.

Let's relate this to adjusting a bookshelf. If one shelf is sagging, you might slide in a new bookend to support it properly. This 'swinging around' of support is similar to how we rotate nodes in a tree to ensure stability and balance.

--