|
Answer
|
One possible solution involves a red-black tree
of adjacency lists. To be more precise, we place
the node labels in a red-black tree, where
each node has the following fields:
key[x] : label
(these are the "u"'s in the question)
left[x], right[x], p[x], color[x]
(as usual)
list[x] : points to the adjacency list
This set-up allows us to perform insert, delete and
search in O(log n) time. However, as each adjacency list
nmay hold up to n-1 nodes, the edge operations are
Omega (n) in the worst-case. Therefore, each
adjacency list too is implemented as a red-black tree.
That is, list[x] will point to the root of
a red-black tree.
These adjacency-list red-black trees have cells/nodes
with the following fields:
key[x] : label
(these are the "v"'s in the question)
(that is, if we are in the red-black tree
for u, then the presence of v indicates
the presence of edge (u,v))
left[x], right[x], p[x], color[x] (as usual)
It is clear how to perform insertedge(u,v) and searchedge(u,v):
first find u in the main red-black tree, which leads
to the root of the red-black tree for u. In this tree,
find v for a search and insert v for insertedge.
For insertedge, we also insert u in the tree for v.
deleteedge(u,v) deletes v from the u-tree and u from
the v-tree.
All operations take O(log n) in the worst case.
We now return to delete(u). It is the only remaining
problem: deleting the tree for u is simple and takes
O(1) time. However, from each v-tree we need to
eliminate the u-entry. This is too much work. Instead,
we leave the node in the tree, and check the
legality of a node during a searchedge by
checking whether u is indeed a valid label (in O(log n)
time, as the labels are picked from a set of
size at most n).
As a second solution,
we may replace the small adjacency list red-black trees
by one red-black tree for all edges.
The ordering needed to do this is as follows:
first order the nodes of an edge pair, so that u < v
for edge (u,v). Then (u,v) is < (w,z) if u < w or
if u=w and v < z. (This is called lexicographical ordering.)
This tree can have up to n^2 elements, but its
height is still O(log n).
|