17.2. Rebalancing Process

In today's lecture, the goal is to explain how to maintain the balance as the tree grows and shrinks.

Maintaining balance in search trees is critical for ensuring that operations like insertions and deletions remain efficient. If a search tree becomes unbalanced, the time taken for these operations can degrade from logarithmic to linear time. Therefore, we need to establish mechanisms that allow us to keep the tree structured in a way that allows for fast searching, inserting, and deleting, even as we modify the tree.

Imagine a library that needs to keep its books organized on shelves. If books are added haphazardly to the shelves, finding a specific book might take a long time. However, if the library staff regularly checks the organization of the shelves to ensure that similar books are kept close together, locating a specific book is much quicker. Similarly, maintaining balance in a search tree helps keep data organized and accessible efficiently.

Trees have many different notions of balance, which we can think of as being like a physical balance. If we hold the tree by its root, both sides should be balanced.

The concept of balance in trees is analogous to a scale—there must be equilibrium in the number of nodes between the left and right subtrees. A perfectly balanced tree would have an equal number of nodes on both sides. This definition can become restrictive, so we often relax the requirement, allowing for some difference—such as having the heights of left and right subtrees differ by at most 1 in AVL trees.

Think of a seesaw, where for it to be balanced, the weights on either side must be equal. However, if one side has a heavier weight and the other only slightly lighter, the seesaw still functions reasonably well. Similarly, in balance trees, a little discrepancy in the number of nodes still allows for effective operation.

The height of the tree is defined as the number of nodes from the root to a leaf, and a height-balanced tree is one where the heights of the left and right subtrees differ by at most 1.

The height of a tree is determined by counting the number of nodes along the longest path from the root down to a leaf. In AVL trees, we impose a balance criterion based on height: for any given node, the heights of the left and right subtrees should differ by no more than 1. This relaxed condition allows us to maintain balance during tree modifications while still keeping search operations efficient.

Consider a ladder that needs to stand upright—if one side is significantly lower than the other, the ladder might topple over. However, if the two sides of the ladder are close in height, the ladder stays standing. In the same way, if the heights of the subtrees in a height-balanced tree are similar, the tree remains stable and functional.

AVL trees are a type of height-balanced tree where the difference in height between left and right subtrees is at most 1 at every node.

The AVL tree, named after its inventors, is significant because it guarantees that the time complexity of operations is logarithmic. By maintaining strict balancing criteria, AVL trees ensure a predictable and efficient performance for searching, insertion, and deletion. Each node checks its children's heights and may require rebalancing if the height difference exceeds the allowed limits.

Think of AVL trees as a well-organized work desk. If papers, supplies, and tools are scattered chaotically, finding what you need becomes a tedious task. Regularly organizing these items so that everything is equally accessible makes it much easier to find the right tool quickly. Similarly, AVL trees ensure that each operation remains fast by keeping the data balanced.

It is essential to rebalance the tree whenever an insertion or deletion alters the structure, ensuring the height difference remains within the acceptable range.

Whenever a node is added or removed from an AVL tree, it could lead to a situation where the height difference at a certain node exceeds 1 (the balance condition). To correct this, rotations (such as right or left rotations) are performed on the affected node to restore balance. This rebalancing is done bottom-up, meaning we check all ancestor nodes of the modified node, fixing any imbalances that result from the operation.

Imagine a balancing act in a circus—if one performer adds an extra weight, they risk toppling over. To adjust, they may need to shift their position or redistribute weights across their bodies to maintain balance. Just as the performer repositions to keep steady, we apply rotations to maintain tree balance after modifying its structure.

--