第七章搜索結(jié)構(gòu)課件

東南大學(xué)計算機學(xué)院xx第七章搜索結(jié)構(gòu)1感謝你的觀看2019年8月23東南大學(xué)計算機學(xué)院xx第七章搜索結(jié)構(gòu)1感謝你的觀看201本章主要內(nèi)容搜索的概念靜態(tài)搜索結(jié)構(gòu)順序搜索有序順序表順序搜索折半搜索斐波那契搜索二叉搜索樹2感謝你的觀看2019年8月23本章主要內(nèi)容搜索的概念2感謝你的觀看2019年8月23搜索的概念在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素搜索可能成功也可能不成功可唯一標(biāo)識一個元素的屬性稱為關(guān)鍵字(key)基于關(guān)鍵字的搜索結(jié)果是唯一的基于其他屬性的搜索結(jié)果可能不唯一衡量搜索算法時間效率的標(biāo)準(zhǔn)平均比較次數(shù)，或平均搜索長度(ASL)3感謝你的觀看2019年8月23搜索的概念在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素3感謝你的觀順序搜索從表頭(或尾)開始，依次用各對象的關(guān)鍵字與給定值x比較若值相等，搜索成功，返回下標(biāo)若整個表都未找到，搜索失敗4pi:搜索第i

個元素概率ci:搜索到第i

個元素所需比較次數(shù)pi=1/nci=i+1ASLunsucc=

