Advanced Data Structures

1. Why isn't it enough to implement Tree_Link(u,w) using Find_Path(w) rather than expose(w)? (Hint: For the analysis of the number of splices, line -5 on page 63, show an example of the destruction of too many heavy solid edges.)

2. Show that the update of accounting information can be performed in constant time during each of the following operations:
   1. a single rotation of a BST as in Section 5.3;
   2. the operation disassemble(v), given a root v of a BST implementing Path_with_Cost.
   3. the operation assemble(u,v,w), given roots u, v, and w of BSTs implementing Path_with_Cost.

3. Correct the three wrongs in Figure 5.5(b).

4. Execute "by hand" expose(u) in the tree in Figure 5.5(a) (provide trace by drawing the intermediate virtual trees).

5. Provide (and prove correct) a loop invariant to show that the function Find_Path_Cost (page 67) returns correct value.

Prove that the total weight of a vertex is equal to the number of its descendants in its virtual tree (page 68, line 3).