5.5.2 Where is the lowest leaf?

The lowest leaf of an unbalanced AVL tree has to do with the last insertion operation. For the purpose of our discussion, we’ll use a infix notation. This means that in the notation (T_A,n,T_B), T_A is the left subtree, and T_B is the right subtree when n is the root of this particular tree.

When a node n of an AVL tree is not balanced, it means one of its subtree is at least two levels higher than the other one. For the purpose of our discussion, let us assume the left tree is higher. In other words, in a subtree (T_L,n,T_R), the height of T_L is at least two more than the height of T_R.

Even though we know that T_L is the higher one, we still need to know which subtree of T_L is higher. In other words, we need to look at the subtree as ((T_LL,n_L,T_LR),n,T_R). Here, we have three subtrees, T_LL, T_LR and T_R. We know that T_LL or T_LR has a height that is one more than T_R for the subtree (T_LL,n_L,T_LR) to be 2 levels higher than T_R.

In the case that T_LL is no shorter than T_LR, we can restructure this subtree as follows: (T_LL,n_L,(T_LR,n,T_R)). In other words, n_L becomes the new root of this subtree. The restructuring is valid because the in-order traversal of the subtree still yields the same order. This restructuring requires the recomputation of the heights of nodes n and n_L.

In the case that T_LR is the highest subtree, we need to represent T_LR as (T_LRL,n_LR,T_LRR). This means that our original subtree is ((T_LL,n_L,(T_LRL,n_LR,T_LRR)),n,T_R). Given this break down, we can rearrange the tree as ((T_LL,n_L,T_LRL),n_LR,(T_LRR,n,T_R)). Note that the problem is solved because both subtrees of n_LR are now moved up, and hence the height of the tree rooted at n_LR after the rearrangement is reduced by one. This restructuring requires the recomputation of nodes n, n_L, and n_LR.

The other two cases are symmetric. If T_R is higher than T_L, then we first reexpress the tree as (T_L,n,(T_RL,n_R,T_RR)). If T_RR is higher than T_RL, then we restructure the subtree as ((T_L,n,T_RL),n_R,T_RR). This requries the recomputation of the heights of n and n_R.

If T_RL is higher than T_RR, then we represent the subtree as (T_L,n,((T_RLL,n_RL,T_RLR),n_R,T_RR)). Then, it is restructured to become ((T_L,n,T_RLL),n_RL,(T_RLR,n_R,T_RR)). This requires the recomputation of the heights of n, n_R and n_RL.