查找比較全的.ppt課件

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容17.1 基本概念7.2 靜態(tài)查找表7.3 動(dòng)態(tài)查找表7.4 哈希表第7章 查找29.1 基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表 查 找查找成功查找不成功靜態(tài)查找動(dòng)態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢(Searching)特定元素是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來(lái)識(shí)別一個(gè)記錄 ( 預(yù)先確定的記錄的某種標(biāo)志 ) 可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如“學(xué)號(hào)”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)識(shí)別若干記錄的關(guān)鍵字

2、3（2）對(duì)查找表常用的操作有哪些？ 查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中；查詢某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。 （3) 有哪些查找方法？ 查找方法取決于表中數(shù)據(jù)的排列方式;討論：（1）查找的過(guò)程是怎樣的？ 給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同?！疤囟ǖ摹?關(guān)鍵字4明確：查找的過(guò)程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過(guò)程。所以用比較次數(shù)的平均值來(lái)評(píng)估算法的優(yōu)劣。稱為平均查找長(zhǎng)度（ASL：avera

3、ge search length）。物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時(shí)間效率越高。 （4）如何評(píng)估查找方法的優(yōu)劣？5針對(duì)靜態(tài)查找表的查找算法主要有： 9.2 靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見(jiàn)教材P216。一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹(shù)表的查找四、分塊查找（索引順序查找）6一、順序查找（ Linear search，又稱線性查找 ）（1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：typedef struct ElemType *elem; /表基址，0號(hào)單元留空。表容量為全部元素 int le

4、ngth; /表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。 對(duì)順序結(jié)構(gòu)如何線性查找？見(jiàn)下頁(yè)之例對(duì)單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫(xiě)；只要知道頭指針head就可以“順藤摸瓜”；對(duì)非線性樹(shù)結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！7二、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)： ASL 太長(zhǎng)，時(shí)間效率太低。這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直

5、到查找成功或失敗為止。對(duì)順序表結(jié)構(gòu)實(shí)現(xiàn)折半查找算法 對(duì)單鏈表結(jié)構(gòu)如何折半查找？ 無(wú)法實(shí)現(xiàn)！因全部元素的定位只能從頭指針head開(kāi)始對(duì)非線性(樹(shù))結(jié)構(gòu)如何折半查找？ 可借助二叉排序樹(shù)來(lái)查找（屬動(dòng)態(tài)查找表形式）。 如何改進(jìn)？討論 順序查找的特點(diǎn)：8 運(yùn)算步驟：(1) low =1,high =11 ,mid =6 ，待查范圍是 1,11；(2) 若 ST.elemmid.key key，說(shuō)明keylow ,mid-1， 則令：high =mid1;重算 mid ；(4)若 ST.elem mid .key = key，說(shuō)明查找成功，元素序號(hào)=mid;結(jié)束條件： （1）查找成功 ： ST.elemm

6、id.key = key （2）查找不成功 ： highlow （意即區(qū)間長(zhǎng)度小于0）解： 先設(shè)定3個(gè)輔助標(biāo)志: low,high,mid，折半查找舉例：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置 已知如下11個(gè)元素的有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為21 和85的數(shù)據(jù)元素。顯然有：mid= (low+high)/29討論 若關(guān)鍵字不在表中，怎樣得知和停止？典型標(biāo)志是：當(dāng)查找范圍的上界下界時(shí)停止查找。討論 二分查找的效率（ASL）1次比較就查找成功的元素有1個(gè)（20），即中間

7、值；2次比較就查找成功的元素有2個(gè)（21），即1/4處（或3/4）處；3次比較就查找成功的元素有4個(gè)（22），即1/8處（或3/8）處 4次比較就查找成功的元素有8個(gè)（23），即1/16處（或3/16）處 則第m次比較時(shí)查找成功的元素會(huì)有（2m-1）個(gè)；為方便起見(jiàn)，假設(shè)表中全部n個(gè)元素 2m-1個(gè)，此時(shí)就不討論第m次比較后還有剩余元素的情況了。全部比較總次數(shù)為120221322423m2m1 推導(dǎo)過(guò)程10平均每個(gè)數(shù)據(jù)的查找時(shí)間還要除以n，所以：課堂練習(xí)（多項(xiàng)選擇）：采用鏈?zhǔn)酱尜A結(jié)構(gòu) 記錄的長(zhǎng)度128 采用順序存貯結(jié)構(gòu) 記錄按關(guān)鍵字遞增有序使用折半查找算法時(shí)，要求被查文件：思考：假設(shè)在有序線性表

