二叉排序树查找成功时的平均查找长度公式及证明
二叉排序树是基于二分查找步骤生成的二叉树。
设二叉排序树的高度为h，共有n个结点
有如下性质：
1.前h-1层结点全部占满（即为满二叉树）
2.最后一层结点可以通过平移使得整个树转化成完全二叉树
思路：
首先求前h-1层的对比次数
之后求最后一层的对比次数
公式为：
下面给出证明过程：
二叉排序树是基于二分查找步骤生成的二叉树。
设二叉排序树的高度为h，共有n个结点
有如下性质：
1.前h-1层结点全部占满（即为满二叉树）
2.最后一层结点可以通过平移使得整个树转化成完全二叉树
思路：
首先求前h-1层的对比次数
之后求最后一层的对比次数
公式为：
下面给出证明过程：