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

Question

我正在寻找一种顺序算法（如果存在）来测试两个 BST 在 O(n) 中是否具有相同的键，使用 O(1) 内存并允许递归。
怎么做：两个synchronized中序遍历，这样就可以比较两个BST的ith元素了？

Answer 1

如何操作取决于您的语言。

在像 Python 这样的语言中，您所做的就是使用 yield 编写 BST。这将创建一个保持少量状态的生成器。（根据数据结构和算法，在这种情况下它应该是O(1)或O(log(n))。众所周知，在现实世界中log(n)是一个常数。虽然对于像这样的公司Google是一个稍大的常数...)

在没有 yield 的语言中，您需要安排创建一个对象，该对象具有关于搜索的状态，您可以调用该方法，该方法将 return 当前元素（或告诉您它是完成），然后继续下一个。当你进入方法时保持状态并恢复它是公认的 PITA，但在幕后是 Python 会为你做的。

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

Answer 2

注意：本来这个答案写在O(log(n)是为了space消费，但是一个O(1)的解决方案，后来放上了，在下面。我更愿意保留原始上下文，因为我相信这个解决方案也很有用。

在这个答案中，我将尝试为没有 yield 的语言开发一种方法。不幸的是，我的方法使用了堆栈，所以肯定不是O(1)。如果树或多或少是平衡的，堆栈消耗将倾向于 O(log_2(n)).

我的做法是基于 BST 上的中序迭代器。它必须在生产环境中得到改进。因此，我将定义以下迭代器 class（使用 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 分别是左 link、右 link 和键的访问器。

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

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()); 
}

关于space的消耗，我怀疑这种做法等同于递归的做法。但是，我也怀疑它存在一种 space 消耗严格 O(1) 的方法。这最后将基于 "threads" 暂时放入正确的空指针以恢复祖先。在现代架构中，您可以使用指针的最低有效位来标记它是否是线程；所以你不需要额外的 space.

已编辑：我还没有看到作者评论说他已经有了 O(log(n)) 解决方案。在那之后，我很快意识到我的方法可以修改为没有堆栈的迭代。因此，在接下来的内容中，我给出了 O(1) in space 解决方案，该解决方案使用 "threads" 来存储在顺序意义上作为继承者的祖先。

首先，将以下辅助方法放入 Inorder class:

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() 才能将线程恢复为空指针。这可以这样做：

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);
}

class 的其余部分是一样的，瞧！你在 space 中有一个 O(1) 方法来检查两个 BST 是否是相同的键。

当然树完全遍历很重要，否则树会处于不一致的状态。如果树不同，那肯定会发生。我留给你一个清洁程序，确保两棵树都被清除掉它们的线程。

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

Check if two Binary Search Tree have the same keys

algorithm

recursion

binary-tree

binary-search-tree