是否可以仅通过 O(n) <-比较来提取 < 上二叉搜索树的给定前序和 post 序？
Can one extract the in-order given pre- and post-order for a binary search tree over < with only O(n) <-comparisons?
假设有一个二叉搜索树 B，它不一定是平衡的，在某个域 D 上具有严格的顺序关系 < 和 n 个元素。
给定 B 提取的预序 R，post-序 T：
- 是否可以在不访问
< 的情况下在 O(n) 中计算 B 的有序 S？
- 是否可以仅使用与
< 的 O(n) 次比较来计算 B 的有序 S？
- 此外，是否可以在总复杂度 O(n) 中计算 S？
注意：这是对现已删除的未答复 question.[的重新post =15=]
1。 In-order 没有关系 <
如 中所述，这是不可能的。简而言之，输入 R = cba, T = abc 是模棱两可的，可能源于这两棵树：
a a
/ \
b b
\ /
c c
S = bca S = acb
2。 In-order 在 O(n) 次比较中
使用 < 关系，可以像上面那样突然区分树，尽管产生相同的 pre-order R 和 post-order T。给定：
R = Ca
with C a 的子节点的任意 non-empty 范围 C = u...v（即范围以 u 开始并以 v 结束）一个可以推断如下：
(1) a < u -> a has 1 direct child (to its right) -> all children are greater than a
(2) v < a -> a has 1 direct child (to its left) -> all children are less than a
(3) otherwise -> a has 2 direct children
(1) 和 (2) 中的递归是微不足道的，我们花费了 O(1) <.在 (3) 的情况下，我们有以下形式：
R = XbYca
T = abXcY
其中 X 和 Y 是任意序列。我们可以将其拆分为递归步骤：
R = XbYca
T = abXcY
/ \
R = Xb R = Yc
T = bX T = cY
请注意，这不需要与 < 进行比较，但需要拆分两个范围。由于 X 和 Y 不需要相同的长度，找到 splitting-point 需要我们在 R 中找到 b，这可以在 O(n) 中为递归树的每一层完成。所以我们总共需要 O(n*d) 次相等比较，其中 d 是原始二叉搜索树 B（以及镜像 B 的递归树）的深度。
在每个递归步骤中我们最多使用 2 < 次比较，取出范围中的一个元素，因此我们不能使用超过 2*n < 次比较（这是在 O( n)).
3。 In-order 总计 O(n)
在上面给出的算法中，问题是如果不能对所有元素进行查找 table，则找到分割包含所有子元素的范围的点不能比线性时间更好。
但是，如果定义 B 的宇宙足够小，可以为所有条目创建索引 table，那么可以 pre-parse R（例如 R = xbyca）在 O(n) 中创建一个 table 像这样：
a -> 4
b -> 1
c -> 3
d -> N/A
e -> N/A
....
x -> 0
y -> 2
z -> N/A
只有在可行的情况下，才能使用 2 中描述的算法实现整体 O(n)。它消耗 O(2^D) space。
是否有可能在 O(n) 中生成 in-order S。
我没有这方面的证据，但我认为这是不可能的。理由是这个问题与比较排序太相似了，不能比线性排序更好。
在“2”中。我们摆脱了线性比较，因为我们可以利用输入的结构结合大量相等性检查来至少在局部重建二叉搜索树的原始结构。但是，我看不出如何在不到线性时间内提取每个 sub-tree 的大小。
假设有一个二叉搜索树 B，它不一定是平衡的，在某个域 D 上具有严格的顺序关系 < 和 n 个元素。
给定 B 提取的预序 R，post-序 T：
- 是否可以在不访问
<的情况下在 O(n) 中计算 B 的有序 S？ - 是否可以仅使用与
<的 O(n) 次比较来计算 B 的有序 S？ - 此外，是否可以在总复杂度 O(n) 中计算 S？
注意：这是对现已删除的未答复 question.[的重新post =15=]
1。 In-order 没有关系 <
如
a a
/ \
b b
\ /
c c
S = bca S = acb
2。 In-order 在 O(n) 次比较中
使用 < 关系，可以像上面那样突然区分树，尽管产生相同的 pre-order R 和 post-order T。给定：
R = Ca
with C a 的子节点的任意 non-empty 范围 C = u...v（即范围以 u 开始并以 v 结束）一个可以推断如下：
(1) a < u -> a has 1 direct child (to its right) -> all children are greater than a
(2) v < a -> a has 1 direct child (to its left) -> all children are less than a
(3) otherwise -> a has 2 direct children
(1) 和 (2) 中的递归是微不足道的，我们花费了 O(1) <.在 (3) 的情况下，我们有以下形式：
R = XbYca
T = abXcY
其中 X 和 Y 是任意序列。我们可以将其拆分为递归步骤：
R = XbYca
T = abXcY
/ \
R = Xb R = Yc
T = bX T = cY
请注意，这不需要与 < 进行比较，但需要拆分两个范围。由于 X 和 Y 不需要相同的长度，找到 splitting-point 需要我们在 R 中找到 b，这可以在 O(n) 中为递归树的每一层完成。所以我们总共需要 O(n*d) 次相等比较，其中 d 是原始二叉搜索树 B（以及镜像 B 的递归树）的深度。
在每个递归步骤中我们最多使用 2 < 次比较，取出范围中的一个元素，因此我们不能使用超过 2*n < 次比较（这是在 O( n)).
3。 In-order 总计 O(n)
在上面给出的算法中，问题是如果不能对所有元素进行查找 table，则找到分割包含所有子元素的范围的点不能比线性时间更好。
但是，如果定义 B 的宇宙足够小，可以为所有条目创建索引 table，那么可以 pre-parse R（例如 R = xbyca）在 O(n) 中创建一个 table 像这样：
a -> 4
b -> 1
c -> 3
d -> N/A
e -> N/A
....
x -> 0
y -> 2
z -> N/A
只有在可行的情况下，才能使用 2 中描述的算法实现整体 O(n)。它消耗 O(2^D) space。
是否有可能在 O(n) 中生成 in-order S。
我没有这方面的证据，但我认为这是不可能的。理由是这个问题与比较排序太相似了，不能比线性排序更好。
在“2”中。我们摆脱了线性比较，因为我们可以利用输入的结构结合大量相等性检查来至少在局部重建二叉搜索树的原始结构。但是，我看不出如何在不到线性时间内提取每个 sub-tree 的大小。