T8 折半查找判定树

• 判定规则

  • 向下取整：$\mathrm{mid}=\lfloor (\mathrm{low}+\mathrm{high})/2\rfloor$
    • 元素个数：左子树 大于等于 右子树
  • 向上取整：$\mathrm{mid}=\lceil (\mathrm{low}+\mathrm{high})/2\rceil$
    • 元素个数：左子树 小于等于 右子树

• 比较次数

  • (成功或者不成功都是)最多: $\lfloor {\log }_{2}n\rfloor +1$ 即折半查找树的高度

• 平均查找长度

  • $AS{L}_s=\frac{1}{n}{\sum }_{i=1}^n{l}_i$
    • $l_i$：第 $i$ 个结点的深度
  • $AS{L}_f=\frac{1}{n+1}{\sum }_{i=0}^n{l}_i^{\prime }$
    • $l_i^{\prime }$：第 $i$ 个失败结点父节点的深度
  • 若成功结点的个数为 $n$,则失败结点的个数必为 $n+1$
  • 成功结点计算包括自己在内的深度, 失败结点计算到父节点的深度(不包括自己在内)