§9.2.2三分（折半）查找 §92.2二分（折半）查找 费终满的置紫%公新拉提的三骨路密孕第素数湘关， 与 ·时间分析 〔06品2品.品品2)，批2康纳，执85庆藏 ◆查找R同：比较1次；意望R3、R:比较2次；意找RR国、R闪 I0j:比较3次：童找R☒，R、R8图、R1:比较4次 R1 ○内部结点 R[1..5 6 11 外部结点 R111 R[1.516 R7.11 3 9 45 7) 10.11] 31 9 12 45 R78剧 人101 4 7 10 R22 5.51 88周 R1111 1 4 7 10 422 R5.5 Rs8 R11-1 1 234567891011 2345678901 d/ 12234556788910111正 12234约567889105f1市 89.2.2三分（折半）查找 §9.2.2分块查找（索引顺序查找） 时间分折 ■存，结构 ◆总销：查找过程走了一条从判定封的根到放查轴点的路径。 感动：峰止于一个内督结点，所需的Ky比较次数恰为该结点在树中的层 将R[1nj均分成b块，前b一1块中的点数为5=nWb,量后一块中的的 点数可能小于5，引入素引康标记块。 表整货于)十外都铺点。所需的K©y比较次数为演上内部施点总 ■关键字状态 ◆平均童数长度(A3L), 分染有序：块间有序，块内不一定有序 侧子：n=18,b=3,s=6 设n=2-1,则制高h=g(n+1)不计外部结点的满二叉树 第k展上纳点数为2水一，找该层上每个轴点的比较次数为k,在等餐事限 设下， 最大关镜宇 224886 起始地址 7 13 4-20,-2c-之2="出ga+n-1sle+-l n 参量坏时间，意线失败，不超过树高g(+1 在链表上可做折半查找网？ 2212389203324382448505874498653 §9.2.2分块查找（索引顺序查找） §9.3树上的查找（动态查找） 查找过程（两步查找） 于新学艺效导世。本节计论适用 ◆家引豪意线：南定块。n较大时用折半查找，较小时用顺序查找， 女柴内意线：只能原序查找。 59.3.1二叉查找树(BST) ·性能分析 ■定义：二叉查找制树成是空树，或满足下述B$T性质的二叉树： ◆以新半查载南定染 ①惹它的左子树非空，则左子树上所有结点的k©ys均小于根 ASL=ASLm+ASL=Ig(b+1)-1+(s+12lg(n/s+1)+s/2 的key ②装它的右子树非空，则右子制上所有结点的k©ys均大于根 ◆以顺序查找确定禁 的key ASL=ASL+ASL=(b+12+(s+1)/2=(s2+2s+n/(2s) 图左右子树又都是二叉查找树 当s=,万时，ASL取银小值√n+1 Note:性质1或2中，可以将“<”改为”≤”：或“>”改为“≥州 不一定等分 BST性质 二叉查找树的中序序列是一个递增有序序列 22 7 § 9.2.2 二分（折半）查找 „ 查找过程 判定(比较)树：分析查找过程的二叉树，形态只与结点数相关，与 输入实例的取值无关（为什么？）。例如n＝11的形态如下图所示。 1 2 3 4 5 6 7 8 9 10 11 （05,13,19,21,37,56,64,75,80, 88, 92），找21成功，找85失败。 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] Φ R[5..5] R[11..11] -1 1-2 2-3 4-5 3-4 R[1..2] R[2..2] Φ 5 8 R[4..5] Φ Φ Φ 5-6 6-7 7-8 Φ Φ Φ 11 R[7..8] Φ R[8..8] 8-9 9-10 Φ Φ 10-11 11- Φ ＜ ＝ ＞ 内部结点 外部结点 8 § 9.2.2 二分（折半）查找 „ 时间分析 ™ 查找R[6]：比较1次; 查找R[3]、R{9]：比较2次; 查找R[1]、R[4]、R[7]、 R[10]：比较3次; 查找R[2]、R[5]、R[8]、R[11]：比较4次 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] Φ R[5..5] R[11..11] -1 1-2 2-3 4-5 3-4 R[1..2] R[2..2] Φ 5 8 R[4..5] Φ Φ Φ 5-6 6-7 7-8 Φ Φ Φ 11 R[7..8] Φ R[8..8] 8-9 9-10 Φ Φ 10-11 11- Φ ＜ ＝ ＞ 9 § 9.2.2 二分（折半）查找 „ 时间分析 ™ 总结：查找过程走了一条从判定树的根到被查结点的路径。 成功：终止于一个内部结点，所需的Key比较次数恰为该结点在树中的层 数; 失败：终止于一个外部结点，所需的Key比较次数为该路径上内部结点总 数。（层数－1） ™ 平均查找长度（ASL）： 设n＝2h-1, 则树高h＝lg(n+1) //不计外部结点的满二叉树 第k层上结点数为2k－1，找该层上每个结点的比较次数为k，在等概率假 设下： ™ 最坏时间：查找失败，不超过树高 lg(n+1) ™ 在链表上可做折半查找吗？ ∑ ∑∑ = == − + − ≈ + − + = = = = n i n i h k k bs i i i n n n n k n C n ASL PC 1 11 1 lg( 1) 1 lg( 1) 1 1 2 1 1 10 § 9.2.2 分块查找（索引顺序查找） „ 存储结构 将R[1..n]均分成b块，前b－1块中结点数为s＝ n/b ，最后一块中的结 点数可能小于s，引入索引表标记块。 „ 关键字状态 分块有序：块间有序，块内不一定有序; 例子：n＝18，b＝3，s＝6 1 7 13 最大关键字 22 48 86 起始地址 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 11 § 9.2.2 分块查找（索引顺序查找） „ 查找过程（两步查找） ™ 索引表查找：确定块。n较大时用折半查找，n较小时用顺序查找。 ™ 块内查找：只能顺序查找。 „ 性能分析 ™ 以折半查找确定块： ASL＝ ASLbs＋ASLss＝lg(b＋1) －1＋(s＋1)/2≈lg(n/s＋1)＋s/2 ™ 以顺序查找确定块： ASL＝ ASLss＋ASLss＝(b＋1)/2＋(s＋1)/2＝(s2＋2s＋n)/(2s) 当s＝ 时，ASL取极小值 ＋1 ™ 块不一定等分 n n 12 § 9.3 树上的查找（动态查找） 折半查找效率最高，但它不适应插删操作。本节讨论适用 于动态查找，即查找过程中动态维护表结构。 § 9.3.1 二叉查找树（BST） „ 定义：二叉查找树或是空树，或满足下述BST性质的二叉树： ①若它的左子树非空，则左子树上所有结点的keys均小于根 的key ②若它的右子树非空，则右子树上所有结点的keys均大于根 的key ③左右子树又都是二叉查找树 Note：性质1或2中，可以将“﹤” 改为“≤”；或“﹥”改为“≥” „ BST性质 二叉查找树的中序序列是一个递增有序序列