8、a20上進(jìn)行折半查找，則平均查找長(zhǎng)度為 。11查找過(guò)程可用二叉樹(shù)描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過(guò)程的二叉樹(shù)稱為判定樹(shù)。n個(gè)元素的表的折半查找的判定樹(shù)是唯一的，即：判定樹(shù)由表中元素個(gè)數(shù)決定。 找到有序表中任一記錄的過(guò)程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。 比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在判定樹(shù)上的層次數(shù)。 查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過(guò)樹(shù)的深度 d : d = log2 n + 1 若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹(shù)的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。 查找不成功的過(guò)程 就是走了一條從根結(jié)點(diǎn)到外部結(jié)

9、點(diǎn)的路徑。折半查找效率分析法：12三、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的關(guān)鍵字都比后一塊中關(guān)鍵字?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無(wú)序13查找步驟分兩步進(jìn)行： 對(duì)索引表使用折半查找法（因?yàn)樗饕硎怯行虮恚?確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無(wú)序

10、表）；查找效率：ASL=Lb+Lw對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時(shí)，ASLbs=3.5,而折半法為3.1,順序法為514特點(diǎn)：一、二叉排序樹(shù)的定義二、二叉排序樹(shù)的插入與刪除三、二叉排序樹(shù)的查找分析四、平衡二叉樹(shù)五、B-樹(shù)和B+樹(shù)9.2 動(dòng)態(tài)查找表表結(jié)構(gòu)在查找過(guò)程中動(dòng)態(tài)生成。要求：對(duì)于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key 的記錄。典型的動(dòng)態(tài)表二叉排序樹(shù)15一、二叉排序樹(shù)的定義（a）（b）練：下列2種圖形中，哪個(gè)不是二叉排序樹(shù) ？-或是一棵空樹(shù)；或者是具有如下性質(zhì)的非空二叉樹(shù)：

11、 （1）左子樹(shù)的所有結(jié)點(diǎn)均小于根的值； （2）右子樹(shù)的所有結(jié)點(diǎn)均大于根的值； （3）它的左右子樹(shù)也分別為二叉排序樹(shù)。討論：對(duì)(a)中序遍歷后的結(jié)果是什么？16二、二叉排序樹(shù)的插入與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹(shù)的優(yōu)點(diǎn)： 查找過(guò)程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹(shù)，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）； 如果查找不成功，能夠方便地將被查元素插入到二叉樹(shù)的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹(shù)形態(tài)也不同！這種既查找又插入的過(guò)程稱為動(dòng)態(tài)查找。二叉排序樹(shù)既有類似于折半查找的特性，又采用了鏈表存儲(chǔ)

12、，它是動(dòng)態(tài)查找表的一種適宜表示。174524531290如果待查找的關(guān)鍵字序列輸入順序?yàn)椋海?4，53， 45，45，12，24，90），2453451290查找成功，返回查找成功，返回討論1：二叉排序樹(shù)的插入和查找操作 則生成二叉排序樹(shù)的過(guò)程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹(shù)形態(tài)不同：查找成功，返回查找成功，返回18二叉排序 樹(shù)的靜態(tài)查找思想若二叉排序樹(shù)為空，則查找 失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子樹(shù)重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹(shù)的葉

13、子結(jié)點(diǎn)時(shí)，還沒(méi)有找到待查結(jié)點(diǎn)，則查找不成功。19二叉排序樹(shù)的動(dòng)態(tài)查找算法查找算法：若二叉排序樹(shù)為空，則返回插入位置，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子樹(shù)重復(fù)此步驟。插入算法：若二叉排序樹(shù)為空，則被查結(jié)點(diǎn)為新的根節(jié)點(diǎn)；否則，作為一個(gè)新的葉子結(jié)點(diǎn)插入在由查找返回的位置上。20二叉排序樹(shù)的刪除要?jiǎng)h除二叉排序樹(shù)中的p結(jié)點(diǎn)，分三種情況：p為葉子結(jié)點(diǎn)，只需修改p雙親f的指針f-lchild=NULL 或 f-rchild=NULLp只有左子樹(shù)或右子樹(shù)p只有左子樹(shù)，用p的左孩子代替p (1)(2)p只有右子樹(shù)，用p的右孩子代替

