// 证明在任意一个有n个节点的二叉搜索树只有n-1种旋转
// 数学归纳法
// 假如 n =1，则只有一个根节点，而左旋与右旋必然有另个支点，所有一个 节点时是不能旋转 就是0种可能 也就是 n -1 = 1-1 = 0
// 假设 n = k 成立，则有 k -1种可能的旋转
// 那么对于n=k+1时，也就二叉搜索树新添加一个节点，则这个节点一定在叶节点，并且其父节点一定不为空，这个叶节点可能是左节点也可能有节点
// 如果是左子结点，那么相对于原二叉查找树，增加了一个右旋操作；如果是右子结点，那么增加了一个左旋的操作，则原来有k-1种可能,加上一种可能也就是k种
// 也就是k+1-1=k
// 根据以上证明我们得到证明的结论正确
二叉搜索树性质证明
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 二叉搜索树，平衡树，B，b-，b+,b*,红黑树 二叉搜索树 1.所有非叶子结点至多拥有两个儿子（Le...
- 从广义上来讲：数据结构就是一组数据的存储结构 ， 算法就是操作数据的方法数据结构是为算法服务的，算法是要作用在特定...
