17.1.4. AVL Trees

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 type of self-balancing binary search tree. The key feature is that they maintain a balance condition based on the heights of subtrees. Specifically, the heights of the left and right subtrees of any node can differ by at most one. This constraint ensures that the tree remains approximately balanced, which contributes to maintaining efficient operations such as search, insert, and delete. This balancing feature was introduced by two individuals, Adelson-Velsky and Landis, hence the name AVL.

Imagine a pair of scales used to weigh objects. If one side is heavier than the other by too much, adjustments need to be made to restore balance. Similarly, in an AVL tree, the heights of the left and right subtrees of each node must remain balanced, akin to maintaining equilibrium on those scales.

The height is the number of nodes from the root to a leaf. For example, if I have a tree which looks like this, then here the height is 1, 2, 3, 4 because on this path we have 4 nodes. So, the heights become 4 it is a length of the longest path measured in terms of nodes.

The height of a tree is defined as the total number of nodes present on the longest path from the root node down to the furthest leaf node. For instance, in a tree where there are four nodes along the longest path, the height of that tree is 4. This measurement is essential because it helps in understanding how balanced the tree is; a lower height indicates better balance and more efficient operations on the tree.

Consider climbing a staircase. Each step represents a node, and reaching the top requires taking the longest path (i.e., the most steps). The total number of steps you took to reach the top mirrors the height of the tree. A balanced staircase enables you to climb smoothly without too many steps on one side.

Now, in 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 by at most 1.

In AVL trees, the definition of balance is based upon the height of the nodes rather than strictly their number. A tree is considered height-balanced when the height of the left and right subtrees of any given node does not differ by more than one. This relaxed condition compared to other trees allows for a more flexible structure while still preserving efficient search operations.

Think of a seesaw at a playground. If one side is not too much heavier than the other, the seesaw stays level and can function properly. Likewise, in an AVL tree, if the difference in heights of the subtrees is minimal, then the tree remains efficient just like a functioning seesaw.

So, 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 thing is treated, so we could have till this way or till this way, so we call this the slope.

In the context of AVL trees, the slope is defined as the difference between the heights of the left and right subtrees. This helps in quickly identifying whether a node is balanced. If the slope is 0, both subtrees are of equal height; if it’s +1 or -1, the tree is still balanced; but a slope of +2 or -2 signals an imbalance that needs to be corrected.

Imagine measuring the angle of a hill. If the hill is sloping too steeply on one side (say +2), it indicates a potential risk of toppling over. Similarly, in an AVL tree, a slope that exceeds +1 or -1 warns us that the tree is at risk of becoming unbalanced and needs to be adjusted.

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. So, we would have a single disturbance from minus 2 or plus 2 it will never become very badly unbalance.

When performing insertions or deletions in an AVL tree, it's crucial to maintain its balanced state. If any operation causes a node to have a slope greater than +1 or -1, the tree will be rebalanced immediately. This is done to prevent the tree from becoming unbalanced, ensuring that operations remain efficient.

Consider a tightrope walker who must adjust their weight almost instantly to maintain balance while walking. Just as the walker shifts their weight to prevent falling off the rope, an AVL tree implements rotations to realign its structure, ensuring it remains stable and supports quick searches.

--