二分查找判定树 (1)若查找给定值 为20的元素,依次与 表中25,10,15,20元素 比较,共比较4次。 (2)若查找给定值为26的元素依次与2530,28元素 比较共比较3次。 (3)在查找成功时会找到图中某个圆形结点则成 功时的平均查找长度 1×1+2×2+4×3+4×4 ASlsucc= 在查找不成功时会找到图中某个方形结点则 不成功时的平均查找长度: 4×3+8×4 AsLunsucc =3.67 16 12
16 25 10 30 2 15 28 35 3 20 29 40 二分查找判定树 (2)若查找给定值为26的元素,依次与25,30,28元素 比较,共比较3次。 (3)在查找成功时,会找到图中某个圆形结点,则成 功时的平均查找长度： 3 11 1 1 2 2 4 3 4 4 ASLsucc＝ ＝ + + + (1)若查找给定值 为20的元素,依次与 表中25,10,15,20元素 比较,共比较4次。 在查找不成功时,会找到图中某个方形结点,则 不成功时的平均查找长度： 3.67 12 4 3 8 4 ASLunsucc ＝ ＝ +
对比顺序查找和二分查找的性能之差别: 顺序查找二分查找 表的特性无序表 有序表 存储结构顺序或链式 结构 顺序结构 插删操作 易于进行需移动元素 ASL值 大 17
17 对比顺序查找和二分查找的性能之差别： 顺序查找 二分查找 表的特性 存储结构 插删操作 ASL值 无序表 有序表 顺序或链式 结构 顺序结构 易于进行 需移动元素 大 小