數(shù)據(jù)結(jié)構(gòu)與算法分析第八章查找

數(shù)據(jù)結(jié)構(gòu)與算法分析第八章查找第1頁，課件共151頁，創(chuàng)作于2023年2月所謂搜索(查找檢索)，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象

1.搜索成功即找到滿足條件的數(shù)據(jù)對象,作為結(jié)果,可報告該對象在結(jié)構(gòu)中的位置,還可給出該對象中的具體信息2.搜索不成功或搜索失敗。作為結(jié)果,應(yīng)報告一些信息,如失敗標志、位置等第2頁，課件共151頁，創(chuàng)作于2023年2月通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對象(或記錄)組成在每個對象中有若干屬性，其中有一個屬性，其值可唯一地標識這個對象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實際應(yīng)用時，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一第3頁，課件共151頁，創(chuàng)作于2023年2月實施搜索時有兩種不同的環(huán)境靜態(tài)環(huán)境搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變

靜態(tài)搜索表

動態(tài)環(huán)境為保持較高的搜索效率,搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動進行調(diào)整，結(jié)構(gòu)可能發(fā)生變化動態(tài)搜索表第4頁，課件共151頁，創(chuàng)作于2023年2月查找算法的評價指標查找成功:最少比較次數(shù)最多比較次數(shù)平均比較次數(shù)查找失敗:最少比較次數(shù)最多比較次數(shù)平均比較次數(shù)第5頁，課件共151頁，創(chuàng)作于2023年2月

以順序表或線性鏈表表示靜態(tài)查找表順序查找第6頁，課件共151頁，創(chuàng)作于2023年2月ST.elem順序查找過程假設(shè)給定值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)

為確定記錄在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值第11頁，課件共151頁，創(chuàng)作于2023年2月其中:n為表長，Pi

為查找表中第i個記錄的概率，且，Ci為找到該記錄時，曾和給定值比較過的關(guān)鍵字的個數(shù)第12頁，課件共151頁，創(chuàng)作于2023年2月在等概率情形pi=1/n,i=1,2,,n

在搜索不成功情形，ASLunsucc=n+1

第13頁，課件共151頁，創(chuàng)作于2023年2月查找成功:最少比較次數(shù)1

最多比較次數(shù)n

平均比較次數(shù)(n+1)/2

查找失敗:最少比較次數(shù)n+1

最多比較次數(shù)n+1

平均比較次數(shù)n+1第14頁，課件共151頁，創(chuàng)作于2023年2月

上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表折半查找

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行第15頁，課件共151頁，創(chuàng)作于2023年2月基于有序順序表的折半搜索設(shè)n個對象存放在一個有序順序表中，并按其關(guān)鍵碼從小到大排好了序折半搜索時,先求位于搜索區(qū)間正中的對象的下標mid，用其關(guān)鍵碼與給定值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月搜索成功時檢測指針停留在樹中某個結(jié)點搜索不成功時檢測指針停留在某個外結(jié)點（失敗結(jié)點）3515455025102030搜索22搜索45第22頁，課件共151頁，創(chuàng)作于2023年2月有序順序表的折半搜索的判定樹

(10,20,30,40,50,60)1050======30<<<<<<>>>>>>204060第23頁，課件共151頁，創(chuàng)作于2023年2月先看一個具體的情況，假設(shè)：n=11分析折半查找的平均查找長度6391425781011判定樹12233334444第24頁，課件共151頁，創(chuàng)作于2023年2月查找成功:最少比較次數(shù)?

最多比較次數(shù)?

平均比較次數(shù)?

查找失敗:最少比較次數(shù)?

最多比較次數(shù)?

平均比較次數(shù)?第25頁，課件共151頁，創(chuàng)作于2023年2月假設(shè)n=2h-1并且查找概率相等則

在n>50時，可得近似結(jié)果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結(jié)點的完全二叉樹的深度相同第26頁，課件共151頁，創(chuàng)作于2023年2月索引順序查找1）由索引確定記錄所在區(qū)間2）在順序表的某個區(qū)間內(nèi)進行查找注意：索引可以根據(jù)查找表的特點來構(gòu)造可見:

