![數據結構與算法分析第八章查找_第1頁](http://file4.renrendoc.com/view/20cece2adff85383845a8a6b1dd6bafe/20cece2adff85383845a8a6b1dd6bafe1.gif)
![數據結構與算法分析第八章查找_第2頁](http://file4.renrendoc.com/view/20cece2adff85383845a8a6b1dd6bafe/20cece2adff85383845a8a6b1dd6bafe2.gif)
![數據結構與算法分析第八章查找_第3頁](http://file4.renrendoc.com/view/20cece2adff85383845a8a6b1dd6bafe/20cece2adff85383845a8a6b1dd6bafe3.gif)
![數據結構與算法分析第八章查找_第4頁](http://file4.renrendoc.com/view/20cece2adff85383845a8a6b1dd6bafe/20cece2adff85383845a8a6b1dd6bafe4.gif)
![數據結構與算法分析第八章查找_第5頁](http://file4.renrendoc.com/view/20cece2adff85383845a8a6b1dd6bafe/20cece2adff85383845a8a6b1dd6bafe5.gif)
版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數據結構與算法分析第八章查找第1頁,課件共151頁,創(chuàng)作于2023年2月所謂搜索(查找檢索),就是在數據集合中尋找滿足某種條件的數據對象
1.搜索成功即找到滿足條件的數據對象,作為結果,可報告該對象在結構中的位置,還可給出該對象中的具體信息2.搜索不成功或搜索失敗。作為結果,應報告一些信息,如失敗標志、位置等第2頁,課件共151頁,創(chuàng)作于2023年2月通常稱用于搜索的數據集合為搜索結構,它是由同一數據類型的對象(或記錄)組成在每個對象中有若干屬性,其中有一個屬性,其值可唯一地標識這個對象。稱為關鍵碼。使用基于關鍵碼的搜索,搜索結果應是唯一的。但在實際應用時,搜索條件是多方面的,可以使用基于屬性的搜索方法,但搜索結果可能不唯一第3頁,課件共151頁,創(chuàng)作于2023年2月實施搜索時有兩種不同的環(huán)境靜態(tài)環(huán)境搜索結構在插入和刪除等操作的前后不發(fā)生改變
靜態(tài)搜索表
動態(tài)環(huán)境為保持較高的搜索效率,搜索結構在執(zhí)行插入和刪除等操作的前后將自動進行調整,結構可能發(fā)生變化動態(tài)搜索表第4頁,課件共151頁,創(chuàng)作于2023年2月查找算法的評價指標查找成功:最少比較次數最多比較次數平均比較次數查找失敗:最少比較次數最多比較次數平均比較次數第5頁,課件共151頁,創(chuàng)作于2023年2月
以順序表或線性鏈表表示靜態(tài)查找表順序查找第6頁,課件共151頁,創(chuàng)作于2023年2月ST.elem順序查找過程假設給定值e=64,要求ST.elem[k]=e,問:k=?kk第7頁,課件共151頁,創(chuàng)作于2023年2月ST.elemiST.elemi60ikey=64key=60i64第8頁,課件共151頁,創(chuàng)作于2023年2月intSearch_Seq(TBST,TYPEkey){ST.elem[0].key=key;//“哨兵”
for(i=ST.length;ST.elem[i].key!=key;--i);//從后往前找
returni;//找不到時,i為0}第9頁,課件共151頁,創(chuàng)作于2023年2月分析順序查找的時間性能第10頁,課件共151頁,創(chuàng)作于2023年2月查找算法的平均查找長度(AverageSearchLength)
為確定記錄在查找表中的位置,需和給定值進行比較的關鍵字個數的期望值第11頁,課件共151頁,創(chuàng)作于2023年2月其中:n為表長,Pi
為查找表中第i個記錄的概率,且,Ci為找到該記錄時,曾和給定值比較過的關鍵字的個數第12頁,課件共151頁,創(chuàng)作于2023年2月在等概率情形pi=1/n,i=1,2,,n
在搜索不成功情形,ASLunsucc=n+1
第13頁,課件共151頁,創(chuàng)作于2023年2月查找成功:最少比較次數1
最多比較次數n
平均比較次數(n+1)/2
查找失敗:最少比較次數n+1
最多比較次數n+1
平均比較次數n+1第14頁,課件共151頁,創(chuàng)作于2023年2月
上述順序查找表的查找算法簡單,但平均查找長度較大,特別不適用于表長較大的查找表折半查找
若以有序表表示靜態(tài)查找表,則查找過程可以基于“折半”進行第15頁,課件共151頁,創(chuàng)作于2023年2月基于有序順序表的折半搜索設n個對象存放在一個有序順序表中,并按其關鍵碼從小到大排好了序折半搜索時,先求位于搜索區(qū)間正中的對象的下標mid,用其關鍵碼與給定值x比較第16頁,課件共151頁,創(chuàng)作于2023年2月1.Element[mid].key==x搜索成功2.Element[mid].key>x把搜索區(qū)間縮小到表的前半部分,繼續(xù)折半搜索3.Element[mid].key<x把搜索區(qū)間縮小到表的后半部分,繼續(xù)折半搜索如果搜索區(qū)間已縮小到一個對象,仍未找到想要搜索的對象,則搜索失敗第17頁,課件共151頁,創(chuàng)作于2023年2月ST.elemST.length例如:key=64
的查找過程如下mid=(low+high)/2Low
指示查找區(qū)間的下界high
指示查找區(qū)間的上界第18頁,課件共151頁,創(chuàng)作于2023年2月搜索成功的例子-101346810126012345678搜索lowmidhigh6
6810125678lowmidhigh665lowmidhigh6第19頁,課件共151頁,創(chuàng)作于2023年2月搜索失敗的例子-101346810125012345678搜索lowmidhigh5
6810125678lowmidhigh655lowmidhigh5第20頁,課件共151頁,創(chuàng)作于2023年2月intSearch_Bin(TBST,TYPEkey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;if(key<ST.elem[mid].key)high=mid-1;
if(key>ST.elem[mid].key)low=mid+1;}return0;}第21頁,課件共151頁,創(chuàng)作于2023年2月搜索成功時檢測指針停留在樹中某個結點搜索不成功時檢測指針停留在某個外結點(失敗結點)3515455025102030搜索22搜索45第22頁,課件共151頁,創(chuàng)作于2023年2月有序順序表的折半搜索的判定樹
(10,20,30,40,50,60)1050======30<<<<<<>>>>>>204060第23頁,課件共151頁,創(chuàng)作于2023年2月先看一個具體的情況,假設:n=11分析折半查找的平均查找長度6391425781011判定樹12233334444第24頁,課件共151頁,創(chuàng)作于2023年2月查找成功:最少比較次數?
最多比較次數?
平均比較次數?
查找失敗:最少比較次數?
最多比較次數?
平均比較次數?第25頁,課件共151頁,創(chuàng)作于2023年2月假設n=2h-1并且查找概率相等則
在n>50時,可得近似結果
一般情況下,表長為n的折半查找的判定樹的深度和含有n個結點的完全二叉樹的深度相同第26頁,課件共151頁,創(chuàng)作于2023年2月索引順序查找1)由索引確定記錄所在區(qū)間2)在順序表的某個區(qū)間內進行查找注意:索引可以根據查找表的特點來構造可見:
索引順序查找的過程也是一個“縮小區(qū)間”的查找過程第27頁,課件共151頁,創(chuàng)作于2023年2月分塊查找查找過程:將表分成幾塊,塊內無序,塊間有序;先確定待查記錄所在塊,再在塊內查找適用條件:分塊有序表算法實現用數組存放待查記錄,每個數據元素至少含有關鍵字域建立索引表,每個索引表結點含有最大關鍵字域和指向本塊第一個結點的指針第28頁,課件共151頁,創(chuàng)作于2023年2月12345678910111213141516171822121389203342443824486058745786532248861713索引表查38第29頁,課件共151頁,創(chuàng)作于2023年2月分塊查找方法評價第30頁,課件共151頁,創(chuàng)作于2023年2月索引順序查找的平均查找長度=
查找“索引”的平均查找長度
+查找“順序表”的平均查找長度第31頁,課件共151頁,創(chuàng)作于2023年2月ASL最大最小兩者之間表結構有序表、無序表有序表分塊有序表存儲結構順序存儲結構線性鏈表順序存儲結構順序存儲結構線性鏈表查找方法比較順序查找折半查找分塊查找第32頁,課件共151頁,創(chuàng)作于2023年2月二叉排序樹(二叉查找樹)第33頁,課件共151頁,創(chuàng)作于2023年2月(1)若它的左子樹不空,則左子樹上所有結點的值均小于根結點的值
二叉排序樹或者是一棵空樹;或者是具有如下特性的二叉樹(3)它的左、右子樹也都分別是二叉排序樹(2)若它的右子樹不空,則右子樹上所有結點的值均大于根結點的值第34頁,課件共151頁,創(chuàng)作于2023年2月503080209010854035252388是二叉排序樹66不第35頁,課件共151頁,創(chuàng)作于2023年2月二叉排序樹的
查找算法第36頁,課件共151頁,創(chuàng)作于2023年2月
1)若給定值等于根結點的關鍵字,則查找成功
2)若給定值小于根結點的關鍵字,則繼續(xù)在左子樹上進行查找
3)若給定值大于根結點的關鍵字,則繼續(xù)在右子樹上進行查找否則:若二叉排序樹為空,則查找不成功第37頁,課件共151頁,創(chuàng)作于2023年2月50308020908540358832查找關鍵字50505030403550508090==50,35,90,95第38頁,課件共151頁,創(chuàng)作于2023年2月n個結點的二叉搜索樹的數目3個結點的二叉搜索樹122133132123123{123}{132}{213}{231}{312}{321}第39頁,課件共151頁,創(chuàng)作于2023年2月
如果對一棵二叉搜索樹進行中序遍歷,可以按從小到大的順序,將各結點關鍵碼排列起來,所以也稱二叉搜索樹為二叉排序樹第40頁,課件共151頁,創(chuàng)作于2023年2月在查找過程中,生成了一條查找路徑
從根結點出發(fā),沿著左分支或右分支逐層向下直至關鍵字等于給定值的結點或者從根結點出發(fā),沿著左分支或右分支逐層向下直至指針指向空樹為止
——查找成功
——查找不成功第41頁,課件共151頁,創(chuàng)作于2023年2月351545504025102030搜索45搜索成功
搜索28搜索失敗第42頁,課件共151頁,創(chuàng)作于2023年2月查找性能的分析
對于每一棵特定的二叉排序樹,均可按照平均查找長度的定義來求它的ASL值,顯然,由值相同的n個關鍵字,構造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同,甚至可能差別很大第43頁,課件共151頁,創(chuàng)作于2023年2月由關鍵字序列3,1,2,5,4構造而得的二叉排序樹由關鍵字序列1,2,3,4,5構造而得的二叉排序樹2134535412ASL=(1+2+3+4+5)/5=3ASL=(1+2+3+2+3)/5=2.2第44頁,課件共151頁,創(chuàng)作于2023年2月
輸入數據,建立二叉搜索樹的過程輸入數據
{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981第45頁,課件共151頁,創(chuàng)作于2023年2月
同樣3個數據{1,2,3},輸入順序不同,建立起來的二叉搜索樹的形態(tài)也不同。這直接影響到二叉搜索樹的搜索性能如果輸入序列選得不好,會建立起一棵單支樹,使得二叉搜索樹的高度達到最大
第46頁,課件共151頁,創(chuàng)作于2023年2月{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}123111132223323第47頁,課件共151頁,創(chuàng)作于2023年2月二叉平衡樹(AVL樹)第48頁,課件共151頁,創(chuàng)作于2023年2月
一棵AVL樹或者是空樹,或者是具有下列性質的二叉搜索樹:它的左子樹和右子樹都是AVL樹,且左子樹和右子樹的高度之差的絕對值不超過1
不平衡平衡ABCABCDEDE第49頁,課件共151頁,創(chuàng)作于2023年2月
結點的平衡因子
(balancefactor)每個結點附加一個數字,給出該結點右子樹的高度減去左子樹的高度所得的高度差,這個數字即為結點的平衡因子AVL樹任一結點平衡因子只能取-1,0,1第50頁,課件共151頁,創(chuàng)作于2023年2月如果一個結點的平衡因子的絕對值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹如果一棵二叉搜索樹是平衡的,
且有n個結點,其高度可保持在
O(log2n),平均搜索長度也可保持在O(log2n)第51頁,課件共151頁,創(chuàng)作于2023年2月548254821是平衡樹不是平衡樹第52頁,課件共151頁,創(chuàng)作于2023年2月平衡化旋轉如果在一棵平衡的二叉搜索樹中插入一個新結點,造成了不平衡。此時必須調整樹的結構,使之平衡化平衡化旋轉有兩類:單旋轉(左旋和右旋)
雙旋轉(左旋加右旋和右旋加左旋)第53頁,課件共151頁,創(chuàng)作于2023年2月每插入一個新結點時,AVL樹中相關結點的平衡狀態(tài)會發(fā)生改變。因此,在插入一個新結點后,需要從插入位置沿通向根的路徑回溯,檢查各結點的平衡因子第54頁,課件共151頁,創(chuàng)作于2023年2月如果在某一結點發(fā)現高度不平衡,停止回溯。從發(fā)生不平衡的結點起,沿剛才回溯的路徑取直接下兩層的結點第55頁,課件共151頁,創(chuàng)作于2023年2月如果這三個結點處于一條直線上,則采用單旋轉進行平衡化單旋轉可按其方向分為左單旋轉和右單旋轉,其中一個是另一個的鏡像,其方向與不平衡的形狀相關如果這三個結點處于一條折線上,則采用雙旋轉進行平衡化雙旋轉分為先左后右和先右后左兩類第56頁,課件共151頁,創(chuàng)作于2023年2月右單旋轉R型左單旋轉L型第57頁,課件共151頁,創(chuàng)作于2023年2月左右雙旋轉LR型右左雙旋轉RL型第58頁,課件共151頁,創(chuàng)作于2023年2月左單旋轉
(RotateLeft,L型)第59頁,課件共151頁,創(chuàng)作于2023年2月hhhACEBDhhh+1BACEDhhh+1CEABD+1+20+100在子樹E中插入新結點,該子樹高度增1導致結點A的平衡因子變成+2,產生不平衡(L型)以結點C為旋轉軸,將結點A反時針旋轉第60頁,課件共151頁,創(chuàng)作于2023年2月右單旋轉
(RotateRight,R型)第61頁,課件共151頁,創(chuàng)作于2023年2月在子樹D中插入新結點,該子樹高度增1導致結點A的平衡因子變成-2,產生不平衡(R型)以結點B為旋轉軸,將結點A順時針旋轉hhhACEBDhh+1BACEDhhh+1CEABDh000-1-1-2第62頁,課件共151頁,創(chuàng)作于2023年2月
先左后右雙旋轉
(RotationLeftRight,LR型)第63頁,課件共151頁,創(chuàng)作于2023年2月在子樹F或G中插入新結點,該子樹高度增1導致結點A的平衡因子變成-2,產生不平衡(LR型)首先以結點E為旋轉軸,將結點B反時針旋轉,以E代替原來B的位置,做左單旋轉再以結點E為旋轉軸,將結點A順時針旋轉,做右單旋轉第64頁,課件共151頁,創(chuàng)作于2023年2月插入00-1-2+1-1hhACED0h-1h-1hhAh-1hBCEDB左單旋轉FGFG第65頁,課件共151頁,創(chuàng)作于2023年2月00-200+1hhACED-2h-1hhhAh-1hBCEDB右單旋轉FGFG第66頁,課件共151頁,創(chuàng)作于2023年2月先右后左雙旋轉
(RotationRightLeft,RL型)第67頁,課件共151頁,創(chuàng)作于2023年2月在子樹F或G中插入新結點,該子樹高度增1導致結點A的平衡因子變成2,產生不平衡(RL型)首先以結點D為旋轉軸,將結點C順時針旋轉,以D代替原來C的位置,做右單旋轉再以結點D為旋轉軸,將結點A反時針旋轉,做左單旋轉第68頁,課件共151頁,創(chuàng)作于2023年2月插入右單旋轉+1000-1+10hhACEDh-1BFGh-1+2000hhACEhBFGh-1D第69頁,課件共151頁,創(chuàng)作于2023年2月00+20-10hhACE+2h-1hhhAh-1hBCEDB左單旋轉FGFGD第70頁,課件共151頁,創(chuàng)作于2023年2月構造二叉平衡(查找)樹的方法在插入過程中,采用平衡旋轉技術依次插入的關鍵字為5,4,2,8,6,95424258665842向右旋轉一次先向右旋轉再向左旋轉第71頁,課件共151頁,創(chuàng)作于2023年2月426589642895向左旋轉一次繼續(xù)插入關鍵字9第72頁,課件共151頁,創(chuàng)作于2023年2月輸入關鍵碼序列為{16,3,7,11,9,26,18,14,15}插入和調整過程如下161603163-10701-2左右雙旋731600073110-111612273161190-1-2右單旋37169000371126916110112第73頁,課件共151頁,創(chuàng)作于2023年2月右左雙旋左單18183-116000732611-1971614002691110316027390182611-11691711261第74頁,課件共151頁,創(chuàng)作于2023年2月1518231816-2左右雙旋73000117149-1161501112626141-29從空樹開始的建樹過程第75頁,課件共151頁,創(chuàng)作于2023年2月B樹大型文件訪問方法第76頁,課件共151頁,創(chuàng)作于2023年2月B樹是一種平衡的多路
查找樹第77頁,課件共151頁,創(chuàng)作于2023年2月
在
m
階的B樹上,每個非終端結點可能含有:
n
個關鍵字Ki(1≤i≤n)n<m
n
個指向記錄的指針Di(1≤i≤n)
n+1
個指向子樹的指針Ai(0≤i≤n)多叉樹的特性第78頁,課件共151頁,創(chuàng)作于2023年2月非葉結點中的多個關鍵字均自小至大有序排列,即:K1<K2<…<KnAi-1所指子樹上所有關鍵字均小于KiAi所指子樹上所有關鍵字均大于Ki查找樹的特性第79頁,課件共151頁,創(chuàng)作于2023年2月平衡樹的特性樹中所有葉子結點均不帶信息,且在樹中的同一層次上根結點或為葉子結點,或至少含有兩棵子樹其余所有非葉結點均至少含有m/2棵子樹,至多含有m
棵子樹第80頁,課件共151頁,創(chuàng)作于2023年2月
從根結點出發(fā),沿指針搜索結點和在結點內進行順序(或折半)查找兩個過程交叉進行查找過程第81頁,課件共151頁,創(chuàng)作于2023年2月
若查找成功,則返回指向被查關鍵字所在結點的指針和關鍵字在結點中的位置若查找不成功,則返回插入位置第82頁,課件共151頁,創(chuàng)作于2023年2月在查找不成功之后,需進行插入顯然,關鍵字插入的位置必定在最下層的非葉結點,有下列幾種情況插入第83頁,課件共151頁,創(chuàng)作于2023年2月插入后,該結點的關鍵字個數n<m,不修改指針第84頁,課件共151頁,創(chuàng)作于2023年2月插入后,該結點的關鍵字個數n=m,則需進行“結點分裂”,令s=m/2,在原結點中保留(A0,K1,……,Ks-1,As-1);建新結點(As,Ks+1,……,Kn,An);將(Ks,p)插入雙親結點第85頁,課件共151頁,創(chuàng)作于2023年2月若雙親為空,則建新的根結點第86頁,課件共151頁,創(chuàng)作于2023年2月下列為3階B樹502040
80插入關鍵字=60
6080,9060809090
508060,30
4020305080305080第87頁,課件共151頁,創(chuàng)作于2023年2月
和插入的考慮相反,首先必須找到待刪關鍵字所在結點,并且要求刪除之后,結點中關鍵字的個數不能小于m/2-1,否則,要從其左(或右)兄弟結點“借調”關鍵字,若其左和右兄弟結點均無關鍵字可借(結點中只有最少量的關鍵字),則必須進行結點的“合并”刪除第88頁,課件共151頁,創(chuàng)作于2023年2月在含N
個關鍵字的B樹上進行一次查找,需訪問的結點個數不超過
logm/2((N+1)/2)+1查找性能第89頁,課件共151頁,創(chuàng)作于2023年2月是B樹的一種變型B+樹第90頁,課件共151頁,創(chuàng)作于2023年2月
每個葉子結點中含有n
個關鍵字和n
個指向記錄的指針;并且,所有葉子結點彼此相鏈接構成一個有序鏈表,其頭指針指向含最小關鍵字的結點第91頁,課件共151頁,創(chuàng)作于2023年2月
每個非葉結點中的關鍵字Ki即為其相應指針Ai所指子樹中關鍵字的最大值所有葉子結點都處在同一層次上,每個葉子結點中關鍵字的個數均介于m/2和m之間第92頁,課件共151頁,創(chuàng)作于2023年2月查找過程
在B+樹上,既可以進行縮小范圍的查找,也可以進行順序查找
在進行縮小范圍的查找時,不管成功與否,都必須查到葉子結點才能結束
若在結點內查找時,給定值≤Ki,則應繼續(xù)在Ai所指子樹中進行查找第93頁,課件共151頁,創(chuàng)作于2023年2月插入和刪除類似于B樹進行,即必要時,也需要進行結點的“分裂”或“歸并”第94頁,課件共151頁,創(chuàng)作于2023年2月
5096
155062
78
96
717884
89
96
566220264350
3815sqroot第95頁,課件共151頁,創(chuàng)作于2023年2月第96頁,課件共151頁,創(chuàng)作于2023年2月第97頁,課件共151頁,創(chuàng)作于2023年2月
B+樹的刪除僅在葉結點上進行。當在葉結點上刪除一個關鍵碼-指針索引項后,結點中的子樹棵數仍然不少于m/2,這屬于簡單刪除,其上層索引可以不改變。如果刪除的關鍵碼是該結點的最小關鍵碼,但因在其上層的副本只是起了一個引導搜索的“分界關鍵碼”的作用,所以上層的副本仍然可以保留。如果在葉結點中刪除一個關鍵碼-指針索引項后,該結點中的子樹棵數n小于結點子樹棵數的下限m/2,必須做結點的調整或合并工作。第98頁,課件共151頁,創(chuàng)作于2023年2月刪除18刪除12第99頁,課件共151頁,創(chuàng)作于2023年2月如果右兄弟結點的子樹棵數已達到下限m/2,沒有多余的關鍵碼可以移入被刪關鍵碼所在的結點,這時必須進行兩個結點的合并。將右兄弟結點中的所有關鍵碼-指針索引項移入被刪關鍵碼所在結點,再將右兄弟結點刪去。第100頁,課件共151頁,創(chuàng)作于2023年2月刪除33進行結點合并第101頁,課件共151頁,創(chuàng)作于2023年2月結點的合并將導致雙親結點中“分界關鍵碼”的減少,有可能減到非葉結點中子樹棵數的下限m/2
以下。這樣將引起非葉結點的調整或合并。如果根結點的最后兩個子女結點合并,樹的層數就會減少一層。第102頁,課件共151頁,創(chuàng)作于2023年2月
TheB*-Treesplitstwopagesforthree,andcombinesthreepagesintotwo.Inthisway,nodesarealways2/3full.第103頁,課件共151頁,創(chuàng)作于2023年2月
Trie樹是一棵度m
2的樹,它的每一層分支不是靠整個關鍵碼的值來確定,而是由關鍵碼的一個分量來確定。如下圖所示Trie樹,關鍵碼由英文字母組成。它包括兩類結點:元素結點和分支結點。元素結點包含整個key數據;分支結點有27個指針,其中有一個空白字符‘b’,用來終結關鍵碼;其它用來標識‘a’,‘b’,...,‘z’等26個英文字母。Trie樹Trie樹的定義當關鍵碼是可變長時,Trie樹是一種特別有用的索引結構。第104頁,課件共151頁,創(chuàng)作于2023年2月第105頁,課件共151頁,創(chuàng)作于2023年2月
在第0層,所有的關鍵碼根據它們第0位字符,被劃分到互不相交的27個類中。因此,root→brch.link[i]指向一棵子Trie樹,該子Trie樹上所包含的所有關鍵碼都是以第i個英文字母開頭。若某一關鍵碼第j
位字母在英文字母表中順序為i(i=0,1,,26),則它在Trie樹的第
j層分支結點中從第i
個指針向下找第
j+1位字母所在結點。當一棵子Trie樹上只有一個關鍵碼時,就由一個元素結點來代替。在這個結點中包含有關鍵碼,以及其它相關的信息,如對應數據對象的存放地址等。第106頁,課件共151頁,創(chuàng)作于2023年2月
Trie樹的搜索為了在Trie樹上進行搜索,要求把關鍵碼分解成一些字符元素,并根據這些字符向下進行分支。第107頁,課件共151頁,創(chuàng)作于2023年2月在Trie樹上插入bobwhite和bluejay后的結果第108頁,課件共151頁,創(chuàng)作于2023年2月哈希查找(Hash)第109頁,課件共151頁,創(chuàng)作于2023年2月
以上討論的表示查找表的各種結構的共同特點:記錄在表中的位置和它的關鍵字之間不存在一個確定的關系第110頁,課件共151頁,創(chuàng)作于2023年2月
查找的過程為給定值依次和關鍵字集合中各個關鍵字進行比較
查找的效率取決于和給定值進行比較的關鍵字個數第111頁,課件共151頁,創(chuàng)作于2023年2月
用這類方法表示的查找表,其平均查找長度都不為零
不同的表示方法,其差別僅在于:關鍵字和給定值進行比較的順序不同第112頁,課件共151頁,創(chuàng)作于2023年2月
只有一個辦法:預先知道所查關鍵字在表中的位置對于頻繁使用的查找表,希望ASL=0
即,要求:記錄在表中位置和其關鍵字之間存在一種確定的關系第113頁,課件共151頁,創(chuàng)作于2023年2月在一般情況下,需在關鍵字與記錄在表中的存儲位置之間建立一個函數關系,以H(key)作為關鍵字為key的記錄在表中的位置,通常稱這個函數H(key)為哈希函數第114頁,課件共151頁,創(chuàng)作于2023年2月
哈希函數是一個映象,即:將關鍵字的集合映射到某個地址集合上,它的設置很靈活,只要這個地址集合的大小不超出允許范圍即可第115頁,課件共151頁,創(chuàng)作于2023年2月
由于哈希函數是一個壓縮映象,因此,在一般情況,很容易產生“沖突”現象,即:key1key2,而
H(key1)=H(key2)第116頁,課件共151頁,創(chuàng)作于2023年2月
很難找到一個不產生沖突的哈希函數。一般情況下,只能選擇恰當的哈希函數,使沖突盡可能少地產生第117頁,課件共151頁,創(chuàng)作于2023年2月
因此,在構造這種特殊的“查找表”時,除了需要選擇一個“好”(盡可能少產生沖突)的哈希函數之外;還需要找到一種“處理沖突”的方法第118頁,課件共151頁,創(chuàng)作于2023年2月哈希表的定義
根據設定的哈希函數H(key)和所選處理沖突的方法,將一組關鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上,并以關鍵字在地址集中的“映象”作為相應記錄在表中的存儲位置,如此構造所得的查找表稱為“哈希表”第119頁,課件共151頁,創(chuàng)作于2023年2月構造哈希函數的方法對數字的關鍵字可有下列構造方法
若是非數字關鍵字,則需先對其進行數字化處理
直接定址法平方取中法
除留余數法
折疊法
數字分析法第120頁,課件共151頁,創(chuàng)作于2023年2月數字分析法
第121頁,課件共151頁,創(chuàng)作于2023年2月此方法適合于:能預先估計出全體關鍵字的每一位上各種數字出現的頻度
假設關鍵字集合中的每個關鍵字都是由s位數字組成(u1,u2,…,us),分析關鍵字集中的全體,并從中提取分布均勻的若干位或它們的組合作為地址第122頁,課件共151頁,創(chuàng)作于2023年2月平方取中法第123頁,課件共151頁,創(chuàng)作于2023年2月
以關鍵字的平方值的中間幾位作為存儲地址。求“關鍵字的平方值”的目的是“擴大差別”,同時平方值的中間各位又能受到整個關鍵字中各位的影響
此方法適合于:
關鍵字中的每一位都有某些數字重復出現頻度很高的現象第124頁,課件共151頁,創(chuàng)作于2023年2月折疊法第125頁,課件共151頁,創(chuàng)作于2023年2月
將關鍵字分割成若干部分,然后取它們的疊加和為哈希地址。有兩種疊加處理的方法:移位疊加和間界疊加
此方法適合于:
關鍵字的數字位數特別多第126頁,課件共151頁,創(chuàng)作于2023年2月直接定址法第127頁,課件共151頁,創(chuàng)作于2023年2月哈希函數為關鍵字的線性函數
H(key)=key或者
H(key)=akey+b此法適合于:地址集合的大小==關鍵字集合的大小第128頁,課件共151頁,創(chuàng)作于2023年2月除留余數法第129頁,課件共151頁,創(chuàng)作于2023年2月
設定哈希函數為:H(key)=keyMODp
其中,p≤m(表長)并且
p
應為不大于m的素數或是不含20以下的質因子第130頁,課件共151頁,創(chuàng)作于2023年2月
實際造表時,采用何種構造哈希函數的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài)),總的原則是使產生沖突的可能性降到盡可能地小第131頁,課件共151頁,創(chuàng)作于2023年2月處理沖突的方法“處理沖突”的實際含義是為產生沖突的地址尋找下一個哈希地址1.開放定址法2.鏈地址法第132頁,課件共151頁,創(chuàng)作于2023年2月
為產生沖突的地址H(key)求得一個地址序列:
H0,H1,H2,…,Hs
1≤s≤m-1其中:H0=H(key)Hi=(H(key)+di
)MODm
i=1,2,…,s開放定址法(閉域法)第133頁,課件共151頁,創(chuàng)作于2023年2月增量di
的三種取法第134頁,課件共151頁,創(chuàng)作于2023年2月
1)線性探測再散列
di=ci
最簡單的情況c=12)平方探測再散列
di=12,-12,22,-22,…,3)隨機探測再散列
di
是一組偽隨機數列或者
di=i×H2(key)(又稱雙散列函數探測)第135頁,課件共151頁,創(chuàng)作于2023年2月即:產生的Hi
均不相同,且所產生的
s(m-1)個Hi值能覆蓋哈希表中所有地址。且要求:
增量di
應具有“完備性”
隨機探測時的m
和di沒有公因子
平方探測時的表長m必為形如4j+3
的素數(如:7,11,19,23,…等)第136頁,課件共151頁,創(chuàng)作于2023年2月{19,01,23,14,55,68,11,82,36}H(key)=keyMOD1119012314
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 上海交通職業(yè)技術學院《金融科技》2023-2024學年第一學期期末試卷
- 上海建設管理職業(yè)技術學院《時間序列分析實驗》2023-2024學年第一學期期末試卷
- 上海濟光職業(yè)技術學院《軌道車輛傳動與控制》2023-2024學年第一學期期末試卷
- 上海行健職業(yè)學院《材料力學》2023-2024學年第一學期期末試卷
- 第一單元第3課 尋找網絡資源-使用網絡搜索引擎 教學實錄 2023-2024學年遼師大版(2015)初中信息技術七年級下冊
- 2024年中國工業(yè)用革市場調查研究報告
- 上海工商外國語職業(yè)學院《網球(I)》2023-2024學年第一學期期末試卷
- 上海工商外國語職業(yè)學院《EDA技術與版圖設計》2023-2024學年第一學期期末試卷
- 一年級語文上冊 第8單元 課文(四)13《烏鴉喝水》同步教學實錄 新人教版
- 2點亮小燈泡(教學實錄)-2023-2024學年四年級科學下冊教科版
- GB/T 44916-2024船舶和海上技術船用超低溫閘閥設計與試驗要求
- 安徽省合肥市包河區(qū)2023-2024學年三年級上學期語文期末試卷
- 【MOOC】新媒體文化十二講-暨南大學 中國大學慕課MOOC答案
- 2024-2025學年二年級數學上冊期末樂考非紙筆測試題(二 )(蘇教版)
- 2024年度智能制造生產線改造項目合同
- 2024年度食堂檔口承包合同(含菜品研發(fā))3篇
- DB32T 4578.2-2023 丙型病毒性肝炎防治技術指南 第2部分:患者管理
- 護理輪科心得
- 倉庫安全培訓
- 英語期末復習講座模板
- 9《作息有規(guī)律》(說課稿)2024-2025學年統(tǒng)編版(2024)道德與法治一年級上冊
評論
0/150
提交評論