是否总是可以通过树旋转将一个BST转换为另一个BST？ [英] Is it always possible to turn one BST into another using tree rotations?

问题描述

给出一组值，可能有许多不同的二进制搜索树可以由这些值形成。例如，对于值1、2和3，我们可以从这些值中获得五个BST：

Given a set of values, it's possible for there to be many different possible binary search trees that can be formed from those values. For example, for the values 1, 2, and 3, there are five BSTs we can make from those values:

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

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

Many data structures that are based on balanced binary search trees use tree rotations as a primitive for reshaping a BST without breaking the required binary search tree invariants. Tree rotations can be used to pull a node up above its parent, as shown here:

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

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

Given a BST containing a set of values, is it always possible to convert that BST into any arbitrary other BST for the same set of values? For example, could we convert between any of the five BSTs above into any of the other BSTs just by using tree rotations?

推荐答案

问题的答案取决于BST中是否允许您使用相等的值，这些值看起来可能彼此不同。例如，如果您的BST存储键/值对，则并非总是可能将那些键/值对的一个BST变成相同键/值对的另一个BST。

The answer to your question depends on whether you are allowed to have equal values in the BST that can appear different from one another. For example, if your BST stores key/value pairs, then it is not always possible to turn one BST for those key/value pairs into a different BST for the same key/value pairs.

这样做的原因是，无论执行了多少棵树旋转，BST中节点的顺序遍历都保持不变。结果，如果节点的顺序遍历结果不同，则无法从一个BST转换为另一个BST。举一个非常简单的例子，假设您有一个BST持有两个数字1的副本，每个副本都标注了不同的值（例如A或B）。在这种情况下，无法通过树旋转将这两棵树变成彼此：

The reason for this is that the inorder traversal of the nodes in a BST remains the same regardless of how many tree rotations are performed. As a result, it's not possible to convert from one BST to another if the inorder traversal of the nodes would come out differently. As a very simple case, suppose you have a BST holding two copies of the number 1, each of which is annotated with a different value (say, A or B). In that case, there is no way to turn these two trees into one another using tree rotations:

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

您可以检查通过强行旋转（可以很小）一组可能的树来实现。但是，足以注意到第一棵树的有序遍历为1：a，1：b，第二棵树的有序遍历为1：b，1：a。因此，没有旋转次数就足以在树之间进行转换。

You can check this by brute-forcing the (very small!) set of possible trees you can make with the rotations. However, it suffices to note that an inorder traversal of the first tree gives 1:a, 1:b and an inorder traversal of the second tree gives 1:b, 1:a. Consequently, no number of rotations will suffice to convert between the trees.

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

On the other hand, if all the values are different, then it is always possible to convert between two BSTs by applying the right number of tree rotations. I'll prove this using an inductive argument on the number of nodes.

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

As a simple base case, if there are no nodes in the tree, there is only one possible BST holding those nodes: the empty tree. Therefore, it's always possible to convert between two trees with zero nodes in them, since the start and end tree must always be the same.

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

For the inductive step, let's assume that for any two BSTs of 0, 1, 2, .., n nodes with the same values, that it's always possible to convert from one BST to another using rotations. We'll prove that given any two BSTs made from the same n + 1 values, it's always possible to convert the first tree to the second.

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

To do this, we'll start off by making a key observation. Given any node in a BST, it is always possible to apply tree rotations to pull that node up to the root of the tree. To do this, we can apply this algorithm:

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

之所以起作用，是因为每次节点与父级一起旋转，其高度增加一。结果，在对上述形式进行了足够多的旋转之后，我们可以将根向上移到树的顶部。

The reason that this works is that every time a node is rotated with its parent, its height increases by one. As a result, after applying sufficiently many rotations of the above forms, we can get the root up to the top of the tree.

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

This now gives us a very straightforward recursive algorithm we can use to reshape any one BST into another BST using rotations. The idea is as follows. First, look at the root node of the second tree. Find that node in the first tree (this is pretty easy, since it's a BST!), then use the above algorithm to pull it up to the root of the tree. At this point, we have turned the first tree into a tree with the following properties:

1. 第一棵树的根节点是


2. 第一棵树的右子树包含与第二棵树的右子树相同的节点，但形状可能不同。


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

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

Consequently, we could then recursively apply this same algorithm to make the left subtree have the same shape as the left subtree of the second tree and to make the right subtree have the same shape as the right subtree of the second tree. Since these left and right subtrees must have strictly no more than n nodes each, by our inductive hypothesis we know that it's always possible to do this, and so the algorithm will work as intended.

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

To summarize, the algorithm works as follows:

1. 如果两棵树都是空的，我们就完成了。


2. 在第一棵树中找到第二棵树的根节点。


3. 应用旋转将节点移到根。


4. 递归地重塑第一棵树的左子树与第二棵树的左子树具有相同的形状。


5. 递归重塑第一棵树的右子树以具有相同的形状

1. If the two trees are empty, we are done.
2. Find the root node of the second tree in the first tree.
3. Apply rotations to bring that node up to the root.
4. Recursively reshape the left subtree of the first tree to have the same shape as the left subtree of the second tree.
5. Recursively reshape the right subtree of the first tree to have the same shape as the right subtree of the second tree.

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

To analyze the runtime of this algorithm, note that applying steps 1 - 3 requires at most O(h) steps, where h is the height of the first tree. Every node will be brought up to the root of some subtree exactly once, so we do this a total of O(n) times. Since the height of an n-node tree is never greater than O(n), this means that the algorithm takes at most O(n²) time to complete. It's possible that it will do a lot better (for example, if the two trees already have the same shape, then this runs in time O(n)), but this gives a nice worst-case bound.

希望这会有所帮助！

这篇关于是否总是可以通过树旋转将一个BST转换为另一个BST？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！