3
$\begingroup$

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of membership of vertex $u \in V$? i.e., is $u\in V_1$?

Ideally a data structure with at most polynomial space complexity.

An example is as follows:

I have a tree that I will remove an edge from it to induce a forest of two tree components. Then, I want to attach another edge to reconnect the components to produce a new tree. This procedure is then repeated M times. I am looking for a data structure that enables this process to run in O(M) time.

Improve this question
$\endgroup$
  • $\begingroup$ Please augment you question: Do you have any requirements regarding the representations of each set of vertices? Why, given an instance of a generic tree data structure, wouldn't "the original tree" (with the edge in question removed) and the sub-tree thus disconnected suffice? Does $T$ need to be kept intact? $\endgroup$ – greybeard Aug 29 '20 at 7:37
  • 1
    $\begingroup$ Is this correct? You repeat the following a bunch of times: 1) User provides an edge, and you remove this edge. This splits the tree into 2 parts: $V_1$ (contains node $1$) and $V_2 = V \setminus V_1$. 2) The user provides vertices $u_1, \ldots, u_k$. For each $u_i$ you should say if it belongs to $V_1$. 3) A user provides an edge $(u,v)$, where $u \in V_1$, $v \in V_2$. You connect the trees using this edge. $\endgroup$ – Dmitry Aug 29 '20 at 10:51
  • 1
    $\begingroup$ It's too much work to describe it properly, so I'll outline the main ideas: 1) You select a root and use Euler tour to represent the tree. 2) Each subtree corresponds to a segment in this tour. You should just remove this segment. Merging requires some work, but is similar. 3) To do the previous operation efficiently, you can use treaps. 4) To determine the segment for a subtree, for each node you can store pointers on the leftmost and the rightmost treap node in the tour. $\endgroup$ – Dmitry Aug 30 '20 at 0:30
  • 1
    $\begingroup$ For merging, you'll have to reorganize tree corresponding to $V_2$, so that the connected node ($v$) becomes a root. Essentially, you'll need to move everything from the left of $left(v)$ to the right of the tree. Again, treaps can do this efficiently. $\endgroup$ – Dmitry Aug 30 '20 at 0:41
  • 1
    $\begingroup$ Please edit the question to describe the operations that the data structure must support. I'm having a hard time understanding what the requirements are. Please don't leave information only in the comments. Instead, revise the question, then flag comments as 'no longer needed' once they are addressed. We want questions to stand on their own, so that people don't need to read the comments to understand what you are asking. $\endgroup$ – D.W.♦ Aug 30 '20 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.