algorithm - 查找两个二叉搜索树的公共(public)元素的最佳方法

Question

我有两个 BST，由具有唯一 ID 的元素组成。我想找到这些 BST 的共同元素。

最简单的方法是一个一个地获取第一个BST的元素，然后将它们与第二个BST进行检查。但由于我必须无数次地重复这种比较，所以我正在寻找最快的算法。

Answer 1

假设您的两棵树的大小分别为 m 和 n。您提出的解决方案及时有效Θ(n log(m))(或相反)。实际上，您可以按时Θ(m + n) 执行此操作。

让我们从一个相关的问题开始。假设您有两个列表，每个列表都已排序，大小分别为 m 和 n。您可以很容易地找到 Θ(m + n) 中常见元素的数量。只需放置两个“指针”，每个列表一个。通过比较这两项，您可以确定是增加第一个指针、第二个指针还是两者(最后一种情况是找到相同元素时)。 (编辑 - 您可以在 this question 的答案中看到这一点。)

BST 的中序遍历在概念上与排序链表的遍历相同，因此您可以在此处执行相同的操作。