1

我的问题如下：

我有一个带有键的二叉搜索树：a1<a2<...<an，问题是使用 O 中的递归算法打印树中的所有 (a_i, a_i+1) 对（其中 i={1,2,3,...}） (n) 没有任何全局变量并使用 O(1) 额外空间的时间。一个例子：假设键是：1,2, ..., 5 将被打印的对：(1,2) (2,3) (3, 4) (4, 5)

因此，您不能在树中进行中序遍历并找到每个节点的后继/前继。因为这将花费 O(nh) 时间，并且如果树是平衡的，那么整棵树的时间将为 O(nlgn)。

4

2 回答 2

3

虽然你是对的，找到一个有序的后继或前驱可能需要 O(h) 时间，但事实证明，如果你从 BST 中的最小值开始并反复找到它的后继，完成的工作总量最终会到来无论树的形状如何，都达到 O(n)。

对此的直觉是考虑在迭代进行后继查找时遍历树中每条边的次数。具体来说，您将准确地访问树中的每条边两次：一次是当您下降到子树时，一次是当您从子树中走出来访问该子树中的每个节点时。由于 n 节点树有 O(n) 条边，这需要 O(n) 时间才能完成。

如果您对此持怀疑态度，请尝试编写一个简单的程序来验证它。我记得当我第一次听到这个结果时，我并不相信这个结果，直到我写了一个程序来确认它。:-)

在伪代码中，逻辑如下所示：

  1. 通过从根开始并重复跟随左子指针直到不存在这样的指针，找到树中的最小值。
  2. 直到所有节点都被访问过，记住当前节点并找到它的后继节点如下：
    1. 如果当前节点有一个右孩子：
      1. 向右走。
      2. 向左走，直到没有剩下的孩子。
      3. 输出你开始的节点，然后是这个节点。2：否则：
      4. 一直走到父节点，直到你发现你开始的节点是其父节点的左子节点。
      5. 如果你击中了根并且从未发现你是从左孩子向上遍历的，那么你就完成了。
      6. 否则，输出你记得的节点，然后是当前节点。

希望这可以帮助！

于 2013-01-06T17:14:40.850 回答
1

Oli 是正确的，中序遍历是 O(n)，但你是对的，使用一般的后继/前继例程会增加算法的复杂性。所以：

一个简单的解决方案是使用按序遍历来遍历树，跟踪您最后一次被带入右指向边（例如，使用名为last_right_ancestor_seen的变量指向其父节点）和最后一个叶节点你已经看到了（比如说，在last_leaf_seen中（实际上是任何没有右子节点的节点）。每次处理叶节点时，它的前身是last_right_ancestor，每次遇到非叶节点时，它的前身是last_leaf_seen，并且你只需打印两个。O(n) 时间，O(1) 空间。

希望它足够清楚，如果没有，我可以给你画一个图表。

编辑：这是未经测试的，但可能是正确的：

walk(node* current, node* last_right_ancestor_seen, node* last_leaf_seen) {

    if(current->left != null) {
        walk(current->left, last_right_ancestor_seen, last_leaf_seen);
    }

    if(current->is_leaf()) {
            if(last_right_ancestor_seen != null)
                print(last_right_ancestor_seen->value, current->value);
    }
    else {
        print(last_leaf_seen->value, current->value);
    }

    if(current->right != null) {
        *last_right_ancestor_seen = *current;
        walk(current->right, last_right_ancestor_seen, last_leaf_seen);
    }
    else {
        *last_leaf_seen = *current;
    }

}
于 2013-01-06T15:13:01.597 回答