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). |
Solution |
Assume that all external nodes are
non-existent and thus correspond to nil
pointers.
Let k be the key to be inserted
in the tree with root r.
First we find the parent y of the new node x.
create new node x key[x]=k left[x]=right[x]=nil rank[x]=1 color[x]=red y=r if k < key[y] then z=left[y] else z=right[y] while z != nil do: y = z if k < key[y] then z=left[y] else z=right[y] (y is now the parent) p[x]=y if k < key[y] then left[y]=x else right[y]=xNext we iterate two levels at a time as long as the parent and uncle of x are red. Without loss of generality we will assume that the color of the root is always black. The procedure uncle(x) is obvious: if p[x]=nil then return nil (x is the root) else if p[p[x]]=nil then return nil (p[x] is root) else if left[p[p[x]]]=p[x] then return right[p[p[x]]] else return left[p[p[x]]]With this in hand, we tackle the algorithm: while uncle(x) != nil and color[p[x]]=red and color[uncle(x)]=red do color[p[x]]=black color[uncle(x)]=black x=p[p[x]] color[x]=red rank[x]+=1 if uncle(x) != nil and color[p[x]]=red and color[uncle(x)]=black do ROTATION! |
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 pointed to by u searchmax(a,b) ; find the maximum y-key among all nodes with x-key between a and b |
Solution |
One possibility is a red-black tree organized
on the x-keys. This will guarantee that the height
is O(log n). As augmented fields we have:
y-key[u] max[u]: pointer to the node with the maximal y-key in the subtree of uIt is trivial to perform search, delete and insert in O(log n) time, following the algorithms for red-black trees. We need only point out how max[.] is updated. But when a key is inserted, max[.] can only change for the keys on the insertion path, and can thus be updated on the fly. Similarly. the red-black tree rotations cause no problems. The tricky part is searchmax(a,b). First we find the deepest node u on the search paths for both a and b. This was done in the tutorial and won't be repeated here. Clearly, its key is between a and b. If u does not exist, then searchmax(a,b) returns nil. If u exists, we proceed as follows: x=u MAXKEY=y-key[x] while x!=nil do: if key[x] > a then x=left[x] else x=right[x] if x!=nil and key[x] in [a,b] then MAXKEY = max (y-key[x], y-key[max[right[x]]], MAXKEY) x=u while x!=nil do: if key[x] < b then x=right[x] else x=left[x] if x!=nil and key[x] in [a,b] then MAXKEY = max (y-key[x], y-key[max[left[x]]], MAXKEY) return MAXKEY |
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. |
Solution |
First of all, if a tree with n nodes
of which 50% are marked deleted is given,
then we can make a new red-black tree
consisting only of the good (non-deleted)
nodes in time about n. To do so,
first list the nodes in order (in linear
time), omitting marked nodes of course.
Then make a binary search tree
of minimal height h = floor(log_2 n)
in linear time (as we saw in class).
In this tree, all levels except the last one
are full. Color all the nodes of the
full levels black.
Make all the nodes in the last level red, and
you have a red-black tree.
The time for this rebuilding is equal to
n, say.
Consider the first part, in which we can
clearly perform at most one rebuild operation
in the given n/2 iterations. In that case,
we have at most C (n/2) log (3n/2) cost
for the standard operations. To this, we add a
time cost of n for a rebuild at the end
(because a rebuild can only occur if all n/2
operations were lazy-deletes).
For part 2, we will divide the time cost
of a rebuild of a tree of size n
over the n/2 previous iterations (none of
which were rebuilds, by the way), giving a cost
of 2 to each iteration. This is just another
way of accounting. In this manner,
each iteration "costs" 2 plus the real time
it takes for whatever we want to do, the total
being less than
2 + C log (n)as the total tree size is at most n at any given time. Thus, summed over all iterations, the time is bounded by n( 2 + C log (n) ) = O(n log n). |
Copyright © 2000 Luc Devroye. Email: luc@cs.mcgill.ca.