相关疑难解决方法(0)

给定一组值,可以存在许多可以由这些值形成的不同的可能二进制搜索树.例如,对于值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,是否总是可以将该BS​​T转换为任意其他BST用于同一组值？例如,我们是否可以仅使用树旋转将上述五个BST中的任何一个转换为任何其他BST？

当我在学习关于二叉树的期中考试时，我发现了一个陈述，即任何任意的 n 节点二叉树都可以转换为最多 2*n-2 次旋转的任何其他 n 节点二叉树。有什么证据吗？我用渐近符号找到了某种证明，但不是那么清楚。我的意思是有人可以解释/说明为什么这是真的吗？如果它说 n 节点二叉树，它是否包括根？