从有序表构造出的二叉搜索树(判定树) 查找 查找 ()成功( 心(3102 失败 搜索成功的情形 搜索不成功的情形 若设η=2h-1,则描述对分搜索的二叉搜索树是高 度为h-1的满二叉树。2h=n+1,h=log2(n+1)。 第0层结点有1个,搜索第0层结点要比较1次;第1 层结点有2个,搜索第1层结点要比较2次;
搜索成功的情形 搜索不成功的情形 从有序表构造出的二叉搜索树(判定树) ◼ 若设 n = 2h-1，则描述对分搜索的二叉搜索树是高 度为 h-1 的满二叉树。2h = n+1, h = log2(n+1)。 ◼ 第0层结点有1个，搜索第0层结点要比较1次；第1 层结点有2个，搜索第1层结点要比较2次；…
在假定每个结点的查找概率相同的情况下,二分检 索的平均查找次数为: ASL bins (1·20+2·2+3·2+…+i·2+..+k2 用数学归纳法容易证明:∑21=2(k-1)+1 ASL (2·(-1)+1)=-(7+1og2n+1)-1)+1) =log2(n+1)-1+-log2(n+1 log2(n+1)-1
(1 2 2 2 3 2 ... 2 ... 2 ) 1 0 1 2 −1 −1 + + + + + + i k i k n ASLbins= 在假定每个结点的查找概率相同的情况下，二分检 索的平均查找次数为： 2 2 ( 1) 1 1 1 = − + = − i k k k i i 用数学归纳法容易证明： (( 1)(log ( 1) 1) 1) 1 (2 ( 1) 1) 1 2 − + = n + n + − + n k n k ASLbins= log ( 1) 1 log ( 1) 1 2 + − + 2 n + n = n = log2 (n+1)-1
923分块检索 分块查找( Blocking Search)又称索引顺序查 找。它是一种性能介于顺序查找和二分查找之间的 查找方法 1、查找表存储结构 查找表由“分块有序”的线性表和索引表组成 (1)“分块有序”的线性表 线性表R被均分为若干块,每一块中的关键字 不一定有序,但前一块中的最大关键字必须小于后 块中的最小关键字,即表是"分块有序"的
9.2.3分块检索 分块查找(Blocking Search)又称索引顺序查 找。它是一种性能介于顺序查找和二分查找之间的 查找方法。 1、 查找表存储结构 查找表由“分块有序”的线性表和索引表组成 。 （1）“分块有序”的线性表 线性表R被均分为若干块，每一块中的关键字 不一定有序，但前一块中的最大关键字必须小于后 一块中的最小关键字，即表是"分块有序"的
)索引表 抽取各块中的最大关键字及其起始位置构成一个 索引表ID[b],即 ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R 中的起始位置。由于表R是分块有序的,所以索引表是 一个递增有序表 【例】例如,图92就是一个带索引的分块有序的线 性表。其中线性表L共有20个结点,被分成3块,第 块中最大关键字25小于第二块中的最小关键字27 第二块中最大关键字55小于第三块中的最小关键 字60
（2）索引表 抽取各块中的最大关键字及其起始位置构成一个 索引表ID[l..b]，即： ID[i](1≤i≤b)中存放第i块的最大关键字及该块在表R 中的起始位置。由于表R是分块有序的，所以索引表是 一个递增有序表。 【例】例如，图9.2就是一个带索引的分块有序的线 性表。其中线性表L共有20个结点，被分成3块，第 一块中最大关键字25小于第二块中的最小关键字27 ，第二块中最大关键字55小于第三块中的最小关键 字60
012345678910111213141516171819 2042517 12640|30275548357066 9060|6 7369 0713]adt(地址 索引表 2555901kegy(关键字) 图9,2分块有序表的索引存储表示 2、分块查找的基本思想 分块查找的基本思想 (1)首先查找索引表 索引表是有序表,可采用二分查找或顺序查找, 以确定待查的结点在哪一块。 (2)然后在已确定的块中进行顺序查找
图9.2 分块有序表的索引存储表示 2、分块查找的基本思想 分块查找的基本思想是： （1）首先查找索引表 索引表是有序表，可采用二分查找或顺序查找， 以确定待查的结点在哪一块。 （2）然后在已确定的块中进行顺序查找