性能分析 ASLL=LL+L 据L为确定块的平均查找长度;L为块内查找次数。 结 若顺序查找:ASLb=Lb+Lw=(n/s+s)2+1 若折半查找:ASLb=Lb+Lv=log2(n/s+1)+s/2 三种查找方法比较 顺序查找 折半查找 分块查找 ASI 大 中 表结构要求 无 有序变 块之间有序 93动态查找表 >二又排序树BST >二叉排序树的定义:page227 构 查找过程 之>二又排序树的插入和删除 二叉排序树的查找分析 含有n个结点的二叉排序树的平均查找长度 和树的形态有关:最差的形态是:单支树 ((n+1)2);最好的形态是:判定树(log2n) 在随机情况下,二叉排序树的平均查找长度 和ogn是等数量级的。7 数 据 结 构 之 查 找 13 ¾ 性能分析 ASLbs=Lb+Lw， Lb为确定块的平均查找长度；Lw为块内查找次数。 若顺序查找： ASLbs=Lb+Lw =(n/s+s)/2+1 若折半查找： ASLbs=Lb+Lw = log2(n/s+1)+s/2 三种查找方法比较 顺序查找 折半查找 分块查找 ASL 大 小 中 表结构要求 无 有序表 块之间有序 数 据 结 构 之 查 找 14 9.3 动态查找表 ¾ 二叉排序树(BST) ¾ 二叉排序树的定义：page 227 ¾ 查找过程 ¾ 二叉排序树的插入和删除 ¾ 二叉排序树的查找分析 含有n个结点的二叉排序树的平均查找长度 和树的形态有关：最差的形态是：单支树 ( (n+1)/2 )；最好的形态是：判定树( log2 n )。 在随机情况下，二叉排序树的平均查找长度 和 log n是等数量级的