Geek Answers Handbook

Check if 2 tree nodes (ancestor / descendant) in O (1) are related to preprocessing

Check if 2 nodes of the tree are connected (i.e. ancestor descendant)

  • solve it O (1) times, with O (N) space (N = # nodes)
  • pre-processing allowed.

What is it. I will move on to my decision below. Please stop if you want to think first.

For pre-processing, I decided to pre-order (recursively go through the root first, then the children) and give a label to each node.

Let me explain the shortcuts in detail. Each label will consist of comma separated natural numbers, such as "1,2,1,4,5" - the length of this sequence is (depth node + 1). For example. root label "1", root children will have labels "1,1", "1,2", "1,3", etc. The nodes of the next level will have labels like "1,1,1", "1,1,2", ..., "1,2,1", "1,2,2", ...

Suppose that the “order number” of a node is an “index based on 1 of this node” in its parent list.

General rule: the node label consists of its parent label, followed by a comma, and the "order number" of the node.

Thus, in order to answer if two nodes are connected in O (1) (i.e., the descendant ancestor), I will check whether the label of one of them is a “prefix” of the other label. Although I'm not sure that we can assume that such labels occupy O (N) space.

Any criticism is expected with corrections or an alternative approach.

+7
source share
3 answers

You can do this at O ​​(n) pre-processing time and O (n) space with O (1) request time if you save the pre-order number and post-mapping number for each vertex and use this fact:

For two given nodes x and y of the tree T, x is the ancestor of y if and only if x occurs before y in the bypass of proviso T and after y in the postoperative bypass.

(From this page: http://www.cs.arizona.edu/xiss/numbering.htm )

What you did in the worst case is Theta (d), where d is the depth of a higher node, and therefore not O (1). Space is also not O (n).

+11
source

if you consider a tree where the node in the tree has n / 2 children (say), the time for setting labels will be higher than O (n * n). So this labeling scheme does not work ...

+1
source

There are linear algorithms for minimum total ancestor time (at least autonomous). For example, look here . You can also look at tarjan offline LCA algorithm . Please note that these articles require you to know the pairs for which you will perform LCA in advance. I think there are also online time algorithms for precalculating time, but they are very complex. For example, there is a linear preliminary estimation time algorithm for a minimum range query problem. As far as I remember, this solution went through the LCA problem twice. The problem with the algorithm is that it had such a large constant that it requires huge input to be faster than the O (n * log (n)) algorithm.

There is a much simpler approach that requires O (n * log (n)) additional memory and is again responsible for constant time.

Hope this helps.

0
source

More articles:


All Articles