索引順序查找的過程也是一個“縮小區(qū)間”的查找過程第27頁，課件共151頁，創(chuàng)作于2023年2月分塊查找查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找適用條件：分塊有序表算法實現(xiàn)用數(shù)組存放待查記錄,每個數(shù)據(jù)元素至少含有關(guān)鍵字域建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字域和指向本塊第一個結(jié)點的指針第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最大最小兩者之間表結(jié)構(gòu)有序表、無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)線性鏈表查找方法比較順序查找折半查找分塊查找第32頁，課件共151頁，創(chuàng)作于2023年2月二叉排序樹（二叉查找樹）第33頁，課件共151頁，創(chuàng)作于2023年2月（1）若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹（3）它的左、右子樹也都分別是二叉排序樹（2）若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值第34頁，課件共151頁，創(chuàng)作于2023年2月503080209010854035252388是二叉排序樹66不第35頁，課件共151頁，創(chuàng)作于2023年2月二叉排序樹的

查找算法第36頁，課件共151頁，創(chuàng)作于2023年2月

1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功

2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找

3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找否則:若二叉排序樹為空，則查找不成功第37頁，課件共151頁，創(chuàng)作于2023年2月50308020908540358832查找關(guān)鍵字50505030403550508090==50,35,90,95第38頁，課件共151頁，創(chuàng)作于2023年2月n個結(jié)點的二叉搜索樹的數(shù)目3個結(jié)點的二叉搜索樹122133132123123{123}{132}{213}{231}{312}{321}第39頁，課件共151頁，創(chuàng)作于2023年2月

如果對一棵二叉搜索樹進行中序遍歷，可以按從小到大的順序，將各結(jié)點關(guān)鍵碼排列起來，所以也稱二叉搜索樹為二叉排序樹第40頁，課件共151頁，創(chuàng)作于2023年2月在查找過程中，生成了一條查找路徑

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點或者從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止

——查找成功

——查找不成功第41頁，課件共151頁，創(chuàng)作于2023年2月351545504025102030搜索45搜索成功

搜索28搜索失敗第42頁，課件共151頁，創(chuàng)作于2023年2月查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大第43頁，課件共151頁，創(chuàng)作于2023年2月由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2第44頁，課件共151頁，創(chuàng)作于2023年2月

輸入數(shù)據(jù)，建立二叉搜索樹的過程輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}535378537865537865175378658717537865091787537865811787095378651517870981第45頁，課件共151頁，創(chuàng)作于2023年2月