n+1搜索不成功的平均搜索長度搜索成功的平均搜索長度：…n個元素感謝你的觀看2019年8月23順序搜索從表頭(或尾)開始，依次用各對象的關(guān)鍵字與給定值x比有序順序表順序搜索從表頭(或尾)開始，依次用各對象的關(guān)鍵字與給定值x比較若值相等，搜索成功，返回下標(biāo)若x比關(guān)鍵字大時，搜索失敗5搜索成功的平均搜索長度：搜索不成功的平均搜索長度…n個元素，n+1個空檔感謝你的觀看2019年8月23有序順序表順序搜索5搜索成功的平均搜索長度：搜索不成功的平均有序順序表折半搜索low=0,high=n-1,mid=(low+high)/2x先和mid元素比較若相等，搜索成功，返回下標(biāo)若x更小，繼續(xù)在前半部分搜索high=mid-1,mid=(low+high)/2若x更大，繼續(xù)在后半部分搜索low=mid+1,mid=(low+high)/26搜索40lowmidhigh102030405060012345lowmidhigh102030405060012345lowmidhigh10203040506001234540>3040<5040=40搜索成功感謝你的觀看2019年8月23有序順序表折半搜索6搜索40lowmidhigh102030有序順序表折半搜索low=0,high=n-1,mid=(low+high)/2x先和mid元素比較若相等，搜索成功，返回下標(biāo)若x更小，繼續(xù)在前半部分搜索high=mid-1,mid=(low+high)/2若x更大，繼續(xù)在后半部分搜索low=mid+1,mid=(low+high)/27搜索25lowmidhigh102030405060012345lowmidhigh102030405060012345lowmidhigh10203040506001234525<3025>1025>20lowmidhigh102030405060012345low>high，搜索失敗感謝你的觀看2019年8月23有序順序表折半搜索7搜索25lowmidhigh102030有序順序表折半搜索折半搜索構(gòu)造的判定樹設(shè)滿二叉樹n=2h-1則有2h=n+1，h=log2(n+1)平均搜索長度850======30<<<<<<>>>>>>20406010錯位相減法感謝你的觀看2019年8月23有序順序表折半搜索850======30<<<<<<>>>>有序順序表斐波那契搜索9F(n)=n,F(n-1)+F(n-2),n=0,1n≥20112350123458132134558967891011nF(n)感謝你的觀看2019年8月23有序順序表斐波那契搜索9F(n)=n,F(n-1)+F(有序順序表斐波那契搜索low=1,high=n,mid=F(x-1),F(x)是最小的≥n的斐波那契數(shù)x先和mid元素比較若相等，搜索成功，返回下標(biāo)若x更小，繼續(xù)在前半部分搜索high=mid-1,mid=low+F(x-2)-1若x更大，繼續(xù)在后半部分搜索low=mid+1,mid=low+F(x-3)-1100112350123458132134558967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索25感謝你的觀看2019年8月23有序順序表斐波那契搜索1001123501234581321有序順序表斐波那契搜索low=1,high=n,mid=F(x-1),F(x)是最小的≥n的斐波那契數(shù)x先和mid元素比較若相等，搜索成功，返回下標(biāo)若x更小，繼續(xù)在前半部分搜索high=mid-1,mid=low+F(x-2)-1若x更大，繼續(xù)在后半部分搜索low=mid+1,mid=low+F(x-3)-1110112350123458132134558967891011nF(n)101520253035123456404550556065789101112lowmidhigh搜索55感謝你的觀看2019年8月23有序順序表斐波那契搜索1101123501234581321二叉搜索樹二叉搜索樹的概念或者是空樹或者具有以下性質(zhì)每個結(jié)點都有一個關(guān)鍵字(key)左子樹上所有結(jié)點的key小于根結(jié)點的key右子樹上所有結(jié)點的key大于根結(jié)點的key左子樹和右子樹也是二叉搜索樹12感謝你的觀看2019年8月23二叉搜索樹二叉搜索樹的概念12感謝你的觀看2019年8月23二叉搜索樹搜索x操作從根開始搜索x若當(dāng)前結(jié)點為空，則搜索失敗，否則x小于當(dāng)前結(jié)點key，在左子樹搜索x大于當(dāng)前結(jié)點key，在右子樹搜索1353658781947809452317搜索23感謝你的觀看2019年8月23二叉搜索樹搜索x操作13536587819478094523二叉搜索樹搜索x操作從根開始搜索x若當(dāng)前結(jié)點為空，則搜索失敗，否則x小于當(dāng)前結(jié)點key，在左子樹搜索x大于當(dāng)前結(jié)點key，在右子樹搜索1453658781947809452317搜索94感謝你的觀看2019年8月23二叉搜索樹搜索x操作14536587819478094523二叉搜索樹插入x操作從根開始搜索x，若存在，放棄否則搜索到葉子結(jié)點時x小于葉子結(jié)點key，作為葉子結(jié)點左孩子x大于葉子結(jié)點key，作為葉子結(jié)點右孩子15插入885365878194780945231788感謝你的觀看2019年8月23二叉搜索樹插入x操作15插入8853658781947809二叉搜索樹刪除x操作從根開始搜索x，若不存在，放棄；否則：x只有左子樹，左孩子填補x只有右子樹，右孩子填補x有左右子樹，右子樹上中序第一結(jié)點v(左走直到頭)填補，用v的右孩子填補v16536587819478094517刪除4523感謝你的觀看2019年8月23二叉搜索樹刪除x操作16536587819478094517二叉搜索樹刪除x操作從根開始搜索x，若不存在，放棄；否則：x只有左子樹，左孩子填補x只有右子樹，右孩子填補x有左右子樹，右子樹上中序第一結(jié)點v(左走直到頭)填補，用v的右孩子填補v175378094517刪除78239488感謝你的觀看2019年8月23二叉搜索樹刪除x操作175378094517刪除782394二叉搜索樹刪除x操作從根開始搜索x，若不存在，放棄；否則：x只有左子樹，左孩子填補x只有右子樹，右孩子填補x有左右子樹，右子樹上中序第一結(jié)點v(左走直到頭)填補，用v的右孩子填補v1853659978094517刪除782381948188感謝你的觀看2019年8月23二叉搜索樹刪除x操作1853659978094517刪除78二叉搜索樹性能分析滿二叉樹19中間結(jié)點等概率搜索，中間結(jié)點數(shù)為n葉子結(jié)點等概率搜索，葉子結(jié)點數(shù)為n+1葉子為搜索失敗情況其他為key感謝你的觀看2019年8月23二叉搜索樹性能分析19中間結(jié)點等概率搜索，葉子結(jié)點等概率搜索二叉搜索樹性能分析一般二叉樹20p(n)表示在一棵有n個結(jié)點的二叉樹上成功搜索一個關(guān)鍵值的平均比較次數(shù)左子樹有i個結(jié)點右子樹有n-i-1個結(jié)點根隨機情況下，二叉樹操作代價平均為O(log2n)葉子為搜索失敗情況其他為key感謝你的觀看2019年8月23二叉搜索樹性能分析20p(n)表示在一棵有n個結(jié)點的二叉樹上二叉搜索樹性能分析一般二叉樹21pi：搜索中間結(jié)點i概率hi：j深度qj：搜索葉子結(jié)點j概率hj：j的深度葉子為搜索失敗情況其他為key感謝你的觀看2019年8月23二叉搜索樹性能分析21pi：搜索中間結(jié)點i概率qj：搜索二叉搜索樹最優(yōu)二叉搜索樹假設(shè)有n個key，每個key搜索概率不同，除key之外的值(即搜索不成功情況)搜索概率也不同，構(gòu)造平均搜索長度最小的二叉樹例如，3個key

={10，20，30}，每個key搜索概率為P={0.5,0.1,0.05}，除key之外(空隙中)的值搜索概率為Q={0.15,0.1,0.05,0.05}221020300.50.10.050.150.10.050.05感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹221020300.50.10.05二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)，則C(0,n)是最后結(jié)果w(i,j)表示第i+1到j(luò)個key權(quán)值及第i到j(luò)個空隙權(quán)值和

