★算法评价 今判定树:描述查找过程的二叉树叫 冷有n个结点的判定树的深度为ogn+1 折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 今折半查找的ASL 设表长n=2-1,h=log2(m+1),即判定树是深度为h的满二叉树 设表中每个记录的查找概率相等p, 则:ASL=∑pc=1∑c=1∑ J·21n+1 log,(n+1)-l log, (n+1)算法评价 ❖判定树：描述查找过程的二叉树叫~ ❖有n个结点的判定树的深度为log2n+1 ❖折半查找法在查找过程中进行的比较次数最多不超过 其判定树的深度 ❖折半查找的ASL log ( 1) 1 log ( 1) 1 1 2 1 1 1 2 1, log ( 1), 2 2 1 1 1 1 2 + −  + − + = = =  = = = − = +   = − = = n n n n j n c n ASL p c n p n h n h h j j n i i n i i i i h 则： 设表中每个记录的查找概率相等 设表长 即判定树是深度为 的满二叉树