Solve b)

Exercise 7 We augment a red-black tree T with a field f. For each example determine if the additional information can be maintained under insertions and deletions without affecting the O(log n) running time. Use the red-black augmentation theorem (give expressions for the new field) or give a counter-example to show that more than O(log n) time is needed. Every node v is augmented with a field f storing ... (a) [2 points) ... the value of its smallest descendant. (b) [2 points) ... the sum of all elements larger than the element at v. Exercise 7 We augment a red-black tree T with a field f. For each example determine if the additional information can be maintained under insertions and deletions without affecting the O(log n) running time. Use the red-black augmentation theorem (give expressions for the new field) or give a counter-example to show that more than O(log n) time is needed. Every node v is augmented with a field f storing ... (a) [2 points) ... the value of its smallest descendant. (b) [2 points) ... the sum of all elements larger than the element at v