从无序数组构造的两个二叉搜索树的相等性

Question

给定两个大小为N的未排序数组,我们将确定从它们构造的二进制搜索树是否相等.

因此,数组的元素被选中并插入到基本(无平衡,无红黑,无任何)二叉搜索树中.直接给出两个数组,我们可以确定它们是否会产生相同的二进制搜索树.

有一个明显的O(N ²)最坏情况时间复杂度解决方案:构造两棵树,并比较它们的相等性.

是否有O(N)或O(N log N)解决方案？

我试图提取的问题的想法是:BST的构造取决于元素的相对位置.例如,如果在一个数组中有一个紧邻20的值为51的元素,则在另一个数组中必须没有20到51之间的元素才能使树相等(否则20的右子将是该数字,而不是51 ).

我尝试了几种方法:

1. 天真的方法:构建2棵树并进行比较.
2. 我使用了一个有趣的变体,我将数组分成2个(一个较小的子数组和一个比数组大的子数组),并递归地将左数组传递给左子,另一个传递给右.就地和厚脸皮,但仍然是O(N ²).
3. 一位朋友尝试将最长的子序列应用于它并找到它然后进行比较,但这是不正确的.
4. 我正在试图用LinkedHashMap解决它,但我很难证明它的正确性.

帮助,以及解决这个问题的任何提示将非常感激.

Answer 1

概括

我认为您可以通过使用范围最小查询来构造二叉树，将朴素方法从 O(N^2) 改进为 O(NlogN) 。

快速构建二叉树

假设我们要为数组 A 构造二叉树。

这个想法是首先构造一个数组 B，其中 B[i] 是 A 中第 i 个最大元素的位置。这可以通过 O(NlogN) 排序来完成。

然后，我们可以对数组 B 使用范围最小值查询，以找到给定范围 a<=i<=b 的 B[i] 的最小值。换句话说，这让我们可以找到 A 中第一个位置，其中我们的值在第 a 个和第 b 个最大元素之间。

RMQ 需要 O(N) 的时间进行预处理，然后可以在 O(1) 的时间内回答查询。

然后，我们可以递归地查找每个元素的左子元素和右子元素（如果有）并检查它们是否匹配。

伪代码

假设两个数组是 A 和 A2，为了简单起见，我们假设 A,A2 已经过预处理，使得第 i 个最大元素等于 i。

如果 find_children(1,N) 为 True，则树是相同的：

find_children(low,high)
   if high==low
      return True
   node = A[RMQ(low,high)]
   return node == A2[RMQ2(low,high)]
          and find_children(low,node-1)
          and find_children(node+1,high)

该函数对树中的每个节点（和空子指针）调用一次，因此需要时间 O(N)。

总的来说，这是 O(NlogN)，因为预处理排序需要 O(NlogN)。

解释

假设我们已将元素 20 和 51 输入到二叉树中。然后我们将 20 作为根，51 作为右子节点。要查找 51 的左孩子，我们需要查找数组中值大于 20 且小于 51 的第一个元素。该值由应用于范围 20+1->51- 的范围最小查询给出。 1.

因此，我们可以比以自然方式将它们插入二叉树更快地找到所有节点的左子节点和右子节点（仅在理论上最坏的情况下更快 - 对于典型示例，其他方法可能会更快）。