17.1.2. Notions of Balance

So, trees there are many different notions of balance in a tree, so essentially a balance we should think of it is 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 it is root, the two side should be balanced, they should be equal.

In trees, the concept of balance is similar to a weighing scale. Imagine an old-fashioned scale that weighs goods; for it to work well, the weights on both sides must be equal. In tree structures, this means that if you were to measure the number of nodes (the individual points or 'items' of information) on either side of any given node, they should ideally be equal or have a controlled difference to ensure efficiency in operations like searching, inserting, or deleting nodes.

Think of balancing a seesaw in a playground. For the seesaw to be level and stable, equal weights must be placed on both sides. If one side is heavier, it tips to that side, making it unstable. Similarly, in a balanced tree, the structure must be maintained to ensure that one side doesn’t become too heavy (or deep) compared to the other, allowing for quicker operations.

Then, it is easy to see that you when you get a complete binary trees, so example you could have a tree which has this structure or if you extend it one more level, then for every node in the left you must extended on the right, but then these must also be balanced.

Exact balance means that each side of a node must have the same number of nodes, leading to a very strict structure known as a complete binary tree. However, such strict balancing can be difficult to maintain with frequent insertions and deletions. A relaxed balance allows for a slight difference between the number of nodes on either side, which makes it more flexible and easier to manage while still retaining efficiency in tree operations.

Imagine trying to build a tall bookshelf where each shelf must hold the same number of books. If you add or remove books from one shelf, you have to adjust all other shelves as well, which can be a hassle. Instead, if you allow a shelf to have one more or one fewer book than its neighbor, it becomes much easier to manage the shelves as you can still keep the books organized without strict limitations.

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... keeping with our earlier relaxation of the size condition, the height balance tree will be one where the height of the left and the height of the right differ the at most 1.

Instead of focusing solely on the number of nodes, the height balance considers the longest path from the root to the leaves. A height balanced tree (or an AVL tree) ensures that the height difference between the left and right subtrees of any node is at most one. This ensures that the tree remains efficient for operations, as the height is kept logarithmic relative to the number of nodes.

Think about climbing a staircase with steps of varying heights. If one side has significantly taller steps than the other, it would take longer and be harder to reach the top. However, if both sides are kept to a similar height, it provides a more balanced and manageable climb, much like maintaining balance in a tree allows for faster access and modifications.

So, let us refer to the difference between the height as just the slope... and this slope is height of the left minus height of the right.

The slope in the context of AVL trees refers to the difference in height between the left and right subtrees. It can take values of -1, 0, or +1, representing a degree of balance. A perfectly balanced tree has a slope of 0, while trees with slopes of -1 or +1 are still considered balanced but tilted slightly toward one side. Maintaining these values allows for the efficient balance and retrieval of data within the tree structure.

Consider a balancing act where a performer stands on a seesaw with weights. If the performer shifts their weight to one side, momentarily they are tilted, but if they readjust, they can achieve balance again. AVL trees work similarly; when a node is added or removed, the tree 'readjusts' to maintain balance, ensuring smooth operation.

So, what we will try to do is that whenever we do an insert or a delete we will immediately try to rebalance the tree.

After an insertion or deletion operation in an AVL tree, it's crucial to check if the tree has become unbalanced (having a slope of -2 or +2). If it is unbalanced, we perform rotations to rebalance the tree quickly. This process helps in keeping the path from the root to any leaf relatively short, allowing for faster search times.

Imagine a line of dominos set up perfectly. If you knock over one domino (insert or delete), it can create a cascade effect that disrupts the rest of the arrangement. To fix it, you would need to quickly readjust the remaining dominos and ensure they are still lined up properly. Just like quickly rebalancing the dominos, AVL trees must readjust themselves after operations to preserve their efficiency.

--