17.2.1. Single Rotation

So, trees there are many different notions of balance in a tree, so essentially a balance we should think of it as like a physical balance. So, if you go to an old style vegetable seller, when they will have this kind of a balance and then you want at any point if you hold up a tree by its root, the two sides should be balanced, they should be equal.

Trees can be thought of as balanced structures where the left and right sides should contain similar numbers of nodes. The analogy compares tree balance to a physical balance used by vegetable sellers, where both sides must weigh the same. If both sides are not equal, it indicates that the tree is unbalanced. Trying to maintain equal weight on both sides is akin to ensuring equal numbers of nodes in a binary tree.

Imagine a toddler on a seesaw. If one side is much heavier than the other, one side will be closer to the ground, just like an unbalanced tree. For the seesaw to function properly, both sides need similar weights, much like a balanced tree needs equal numbers of nodes on both sides.

Notion of balance that we will use is not with respect to size, but with respect to height. So, we will say that the height is a number of nodes from the root to a leaf.

The text explains that balance in trees can be defined in terms of height rather than the total number of nodes or size. The height of a tree is calculated from the root to the furthest leaf node. For instance, if a tree has four nodes on its longest path, its height is 4. This definition helps differentiate between trees, ensuring we can distinguish simpler structures, like one with only a root, from an empty tree.

Think of a staircase where each step represents a node leading up to a second floor. The height of the staircase would be the number of steps taken to reach the top. If you were to compare two staircases, one with more steps (higher) is significantly different than a flat ground (empty tree).

So, these trees are called AVL trees the named after the two people who independently invented them one person called Adelson-Velsky and independently Landis. So, an AVL tree is a height balanced tree which says that at every node the height of the left and height of the right sub-trees differ by at most 1.

AVL trees are a specific type of self-balancing binary search tree where the difference in height between the left and right subtrees is limited to 1. This means if one subtree is taller, it cannot be more than one node taller than the other, ensuring that all operations (like searching, inserting, and deleting) remain efficient.

Consider a library of shelves, where balanced shelving means that no shelf on one side is heavily weighted or taller than the other by much. If shelves were to become too uneven, it could lead to situations where books are difficult to access or shelves could break — just as an unbalanced AVL tree could lead to inefficiency.

So, let us refer to the difference between the height as just the slope. So, we let 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.

The slope in an AVL tree is defined as the difference in height between the left and right subtrees. If the left subtree is taller, we have a negative slope; if the right subtree is taller, we have a positive slope. The balance condition states that the absolute value of this slope can be at most 1 for the tree to remain balanced.

Imagine balancing items on a scale. If one side is heavier, it tilts to that side. In the context of trees, this tilt represents the slope. If we can ensure that both sides remain equal (or very close), the scale remains balanced and easy to operate, just as we want for our AVL trees.

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 is that whenever we do an insert or a delete we will immediately try to rebalance the tree.

When an item is inserted or deleted from an AVL tree, its structure may become unbalanced. The slope can shift to a value outside the permissible range (-1 to +1), indicating the need for rebalancing. The strategy involves rebalancing the AVL tree after every insertion or deletion to maintain its balanced nature and efficient operation.

Think of a tightrope walker. If they lean too far in one direction, they need to correct their balance quickly to avoid falling. Similarly, when changes (insertions or deletions) happen in an AVL tree, we must 'correct' or rebalance it immediately to keep it balanced.

--