同樣3個數(shù)據(jù){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樹或者是空樹，或者是具有下列性質(zhì)的二叉搜索樹：它的左子樹和右子樹都是AVL樹，且左子樹和右子樹的高度之差的絕對值不超過1

不平衡平衡ABCABCDEDE第49頁，課件共151頁，創(chuàng)作于2023年2月

結(jié)點的平衡因子

(balancefactor)每個結(jié)點附加一個數(shù)字,給出該結(jié)點右子樹的高度減去左子樹的高度所得的高度差,這個數(shù)字即為結(jié)點的平衡因子AVL樹任一結(jié)點平衡因子只能取-1,0,1第50頁，課件共151頁，創(chuàng)作于2023年2月如果一個結(jié)點的平衡因子的絕對值大于1,則這棵二叉搜索樹就失去了平衡,不再是AVL樹如果一棵二叉搜索樹是平衡的,

且有n個結(jié)點，其高度可保持在

O(log2n),平均搜索長度也可保持在O(log2n)第51頁，課件共151頁，創(chuàng)作于2023年2月548254821是平衡樹不是平衡樹第52頁，課件共151頁，創(chuàng)作于2023年2月平衡化旋轉(zhuǎn)如果在一棵平衡的二叉搜索樹中插入一個新結(jié)點，造成了不平衡。此時必須調(diào)整樹的結(jié)構(gòu)，使之平衡化平衡化旋轉(zhuǎn)有兩類：單旋轉(zhuǎn)(左旋和右旋)

雙旋轉(zhuǎn)(左旋加右旋和右旋加左旋)第53頁，課件共151頁，創(chuàng)作于2023年2月每插入一個新結(jié)點時,AVL樹中相關(guān)結(jié)點的平衡狀態(tài)會發(fā)生改變。因此,在插入一個新結(jié)點后，需要從插入位置沿通向根的路徑回溯，檢查各結(jié)點的平衡因子第54頁，課件共151頁，創(chuàng)作于2023年2月如果在某一結(jié)點發(fā)現(xiàn)高度不平衡，停止回溯。從發(fā)生不平衡的結(jié)點起，沿剛才回溯的路徑取直接下兩層的結(jié)點第55頁，課件共151頁，創(chuàng)作于2023年2月如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化單旋轉(zhuǎn)可按其方向分為左單旋轉(zhuǎn)和右單旋轉(zhuǎn),其中一個是另一個的鏡像,其方向與不平衡的形狀相關(guān)如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化雙旋轉(zhuǎn)分為先左后右和先右后左兩類第56頁，課件共151頁，創(chuàng)作于2023年2月右單旋轉(zhuǎn)R型左單旋轉(zhuǎn)L型第57頁，課件共151頁，創(chuàng)作于2023年2月左右雙旋轉(zhuǎn)LR型右左雙旋轉(zhuǎn)RL型第58頁，課件共151頁，創(chuàng)作于2023年2月左單旋轉(zhuǎn)

(RotateLeft,L型)第59頁，課件共151頁，創(chuàng)作于2023年2月hhhACEBDhhh+1BACEDhhh+1CEABD+1+20+100在子樹E中插入新結(jié)點，該子樹高度增1導(dǎo)致結(jié)點A的平衡因子變成+2，產(chǎn)生不平衡(L型)以結(jié)點C為旋轉(zhuǎn)軸，將結(jié)點A反時針旋轉(zhuǎn)第60頁，課件共151頁，創(chuàng)作于2023年2月右單旋轉(zhuǎn)

(RotateRight,R型)第61頁，課件共151頁，創(chuàng)作于2023年2月在子樹D中插入新結(jié)點,該子樹高度增1導(dǎo)致結(jié)點A的平衡因子變成-2，產(chǎn)生不平衡(R型)以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)hhhACEBDhh+1BACEDhhh+1CEABDh000-1-1-2第62頁，課件共151頁，創(chuàng)作于2023年2月

先左后右雙旋轉(zhuǎn)

(RotationLeftRight,LR型)第63頁，課件共151頁，創(chuàng)作于2023年2月在子樹F或G中插入新結(jié)點，該子樹高度增1導(dǎo)致結(jié)點A的平衡因子變成-2，產(chǎn)生不平衡(LR型)首先以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點B反時針旋轉(zhuǎn)，以E代替原來B的位置，做左單旋轉(zhuǎn)再以結(jié)點E為旋轉(zhuǎn)軸，將結(jié)點A順時針旋轉(zhuǎn)，做右單旋轉(zhuǎn)第64頁，課件共151頁，創(chuàng)作于2023年2月插入00-1-2+1-1hhACED0h-1h-1hhAh-1hBCEDB左單旋轉(zhuǎn)FGFG第65頁，課件共151頁，創(chuàng)作于2023年2月00-200+1hhACED-2h-1hhhAh-1hBCEDB右單旋轉(zhuǎn)FGFG第66頁，課件共151頁，創(chuàng)作于2023年2月先右后左雙旋轉(zhuǎn)

