8

给定一组值，可以从这些值形成许多不同的可能的二叉搜索树。例如，对于值 1、2 和 3，我们可以根据这些值生成五个 BST：

1      1      2      3      3
 \      \    / \    /      /
  2      3  1   3  1      2
   \    /           \    /
    3  2             2  1

许多基于平衡二叉搜索树的数据结构使用树旋转作为重塑 BST 的原语，而不会破坏所需的二叉搜索树不变量。树旋转可用于将节点拉到其父节点上方，如下所示：

                rotate
         u      right           v
        / \     ----->         / \
       v   C                  A   u
      / \       <-----           / \
     A   B      rotate          B   C
                 left

给定一个包含一组值的 BST，是否总是可以将该 BST 转换为同一组值的任意其他 BST？例如，我们是否可以仅通过使用树旋转将上述五个 BST 中的任何一个转换为任何其他 BST？

4

2 回答 2

20

您的问题的答案取决于您是否被允许在 BST 中具有可能看起来彼此不同的相等值。例如，如果您的 BST 存储键/值对，则并不总是可以将这些键/值对的一个 BST 转换为相同键/值对的不同 BST。

这样做的原因是，无论执行多少树旋转，BST 中节点的中序遍历保持不变。因此，如果节点的中序遍历结果不同，就不可能从一个 BST 转换到另一个 BST。作为一个非常简单的例子，假设您有一个 BST 持有数字 1 的两个副本，每个副本都用不同的值（例如 A 或 B）进行注释。在这种情况下，没有办法使用树旋转将这两棵树变成另一棵树：

       1:a            1:b
         \             \
         1:b           1:a

您可以通过暴力破解（非常小！）您可以通过旋转制作的一组可能的树来检查这一点。然而，注意到第一棵树的中序遍历给出 1:a, 1:b 并且第二棵树的中序遍历给出 1:b, 1:a 就足够了。因此，没有任何旋转次数足以在树之间进行转换。

另一方面，如果所有值都不同，则始终可以通过应用正确数量的树旋转在两个 BST 之间进行转换。我将使用关于节点数的归纳论证来证明这一点。

作为一个简单的基本情况，如果树中没有节点，则只有一个可能的 BST 持有这些节点：空树。因此，始终可以在其中包含零节点的两棵树之间进行转换，因为开始树和结束树必须始终相同。

对于归纳步​​骤，我们假设对于任何两个具有相同值的 0、1、2、...、n 个节点的 BST，始终可以使用旋转将一个 BST 转换为另一个。我们将证明给定由相同 n + 1 个值组成的任意两个 BST，总是可以将第一棵树转换为第二棵树。

为此，我们将从进行关键观察开始。给定 BST 中的任何节点，总是可以应用树旋转来将该节点拉到树的根部。为此，我们可以应用以下算法：

while (target node is not the root) {
    if (node is a left child) {
        apply a right rotation to the node and its parent;
    } else {
        apply a left rotation to the node and its parent;
    }
}

这样做的原因是每次节点与其父节点一起旋转时，它的高度都会增加一。结果，在对上述形式进行了足够多的旋转之后，我们可以将根移到树的顶部。

现在，这为我们提供了一个非常简单的递归算法，我们可以使用旋转将任何一个 BST 重塑为另一个 BST。思路如下。首先，查看第二棵树的根节点。在第一棵树中找到那个节点（这很容易，因为它是一个 BST！），然后使用上面的算法将它拉到树的根部。至此，我们已经将第一棵树变成了具有以下属性的树：

  1. 第一棵树的根节点是第二棵树的根节点。
  2. 第一棵树的右子树包含与第二棵树的右子树相同的节点，但可能具有不同的形状。
  3. 第一棵树的左子树包含与第二棵树的左子树相同的节点，但可能具有不同的形状。

因此，我们可以递归地应用相同的算法来使左子树与第二棵树的左子树具有相同的形状，并使右子树与第二棵树的右子树具有相同的形状。由于这些左子树和右子树每个必须严格不超过 n 个节点，根据我们的归纳假设，我们知道这样做总是可能的，因此算法将按预期工作。

总而言之，该算法的工作原理如下：

  1. 如果两棵树是空的，我们就完成了。
  2. 在第一棵树中找到第二棵树的根节点。
  3. 应用旋转将该节点带到根。
  4. 递归地重塑第一棵树的左子树，使其具有与第二棵树的左子树相同的形状。
  5. 递归地重塑第一棵树的右子树，使其具有与第二棵树的右子树相同的形状。

要分析该算法的运行时间，请注意应用步骤 1 - 3 最多需要 O(h) 步骤，其中 h 是第一棵树的高度。每个节点将恰好被带到某个子树的根节点一次，所以我们总共做了 O(n) 次。由于 n 节点树的高度永远不会大于 O(n)，这意味着该算法最多需要 O(n 2 ) 时间来完成。它可能会做得更好（例如，如果两棵树已经具有相同的形状，那么它会在 O(n) 时间内运行），但这给出了一个很好的最坏情况界限。

希望这可以帮助！

于 2012-12-25T04:37:17.997 回答
5

对于二叉搜索树，这实际上可以在O(n)中完成。

任何树都可以“拉直”，即放入所有节点要么是根节点要么是左子节点的形式。

这种形式是独一无二的（从根向下读取给出了元素的顺序）

一棵树被拉直如下：

  • 对于任何右孩子，围绕自身执行左旋转。这会将右孩子的数量减少1 ，因此树在O(n)旋转中被拉直。

如果 A 可以在O(n)次旋转中拉直为 S，B 可以在O (n) 次旋转中拉直为 S ，那么由于旋转是可逆的，因此可以在O(n)次旋转中将 A -> S -> B旋转。

于 2018-01-30T23:00:15.793 回答