3
$\begingroup$

There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries:

  • Set(X): change the given vertex X from type 0 to type 1,
  • Dist(X): find the shortest path from X to a node of type 1 and return the length of this path. This will return zero if X is of type 1.

The naive method would be to just maintain a tree and on every update change the type of vertex; to answer queries of second type, run a bfs starting at X and stop as soon as a vertex with type 1 is found. With this simple scheme, Set(X) would run in $O(1)$ time, but Dist(X) would take $O(n)$ time.

However, in my application the number of queries and number of nodes are both of the order of $10^5$, so the naive method is too slow. In particular, $O(n)$ time is too slow.

Can somebody suggest a better algorithm for doing this?

$\endgroup$
  • $\begingroup$ There is a technique for processing the queries offline. First, chunking them up into blocks and then sorting those within a block according to some criteria. I read the literature but couldn't figure out how to adapt that strategy in this case. Any help would be appreciated. $\endgroup$ – user3286661 Nov 5 '15 at 14:10
1
$\begingroup$

One can improve your naive method by augmenting the data structure. At each node in the tree, store an extra field that contains the distance to the closest descendant of type 1. Assume each node as a pointer to its parent. Let the depth of the tree be $d$.

Now Set(X) takes $O(d)$ time: you traverse the parent pointers to visit each of X's ancestors and update their distance field. Also Dist(X) takes $O(d)$ time: the distance field for X tells you the shortest path to a descendant of X, and by looking at the distance fields for the siblings of the nodes along the path from X to the root, you can find the shortest path to a non-descendant of X. Thus, both operations can be done in $O(d)$ time.

If the tree is balanced, we'll have $d = O(\lg n)$, so both operations run in $O(\lg n)$ time -- a significant improvement over the naive method you mention.

Of course, in the worst case the depth of the tree could be $\Theta(n)$, so this method won't help for such trees. But in practice many trees (e.g., random trees) tend to have depth $O(\lg n)$. And if you need an algorithm that works for all trees, you might be able to take advantage of a heavy-light decomposition to achieve good worst-case running time bounds.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.