§8.1.4检索算法的判定树 判定树的构造方法 若某检索算法A在数据元素集D上进行检索,则A对D的(检索) 判定树定义为: 若D=空,则A对D的判定树为空 若第1次是与元素i比较(测试),则令i为判定树的根 若与i比较后,下一步的检索操作是在数据集D2Dn之一中 进行(即可能在D1,Dn中任意一个上进行),则令算法A的 其余部分对D12…,Dn的判定树(子树)为根结点i的各子树, 这里,D1,Dn应为(D-{i})的一个划分。(即D1U.∪Dn=D i1},且D∩D=空,j≠k,jk∈{1,m})
11 • 判定树的构造方法 –若某检索算法A在数据元素集D上进行检索，则A对D的（检索） 判定树定义为： –若D=空，则A对D的判定树为空 –若第1次是与元素i 1比较（测试），则令i 1为判定树的根 –若与i 1比较后，下一步的检索操作是在数据集D1 ,...,Dm之一中 进行（即可能在D1 ,...,Dm中任意一个上进行），则令算法A的 其余部分对D1 ,...,Dm的判定树（子树）为根结点i 1的各子树， 这里，D1 ,...,Dm应为(D-{i1 })的一个划分。（即D1∪...∪Dm=D- {i1 }，且Dj∩Dk=空，j≠k，j, k∈{1,...,m}） §8.1.4 检索算法的判定树
(a)顺序查找判定树 2 4 (b)折半查找判定树 (c)折半查找判定树(带外结点 图判定树 12
12 1 2 3 4 5 6 7 8 9 （a）顺序查找判定树 5 2 7 1 3 6 8 4 9 （b）折半查找判定树 5 2 7 1 3 6 8 4 9 （c）折半查找判定树(带外结点 ) 图 - 判定树
§8.1.4检索算法的判定树 ·判定树的深度就表示检索算法的最大比较次数 树的分枝数越大(即数据集分块越多),树深 度就越小 检索某结的比较次数,就是从树根到该结点的 路径上的结点个数 ·外结点 ·增设了外结点的判定树为完全二叉树 13
13 • 判定树的深度就表示检索算法的最大比较次数 • 树的分枝数越大（即数据集分块越多），树深 度就越小 • 检索某结的比较次数，就是从树根到该结点的 路径上的结点个数 • 外结点 • 增设了外结点的判定树为完全二叉树 §8.1.4 检索算法的判定树
§8.1.4检索算法的判定树 增设了外结点的判定树为完全二叉树 判定树的内路径长定义为该树中各内结点的路径长 (从根到某结点的路径长定义为该结点的内径长)之和 外路径长定义为树中各外结点的路径长之和 设I与E分别代表判定树的内与外路径长,则有 E=I+2n 这里n为内结点数目
14 • 增设了外结点的判定树为完全二叉树 • 判定树的内路径长定义为该树中各内结点的路径长 （从根到某结点的路径长定义为该结点的内径长）之和 • 外路径长定义为树中各外结点的路径长之和 •设I与E分别代表判定树的内与外路径长，则有 E=I+2n 这里n为内结点数目 §8.1.4 检索算法的判定树
§8.1.4检索算法的判定树 实际中,各关键被查概率可能不同,为此,引入加权 内外路径长 设w,与1分别为结点i权值与在树中的层次数(即结点 i的路径长),则定义w;与1的积为的加权路径长 加权内路径长上∑wl 2n+1 加权外路径长E=∑w1 15
15 §8.1.4 检索算法的判定树 • 实际中，各关键被查概率可能不同，为此，引入加权 内外路径长 • 设wi与l i分别为结点i的权值与在树中的层次数（即结点 i的路径长），则定义wi与l i的积为i的加权路径长 • 加权内路径长I= • 加权外路径长E= i n i i w l =1 i n i i w l + = 2 1 1