| Question 1 | Red-black trees. In class, we saw a rough algorithm for insert. Using the fields color[.], rank[.], left[.], right[.], key[.] and p[.], give the full algorithm, rotation excluded (so, you may assume that rotation works fine). |
| Question 2 |
Data structure.
Suggest a data structure for
data with two keys, x and y, in which
we can implement the following
operations in O(log n) worst-case time:
makenull search (k) ; k is an x-key searched for insert(x,y) ; insert a node with keys x and y delete(u) ; delete node pinted to by u searchmax(a,b) ; find the maximum y-key among all nodes with x-key between a and b |
| Question 3 | Red-black tree with lazy delete. Consider a red-black tree with lazy-delete, that is, when 50% of the nodes are marked "deleted", the tree is junked and a new red-black tree is constructed from scratch from the non-marked nodes. Assume that the tree initially has n nodes, and that we perform n/2 operations from the set "search, insert, delete". With the standard red-black tree implementation, each operation would take time bounded by C log (3n/2) as the tree can have at most 3n/2 elements. The total time bound would be C n log (3n/2) = O(n log n). With lazy delete thrown in, we would like to get O(n log n) as well. Prove that. Then prove that it is still O(n log n) when we start from an empty tree and perform n arbitrary operations from the set. Hint for part 2: think about the cost of the rebuild operation in terms of the time since the last rebuild. |
Copyright © 2000 Luc Devroye. Email: luc@cs.mcgill.ca.