通过预处理检查 O(1) 中的 2 个树节点是否相关(祖先/后代) [英] 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 = # 节点数)
- 允许预处理
就是这样.我将在下面介绍我的解决方案(方法).如果你想先想想自己，请停下来.
对于预处理，我决定进行预排序(首先递归遍历根，然后是子节点)并为每个节点指定一个标签.
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) 中相关(即祖先-后代)，我将检查其中一个的标签是否是前缀"别人的标签.虽然我不确定这样的标签是否可以被认为占据 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) 的预处理时间和 O(n) 空间内完成，用 O(1) 查询时间，如果你存储预购号和每个顶点的后序编号并使用这个事实:
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:
对于树 T 的两个给定节点 x 和 y，如果且仅当 x 在 T 的前序遍历中出现在 y 之前且在 y 之后在后序遍历中.
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.
(来自此页面:http://www.cs.arizona.edu/xiss/numbering.htm)
您在最坏的情况下所做的是 Theta(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).
这篇关于通过预处理检查 O(1) 中的 2 个树节点是否相关(祖先/后代)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
