Question: 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
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
Step by Step Solution
3.30 Rating (156 Votes )
There are 3 Steps involved in it
Rebalancing of a subtree during a deletion with both children of y having the s... View full answer
Get step-by-step solutions from verified subject matter experts
