Homework 6

Handed out: Th Nov 3
Due: Th Nov 10 at beg. of class

1. 14.1-6 p 307

2. Augment RB trees so that the following operation
can be implemented in O(log n) time:
Given a pointer to a node x in tree T, SMALLER(T,x)
returns the sum of all elements in T that are less than x.
Assume that the elements in T are all distinct.
- What field do you need to add in each node?
- Using that field, how can you implement the new operation
efficiently?
- Reason that the field can be maintained efficiently
while executing Insert and Delete operations.
Hint: Similar to OS-Rank(T,x) that was discussed in class.

3. 15-2 p 364

4. 15-6 p 368

5. EC 15-5 p 367