algorithm - 二叉搜索树交集

Question

我有 2 个二叉搜索树 T1 和 T2，节点数相同 n >= 1。对于每个节点 P，我们有 LEFT(P) 和 RIGHT(P) 用于节点之间的链接，KEY(P) 用于关闭节点。 T1 的根是 R1，T2 的根是 R2。我需要一个线性算法来确定在 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() 值的树。

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

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

---

在回答您最初的提议时:

Is this a linear algorithm?

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