证明：任何一棵含n个节点的二叉搜索树可以通过O(n)次旋转，

[问答题]

证明：任何一棵含n个节点的二叉搜索树可以通过O(n)次旋转，转变为其他任何一棵含n个节点的二叉搜索树。（提示：先证明至多n-1次右旋足以将树转变为一条右侧伸展的链。）

查看答案及解析

yycode

按照左根右的顺序，进行左旋将根节点的左子树旋转为空，然后再将右子树的左节点旋转为空，因为一颗为n的二叉搜索树恰有n-1种可能的旋转方式，所有至多n-1次可将一颗二叉搜索树旋转成一课只有有子树的右侧伸展链，通过相应的逆操作也可以将旋转回去

综上证明完毕

发表于 2020-11-04 10:11:19 回复(0)

提交观点

问题信息

上传者：小小

难度：

1条回答 0收藏 1424浏览

扫一扫，把题目装进口袋