14、p (3)(4)p左、右子樹(shù)均非空 沿p左子樹(shù)的根C的右子樹(shù)分支找到S，S的右子樹(shù)為空 法1：令*p的左子樹(shù)為 *f的左子樹(shù)，*p的右子樹(shù)為*s的右子樹(shù)； 法2：令*s代替*p 將S的左子樹(shù)成為S的雙親Q的右子樹(shù)，用S取代p (5)若C無(wú)右子樹(shù)，用C取代p (6)21FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：請(qǐng)從下面的二叉排序樹(shù)中刪除結(jié)點(diǎn)P。SSL22SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)63421815634215刪除1823中序遍

15、歷：P PR S QSPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRP6342181215刪除126342181524FPCPRCLQQLSSL中序遍歷：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍歷：CL C QL Q SL S PR F(5)FPCPRCL中序遍歷：CL C P PR FFCPRCL中序遍歷：CL C PR F(6)251036241812156342181215刪除1026四、平衡二叉樹(shù)平衡二叉樹(shù)又稱AVL樹(shù)，它是具有如下性質(zhì)的二叉樹(shù)：為了方便起見(jiàn)，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字，給出

16、該結(jié)點(diǎn)左子樹(shù)與右子樹(shù)的高度差。這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子balance。這樣，可以得到AVL樹(shù)的其它性質(zhì)：即|左子樹(shù)深度-右子樹(shù)深度| 1左、右子樹(shù)是平衡二叉樹(shù)；所有結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值 127(a) 平衡樹(shù) (b) 不平衡樹(shù)例：判斷下列二叉樹(shù)是否AVL樹(shù)？任一結(jié)點(diǎn)的平衡因子只能?。?1、0 或 1；如果樹(shù)中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則這棵二叉樹(shù)就失去平衡，不再是AVL樹(shù)；對(duì)于一棵有n個(gè)結(jié)點(diǎn)的AVL樹(shù)，其高度保持在O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)。00011-1-120001-128如果在一棵AVL樹(shù)中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須

17、重新調(diào)整樹(shù)的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過(guò)程為平衡旋轉(zhuǎn)?，F(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類： LL平衡旋轉(zhuǎn) RR平衡旋轉(zhuǎn) LR平衡旋轉(zhuǎn) RL平衡旋轉(zhuǎn)29若在A的左子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：30若在A的右子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCAB

18、CABC若在A的左子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：這種調(diào)整規(guī)則可以保證二叉排序樹(shù)的次序不變31013037024例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹(shù)： （ 13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053 32五、B-樹(shù)和B+樹(shù)B-樹(shù)一、B-樹(shù)的基本概念1.定義一棵m階的B-樹(shù),或?yàn)榭諛?shù),或?yàn)闈M足下列特性的m

19、叉樹(shù): (l)所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)如下: 其中,k1,k2,.,kn為n個(gè)按從小到大順序排列的鍵值; p0,pl,p2,.,pn為(n+1)個(gè)指針,用于指向該結(jié)點(diǎn)的(n+l)棵子樹(shù),p0所指向子樹(shù)中的所有關(guān)鍵字的值均小于kl,pn所指向子樹(shù)中的所有關(guān)鍵字的值均大于kn,pi(1in-1)所指向子樹(shù)中的所有關(guān)鍵字的值均大于ki且小于ki+1; n(nm-1)為鍵值的個(gè)數(shù),即子樹(shù)個(gè)數(shù)為(n+l)。 (2)樹(shù)中每個(gè)結(jié)點(diǎn)至多有m棵子樹(shù)。 (3)除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn),否則至少有兩棵子樹(shù)。 (4)除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹(shù)。 (5)所有葉子結(jié)點(diǎn)在同一個(gè)層次上,且不含有任何信息。np0k1

