证明这些旋转动作可以探索整个二叉树搜索 space
Proof that these rotation moves can explore the whole binary tree search space
我正在做这个项目，我需要找到后续的理论证明。
我有一种特殊类型的二叉树，其中
1) 每个内部节点肯定会有两个子节点。
2) 有n个叶节点，可以假定从最左到最右为1到n的顺序。
现在很明显，具有这两个属性的可能树的数量呈指数级增长。
如果我从任何随机树开始并随机采样内部节点之一，则随机执行左旋转或右旋转 (https://en.wikipedia.org/wiki/Tree_rotation) 这两个操作之一。是否可以在搜索中从任意一棵树开始到任意一棵其他树space.
我尝试了各种资源，但找不到任何证据。我自己尝试过，但无法找到解决方案。如果有人可以帮助我，我会很高兴。
首先证明所有具有相同叶节点数的树都具有相同数量的内部节点。这是通过检查有多少叶节点有一个具有 I 个内部节点的树来显示的。对于 I 个内部节点，有 2*I 个边。 I-1 这些边连接内部节点，因此 I+1 边留给叶节点。因此，具有 n 个叶节点的树具有 n-1 个内部节点。
要看到一棵树可以转换为另一棵树，将两棵树都转换为某个 'base' 树就足够了。例如。让 A 成为树，其中每个内部节点（除了最后一个）在左侧叶子节点和右侧内部节点上。它更像是一条路径 :-) 要将任何树转换为 A 只需要右旋转，这很容易找到如何进行旋转的顺序节点。要将 T1 转换为 T2，只需将 T1 转换为 A，而不是将 A 转换为 T2。
我正在做这个项目，我需要找到后续的理论证明。
我有一种特殊类型的二叉树，其中
1) 每个内部节点肯定会有两个子节点。
2) 有n个叶节点，可以假定从最左到最右为1到n的顺序。
现在很明显，具有这两个属性的可能树的数量呈指数级增长。
如果我从任何随机树开始并随机采样内部节点之一，则随机执行左旋转或右旋转 (https://en.wikipedia.org/wiki/Tree_rotation) 这两个操作之一。是否可以在搜索中从任意一棵树开始到任意一棵其他树space.
我尝试了各种资源，但找不到任何证据。我自己尝试过，但无法找到解决方案。如果有人可以帮助我，我会很高兴。
首先证明所有具有相同叶节点数的树都具有相同数量的内部节点。这是通过检查有多少叶节点有一个具有 I 个内部节点的树来显示的。对于 I 个内部节点，有 2*I 个边。 I-1 这些边连接内部节点，因此 I+1 边留给叶节点。因此，具有 n 个叶节点的树具有 n-1 个内部节点。
要看到一棵树可以转换为另一棵树，将两棵树都转换为某个 'base' 树就足够了。例如。让 A 成为树，其中每个内部节点（除了最后一个）在左侧叶子节点和右侧内部节点上。它更像是一条路径 :-) 要将任何树转换为 A 只需要右旋转，这很容易找到如何进行旋转的顺序节点。要将 T1 转换为 T2，只需将 T1 转换为 A，而不是将 A 转换为 T2。