将一个二叉树右转换为另一个二叉树的时间复杂度
将一个二叉树右转换为另一个二叉树的时间复杂度
提问于 2020-04-07 14:24:36
如果T2可以通过仅在T1上执行右旋转从T1获得，则BST T2是右可转换到另一BST T2的。我需要证明这个操作可以在$O(n^2)$ right旋转中完成。
假设我们假设T1是右可转换到T2的。我理解算法的递归性质，因为我们首先将T2的根(它必须位于T1的最左侧路径中才能右转换)带到T1的根，然后对T1的两个子树重复这个过程。
然而，我不能想出一个例子来展示最坏的情况。我能够想到这两棵树，尽管我不确定如何证明这是最坏的情况。
Tree 1 Tree 2
6 1
/ \
5 2
/ \
4 3
/ \
3 4
/ \
2 6
/ /
1 5通过从节点2开始向右旋转5+4+3+2次，可以将树1右转为T2。
一般来说，我如何找到需要$O(n^2)$右旋转将一个BST转换为另一个BST的情况？
回答 1
Stack Overflow用户
发布于 2020-04-07 16:01:03
校样草图：
让T1=(V,E)，n=#V。考虑一下从T1开始的重复(右)旋转过程中出现的树<T1 = X_0, X_1, ..., X_(t-1), X_t = T2>序列。对于任何给定的旋转，让“旋转锚”表示旋转的子树的根节点。
观察#1：
旋转任何给定子树不会改变其顶点集。
观察#2：
在给定子树的任意右旋转序列s中，每个顶点至多是旋转锚点一次。(每次向右旋转时，锚点都会迁移到右子树中。右旋转后的新根以左子树为起点；或者请注意，每次旋转，右子树增长1个顶点；因此，对于子树S，存在最大#V(S)-1旋转)。
观察#3：
向右旋转不会改变子树的数量。
任何树中的子树的数量都等于可用根的数量，即#V-1。因此，最大长度的右旋转序列涉及O(n)子树，每个子树具有最大#V(S)-1 (= O(n))个旋转，总共O(n^2)个。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61073951
复制相关文章
相似问题
腾讯云开发者