20、p1k2p2kipiknpn332. 說(shuō)明(1)對(duì)于非根結(jié)點(diǎn)的所有分支結(jié)點(diǎn),n的取值范圍為 m/2-1nm-1。(2)對(duì)于根結(jié)點(diǎn),n的取值范圍為1nm1。(3)對(duì)于葉子結(jié)點(diǎn),其子樹(shù)均為空樹(shù)(即沒(méi)有子結(jié)點(diǎn)),又規(guī)定不含有任何信息:所,可以把它看作不在樹(shù)中的外部結(jié)點(diǎn)。(4)B-樹(shù)的階m可以事先任意指定,一旦指定后,就固定不變。2-3樹(shù)的含義圖9-13是一棵由10個(gè)鍵值生成的四階B_樹(shù)的示意圖,該樹(shù)共有四層,所有葉子點(diǎn)均在第四層上。341501301951251552709023540atbcdfgeh圖9-13 B-樹(shù)375808535二、B-樹(shù)的查找1.查找方法由B-樹(shù)的定義可知,在B-樹(shù)上進(jìn)行

21、查找的過(guò)程與二叉排序樹(shù)的查找類似。根據(jù)給定的鍵值k,先在根結(jié)點(diǎn)的鍵值的集合中采用順序(當(dāng)m較小時(shí))或二分(當(dāng)m較大時(shí))查找方法進(jìn)行查找。若有k=ki,則查找成功,根據(jù)相應(yīng)的指針即可取得記錄:否則,若k在ki和ki+1之間,取指針pi所指的結(jié)點(diǎn),重復(fù)這個(gè)查找過(guò)程,直到在某結(jié)點(diǎn)中查找成功,或在某結(jié)點(diǎn)處出現(xiàn)pi 為空,查找失敗 .例如，在圖9-13所示B_樹(shù)中查找關(guān)鍵字80和38。362.性能分析在B-樹(shù)上進(jìn)行查找需比較的結(jié)點(diǎn)數(shù)最多為B-樹(shù)的高度,B-樹(shù)的高度與B-樹(shù)的階m和鍵值總數(shù)N有關(guān),下面就來(lái)討論它們之間的關(guān)系。(1)若B-樹(shù)的高度為h+1,則h+1層(即葉結(jié)點(diǎn)所在的層)的結(jié)點(diǎn)數(shù)為N+1。因?yàn)?/p>

22、每個(gè)非葉結(jié)點(diǎn)中的指針數(shù)等于其中的鍵值數(shù)加1,因此有: 結(jié)點(diǎn)總數(shù)=指針總數(shù)+1=(鍵值總數(shù)N+非葉結(jié)點(diǎn)數(shù))+l (h+1)層的結(jié)點(diǎn)數(shù)=葉結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)總數(shù)非葉結(jié)點(diǎn)數(shù) =N+1。(2)根據(jù)B-樹(shù)的定義,B-樹(shù)的第一層(即根結(jié)點(diǎn))的結(jié)點(diǎn)數(shù)至少為1個(gè),第二層的結(jié)點(diǎn)數(shù)至少為2,第三層的結(jié)點(diǎn)數(shù)至少為2*m/2,第四層的結(jié)點(diǎn)數(shù)至少為2*(m/2)2,以此類推,第h+1層的結(jié)點(diǎn)數(shù)至少為2*(m/2)h-1。(3)綜上所述,可得到如下不等式: h1+logm/2(N+1)/237三、B-樹(shù)的插入在B-樹(shù)中插入一個(gè)鍵值k,不是在樹(shù)中添加一個(gè)葉子結(jié)點(diǎn),而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)鍵值。且要使插入的結(jié)點(diǎn)中

23、的鍵值字個(gè)數(shù)m1,將涉及到結(jié)點(diǎn)的“分裂問(wèn)題。1.插入方法首先要經(jīng)過(guò)一個(gè)從樹(shù)根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的查找過(guò)程,如果鍵值k已在樹(shù)中,則不用做其他事;否則,找出插入位置,然后再進(jìn)行插入。對(duì)于葉子結(jié)點(diǎn)處于第(h+1)層的樹(shù),插入的位置總是在第h層。若結(jié)點(diǎn)的關(guān)鍵字值個(gè)數(shù)不超過(guò)(m-l),直接把鍵值插就行了;否則需要把結(jié)點(diǎn)分裂成兩個(gè)。分裂的做法是,取一新結(jié)點(diǎn),把原結(jié)點(diǎn)上的鍵和k按升序排序后,從中間位置(即m/2之處)把鍵值(不包括中間位置的鍵值)成兩部分,左部分所含鍵值放在舊結(jié)點(diǎn)中,右部分所含鍵值放在新結(jié)點(diǎn)中,中間位置鍵值連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到父親結(jié)點(diǎn)中。如果父結(jié)點(diǎn)的鍵值個(gè)數(shù)也超過(guò)(m-l),要再分裂,再往

