定义

二叉判定树是用于描述解决问题的思路,比如可以使用判定树描述N个数的比较过程,是一种对过程的描述。
它也可以用于描述二分查找(即折半查找,以下都作二分查找)的过程。

描述二分查找的二叉判定树,我们也可以叫折半查找判定树,
从这样的判定树,我们可以分析二分查找算法的效率

如何构造长度为n的折半查找判定树

  1. 当n=0时,折半查找判定树为空;
  2. 当n>0时,折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树,根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。

画出长度为18的顺序储存的有序表进行折半查找时的判定树,并求平均查找长度

首先找根节点:mid = (18+1) / 2 = 9 (向下取整)

判断左子树:    左子树的查找范围是(1 ~ 8),mid = ( 1 + 8 ) / 2 = 4

判断右子树:    右子树的查找范围是(10 ~ 18),mid = ( 10 + 18 ) / 2 = 14

递归进行下去,得到结果:

 平均查找长度:(1 + 2*2 + 4*3 + 8*4 + 3*5)/ 18 = 32 / 9

拓展

我们刚刚做出的这个判定树是采取了向下取整,但向上向下都是可以的,

必须注意的一点是:在一颗判定树中,要向下取整,全都向下取整,不能混有向上取整

折半查找判定树的中序遍历,刚好是原来那些数排好序的样子

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