(RotationRightLeft,RL型)第67頁，課件共151頁，創(chuàng)作于2023年2月在子樹F或G中插入新結(jié)點，該子樹高度增1導(dǎo)致結(jié)點A的平衡因子變成2，產(chǎn)生不平衡(RL型)首先以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點C順時針旋轉(zhuǎn)，以D代替原來C的位置,做右單旋轉(zhuǎn)再以結(jié)點D為旋轉(zhuǎn)軸，將結(jié)點A反時針旋轉(zhuǎn)，做左單旋轉(zhuǎn)第68頁，課件共151頁，創(chuàng)作于2023年2月插入右單旋轉(zhuǎn)+1000-1+10hhACEDh-1BFGh-1+2000hhACEhBFGh-1D第69頁，課件共151頁，創(chuàng)作于2023年2月00+20-10hhACE+2h-1hhhAh-1hBCEDB左單旋轉(zhuǎn)FGFGD第70頁，課件共151頁，創(chuàng)作于2023年2月構(gòu)造二叉平衡（查找）樹的方法在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)第71頁，課件共151頁，創(chuàng)作于2023年2月426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9第72頁，課件共151頁，創(chuàng)作于2023年2月輸入關(guān)鍵碼序列為{16,3,7,11,9,26,18,14,15}插入和調(diào)整過程如下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樹上，每個非終端結(jié)點可能含有：

n

個關(guān)鍵字Ki（1≤i≤n）n<m

n

個指向記錄的指針Di（1≤i≤n）

n+1

個指向子樹的指針Ai（0≤i≤n）多叉樹的特性第78頁，課件共151頁，創(chuàng)作于2023年2月非葉結(jié)點中的多個關(guān)鍵字均自小至大有序排列，即：K1<K2<…<KnAi-1所指子樹上所有關(guān)鍵字均小于KiAi所指子樹上所有關(guān)鍵字均大于Ki查找樹的特性第79頁，課件共151頁，創(chuàng)作于2023年2月平衡樹的特性樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹其余所有非葉結(jié)點均至少含有m/2棵子樹，至多含有m

棵子樹第80頁，課件共151頁，創(chuàng)作于2023年2月

從根結(jié)點出發(fā)，沿指針搜索結(jié)點和在結(jié)點內(nèi)進行順序（或折半）查找兩個過程交叉進行查找過程第81頁，課件共151頁，創(chuàng)作于2023年2月

若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置若查找不成功，則返回插入位置第82頁，課件共151頁，創(chuàng)作于2023年2月在查找不成功之后，需進行插入顯然，關(guān)鍵字插入的位置必定在最下層的非葉結(jié)點，有下列幾種情況插入第83頁，課件共151頁，創(chuàng)作于2023年2月插入后，該結(jié)點的關(guān)鍵字個數(shù)n<m，不修改指針第84頁，課件共151頁，創(chuàng)作于2023年2月插入后，該結(jié)點的關(guān)鍵字個數(shù)n=m，則需進行“結(jié)點分裂”，令s=m/2，在原結(jié)點中保留（A0，K1，……，Ks-1，As-1）；建新結(jié)點（As，Ks+1，……，Kn，An）；將（Ks，p）插入雙親結(jié)點第85頁，課件共151頁，創(chuàng)作于2023年2月若雙親為空，則建新的根結(jié)點第86頁，課件共151頁，創(chuàng)作于2023年2月下列為3階B樹502040

80插入關(guān)鍵字=60

6080,9060809090

508060,30

4020305080305080第87頁，課件共151頁，創(chuàng)作于2023年2月

和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點，并且要求刪除之后，結(jié)點中關(guān)鍵字的個數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點均無關(guān)鍵字可借(結(jié)點中只有最少量的關(guān)鍵字)，則必須進行結(jié)點的“合并”刪除第88頁，課件共151頁，創(chuàng)作于2023年2月在含N

個關(guān)鍵字的B樹上進行一次查找，需訪問的結(jié)點個數(shù)不超過

logm/2((N+1)/2)+1查找性能第89頁，課件共151頁，創(chuàng)作于2023年2月是B樹的一種變型B+樹第90頁，課件共151頁，創(chuàng)作于2023年2月

每個葉子結(jié)點中含有n

個關(guān)鍵字和n

個指向記錄的指針；并且，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點第91頁，課件共151頁，創(chuàng)作于2023年2月

每個非葉結(jié)點中的關(guān)鍵字Ki即為其相應(yīng)指針Ai所指子樹中關(guān)鍵字的最大值所有葉子結(jié)點都處在同一層次上，每個葉子結(jié)點中關(guān)鍵字的個數(shù)均介于m/2和m之間第92頁，課件共151頁，創(chuàng)作于2023年2月查找過程

