1、东南大学计算机学院东南大学计算机学院 xxxx第七章第七章 搜索结构搜索结构1感谢你的观看2019年8月23本章主要内容本章主要内容n搜索的概念搜索的概念n静态搜索结构静态搜索结构r顺序搜索顺序搜索r有序顺序表有序顺序表顺序搜索顺序搜索折半搜索折半搜索斐波那契搜索斐波那契搜索n二叉搜索树二叉搜索树2感谢你的观看2019年8月23搜索的概念搜索的概念n在数据集合中寻找满足某种条件的数据元素在数据集合中寻找满足某种条件的数据元素r搜索可能成功搜索可能成功r也可能不成功也可能不成功n可唯一标识一个元素的属性称为关键字可唯一标识一个元素的属性称为关键字(key)r基于关键字的搜索结果是唯一的基于关键字
2、的搜索结果是唯一的r基于其他属性的搜索结果可能不唯一基于其他属性的搜索结果可能不唯一n衡量搜索算法时间效率的标准衡量搜索算法时间效率的标准r平均比较次数，或平均搜索长度平均比较次数，或平均搜索长度(ASL)3感谢你的观看2019年8月23顺序搜索顺序搜索n从表头从表头(或尾或尾)开始，依次用各对象的关键字与开始，依次用各对象的关键字与给定值给定值x比较比较r若值相等，搜索成功，返回下标若值相等，搜索成功，返回下标r若整个表都未找到，搜索失败若整个表都未找到，搜索失败4 1-01-0succ)1(.ASLniiniiipcp其中其中pi:搜索第搜索第 i 个元素概率个元素概率ci:搜索到第搜索到
3、第 i 个元素所需比较次数个元素所需比较次数.-102121)(11)(1nisuccnnnninASLpi=1/nci=i+1ASLunsucc=n+1搜索不成功的平均搜索长度搜索不成功的平均搜索长度搜索成功的平均搜索长度：搜索成功的平均搜索长度：n个元素个元素感谢你的观看2019年8月23有序顺序表有序顺序表n顺序搜索顺序搜索r从表头从表头(或尾或尾)开始，依次用各对象的关键字与给定开始，依次用各对象的关键字与给定值值x比较比较若值相等，搜索成功，返回下标若值相等，搜索成功，返回下标若若x比关键字大时，搜索失败比关键字大时，搜索失败5.-102121)(11)(1nisuccnnnninA
4、SL搜索成功的平均搜索长度：搜索成功的平均搜索长度：搜索不成功的平均搜索长度搜索不成功的平均搜索长度21)(111)(11-10nnnninnASLniunsuccn个元素，个元素，n+1个空档个空档感谢你的观看2019年8月23有序顺序表有序顺序表n折半搜索折半搜索rlow=0,high=n-1,mid=(low+high)/2rx先和先和mid元素比较元素比较若相等，搜索成功，返回下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1,mid=(low+high)/2若若x更大，继续在后半部分搜索更大，继续在后半部分搜索low=mid+1,
5、mid=(low+high)/26搜索搜索40lowmidhigh102030405060012345lowmid high102030405060012345lowmid high1020304050600123454030405040=40搜索成功搜索成功感谢你的观看2019年8月23有序顺序表有序顺序表n折半搜索折半搜索rlow=0,high=n-1,mid=(low+high)/2rx先和先和mid元素比较元素比较若相等，搜索成功，返回下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1,mid=(low+high)/2若若x更大，继
6、续在后半部分搜索更大，继续在后半部分搜索low=mid+1,mid=(low+high)/27搜索搜索25lowmidhigh102030405060012345lowmid high102030405060012345lowmid high10203040506001234525102520lowmid high102030405060012345lowhigh，搜索失败，搜索失败感谢你的观看2019年8月23有序顺序表有序顺序表n折半搜索折半搜索r折半搜索构造的判定树折半搜索构造的判定树设满二叉树设满二叉树n=2h-1则有则有2h=n+1，h=log2(n+1)平均搜索长度平均搜索长度85
7、0302040601011)(log11)(log11)21)(1)2*2*1)(2*3 2*22*(112212210 nnnnhnhhnASLh-hhsucc错位相减法错位相减法感谢你的观看2019年8月23有序顺序表有序顺序表n斐波那契搜索斐波那契搜索9F(n)=n,F(n-1)+F(n-2),n=0,1n20112350123458132134558967891011nF(n)感谢你的观看2019年8月23有序顺序表有序顺序表n斐波那契搜索斐波那契搜索rlow=1,high=n,mid=F(x-1),F(x)是最小的n的斐波那契数rx先和先和mid元素比较元素比较若相等，搜索成功，返回
8、下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1,mid=low+F(x-2)-1若若x更大，继续在后半部分搜索更大，继续在后半部分搜索low=mid+1,mid=low+F(x-3)-110011235012345813 21 34 55 8967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索搜索25感谢你的观看2019年8月23有序顺序表有序顺序表n斐波那契搜索斐波那契搜索rlow=1,high=n,mid=F(x-1),F(x)是最小的n的斐波那契数rx先
9、和先和mid元素比较元素比较若相等，搜索成功，返回下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1,mid=low+F(x-2)-1若若x更大，继续在后半部分搜索更大，继续在后半部分搜索low=mid+1,mid=low+F(x-3)-111011235012345813 21 34 55 8967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索搜索55感谢你的观看2019年8月23二叉搜索树二叉搜索树n二叉搜索树的概念二叉搜索树的概念r或者是空树或者是空树r或者
10、具有以下性质或者具有以下性质每个结点都有一个关键字每个结点都有一个关键字(key)左子树左子树上所有结点的上所有结点的key小于小于根结点的根结点的key右子树右子树上所有结点的上所有结点的key大于大于根结点的根结点的key左子树和右子树也是二叉搜索树左子树和右子树也是二叉搜索树12感谢你的观看2019年8月23二叉搜索树二叉搜索树n搜索搜索x操作操作r从根开始搜索从根开始搜索xr若当前结点为空，则搜索失败，否则若当前结点为空，则搜索失败，否则x小于当前结点小于当前结点key，在左子树搜索，在左子树搜索x大于当前结点大于当前结点key，在右子树搜索，在右子树搜索135365878194780
11、9452317搜索搜索23感谢你的观看2019年8月23二叉搜索树二叉搜索树n搜索搜索x操作操作r从根开始搜索从根开始搜索xr若当前结点为空，则搜索失败，否则若当前结点为空，则搜索失败，否则x小于当前结点小于当前结点key，在左子树搜索，在左子树搜索x大于当前结点大于当前结点key，在右子树搜索，在右子树搜索1453658781947809452317搜索搜索94感谢你的观看2019年8月23二叉搜索树二叉搜索树n插入插入x操作操作r从根开始搜索从根开始搜索x，若存在，放弃，若存在，放弃r否则搜索到叶子结点时否则搜索到叶子结点时x小于叶子结点小于叶子结点key，作为叶子结点左孩子，作为叶子结点
12、左孩子x大于叶子结点大于叶子结点key，作为叶子结点右孩子，作为叶子结点右孩子15插入插入885365878194780945231788感谢你的观看2019年8月23二叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右孩子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v(左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v16536587819478094517删除删除4523感谢你的观看2019年8月23二
13、叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右孩子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v(左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v175378094517删除删除78239488感谢你的观看2019年8月23二叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右孩
14、子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v(左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v1853659978094517删除删除782381948188感谢你的观看2019年8月23二叉搜索树二叉搜索树n性能分析性能分析r满二叉树满二叉树19 nisuccASL1i in n2 2loglog1 112niunsuccASL1nin2log11中间结点等概率搜索，中间结点等概率搜索，中间结点数为中间结点数为n叶子结点等概率搜索，叶子结点等概率搜索，叶子结点数为叶子结点数为n+1叶子为搜索失败情况叶子为搜索失败情况其他为
15、其他为key感谢你的观看2019年8月23二叉搜索树二叉搜索树n性能分析性能分析r一般二叉树一般二叉树20p(n)表示在一棵有表示在一棵有n个结点的二叉树上个结点的二叉树上成功搜索一个关键值的平均比较次数成功搜索一个关键值的平均比较次数左子树有左子树有i个结点个结点右子树有右子树有n-i-1个结点个结点根根 1-nip01 1)1 1(*)1 1(1 1)(*1 1 1 11 1)(i in np pi in ni ip pi in nn nn nnipinnn202log41)(*21)(1ip随机情况下，二叉树操作代价平均为随机情况下，二叉树操作代价平均为O(log2n)叶子为搜索失败情况
16、叶子为搜索失败情况其他为其他为key感谢你的观看2019年8月23二叉搜索树二叉搜索树n性能分析性能分析r一般二叉树一般二叉树21 nisuccASL1i ii ih hp p njunsuccASL0j jj jh hq qpi：搜索中间结点：搜索中间结点 i 概率概率hi：j深度深度qj：搜索叶子结点：搜索叶子结点 j 概率概率hj：j的深度的深度叶子为搜索失败情况叶子为搜索失败情况其他为其他为key感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r假设有假设有n个个key，每个，每个key搜索概率不同，除搜索概率不同，除key之之外的值外的值(即搜索不成功
17、情况即搜索不成功情况)搜索概率也不同，构造搜索概率也不同，构造平均搜索长度最小的二叉树平均搜索长度最小的二叉树例如，例如，3个个key=10，20，30，每个，每个key搜索概率为搜索概率为P=0.5,0.1,0.05，除，除key之外之外(空隙中空隙中)的值搜索概率的值搜索概率为为Q=0.15,0.1,0.05,0.05221020300.50.10.050.150.10.050.05感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最
18、小的造平均搜索长度最小的二叉树二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)，则，则C(0,n)是最后结果是最后结果w(i,j)表示表示第第 i+1 到到 j 个个key权权值及第值及第i到到j个空隙权个空隙权值和值和 w(i,j)=(qi+qj)+(pi+1+pj)23102030p1p2p3q0q1q2q3405060p4p5p6q4q5q6W(2,5)=(q2+q3+q4+q5)+(p3+p4+p5)感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，
19、第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)，则，则C(0,n)是最后结果是最后结果w(i,j)表示表示第第 i+1 到到 j 个个key权权值及第值及第i到到j个空隙个空隙权值和权值和 w(i,j)=(qi+qj)+(pi+1+pj)i+1,j以以k为根的最优二叉树代价为根的最优二叉树代价：=pk +c(i,k-1)+w(i,k-1)+c(k,j)+w(k,j)左子树的
20、代价左子树的代价右子树的代价右子树的代价根的代价根的代价左子树加一层的代价左子树加一层的代价右子树加一层的代价右子树加一层的代价24感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的，造平均搜索长度最小的二叉树二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)，则，则C(0,n)是最后结果是最后结果w(i,j)表示表示第第 i+1 到到 j 个个key
21、权值及第权值及第i到到j个空隙权值和个空隙权值和 w(i,j)=(qi+qj)+(pi+1+pj)i+1,j以以k为根为根的最优二叉树代价的最优二叉树代价：=pk +c(i,k-1)+w(i,k-1)+c(k,j)+w(k,j)=w(i,j)+c(i,k-1)+c(k,j)25左子树的代价左子树的代价右子树的代价右子树的代价树上权值和树上权值和感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i
22、,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)，则，则C(0,n)是最后结果是最后结果w(i,j)表示表示第第 i+1 到到 j 个个key权值及第权值及第i到到j个空隙权值和个空隙权值和 w(i,j)=(qi+qj)+(pi+1+pj)i+1,j以以k为根为根的最优二叉树代价的最优二叉树代价：=pk +c(i,k-1)+w(i,k-1)+c(k,j)+w(k,j)=w(i,j)+c(i,k-1)+c(k,j)i+1,j的最优二叉树代价：的最优二叉树代价：c(i,j)=w(i,j)+min c(i,k-1)+c(k,j)
23、,其中其中i k j 26树上权值和树上权值和左右子树代价和最小值左右子树代价和最小值感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其中其中i k j 27102030p1p2p3q0q1q2q34050
24、60p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 6感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其中其中i k j 282030p1p2p3q0q1q2q
25、3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 610感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其中其中i k j 291030p1p2p3
26、q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 620感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其中其中i k j 30102
27、0p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 630感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其中其中i k
28、j 31102030p1p2p3q0q1q2q35060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 640感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c(k,j),其
29、中其中i k j 32102030p1p2p3q0q1q2q34060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 650感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j)=w(i,j)+min c(i,k-1)+c
30、(k,j),其中其中i k j 33102030p1p2p3q0q1q2q34050p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6),0 k 660感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第1步：各步：各key自成二叉树，计算平均搜索长度自成二叉树，计算平均搜索长度c，保留最小值保留最小值1020300.50.10.050.150.10.050.05100.50.150.1200.10.10.05300.050.050.05c(0,1)=0.75c(1,2)=0.25c(2,3)=0.15w等于树上所有结点等于树上
31、所有结点(内部和外部内部和外部)的权值和，的权值和，c等于等于w加上左右子树的代价加上左右子树的代价c(0,1)=0.75c(1,2)=0.25c(2,3)=0.15W=0.75W=0.25W=0.1534感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第2步：相邻步：相邻2个个key成二叉树成二叉树,计算平均搜索长度计算平均搜索长度c 保留最小值保留最小值1020300.50.10.050.150.10.050.05100.50.150.1200.10.05c(0,1)200.10.10.05100.50.15c(1,2)300.050.050.05200
32、.10.1c(2,3)200.10.10.05300.050.05c(1,2)c(0,1)=0.75c(0,2)=1.15c(1,2)=0.25c(1,3)=0.5c(2,3)=0.15w等于树上所有结点等于树上所有结点(内部和外部内部和外部)的权值和，的权值和，c等于等于w加上左右子树的代价加上左右子树的代价c(0,2)=w+c(1,2)=1.15c(0,2)=w+c(0,1)=1.65c(1,3)=w+c(2,3)=0.5c(1,3)=w+c(0,1)=0.635感谢你的观看2019年8月23二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第3步：相邻步：相邻3个个key成二叉树成二
33、叉树,计算平均搜索长度计算平均搜索长度c 保留最小值保留最小值1020300.50.10.050.150.10.050.05c(0,1)=0.75c(0,3)=1.5c(1,2)=0.25c(2,3)=0.15w等于树上所有结点等于树上所有结点(内部和外部内部和外部)的权值和，的权值和，c等于等于w加上左右子树的代价加上左右子树的代价c(0,2)=1.15c(1,3)=0.5200.10.1100.50.15300.050.050.05200.10.10.05100.50.15300.050.05c(0,3)=w+c(1,3)=1.5c(0,3)=w+c(0,1)+c(2,3)=1.9c(0,3)=w+c(0,2)=2.15300.050.05 0.05200.1100.50.150.136感谢你的观看2019年8月23
