两个二叉搜索树均等的无序阵列构建 [英] Equality of two binary search trees constructed from unordered arrays

问题描述

鉴于大小的两个未排序数组N分别，我们要确定二叉搜索树构建从他们的将是等于或不。

因此​​，阵列的元素被拾取并插入一个基本（没有平衡，无红黑色，什么都没有）二叉搜索树。 直接给出两个数组，我们可以判断它们是否会引起同一个二叉搜索树。

So, the elements of the array are picked and inserted into a basic (no balancing, no red-black, nothing) binary search tree. Given directly two arrays, can we determine whether they give rise to the same Binary Search Tree.

有一个明显的O（N ² ）最坏情况下的时间复杂度的解决方案：构建两棵树，并比较他们的平等。

There is an obvious O(N²) worst case time complexity solution: Construct two trees, and compare their equality.

是否有一个O（N）或O（N日志N）的解决办法？

这我试图提取问题的想法是：为BST的结构依赖于元件的相对位置。例如，如果不存在具有值51紧邻20在一个数组中的元素，必须有其他的阵列在20和51之间没有任何元素的树木为等于（否则20的右子将是数，而不是51 ）。

The idea of the problem that I am trying to extract is: The construction of the BST depends on the relative positions of the elements. For example, if there is an element with value 51 immediately next to 20 in one array, there must be no element between 20 and 51 in the other array for the trees to be equal (otherwise 20's right child would be that number, not 51).

我也尝试了一些方法：

1. 的幼稚的做法：构建两棵树和比较
。
2. 我使用了一个有趣的变体，其中编号的阵列划分成2（一个较小的子阵列和一个子阵列大于枢轴），并递归通过左阵列向左子，另一个向对。就地和厚脸皮的，但还是O（N ² ）。
3. 甲朋友试图施加最长子序列到它并发现它，然后比较，但是这是不正确。
4. 我正在大举进入可能解决它与LinkedHashMap中，但我有一个艰难的时间证明了其正确性。

1. The naive approach: construct 2 trees and compare.
2. I used an interesting variant where I'd partition the array into 2 (one smaller sub-array and one sub-array bigger than the pivot), and recursively pass the left array to the left child, and the other to the right. In-place and cheeky, but still O(N²).
3. A friend tried applying the longest sub-sequence to it and finding it and then comparing, but that is incorrect.
4. I was making inroads into maybe solving it with a LinkedHashMap, but I am having a tough time proving its correctness.

帮助，以及对解决这一问题将是非常美联社preciated任何提示。

Help, and any hints towards solving this problem would be much appreciated.

推荐答案

构建两棵树和比较不必为O（N ^ 2）。您可以使用一个辅助的数据结构，可以让你找到在澳新节点的位置（日志N），而不是O（N），从而使BST建设为O（N日志N），即使正在建造的BST不均衡。

"Construct two trees and compare" does not have to be O(N^2). You can use an auxilliary data structure that lets you find the position of the new node in O(log N) instead of O(N), so that the construction of the BST is O(N log N) even if the BST being constructed is not balanced.

通过每个空的位置（即在一个节点一个儿童免费插槽） POS 在BST，有一个相关的间隔（a_pos，B_POS ）（值之一可能是+/-无穷大），使得对价值的新节点 v 将在 POS 当且仅当该值是在间隔

With each empty position (i.e. a free child slot in a node) pos in a BST, there is an associated interval (a_pos,b_pos) (one of the values might be +/- infinity), such that new node for value v will be created at pos if and only if the value is in the interval.

您可以存储间隔均衡区间树，所以，对于每个新到达的值的位置可以在O（日志N）被发现。区间树的更新也为O（log N），因为你只更换一个区间有两个。

You can store the intervals in a balanced interval tree, so that the position for each new arriving value can be found in O(log N). The update of the interval tree is also O(log N), as you only replace one interval with two.

（实际上，间隔从未重叠，所以的辅助结构可以是一个普通的旧（平衡）BST代替间隔树。）

(Actually, the intervals never overlap, so the auxilliary structure can be a plain old (balanced) BST instead of an interval tree.)

例如：

看看下面的非平衡BST，对于数组preFIX构建[1,10,2,9,3，...]

Take the following non-balanced BST, constructed for an array prefix [1,10,2,9,3, ...]

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

字母 AF 表示，其中一个新的节点可以放置（无树叶）可能的地方。与每个字母的，有一个相关联的时间间隔，如下：

The letters a-f denote the possible places where a new node can be placed (nil leaves). With each of the letter, there's an associated interval, as follows:

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

有一个值的新节点 v 将被添加到BST在由时间决定的地方， v 所属。零点将结束在 A ，5日 D 等。关键思想是将树以外存储该信息。

A new node for a value v will be added into the BST at the place determined by the interval that v belongs to. Zero will end up at a, 5 at d and so on. The key idea is to store this information outside of the tree.

如果你能有效地重新present上表（链​​接到实际的树节点），增加新的节点树将采取O（访问表）+ O（1）。在O（1）重新presents将节点添加到非平衡BST，因为你已经知道你在哪里把它。添加5将不需要与1,10,2,9和3，而是比较会抬起头来桌子，并直接放置在 D 。

If you can efficiently represent the above table (with links to the actual tree nodes), adding new node to the tree will take O(access to table) + O(1). The O(1) represents adding the node into the non-balanced BST, given that you already know where you place it. Adding 5 will not require comparing with 1,10,2,9 and 3 but instead will be looked up in the table and and placed directly at d.

在你将新节点，你显然还需要更新表。数据结构重新present表可能是一个区间树（ HTTP：//en.wikipedia。组织/维基/ Interval_tree ）。

Once you place the new node, you obviously also have to update the table. The data structure to represent the table could be an interval tree ( http://en.wikipedia.org/wiki/Interval_tree ).

这篇关于两个二叉搜索树均等的无序阵列构建的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！