24、上插,直至這個(gè)過(guò)程傳到根結(jié)點(diǎn)為止。 383065 802535 4055 6070 758550(a) 插入前的3階 B_樹(shù)3025 2835 4065 8055 6070 758550(b) 插入28后的 B_樹(shù)3930 3825 2835 65 8055 6070 75855040(c) 插入38后的 B_樹(shù)30 5065 8055 6070 7585382520283540(d) 插入20后的 B_樹(shù)圖9-14 B_樹(shù)的插入40四、B-樹(shù)的刪除 B-樹(shù)的刪除過(guò)程與插入過(guò)程類似,只是稍為復(fù)雜一些。要使刪除后的結(jié)點(diǎn)中的鍵值個(gè)數(shù)m/2,將涉及到結(jié)點(diǎn)的“合并問(wèn)題。1.刪除方法在深度為(h+l)的

25、m階B-樹(shù)中刪除一個(gè)鍵值k,首先要查到鍵值k所在的結(jié)點(diǎn)及在結(jié)點(diǎn)中的位置。若k所在結(jié)點(diǎn)的層數(shù)小于h,則把該結(jié)點(diǎn)的右邊(或左邊)指針?biāo)缸訕?shù)中的最小(或最大)鍵值與k對(duì)調(diào),使k移到第h層,這樣可根據(jù)k所在結(jié)點(diǎn)為第h層結(jié)點(diǎn)的情況進(jìn)行刪除,從B_樹(shù)上第h層結(jié)點(diǎn)中刪除一個(gè)鍵值后,使得該結(jié)點(diǎn)的值個(gè)數(shù)n減1,此時(shí)應(yīng)分以下三種情況進(jìn)行處理:(1)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n m/21,在該結(jié)點(diǎn)中刪去鍵值k連同右邊的指針.(2)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n m/2 1,且左(或右)兄弟結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目 m/21,則把左(或右)兄弟結(jié)點(diǎn)中最大(或最小)鍵值移到父結(jié)點(diǎn)中,再把父結(jié)點(diǎn)大于(或小于)上移鍵值的鍵值下移到被刪關(guān)鍵

26、字所在結(jié)點(diǎn)中。41(3)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n m/2 1,及其左、右兄弟結(jié)點(diǎn)的鍵值數(shù)目都等于m/21,則就必須進(jìn)行結(jié)點(diǎn)的“合并”,即把應(yīng)刪的鍵值刪去后,將該結(jié)點(diǎn)中的剩余鍵值和指針連同父結(jié)點(diǎn)中指向該結(jié)點(diǎn)指針的左邊(或右邊)一個(gè)鍵值ki一起合并到左兄弟(或右兄弟)結(jié)點(diǎn)中,將ki從父結(jié)點(diǎn)中刪去。如果因此使父結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目 m/21,則對(duì)此父結(jié)點(diǎn)做同樣處理,以致于可能直到對(duì)根結(jié)點(diǎn)做這樣的處理而使整個(gè)樹(shù)減少一層。3065 802535 4055 6070 758550423065 8025 4055 6070 758550(a) 由圖9-14(a)刪除35后的3階B_樹(shù)3065 7525 4055

27、 6070 8050(b) 刪除85后的B_樹(shù)433065 25 4055 6070 7550(c) 刪除80后的B_樹(shù)50 65 70 7530 4055 60(d) 刪除25后的B_樹(shù)圖9-15 B_樹(shù)的刪除449.4.2 B+樹(shù)一、B+樹(shù)定義1.定義一棵m階的B+樹(shù)滿足下列條件:(1)每個(gè)分支結(jié)點(diǎn)至多有m棵子樹(shù)。(2)除根結(jié)點(diǎn)外,其他每個(gè)分支結(jié)點(diǎn)至少有(m+1)/2棵子樹(shù)。(3)根結(jié)點(diǎn)至少有兩棵子樹(shù),至多有m棵子樹(shù)。(4)有n棵子樹(shù)的結(jié)點(diǎn)有n個(gè)鍵值。(5)所有葉結(jié)點(diǎn)包含全部(數(shù)據(jù)文件中記錄)鍵值及指向相應(yīng)記錄的指針(或存放據(jù)文件分塊后每塊的最大鍵值及指向該塊的指針),而且葉結(jié)點(diǎn)按鍵值大小

