1. Explain why performing a rotation in an n-node binary tree when using the array-based representation of Section 8.3.2 takes Ω(n) time. 2. Repeat the previous problem, considering the case in which...

1. Explain why performing a rotation in an n-node binary tree when using the array-based representation of Section 8.3.2 takes Ω(n) time.

2. Repeat the previous problem, considering the case in which y’s children start with different heights.

May 26, 2022