您问题的答案取决于 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!),然后使用上面的算法将其拉到树的根部。至此,我们已经将第一棵树变成了具有以下属性的树:
- 第一棵树的根节点是第二棵树的根节点。
- 第一棵树的右子树包含与第二棵树的右子树相同的节点,但可能具有不同的形状。
- 第一棵树的左子树包含与第二棵树的左子树相同的节点,但可能具有不同的形状。
因此,我们可以递归地应用相同的算法,使左子树与第二棵树的左子树具有相同的形状,并使右子树与第二棵树的右子树具有相同的形状。由于这些左子树和右子树的每个节点必须严格不超过 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(n2) 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.
希望这可以帮助!