28、順序鏈接(可以把每個(gè)葉結(jié)點(diǎn)看成是一個(gè)基本索引塊,它的指針不再指向另一級(jí)索引塊,而是直指向數(shù)據(jù)文件中的記錄)。(6)所有分支結(jié)點(diǎn)(可看成是索引的索引)中僅包含它的各個(gè)子結(jié)點(diǎn)(即下級(jí)索引索引塊)中最大鍵值及指向子結(jié)點(diǎn)的指針. 45對(duì)于m階的B+樹(shù)和m階的B-樹(shù),定義中的前三點(diǎn)是相同的,主要的差異是:(1)在B+樹(shù)中,具有n個(gè)關(guān)鍵字的結(jié)點(diǎn)則含有n棵子樹(shù),即每個(gè)關(guān)鍵字對(duì)應(yīng)一棵子樹(shù),而在B-樹(shù)中,具有n個(gè)鍵值的結(jié)點(diǎn)含有(n+1)棵子樹(shù);(2)在B+樹(shù)中,每個(gè)結(jié)點(diǎn)(除樹(shù)根結(jié)點(diǎn)外)中的鍵值個(gè)數(shù)n的取值范圍是m/2nm,根結(jié)點(diǎn)n的取值范圍是1nm;而在B_樹(shù)中,它們的取值范圍分別是m/21nml和lnm1。(

29、3)B+樹(shù)中的所有葉子結(jié)點(diǎn)包含了全部鍵值,即其他非葉結(jié)點(diǎn)中的鍵值包含在葉結(jié)點(diǎn)中,而在B-樹(shù)中,葉結(jié)點(diǎn)包含的鍵值與其他結(jié)點(diǎn)包含的鍵值是不重復(fù)的。(4)B+樹(shù)中所有非葉結(jié)點(diǎn)僅起到索引的作用,即結(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹(shù)的最大關(guān)鍵字和指向該子樹(shù)的指針,不含有該鍵值對(duì)應(yīng)記錄的存儲(chǔ)地址。而在B-樹(shù)中,每個(gè)鍵值對(duì)應(yīng)一個(gè)記錄的存儲(chǔ)地址。(5)通常在B+樹(shù)上有兩個(gè)頭指針,一個(gè)指向根結(jié)點(diǎn),另一個(gè)指向鍵值最小的葉子結(jié)點(diǎn),所有葉結(jié)點(diǎn)鏈接成一個(gè)不定長(zhǎng)的線性鏈表。 4640 6535 4060 6555 6540 45 5520 25 3015 30 4010 15roothead圖9-16 B+樹(shù)47二、B+樹(shù)

30、查找在B+樹(shù)中可以采用兩種查找方式,一種是直接從最小鍵值開(kāi)始進(jìn)行順序查找,另一種就是從B+樹(shù)的根結(jié)點(diǎn)開(kāi)始進(jìn)行隨機(jī)查找。這種查找方式與B-樹(shù)的查找方法相似,只是在分支結(jié)點(diǎn)上的鍵值與查找值相等時(shí),查找并不結(jié)束,要繼續(xù)查到葉結(jié)點(diǎn)為止,此時(shí)若查找成功,則按所給指針取出對(duì)應(yīng)記錄即可。因此,在B+樹(shù)中,不管查找成功與否,每次查找都是經(jīng)過(guò)了一條從樹(shù)根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。三、B+樹(shù)插入與B-樹(shù)的插入操作相似,B+樹(shù)的插入也從葉子結(jié)點(diǎn)開(kāi)始,當(dāng)插入后結(jié)點(diǎn)中的鍵值個(gè)數(shù)大于m時(shí)要分裂成兩個(gè)結(jié)點(diǎn),它們所含鍵值個(gè)數(shù)分別為(m+1)/2和(m+1)/2,同時(shí)要使得它們的雙親結(jié)點(diǎn)中包含有這兩個(gè)結(jié)點(diǎn)的最大鍵值和指向它們的指針

31、。若雙親結(jié)點(diǎn)的鍵值數(shù)目因此而大于m,應(yīng)繼續(xù)分裂,依此類推。 48四、B+樹(shù)刪除B+樹(shù)的刪除也是從葉子結(jié)點(diǎn)開(kāi)始,當(dāng)葉結(jié)點(diǎn)中最大鍵值被刪除時(shí),分支結(jié)點(diǎn)中的值可以作為“分界鍵值”存在。若因刪除操作而使結(jié)點(diǎn)中鍵值個(gè)數(shù)少于m/2時(shí),則從兄弟結(jié)點(diǎn)中調(diào)劑鍵值或和兄弟結(jié)點(diǎn)合并,其過(guò)程和B-樹(shù)相似。 499.4 哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析50 前面介紹的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，查找的效率依賴于查找過(guò)程中所進(jìn)行的比較次數(shù)。理想的情況是希望不經(jīng)過(guò)任何比較，一次便能得到所查記錄。哈希表它既是一種查找方法，又是一種存貯方法

32、51哈希表：即散列存儲(chǔ)結(jié)構(gòu)。 散列法存儲(chǔ)的基本思想：建立關(guān)鍵碼字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，或者說(shuō)，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。 優(yōu)點(diǎn)：查找速度極快（O(1)）,查找效率與元素個(gè)數(shù)n無(wú)關(guān)！例1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將2001011810201的所有信息存入V01單元；將2001011810202的所有信息存入V02單元；將2001011810231的所有信息存入V31單元。欲查找學(xué)號(hào)為2001011810216的信息，便可直接訪問(wèn)V16！一、哈希表的概念52例2 ： 有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地址H（k）k，請(qǐng)畫(huà)出存儲(chǔ)結(jié)構(gòu)圖。（

33、注：H（k）k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）k ，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)表達(dá)式，迅即可查到結(jié)果！例如，查找key=9,則訪問(wèn)H(9)=9號(hào)地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或空記錄。 地址9111423242539內(nèi)點(diǎn)：空間效率低！53選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比較，確定查找是否成功。通常