在B+樹上，既可以進行縮小范圍的查找，也可以進行順序查找

在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束

若在結(jié)點內(nèi)查找時，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進行查找第93頁，課件共151頁，創(chuàng)作于2023年2月插入和刪除類似于B樹進行，即必要時，也需要進行結(jié)點的“分裂”或“歸并”第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+樹的刪除僅在葉結(jié)點上進行。當(dāng)在葉結(jié)點上刪除一個關(guān)鍵碼-指針索引項后，結(jié)點中的子樹棵數(shù)仍然不少于m/2，這屬于簡單刪除，其上層索引可以不改變。如果刪除的關(guān)鍵碼是該結(jié)點的最小關(guān)鍵碼，但因在其上層的副本只是起了一個引導(dǎo)搜索的“分界關(guān)鍵碼”的作用，所以上層的副本仍然可以保留。如果在葉結(jié)點中刪除一個關(guān)鍵碼-指針索引項后，該結(jié)點中的子樹棵數(shù)n小于結(jié)點子樹棵數(shù)的下限m/2，必須做結(jié)點的調(diào)整或合并工作。第98頁，課件共151頁，創(chuàng)作于2023年2月刪除18刪除12第99頁，課件共151頁，創(chuàng)作于2023年2月如果右兄弟結(jié)點的子樹棵數(shù)已達到下限m/2，沒有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點，這時必須進行兩個結(jié)點的合并。將右兄弟結(jié)點中的所有關(guān)鍵碼-指針索引項移入被刪關(guān)鍵碼所在結(jié)點，再將右兄弟結(jié)點刪去。第100頁，課件共151頁，創(chuàng)作于2023年2月刪除33進行結(jié)點合并第101頁，課件共151頁，創(chuàng)作于2023年2月結(jié)點的合并將導(dǎo)致雙親結(jié)點中“分界關(guān)鍵碼”的減少，有可能減到非葉結(jié)點中子樹棵數(shù)的下限m/2

以下。這樣將引起非葉結(jié)點的調(diào)整或合并。如果根結(jié)點的最后兩個子女結(jié)點合并，樹的層數(shù)就會減少一層。第102頁，課件共151頁，創(chuàng)作于2023年2月

TheB*-Treesplitstwopagesforthree,andcombinesthreepagesintotwo.Inthisway,nodesarealways2/3full.第103頁，課件共151頁，創(chuàng)作于2023年2月

Trie樹是一棵度m

2的樹，它的每一層分支不是靠整個關(guān)鍵碼的值來確定，而是由關(guān)鍵碼的一個分量來確定。如下圖所示Trie樹，關(guān)鍵碼由英文字母組成。它包括兩類結(jié)點：元素結(jié)點和分支結(jié)點。元素結(jié)點包含整個key數(shù)據(jù)；分支結(jié)點有27個指針，其中有一個空白字符‘b’，用來終結(jié)關(guān)鍵碼；其它用來標識‘a(chǎn)’,‘b’,...,‘z’等26個英文字母。Trie樹Trie樹的定義當(dāng)關(guān)鍵碼是可變長時，Trie樹是一種特別有用的索引結(jié)構(gòu)。第104頁，課件共151頁，創(chuàng)作于2023年2月第105頁，課件共151頁，創(chuàng)作于2023年2月

在第0層，所有的關(guān)鍵碼根據(jù)它們第0位字符,被劃分到互不相交的27個類中。因此，root→brch.link[i]指向一棵子Trie樹，該子Trie樹上所包含的所有關(guān)鍵碼都是以第i個英文字母開頭。若某一關(guān)鍵碼第j

位字母在英文字母表中順序為i(i=0,1,,26),則它在Trie樹的第

j層分支結(jié)點中從第i

個指針向下找第

j+1位字母所在結(jié)點。當(dāng)一棵子Trie樹上只有一個關(guān)鍵碼時，就由一個元素結(jié)點來代替。在這個結(jié)點中包含有關(guān)鍵碼，以及其它相關(guān)的信息，如對應(yīng)數(shù)據(jù)對象的存放地址等。第106頁，課件共151頁，創(chuàng)作于2023年2月

