二叉搜索树性质证明

// 证明在任意一个有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
// 根据以上证明我们得到证明的结论正确

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。