34、關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。若干術(shù)語(yǔ)哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表) 沖 突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表) 54有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7通過(guò)哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！ 0 1 2 3 4 5

35、 655所以，哈希方法必須解決以下兩個(gè)問(wèn)題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。56二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法 除留余數(shù)法 乘余取整法數(shù)字分析法 平方取中法 折疊法 隨機(jī)數(shù)法 要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求

36、二：無(wú)論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。57Hash(key) = akey + b (a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。 例：關(guān)鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為Hash(key)=key/100， 則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001、直接定址法58Hash(key)= B*( A*key mod 1 ) (A、B均為常數(shù)，且0A 724+518+69 =13115、平方取中法617

37、、隨機(jī)數(shù)法Hash(key) = random ( key ) (random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長(zhǎng)度； 哈希表的大??； 關(guān)鍵字的分布情況； 查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：62三、沖突處理方法常見(jiàn)的沖突處理方法有：開(kāi)放定址法（開(kāi)地址法） 鏈地址法（拉鏈法） 再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū) 631、開(kāi)放定址法（開(kāi)地址法） 設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 具體實(shí)現(xiàn)：Hi=(Hash(key)+di) mod m (

38、1i m ) 其中： Hash(key)為哈希函數(shù) m為哈希表長(zhǎng)度 di 為增量序列 1，2，m-1，且di=i 1.線性探測(cè)法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。64關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：哈希表表長(zhǎng)為m=11； 哈希函數(shù)為Hash(key)=key mod 11； 擬用線性探測(cè)法處理沖突。建哈希表如下：解釋： 47、7（以及11、16、92）均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址；0 1 2 3 4 5 6 7 8 9 10477 例：291116922283 Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Has

39、h(29)+1) mod 11=8，哈希地址8為空，因此將29存入。 另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。其中3 還連續(xù)移動(dòng)了兩次（二次聚集）65線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞， 因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問(wèn)題。 討論：66仍舉上例，改用二次探測(cè)法處理沖突，建表如下： 0

40、 1 2 3 4 5 6 7 8 9 10112234792167298 注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。 2. 二次探測(cè)法Hi=(Hash(key)di) mod m其中：Hash(key)為哈希函數(shù) m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)數(shù)； di為增量序列 12，-12，22，-22，q2 3. 若di偽隨機(jī)序列，就稱為偽隨機(jī)探測(cè)法672、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來(lái)，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。 設(shè) 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函