《第七章搜索结构PPT课件》由会员分享，可在线阅读，更多相关《第七章搜索结构PPT课件（36页珍藏版）》请在金锄头文库上搜索。
1、东南大学计算机学院东南大学计算机学院 方效林方效林本课件借鉴了清华大学殷人昆老师和哈尔滨工业大学张岩老师的课件第七章第七章 搜索结构搜索结构本章主要内容本章主要内容n搜索的概念搜索的概念n静态搜索结构静态搜索结构r顺序搜索顺序搜索r有序顺序表有序顺序表顺序搜索顺序搜索折半搜索折半搜索斐波那契搜索斐波那契搜索n二叉搜索树二叉搜索树2搜索的概念搜索的概念n在数据集合中寻找满足某种条件的数据元素在数据集合中寻找满足某种条件的数据元素r搜索可能成功搜索可能成功r也可能不成功也可能不成功n可唯一标识一个元素的属性称为关键字可唯一标识一个元素的属性称为关键字(key)r基于关键字的搜索结果是唯一的基于关键
2、字的搜索结果是唯一的r基于其他属性的搜索结果可能不唯一基于其他属性的搜索结果可能不唯一n衡量搜索算法时间效率的标准衡量搜索算法时间效率的标准r平均比较次数，或平均搜索长度平均比较次数，或平均搜索长度(ASL)3顺序搜索顺序搜索n从表头从表头(或尾或尾)开始，依次用各对象的关键字与开始，依次用各对象的关键字与给定值给定值x比较比较r若值相等，搜索成功，返回下标若值相等，搜索成功，返回下标r若整个表都未找到，搜索失败若整个表都未找到，搜索失败4pi: 搜索第搜索第 i 个元素概率个元素概率ci: 搜索到第搜索到第 i 个元素所需比较次数个元素所需比较次数pi=1/nci=i+1ASLunsucc
3、= n+1搜索不成功的平均搜索长度搜索不成功的平均搜索长度搜索成功的平均搜索长度：搜索成功的平均搜索长度：n个元素个元素有序顺序表有序顺序表n顺序搜索顺序搜索r从表头从表头(或尾或尾)开始，依次用各对象的关键字与给定开始，依次用各对象的关键字与给定值值x比较比较若值相等，搜索成功，返回下标若值相等，搜索成功，返回下标若若x比关键字大时，搜索失败比关键字大时，搜索失败5搜索成功的平均搜索长度：搜索成功的平均搜索长度：搜索不成功的平均搜索长度搜索不成功的平均搜索长度n个元素，个元素，n+1个空档个空档有序顺序表有序顺序表n折半搜索折半搜索rlow=0, high=n-1,mid=(low+high
4、)/2rx先和先和mid元素比较元素比较若相等，搜索成功，返回下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1, mid=(low+high)/2若若x更大，继续在后半部分搜索更大，继续在后半部分搜索low=mid+1, mid=(low+high)/26搜索搜索40lowmidhigh102030405060012345lowmid high102030405060012345lowmid high1020304050600123454030405040=40搜索成功搜索成功有序顺序表有序顺序表n折半搜索折半搜索rlow=0, high
5、=n-1,mid=(low+high)/2rx先和先和mid元素比较元素比较若相等，搜索成功，返回下标若相等，搜索成功，返回下标若若x更小，继续在前半部分搜索更小，继续在前半部分搜索high=mid-1, mid=(low+high)/2若若x更大，继续在后半部分搜索更大，继续在后半部分搜索low=mid+1, mid=(low+high)/27搜索搜索25lowmidhigh102030405060012345lowmid high102030405060012345lowmid high10203040506001234525102520lowmid high102030405060012
6、345lowhigh，搜索失败，搜索失败有序顺序表有序顺序表n折半搜索折半搜索r折半搜索构造的判定树折半搜索构造的判定树设满二叉树设满二叉树n=2h-1则有则有2h=n+1，h=log2(n+1)平均搜索长度平均搜索长度850= = = = = = =3020406010错位相减法错位相减法二叉搜索树二叉搜索树n二叉搜索树的概念二叉搜索树的概念r或者是空树或者是空树r或者具有以下性质或者具有以下性质每个结点都有一个关键字每个结点都有一个关键字(key)左子树左子树上所有结点的上所有结点的key小于小于根结点的根结点的key右子树右子树上所有结点的上所有结点的key大于大于根结点的根结点的key
7、左子树和右子树也是二叉搜索树左子树和右子树也是二叉搜索树12二叉搜索树二叉搜索树n搜索搜索x操作操作r从根开始搜索从根开始搜索xr若当前结点为空，则搜索失败，否则若当前结点为空，则搜索失败，否则x小于当前结点小于当前结点key，在左子树搜索，在左子树搜索x大于当前结点大于当前结点key，在右子树搜索，在右子树搜索1353658781947809452317搜索搜索23二叉搜索树二叉搜索树n搜索搜索x操作操作r从根开始搜索从根开始搜索xr若当前结点为空，则搜索失败，否则若当前结点为空，则搜索失败，否则x小于当前结点小于当前结点key，在左子树搜索，在左子树搜索x大于当前结点大于当前结点key，在
8、右子树搜索，在右子树搜索1453658781947809452317搜索搜索94二叉搜索树二叉搜索树n插入插入x操作操作r从根开始搜索从根开始搜索x，若存在，放弃，若存在，放弃r否则搜索到叶子结点时否则搜索到叶子结点时x小于叶子结点小于叶子结点key，作为叶子结点左孩子，作为叶子结点左孩子x大于叶子结点大于叶子结点key，作为叶子结点右孩子，作为叶子结点右孩子15插入插入885365878194780945231788二叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右
9、孩子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v (左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v16536587819478094517删除删除4523二叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右孩子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v (左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v175378094517删除删
10、除78239488二叉搜索树二叉搜索树n删除删除x操作操作r从根开始搜索从根开始搜索x，若不存在，放弃；否则：，若不存在，放弃；否则：x只有左子树，左孩子填补只有左子树，左孩子填补x只有右子树，右孩子填补只有右子树，右孩子填补x有左右子树，右子树上中序第一结点有左右子树，右子树上中序第一结点v (左走直到头左走直到头)填补，用填补，用v的右孩子填补的右孩子填补v1853659978094517删除删除782381948188二叉搜索树二叉搜索树n性能分析性能分析r满二叉树满二叉树19中间结点等概率搜索，中间结点等概率搜索，中间结点数为中间结点数为n叶子结点等概率搜索，叶子结点等概率搜索，叶子结
11、点数为叶子结点数为n+1叶子为搜索失败情况叶子为搜索失败情况其他为其他为key二叉搜索树二叉搜索树n性能分析性能分析r一般二叉树一般二叉树20p(n)表示在一棵有表示在一棵有n个结点的二叉树上个结点的二叉树上成功搜索一个关键值的平均比较次数成功搜索一个关键值的平均比较次数左子树有左子树有i个结点个结点右子树有右子树有n-i-1个结点个结点根根随机情况下，二叉树操作代价平均为随机情况下，二叉树操作代价平均为O(log2n)叶子为搜索失败情况叶子为搜索失败情况其他为其他为key二叉搜索树二叉搜索树n性能分析性能分析r一般二叉树一般二叉树21pi：搜索中间结点：搜索中间结点 i 概率概率hi：j深度
12、深度qj：搜索叶子结点：搜索叶子结点 j 概率概率hj：j的深度的深度叶子为搜索失败情况叶子为搜索失败情况其他为其他为key二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r假设有假设有n个个key，每个，每个key搜索概率不同，除搜索概率不同，除key之之外的值外的值(即搜索不成功情况即搜索不成功情况)搜索概率也不同，构造搜索概率也不同，构造平均搜索长度最小的二叉树平均搜索长度最小的二叉树例如，例如，3个个key =10，20，30，每个，每个key搜索概率为搜索概率为P=0.5, 0.1, 0.05，除，除key之外之外(空隙中空隙中)的值搜索概率的值搜索概率为为Q=0.15, 0.1,
13、 0.05, 0.05221020300.50.10.050.150.10.050.05二叉搜索树二叉搜索树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权权值及第值及第i到到j个空隙权个空隙权值和值和 w(i,j) = (qi+
14、qj) + (pi+1+ pj)23102030p1p2p3q0q1q2q3405060p4p5p6q4q5q6W(2,5)=(q2+q3+q4+q5) + (p3+p4+p5)二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)，则，则C(0,n)是最后结果是最后结果w(i,j)表示表示第第 i+1 到到
15、 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)左子树的代价左子树的代价右子树的代价右子树的代价根的代价根的代价左子树加一层的代价左子树加一层的代价右子树加一层的代价右子树加一层的代价二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的，造平均搜
16、索长度最小的二叉树二叉树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) = w(i,j) + c(i,k-1) + c(k,j) 25左子树的代价左子树的代价右子树的代价右
17、子树的代价树上权值和树上权值和二叉搜索树二叉搜索树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权值及第权值及第i到到j个空隙权值和个空隙权值和 w(i,j) = (qi+qj) + (pi+1+ pj)i+1, , j以以k为
18、根为根的最优二叉树代价的最优二叉树代价： = 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) , 其中其中i k j 26树上权值和树上权值和左右子树代价和最小值左右子树代价和最小值二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平均
19、搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 27102030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 6二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造平
20、均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 282030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 610二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，造
21、平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 291030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 620二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树，
22、造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 301020p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 630二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉树
23、，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 31102030p1p2p3q0q1q2q35060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 640二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二叉
24、树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 32102030p1p2p3q0q1q2q34060p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 650二叉搜索树二叉搜索树n最优二叉最优二叉搜索树搜索树r给定给定n个个key，第第i个个key对应的权值对应的权值(概率概率)pi，空隙对，空隙对应的权值应的权值qi，造平均搜索长度最小的二
25、叉树，造平均搜索长度最小的二叉树c(i,j)表示第表示第 i+1 到到 j 个个key构造的最优二叉树的代价构造的最优二叉树的代价(平平均搜索长度均搜索长度)c(i,j) = w(i,j) + min c(i,k-1) + c(k,j) , 其中其中i k j 33102030p1p2p3q0q1q2q34050p4p5p6q4q5q6c(0,6)=w(0,6)+minc(0,k)+c(k,6), 0 k 660二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第1步：各步：各key自成二叉树，计算平均搜索长度自成二叉树，计算平均搜索长度c，保留最小值保留最小值1020300.50.10.
26、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等于树上所有结点等于树上所有结点(内部和外部内部和外部)的权值和，的权值和，c等于等于w加上左右子树的代价加上左右子树的代价c(0,1)=0.75c(1,2)=0.25c(2,3)=0.15W=0.75W=0.25W=0.15二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第2步：相邻步：相邻2个个key成二叉树成二叉树, 计算平均搜索长度计算平均搜索长度c 保留最小值保留最小值1020300.50.10.050
27、.150.10.050.05100.50.150.1200.10.05c(0,1)200.10.10.05100.50.15c(1,2)300.050.050.05200.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.5
28、c(1,3)=w+c(0,1)=0.6二叉搜索树二叉搜索树n最优二叉搜索树最优二叉搜索树r第第3步：相邻步：相邻3个个key成二叉树成二叉树, 计算平均搜索长度计算平均搜索长度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.1
