9

给定两个大小为 N 的未排序数组，我们要确定由它们构造的二叉搜索树是否相等。

因此，数组的元素被挑选出来并插入到一个基本的（没有平衡，没有红黑，什么都没有）二叉搜索树中。直接给定两个数组，我们能否确定它们是否产生相同的二叉搜索树。

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

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

我试图提取的问题的想法是：BST 的构造取决于元素的相对位置。例如，如果在一个数组中紧挨着 20 有一个值为 51 的元素，则在另一个数组中必须没有 20 到 51 之间的元素才能使树相等（否则 20 的右孩子将是那个数字，而不是 51 ）。

我确实尝试了几种方法：

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

帮助，以及解决此问题的任何提示将不胜感激。

4

4 回答 4

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.

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

于 2012-12-30T20:47:10.680 回答
1

“构建两棵树并进行比较”不一定是 O(N^2)。您可以使用辅助数据结构，让您在 O(log N) 而不是 O(N) 中找到新节点的位置，因此即使正在构建 BST，BST 的构建也是 O(N log N)不平衡。

对于 BST 中的每个空位置（即节点pos中的空闲子槽），都有一个关联的间隔(a_pos,b_pos)（其中一个值可能是 +/- 无穷大），这样v当pos且仅当该值在区间内。

您可以将间隔存储在平衡的间隔树中，以便可以在 O(log N) 中找到每个新到达值的位置。间隔树的更新也是 O(log N)，因为您只需将一个间隔替换为两个。

（实际上，区间永远不会重叠，因此辅助结构可以是普通的旧（平衡）BST，而不是区间树。）

例子：

采用以下非平衡 BST，为数组前缀 [1,10,2,9,3, ...] 构建

  1
 /  \
a  10
   / \
  2   f
 / \
b   9
   / \
  3   e
 / \
c   d

字母a-f表示可以放置新节点的可能位置（零叶）。每个字母都有一个相关的间隔，如下所示：

[-inf,1] -> a
[1,2] -> b
[2,3] -> c
[3,9] -> d
[9,10] -> e
[10, +inf] -> f

一个值的新节点v将被添加到 BST 中由所属区间确定的位置v。零将结束于a， 5 在d等。关键思想是将这些信息存储在树之外。

如果您可以有效地表示上表（带有指向实际树节点的链接），那么向树中添加新节点将需要 O(access to table) + O(1)。O(1) 表示将节点添加到非平衡 BST 中，前提是您已经知道放置它的位置。添加 5 不需要与 1,10,2,9 和 3 进行比较，而是会在表格中查找并直接放置在d.

放置新节点后，显然还必须更新表。表示表格的数据结构可以是区间树（http://en.wikipedia.org/wiki/Interval_tree）。

于 2012-12-30T22:18:38.563 回答
0

尝试这个：

int identical(struct node* a, struct node* b) 
{
    if (a==NULL && b==NULL)
    {
        return(true);
    } 
    else if (a!=NULL && b!=NULL)
    {
        return(a-> data == b-> data && identical(a->left, b->left) && identical(a->right, b->right));
    } 
    else 
        return(false);
}
于 2013-09-13T07:01:29.560 回答
0

我想出了以下代码。它工作正常，尽管分区效率低下。

    bool isBST (vector<int> vec1, vector<int> vec2) {
    if (vec1.size() == 0 && vec2.size() == 0)
        return true;
    if (vec1.size() != vec2.size())
        return false;
    if (vec1[0] != vec2[0])
        return false;

    vector<int> temp1;
    vector<int> temp2;
    vector<int> temp3;
    vector<int> temp4;
    for (int k = 1; k < vec1.size(); k++) {
       if(vec1[k] < vec1[0])
           temp1.push_back(vec1[k]);
       else
           temp2.push_back(vec1[k]);

       if(vec2[k] < vec2[0])
           temp3.push_back(vec2[k]);
       else
           temp4.push_back(vec2[k]);
    }

    return isBST(temp1, temp3) && isBST(temp2, temp4);

}
于 2013-10-15T10:50:16.507 回答