检查2树节点在O相关的（祖先/后裔）（1）pre-处理 [英] Check if 2 tree nodes are related (ancestor/descendant) in O(1) with pre-processing

问题描述

检查2树节点是相关的（即祖先的后裔）

Check if 2 tree nodes are related (i.e. ancestor-descendant)

• 在解决这个问题的O（1）时间，用O（节点N =＃）（N）的空间
• pre-处理允许

就是这样。我会去我的解决方案（方法）以下。如果你要觉得自己先请停止。的

对于pre-处理，我决定做一个pre阶（递归地通过根部，再儿童），并在每个节点给一个标签。

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

让我解释一下细节上的标签。每个标签将包括逗号分隔的自然数的像1,2,1,4,5 - 这序列的长度等于的（节点+ 1的深度）。例如。根的标签为1，根的孩子有标签1,1，1,2，1,3等。下一级节点将具有像1,1,1标签，1,1,2，...，1,2,1，1,2,2，...

Let me explain the labels in details. Each label will consist of comma-separated natural numbers like "1,2,1,4,5" - the length of this sequence equals to (the depth of the node + 1). E.g. the label of the root is "1", root's children will have labels "1,1", "1,2", "1,3" etc.. Next-level nodes will have labels like "1,1,1", "1,1,2", ..., "1,2,1", "1,2,2", ...

假设的的订单号的一节点是这个节点的 1为基础的指数的在其父的孩子名单。

Assume that "the order number" of a node is the "1-based index of this node" in the children list of its parent.

通用规则：节点的标签是由其父标签其次是逗号和的的订单号的节点

Common rule: node's label consists of its parent label followed by comma and "the order number" of the node.

因此​​，来回答如果两个节点是相关的（即祖先的后裔）在O（1），我会检查，如果其中一人的标签是的一个preFIX 的对方的标签。虽然我不知道，如果这样的标签可以被认为占据O（N）的空间。

Thus, to answer if two nodes are related (i.e. ancestor-descendant) in O(1), I'll be checking if the label of one of them is "a prefix" of the other's label. Though I'm not sure if such labels can be considered to occupy O(N) space.

通过修复或替代方法的任何批评者的预期。

Any critics with fixes or an alternative approach is expected.

推荐答案

您可以在O做到这一点（N）preprocessing时间，O（n）的空间，用O（1）查询的时候，如果你存储在preorder号和后序数为每个顶点，并利用这一点：

You can do it in O(n) preprocessing time, and O(n) space, with O(1) query time, if you store the preorder number and postorder number for each vertex and use this fact:

对于两个给定的节点x和一个树T Y，X是y的祖先，如果和   只有当X Y T中和后的Y preorder穿越之前发生   在后序遍历。

For two given nodes x and y of a tree T, x is an ancestor of y if and only if x occurs before y in the preorder traversal of T and after y in the post-order traversal.

（在此页中：<一href="http://www.cs.arizona.edu/xiss/numbering.htm">http://www.cs.arizona.edu/xiss/numbering.htm)

什么你在最坏的情况下所做的是西塔（d）在d是更高节点的深度，并且因此不为O（1）。空间也不会为O（n）。

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

这篇关于检查2树节点在O相关的（祖先/后裔）（1）pre-处理的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！