The rules for a deletion in an AVL tree specifically require that when the two subtrees of the node denoted as y have equal height, child x should be chosen to be €œaligned€ with y (so that x and y are both left children or both right children). To better understand this requirement, repeat Exercise R-11.11 assuming we picked the misaligned choice of x. Why might there be a problem in restoring the AVL property with that choice?

Repeat Exercise

Consider a deletion operation in an AVL tree that triggers a trinode restructuring for the case in which both children of the node denoted as y have equal heights. Give a schematic figure, in the style of Figure 11.12, showing the tree before and after the deletion. What is the net effect of the height of the rebalanced subtree due to the operation?

h+2 h+1 h-1 h-1 Tj T4 T, T, (a) |h+3 h+2 h+1 h-1 T4 T2 T3 (b) h+2 h+1 h+1 h-1 T2 T1 T3 T4