Trie樹的搜索為了在Trie樹上進行搜索，要求把關(guān)鍵碼分解成一些字符元素,并根據(jù)這些字符向下進行分支。第107頁，課件共151頁，創(chuàng)作于2023年2月在Trie樹上插入bobwhite和bluejay后的結(jié)果第108頁，課件共151頁，創(chuàng)作于2023年2月哈希查找(Hash)第109頁，課件共151頁，創(chuàng)作于2023年2月

以上討論的表示查找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系第110頁，課件共151頁，創(chuàng)作于2023年2月

查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進行比較

查找的效率取決于和給定值進行比較的關(guān)鍵字個數(shù)第111頁，課件共151頁，創(chuàng)作于2023年2月

用這類方法表示的查找表，其平均查找長度都不為零

不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進行比較的順序不同第112頁，課件共151頁，創(chuàng)作于2023年2月

只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置對于頻繁使用的查找表，希望ASL=0

即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系第113頁，課件共151頁，創(chuàng)作于2023年2月在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系，以H(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個函數(shù)H(key)為哈希函數(shù)第114頁，課件共151頁，創(chuàng)作于2023年2月

哈希函數(shù)是一個映象，即：將關(guān)鍵字的集合映射到某個地址集合上，它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可第115頁，課件共151頁，創(chuàng)作于2023年2月

由于哈希函數(shù)是一個壓縮映象，因此，在一般情況，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而

H(key1)=H(key2)第116頁，課件共151頁，創(chuàng)作于2023年2月

很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生第117頁，課件共151頁，創(chuàng)作于2023年2月

因此，在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法第118頁，課件共151頁，創(chuàng)作于2023年2月哈希表的定義

根據(jù)設(shè)定的哈希函數(shù)H(key)和所選處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“映象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱為“哈希表”第119頁，課件共151頁，創(chuàng)作于2023年2月構(gòu)造哈希函數(shù)的方法對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法

若是非數(shù)字關(guān)鍵字，則需先對其進行數(shù)字化處理

直接定址法平方取中法

除留余數(shù)法

折疊法

數(shù)字分析法第120頁，課件共151頁，創(chuàng)作于2023年2月數(shù)字分析法

第121頁，課件共151頁，創(chuàng)作于2023年2月此方法適合于：能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址第122頁，課件共151頁，創(chuàng)作于2023年2月平方取中法第123頁，課件共151頁，創(chuàng)作于2023年2月

以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象第124頁，課件共151頁，創(chuàng)作于2023年2月折疊法第125頁，課件共151頁，創(chuàng)作于2023年2月

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多第126頁，課件共151頁，創(chuàng)作于2023年2月直接定址法第127頁，課件共151頁，創(chuàng)作于2023年2月哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者

H(key)=akey+b此法適合于：地址集合的大小==關(guān)鍵字集合的大小第128頁，課件共151頁，創(chuàng)作于2023年2月除留余數(shù)法第129頁，課件共151頁，創(chuàng)作于2023年2月

設(shè)定哈希函數(shù)為:H(key)=keyMODp

其中，p≤m(表長)并且

p

應(yīng)為不大于m的素數(shù)或是不含20以下的質(zhì)因子第130頁，課件共151頁，創(chuàng)作于2023年2月

實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小第131頁，課件共151頁，創(chuàng)作于2023年2月處理沖突的方法“處理沖突”的實際含義是為產(chǎn)生沖突的地址尋找下一個哈希地址1.開放定址法2.鏈地址法第132頁，課件共151頁，創(chuàng)作于2023年2月

為產(chǎn)生沖突的地址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

是一組偽隨機數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)第135頁，課件共151頁，創(chuàng)作于2023年2月即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的

s(m-1)個Hi值能覆蓋哈希表中所有地址。且要求：

增量di

應(yīng)具有“完備性”

隨機探測時的m

和di沒有公因子

平方探測時的表長m必為形如4j+3

的素數(shù)（如:7,11,19,23,…等）第136頁，課件共151頁，創(chuàng)作于2023年2月{19,01,23,14,55,68,11,82,36}H(key)=keyMOD1119012314