w(i,j)=(qi+…+qj)+(pi+1+…+pj)23102030p1p2p3q0q1q2q3405060p4p5p6q4q5q6W(2,5)=(q2+q3+q4+q5)+(p3+p4+p5)感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹23102030p1p2p3q0q1二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)，則C(0,n)是最后結(jié)果w(i,j)表示第i+1到j(luò)個key權(quán)值及第i到j(luò)個空隙權(quán)值和

w(i,j)=(qi+…+qj)+(pi+1+…+pj)i+1,…,j以k為根的最優(yōu)二叉樹代價：=pk+c(i,k-1)+w(i,k-1)+c(k,j)+w(k,j)左子樹的代價右子樹的代價根的代價左子樹加一層的代價右子樹加一層的代價24感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹左子樹的代價右子樹的代價根的代價左子二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)，則C(0,n)是最后結(jié)果w(i,j)表示第i+1到j(luò)個key權(quán)值及第i到j(luò)個空隙權(quán)值和

w(i,j)=(qi+…+qj)+(pi+1+…+pj)i+1,…,j以k為根的最優(yōu)二叉樹代價：=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左子樹的代價右子樹的代價樹上權(quán)值和感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹25左子樹的代價右子樹的代價樹上權(quán)值二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)，則C(0,n)是最后結(jié)果w(i,j)表示第i+1到j(luò)個key權(quán)值及第i到j(luò)個空隙權(quán)值和

w(i,j)=(qi+…+qj)+(pi+1+…+pj)i+1,…,j以k為根的最優(yōu)二叉樹代價：=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的最優(yōu)二叉樹代價：c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

26樹上權(quán)值和左右子樹代價和最小值感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹26樹上權(quán)值和左右子樹代價和最小值感二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

27102030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤6感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹27102030p1p2p3q0q1二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

282030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤610感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹282030p1p2p3q0q1q2二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

291030p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤620感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹291030p1p2p3q0q1q2二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

301020p1p2p3q0q1q2q3405060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤630感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹301020p1p2p3q0q1q2二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

31102030p1p2p3q0q1q2q35060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤640感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹31102030p1p2p3q0q1二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

32102030p1p2p3q0q1q2q34060p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤650感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹32102030p1p2p3q0q1二叉搜索樹最優(yōu)二叉搜索樹給定n個key，第i個key對應(yīng)的權(quán)值(概率)pi，空隙對應(yīng)的權(quán)值qi，造平均搜索長度最小的二叉樹c(i,j)表示第i+1到j(luò)個key構(gòu)造的最優(yōu)二叉樹的代價(平均搜索長度)c(i,j)=w(i,j)+min{c(i,k-1)+c(k,j)},其中i<k≤j

33102030p1p2p3q0q1q2q34050p4p5p6q4q5q6c(0,6)=w(0,6)+min{c(0,k)+c(k,6)},0<k≤660感謝你的觀看2019年8月23二叉搜索樹最優(yōu)二叉搜索樹33102030p1p2p3q0q1二叉搜索樹最優(yōu)二叉搜索樹第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等于樹上所有結(jié)點(內(nèi)部和外部)的權(quán)值和，c等于w加上左右子樹的代價c(0,1)=0.75c(1,2)=