检查两个二叉搜索树是否有相同的键

Question

我正在寻找一种顺序算法（如果存在的话），以O(n)的时间复杂度和O(1)的内存使用量来测试两个二叉搜索树是否具有相同的键，递归是允许的。
您可以这样做：进行两次同步的中序遍历，以便比较两个BST的第ith个元素。

- Angelo

---

是否具有相同的任何键，或者全部具有相同的键？（虽然“全部”是暗示的，但我想要澄清） - Mooing Duck

假设树具有父指针，那么设置一个迭代器对象以在O（n）时间和O（1）空间内执行中序遍历就很简单了。因此，只需为每个树设置一个并逐步遍历它们即可……？ - Daniel Wagner

@Daniel Wagner，谢谢你，但是每个节点没有父指针。节点的定义如下：{int 信息，节点* 左子节点，节点* 右子节点} - Angelo

使用O(1)内存，但允许递归 如果使用递归，则内存不是O(1)。 - RBarryYoung

@Matt Timmermams，是的，你可以。 - Angelo

Answer 1

如何实现这个取决于你所使用的编程语言。

在像Python这样的语言中，你只需要使用yield编写BST即可。这将创建一个保留少量状态的生成器。（根据数据结构和算法，这种情况下应该是O(1)或O(log(n))。而正如我们所知，在现实世界中，log(n)是一个常数。尽管对于像Google这样的公司来说，它是一个稍微大一些的常数……）

在没有yield的语言中，你需要安排创建一个带有搜索状态的对象，并使用可以调用的方法返回当前元素（或告诉你已完成），然后继续到下一个元素。保存状态并在进入方法时恢复它确实很麻烦，但在幕后，这就是Python为您完成的工作。

如果你想感觉非常聪明，你可以尝试自动化必要的工作。请参见http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html，了解如何使用C预处理器在C中实现此操作的令人印象深刻的演示。（这种技术实际上在一个广泛使用的程序PyTTY中使用。）

- btilly

---

正如我们所知，在现实世界中，log(n)是一个常数。在现实世界中，没有人关心算法复杂度。如果他们正在处理算法复杂度，你必须处理算法约束，例如log(n)不是常数。 - Mooing Duck

在计算能力和表达能力之间，我选择表达能力。毫无疑问，“yield”方法更简单。 - lrleon

Answer 2

注意：原先我用 O(log(n) 的空间复杂度来写这个答案，但随后出现了一个 O(1) 的解决方案。我更喜欢保留原始上下文，因为我相信这种解决方案也可能有用。

在这个答案中，我将尝试为没有 yield 的语言开发一种方法。不幸的是，我的方法使用了栈，因此它绝对不是 O(1) 的。如果树更或多或少地平衡，那么栈的使用量会倾向于 O(log_2(n))。

我的做法基于 BST 上的 inorder 迭代器。在生产环境中必须进行改进。所以，我将定义以下迭代器类（用 C++ 类似语言）：

class Inorder
{
  Node * curr = nullptr; // node currentrly beeing visited
  Stack<Node*> s; // stack for storing the ancestors

  Node * advance_to_min(Node * r) // compute the leftmost node in r and stack the path
  {
    while (LLINK(r) != Node::NullPtr)
      {
        s.push(r);
        r = LLINK(r);
      }
    return r;
  }

public:

  Inorder(Node * root) : curr(advance_to_min(root)) {}

  bool has_curr() const noexcept { return curr != nullptr; }

  Node * get_curr() const { return curr; }

  void next() // get the next node inorder sense
  {
    curr = RLINK(curr);
    if (curr != nullptr)
      {
        curr = advance_to_min(curr);
        return;
      }

    if (s.is_empty())
      curr = nullptr;
    else
      curr = s.pop();
  }
};

上述迭代器不执行验证，并假定树至少有一个节点。LLINK，RLINK和KEY分别是访问左链接、右链接和键的访问器。

因此，使用迭代器检查两个树是否完全相同很容易：

bool same_keys(Node * t1, Node * t2)
{
  Inorder it1(t1), it2(t2);

  for (; it1.has_curr() and it2.has_curr(); it1.next(), it2.next())
    if (KEY(it1.get_curr()) != KEY(it2.get_curr()))
      return false;

  return not (it1.has_curr() or it2.has_curr()); 
}

关于空间消耗，我怀疑这种方法等同于递归方法。但是，我也怀疑是否存在一种空间复杂度严格为O(1)的方法。这个方法将基于“线程”，暂时将正确的空指针放在祖先中以便恢复。在现代架构中，您可以使用指针的最低有效位来标记它是否为线程; 因此您不需要额外的空间。

编辑：我没有看到作者的评论，他已经有了一个O(log(n))的解决方案。之后，我很快意识到我的方法可以修改为迭代而无需堆栈。因此，在接下来的内容中，我将提供一种O(1)空间复杂度的解决方案，该解决方案使用“线程”存储按顺序意义上的后继节点。

首先，在Inorder类中添加以下辅助方法：

static bool is_thread(Node * p) 
{ 
  return (Node*) (((long) p) & 1); 
}

static Node * make_thread(Node * p) 
{ 
  return (Node*) (((long)p) | 1);
}

static Node * make_pointer(Node * p)  
{ 
  return (Node*) (((long) p) & -2); 
}

基本思想是使用最低有效位来区分指针是否为线程。请注意，访问最低有效位为1的指针是无效的。因此，需要使用is_thread()来测试指针是否为线程。当然，堆栈并不是必需的。

现在，必须按如下方式修改advance_to_min()方法：

static Node * advance_to_min(Node * r) // find the leftmost node respect to r
{
  Node * p = r;
  while (LLINK(p) != nullptr)
    {
      p = LLINK(p);

      Node * q = p; // searches predecessor of r inorder
      while (RLINK(q) != nullptr)
        q = RLINK(q);

      // q is the predecessor of r
      RLINK(q) = make_thread(r); // here is put the thread
      r = p;
    }

    return r;
  }

方法next()必须重构以将线程恢复为null指针。可以通过以下方式完成：

void next() // get the next node inorder sense
{
  if (is_thread(RLINK(curr)))
    {
      Node * p = curr;
      curr = make_pointer(RLINK(p)); 
      RLINK(p) = nullptr; // here is deleted the thread
      return;
    }

    curr = RLINK(curr);
    if (curr != nullptr)
      curr = advance_to_min(curr);
}

班级的其余部分相同，完成后！您拥有一种在空间上检查两个BST是否具有相同密钥的O(1)方法。

当然，完全遍历树非常重要，否则，树将处于不一致状态。如果树不同，则肯定会发生这种情况。我给您留下了一个清理程序，确保两棵树都清除了它们的线程。

- lrleon

---

虽然你的算法确实使用了O(log n)的额外空间，但任何递归算法也会为堆栈帧使用O(log n)的额外空间。唯一的区别是，在递归版本中，你看不到它被分配。 - Jim Mischel