二叉搜索树交集

Question

我有 2 个二叉搜索树 T1 和 T2，节点数相同 n >= 1。对于每个节点 P，我们有 LEFT(P) 和 RIGHT(P) 用于节点之间的链接，KEY(P) 用于值离开节点。 T1 的根是 R1，T2 的根是 R2。我需要一个 linear 算法来确定在 T1 和 T2 中都找到的值。

到目前为止我的想法是对T1进行中序遍历并在T2中搜索当前元素，如下所示：

inorder(node)
   if node is not NULL
      inorder(LEFT(node))
      if find(KEY(node), R2)
            print KEY(node)
      inorder(RIGHT(node))

其中 find(KEY(node), R2) 对树 T2 中的 KEY(node) 执行二进制搜索。

这是正确的解决方案吗？这是线性算法吗？（我知道遍历是 O(n) 复杂度）。或者，还有另一种方法可以将 2 个二叉搜索树相交？

谢谢！

Answer 1

您当前的中序遍历使用递归来执行任务。这使得很难同时运行多个。

因此，首先我将重写方法以使用显式堆栈 (example here in C#)。现在，复制所有状态，以便我们同时执行两棵树的遍历。

在任何点我们准备从两棵树中产生一个值，我们比较它们的KEY()值。如果不相等那么我们继续遍历KEY()值较小的树

如果两个值相等，那么我们产生该值并继续遍历两个树。

这在概念上类似于合并两个已排序的序列 - 我们需要做的就是检查每个序列要产生的 "next" 值，产生两个值中较低的值，然后向前移动那个序列。

对您最初提议的答复：

Is this a linear algorithm?

没有。对于您在中序遍历期间访问的每个节点，您正在调用 find 即 O(log n)。所以你的完整算法是（如果我没记错的话）O(n log n).

二叉搜索树交集

Binary search tree intersection

algorithm

tree

complexity-theory

binary-search-tree