《數(shù)據(jù)結(jié)構(gòu)JAVA語(yǔ)言版》課件 第8章 查找

第8章查找

數(shù)據(jù)的組織和查找是大多數(shù)應(yīng)用程序的核心，而查找是所有數(shù)據(jù)處理中最基本、最常用的操作。特別當(dāng)查找的對(duì)象是一個(gè)龐大數(shù)量的數(shù)據(jù)集合中的元素時(shí)，查找的方法和效率就顯得格外重要。

8.1

查找的概念查找表(SearchTable)：相同類型的數(shù)據(jù)元素(對(duì)象)組成的集合，每個(gè)元素通常由若干數(shù)據(jù)項(xiàng)構(gòu)成。關(guān)鍵字(Key，碼)：數(shù)據(jù)元素中某個(gè)(或幾個(gè))數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。若關(guān)鍵字能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，則關(guān)鍵字稱為主關(guān)鍵字；將能標(biāo)識(shí)若干個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為次關(guān)鍵字。查找/檢索(Searching)：根據(jù)給定的K值，在查找表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。◆

查找表中存在滿足條件的記錄：查找成功；結(jié)果：所查到的記錄信息或記錄在查找表中的位置?！?/p>

查找表中不存在滿足條件的記錄：查找失敗。查找有兩種基本形式：靜態(tài)查找和動(dòng)態(tài)查找。靜態(tài)查找（StaticSearch）：在查找時(shí)只對(duì)數(shù)據(jù)元素進(jìn)行查詢或檢索，查找表稱為靜態(tài)查找表。動(dòng)態(tài)查找（DynamicSearch）：在實(shí)施查找的同時(shí)，插入查找表中不存在的數(shù)據(jù)元素，或從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素，查找表稱為動(dòng)態(tài)查找表。查找的對(duì)象是查找表，采用何種查找方法，首先取決于查找表的組織。查找表是數(shù)據(jù)元素的集合，而集合中的元素之間是一種完全松散的關(guān)系，因此，查找表是一種非常靈活的數(shù)據(jù)結(jié)構(gòu)，可以用多種方式來(lái)存儲(chǔ)。根據(jù)存儲(chǔ)結(jié)構(gòu)的不同，查找方法可分為三大類：①順序表和鏈表的查找：將給定的K值與查找表中數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較，找到要查找的數(shù)據(jù)元素；②散列表的查找：根據(jù)給定的值直接訪問(wèn)查找表，從而找到要查找的數(shù)據(jù)元素；③索引查找表的查找：首先根據(jù)索引確定待查找數(shù)據(jù)元素所在的塊，然后再?gòu)膲K中找到要查找的數(shù)據(jù)元素。查找方法評(píng)價(jià)指標(biāo)查找過(guò)程中主要操作是關(guān)鍵字的比較，查找過(guò)程中關(guān)鍵字的平均比較次數(shù)（平均查找長(zhǎng)度ASL：AverageSearchLength）作為衡量一個(gè)查找算法效率高低的標(biāo)準(zhǔn)。ASL定義為：其中：Pi：查找第i個(gè)數(shù)據(jù)元素的概率，Ci：查找第i個(gè)數(shù)據(jù)元素需要進(jìn)行比較的次數(shù)。其中：Pi：查找第i個(gè)數(shù)據(jù)元素的概率，Ci：查找第i個(gè)數(shù)據(jù)元素需要進(jìn)行比較的次數(shù)。

8.2

靜態(tài)查找

由于靜態(tài)查找不需要在靜態(tài)查找表中插入或刪除數(shù)據(jù)元素，所以，靜態(tài)查找表的數(shù)據(jù)結(jié)構(gòu)是線性結(jié)構(gòu)，可以是順序存儲(chǔ)的靜態(tài)查找表或鏈?zhǔn)酱鎯?chǔ)的靜態(tài)查找表。8.2.1順序查找(SequentialSearch)1查找思想

順序查找又稱線性查找，從靜態(tài)查找表的一端開始，將給定數(shù)據(jù)元素的關(guān)鍵碼與表中各數(shù)據(jù)元素的關(guān)鍵碼逐一比較，若表中存在要查找的數(shù)據(jù)元素，則查找成功，并給出該數(shù)據(jù)元素在表中的位置；否則，查找失敗，給出失敗信息。順序存儲(chǔ)的靜態(tài)查找表的類型定義如下。publicclassSeqList<T>{ publicT[]data; //數(shù)組，用于存儲(chǔ)數(shù)據(jù)元素 publicintmaxsize;//容量 publicintlast;//指示最后一個(gè)數(shù)據(jù)元素在數(shù)組中的下標(biāo) publicintCount（）{ returnlast; }}

數(shù)據(jù)元素從下標(biāo)為1的分量開始存放，0號(hào)分量用來(lái)存放要查找的數(shù)據(jù)元素被稱為監(jiān)視哨，監(jiān)視哨設(shè)在順序表的最低端，稱為低端監(jiān)視哨。也可以把監(jiān)視哨設(shè)在順序表的高端，稱為高端監(jiān)視哨。假設(shè)順序表中只存放了數(shù)據(jù)元素的關(guān)鍵碼，關(guān)鍵碼的類型是整型int，順序表的順序查找的算法實(shí)現(xiàn)如下所示。publicintSeqSearch（SeqList<Integer>sqList,intkey）{ sqList.data[0]=key;//低端監(jiān)視哨 intp; for（p=sqList.Count（）;sqList.data[p]!=key;--p）;//從后往前找

returnp;//找不到時(shí)，p為0}2.算法分析從順序查找的查找過(guò)程可知，與給定值進(jìn)行比較的次數(shù)取決于所查數(shù)據(jù)元素在表中的位置。查找表中最后一個(gè)數(shù)據(jù)元素時(shí)，僅需比較一次。查找表中的第1個(gè)數(shù)據(jù)元素時(shí)需要比較n次，查找表中第i個(gè)數(shù)據(jù)元素時(shí)，需要比較n-i+1次，如表8-1所示。數(shù)據(jù)元素序號(hào)比較次數(shù)n1……in-i+11n查找失敗n+1

表8-1順序查找數(shù)據(jù)元素序號(hào)和比較次數(shù)在順序表中查找元素64如圖8-1所示。圖8-1順序查找示例

假設(shè)順序表中每個(gè)數(shù)據(jù)元素的查找概率相同，即pi=1/n（i=1，2，…，n），查找表中第i個(gè)數(shù)據(jù)元素，需進(jìn)行n-i+1次比較，即ci=n-i+1。當(dāng)查找成功時(shí)，順序查找的平均查找長(zhǎng)度為：

當(dāng)查找不成功時(shí)，關(guān)鍵碼的比較次數(shù)總是n+1次。所以順序查找時(shí)間復(fù)雜度為O（n）。在許多情況下，順序查找表中的數(shù)據(jù)元素的查找概率是不相等的。為了提高查找效率，查找表應(yīng)根據(jù)數(shù)據(jù)元素“查找概率越高關(guān)鍵碼的比較次數(shù)越少，查找概率越低，關(guān)鍵碼的比較次數(shù)越多”的原則來(lái)存儲(chǔ)數(shù)據(jù)元素。順序查找雖然簡(jiǎn)單，但效率很低，特別是當(dāng)查找表中的數(shù)據(jù)元素很多時(shí)更是如此。8.2.2

折半查找(BinarySearch)折半查找（BinarySearch）又稱為二分查找，是一種效率較高的查找方法。它的前提條件是查找表中的所有數(shù)據(jù)元素是按關(guān)鍵字有序（升序或降序）。查找過(guò)程中，先確定待查找數(shù)據(jù)元素在表中的范圍，然后逐步縮小范圍（每次將待查數(shù)據(jù)元素所在區(qū)間縮小一半），直到找到或找不到數(shù)據(jù)元素為止。1查找思想

用Low、High和Mid表示待查找區(qū)間的下界、上界和中間位置指針，初值為L(zhǎng)ow=1，High=n。⑴取中間位置Mid：Mid=(Low+High)/2；⑵比較中間位置記錄的關(guān)鍵字與給定的K值：①相等：查找成功；②大于：待查記錄在區(qū)間的前半段，修改上界指針：High=Mid-1，轉(zhuǎn)⑴；③小于：待查記錄在區(qū)間的后半段，修改下界指針：Low=Mid+1，轉(zhuǎn)⑴；直到越界(Low>High)，查找失敗。2算法示例

查找成功實(shí)例

已知11個(gè)數(shù)據(jù)元素的有序表（關(guān)鍵字即為數(shù)據(jù)元素的值），如下所示?，F(xiàn)查找關(guān)鍵字為21的元素。3.算法實(shí)現(xiàn)publicintBinarySearch(SeqList<Integer>sqList,intkey){ intLow=1,High=sqList.Count(),Mid; while(Low<High){ Mid=(Low+High)/2;//Mid結(jié)果只保留整數(shù) if(sqList.data[Mid]==key) returnMid; elseif(sqList.data[Mid]<key) Low=Mid+1; else High=Mid-1; } return0;/*查找失敗*/}4算法分析①查找時(shí)每經(jīng)過(guò)一次比較，查找范圍就縮小一半，該過(guò)程可用一棵二叉樹表示：◆

根結(jié)點(diǎn)就是第一次進(jìn)行比較的中間位置的記錄；◆排在中間位置前面的作為左子樹的結(jié)點(diǎn)；◆排在中間位置后面的作為右子樹的結(jié)點(diǎn)；對(duì)各子樹來(lái)說(shuō)都是相同的。這樣所得到的二叉樹稱為判定樹(DecisionTree)。②將二叉判定樹的第

㏒2n+1層上的結(jié)點(diǎn)補(bǔ)齊就成為一棵滿二叉樹，深度不變，h=

㏒2(n+1)

。③由滿二叉樹性質(zhì)知，第i層上的結(jié)點(diǎn)數(shù)為2i-1(i≤h)，設(shè)表中每個(gè)記錄的查找概率相等，即Pi=1/n，查找成功時(shí)的平均查找長(zhǎng)度ASL：ASL=∑Pi

Ci=i=1n∑j2j-1=j=1hn―1nn+1㏒2(n+1)-1當(dāng)n很大(n>50)時(shí)，ASL≈㏒2(n+1)-1。8.2.3

分塊查找

分塊查找(BlockingSearch)又稱索引順序查找，是前面兩種查找方法的綜合。1查找表的組織①

將查找表分成幾塊。塊間有序，即第i+1塊的所有記錄關(guān)鍵字均大于(或小于)第i塊記錄關(guān)鍵字；塊內(nèi)無(wú)序。②在查找表的基礎(chǔ)上附加一個(gè)索引表，索引表是按關(guān)鍵字有序的，索引表中記錄的構(gòu)成是：最大關(guān)鍵字起始引用2查找思想

先確定待查記錄所在塊，再在塊內(nèi)查找(順序查找)。3算法實(shí)現(xiàn)classIndex<T>{publicTmaxkey;/*塊中最大的關(guān)鍵字*/publicintstartpos;/*塊的起始位置指針*/} intBlock_search(SeqList<Integer>sqList,Index<Integer>[]ind,intkey,intn,intb){ /*在分塊索引表中查找關(guān)鍵字為key的數(shù)據(jù)元素*/ /*表長(zhǎng)為n，塊數(shù)為b*/ inti=0,j; while((i<b)&&(ind[i].maxkey<key)) i++; if(i>b){ System.out.println("Notfound"); return0; } j=ind[i].startpos; while((j<=n)&&(sqList.data[j]<=ind[i].maxkey)){ if(sqList.data[j]==key) break; j++; }/*在塊內(nèi)查找*/ if(j>n||sqList.data[j]!=key){ j=0; System.out.println("Notfound"); } returnj;}4

算法分析設(shè)表長(zhǎng)為n個(gè)記錄，均分為b塊，每塊記錄數(shù)為s，則b=?n/s?。設(shè)記錄的查找概率相等，每塊的查找概率為1/b，塊中記錄的查找概率為1/s，則平均查找長(zhǎng)度ASL：ASL=Lb+Lw=∑j+j=1b∑i=i=1ss―12b+12s+1+8.3

動(dòng)態(tài)查找

當(dāng)查找表以線性表的形式組織時(shí)，若對(duì)查找表進(jìn)行插入、刪除或排序操作，就必須移動(dòng)大量的記錄，當(dāng)記錄數(shù)很多時(shí)，這種移動(dòng)的代價(jià)很大。利用樹的形式組織查找表，可以對(duì)查找表進(jìn)行動(dòng)態(tài)高效的查找。8.3.1二叉排序樹(BST)的定義二叉排序樹(BinarySortTree或BinarySearchTree)的定義為：二叉排序樹或者是空樹，或者是滿足下列性質(zhì)的二叉樹。(1)：若左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值(關(guān)鍵字)都小于根結(jié)點(diǎn)的值；(2)：若右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值(關(guān)鍵字)都大于根結(jié)點(diǎn)的值；(3)：左、右子樹都分別是二叉排序樹。

結(jié)論：若按中序遍歷一棵二叉排序樹，所得到的結(jié)點(diǎn)序列是一個(gè)遞增序列。

BST仍然可以用二叉鏈表來(lái)存儲(chǔ)，結(jié)點(diǎn)類型定義如下：

publicclassBSTNode<T>{ publicTkey;/*關(guān)鍵字域*/ //…/*其它數(shù)據(jù)域*/ publicBSTNode<T>Lchild,Rchild; //無(wú)參構(gòu)造器 publicBSTNode(){ Lchild=null; Rchild=null; }}8.3.2BST樹的查找1查找思想

首先將給定的K值與二叉排序樹的根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：若相等：則查找成功；①

給定的K值小于BST的根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的左子樹上進(jìn)行查找；②給定的K值大于BST的根結(jié)點(diǎn)的關(guān)鍵字：繼續(xù)在該結(jié)點(diǎn)的右子樹上進(jìn)行查找。2.查找實(shí)例在圖所示的二叉排序樹中查找關(guān)鍵字等于100的數(shù)據(jù)元素（樹中結(jié)點(diǎn)內(nèi)的關(guān)鍵字均為數(shù)據(jù)元素的關(guān)鍵字）。首先以key=100和根結(jié)點(diǎn)的關(guān)鍵字作比較，因?yàn)閗ey>45，則查找以45為根的右子樹，此時(shí)右子樹不空，且key>53，則繼續(xù)查找以結(jié)點(diǎn)53為根的右子樹，由于key和53的右子樹根的關(guān)鍵字100相等，則查找成功，返回指向結(jié)點(diǎn)100的指針值。8.3.3BST樹的插入在BST樹中插入一個(gè)新結(jié)點(diǎn)，要保證插入后仍滿足BST的性質(zhì)。1

插入思想

在BST樹中插入一個(gè)新結(jié)點(diǎn)x時(shí)，若BST樹為空，則令新結(jié)點(diǎn)x為插入后BST樹的根結(jié)點(diǎn)；否則，將結(jié)點(diǎn)x的關(guān)鍵字與根結(jié)點(diǎn)T的關(guān)鍵字進(jìn)行比較：①

若相等：不需要插入；②若x.key<T->key：結(jié)點(diǎn)x插入到T的左子樹中；③若x.key>T->key：結(jié)點(diǎn)x插入到T的右子樹中。8.3.4BST樹的刪除

1刪除操作過(guò)程分析

從BST樹上刪除一個(gè)結(jié)點(diǎn)，仍然要保證刪除后滿足BST的性質(zhì)。設(shè)被刪除結(jié)點(diǎn)為p，其父結(jié)點(diǎn)為f，刪除情況如下：①若p是葉子結(jié)點(diǎn)：直接刪除p，如圖(a)

(b)所示。

128610151913149(a)BST樹1286101513149(b)刪除結(jié)點(diǎn)19②若p只有一棵子樹(左子樹或右子樹)：直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即原來(lái)p是f的左子樹，則p的子樹成為f的左子樹；原來(lái)p是f的右子樹，則p的子樹成為f的右子樹，如圖

(b)、(c)所示。1286101513149(b)BST樹12869151314(c)刪除結(jié)點(diǎn)10③若p既有左子樹又有右子樹

：處理方法有以下兩種，可以任選其中一種。◆第一種用p的直接前驅(qū)結(jié)點(diǎn)代替p。即從p的左子樹中選擇值最大的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。s是p的左子樹中的最右邊的結(jié)點(diǎn)且沒(méi)有右子樹，對(duì)s的刪除同①②，如圖(c)

(d)所示。(d)刪除結(jié)點(diǎn)1298615131412869151314(c)BST樹③若p既有左子樹又有右子樹

：處理方法有以下兩種，可以任選其中一種。◆第二種用p的直接后繼結(jié)點(diǎn)代替p。即從p的右子樹中選擇值最小的結(jié)點(diǎn)s放在p的位置(用結(jié)點(diǎn)s的內(nèi)容替換結(jié)點(diǎn)p內(nèi)容)，然后刪除結(jié)點(diǎn)s。s是p的右子樹中的最左邊的結(jié)點(diǎn)且沒(méi)有左子樹，對(duì)s的刪除同①②，如圖(c)(e)所示。(e)刪除結(jié)點(diǎn)121386151412869151314(c)BST樹98.4

平衡二叉樹(AVL)

BST是一種查找效率比較高的組織形式，但其平均查找長(zhǎng)度受樹的形態(tài)影響較大，形態(tài)比較均勻時(shí)查找效率很好，形態(tài)明顯偏向某一方向時(shí)其效率就大大降低。因此，希望有更好的二叉排序樹，其形態(tài)總是均衡的，查找時(shí)能得到最好的效率，這就是平衡二叉排序樹。平衡二叉排序樹(BalancedBinaryTree或Height-BalancedTree)是在1962年由Adelson-Velskii和Landis提出的，又稱AVL樹。8.4.1平衡二叉樹的定義平衡二叉樹或者是空樹，或者是滿足下列性質(zhì)的二叉樹。⑴：左子樹和右子樹深度之差的絕對(duì)值不大于1；⑵：左子樹和右子樹也都是平衡二叉樹。

平衡因子(BalanceFactor)：二叉樹上結(jié)點(diǎn)的左子樹的深度減去其右子樹深度稱為該結(jié)點(diǎn)的平衡因子。因此，平衡二叉樹上每個(gè)結(jié)點(diǎn)的平衡因子只可能是-1、0和1，否則，只要有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，該二叉樹就不是平衡二叉樹。如果一棵二叉樹既是二叉排序樹又是平衡二叉樹，稱為平衡二叉排序樹(BalancedBinarySortTree)。在平衡二叉排序樹上執(zhí)行查找的過(guò)程與二叉排序樹上的查找過(guò)程完全一樣，則在AVL樹上執(zhí)行查找時(shí)，和給定的K值比較的次數(shù)不超過(guò)樹的深度。

設(shè)深度為h的平衡二叉排序樹所具有的最少結(jié)點(diǎn)數(shù)為Nh，則由平衡二叉排序樹的性質(zhì)知：

平衡二叉樹16241241518結(jié)點(diǎn)類型定義如下：

publicclassBBSTNode<T>{ publicTkey;/*關(guān)鍵字域*/ publicintBfactor;/*平衡因子域*/ //.../*其它數(shù)據(jù)域*/ publicBBSTNode<T>Lchild,Rchild;}N0=0，N1=1，N2=2，…

，Nh=Nh-1+Nh-2

該關(guān)系和Fibonacci數(shù)列相似。根據(jù)歸納法可證明，當(dāng)h≥0時(shí)，Nh=Fh+2-1，…而這樣，含有n個(gè)結(jié)點(diǎn)的平衡二叉排序樹的最大深度為h≈√5㏒φ(

(n+1))-2φh√5Fh≈21+√5其中φ=φh√5則Nh≈-1則在平衡二叉排序樹上進(jìn)行查找的平均查找長(zhǎng)度和㏒2n是一個(gè)數(shù)量級(jí)的，平均時(shí)間復(fù)雜度為O(㏒2n)。8.4.2平衡化旋轉(zhuǎn)

一般的二叉排序樹是不平衡的，若能通過(guò)某種方法使其既保持有序性，又具有平衡性，就找到了構(gòu)造平衡二叉排序樹的方法，該方法稱為平衡化旋轉(zhuǎn)。在對(duì)AVL樹進(jìn)行插入或刪除一個(gè)結(jié)點(diǎn)后，通常會(huì)影響到從根結(jié)點(diǎn)到插入(或刪除)結(jié)點(diǎn)的路徑上的某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的子樹可能發(fā)生變化。以插入結(jié)點(diǎn)為例，影響有以下幾種可能性◆

以某些結(jié)點(diǎn)為根的子樹的深度發(fā)生了變化；◆

某些結(jié)點(diǎn)的平衡因子發(fā)生了變化；◆

某些結(jié)點(diǎn)失去平衡。

沿著插入結(jié)點(diǎn)上行到根結(jié)點(diǎn)就能找到某些結(jié)點(diǎn)，這些結(jié)點(diǎn)的平衡因子和子樹深度都會(huì)發(fā)生變化，這樣的結(jié)點(diǎn)稱為失衡結(jié)點(diǎn)。1LL型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的左孩子的左子樹上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。a插入前的平衡因子是1，插入后的平衡因子是2。設(shè)b是a的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1(否則b就是失衡結(jié)點(diǎn))。abbRaRbLxabbRaRbLxabbRaRbLxLL型平衡化旋轉(zhuǎn)示意圖⑵平衡化旋轉(zhuǎn)方法通過(guò)順時(shí)針旋轉(zhuǎn)操作實(shí)現(xiàn)，如下所示。用b取代a的位置，a成為b的右子樹的根結(jié)點(diǎn)，b原來(lái)的右子樹作為a的左子樹。

⑶插入后各結(jié)點(diǎn)的平衡因子分析①旋轉(zhuǎn)前的平衡因子設(shè)插入后b的左子樹的深度為HbL，則其右子樹的深度為HbL-1；a的左子樹的深度為HbL+1。a的平衡因子為2，則a的右子樹的深度為：HaR=HbL+1-2=HbL-1。abbRaRbLxabbRaRbLxLL型平衡化旋轉(zhuǎn)示意圖②旋轉(zhuǎn)后的平衡因子

a的右子樹沒(méi)有變，而左子樹是b的右子樹，則平衡因子是：HaL-HaR=(HbL-1)-(HbL-1)=0

即a是平衡的，以a為根的子樹的深度是HbL。

b的左子樹沒(méi)有變化，右子樹是以a為根的子樹，則平衡因子是：HbL-HbL=0

即b也是平衡的，以b為根的子樹的深度是HbL+1，與插入前a的子樹的深度相同，則該子樹的上層各結(jié)點(diǎn)的平衡因子沒(méi)有變化，即整棵樹旋轉(zhuǎn)后是平衡的。abbRaRbLxabbRaRbLxLL型平衡化旋轉(zhuǎn)示意圖⑷旋轉(zhuǎn)算法假設(shè)關(guān)鍵字的類型是整型，算法如下。

publicBBSTNode<Integer>LL_rotate(BBSTNode<Integer>a){BBSTNode<Integer>b=newBBSTNode<Integer>();b=a.Lchild;a.Lchild=b.Rchild;b.Rchild=a;a.Bfactor=b.Bfactor=0;//a=b;a保持不變，返回breturnb;}2LR型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的左孩子的右子樹上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。設(shè)b是a的左孩子，c為b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點(diǎn)。abbLaRcLxcRxc2LR型平衡化旋轉(zhuǎn)⑵插入后結(jié)點(diǎn)c的平衡因子的變化分析①插入后c的平衡因子是1：假設(shè)在c的左子樹上插入。設(shè)c的左子樹的深度為HcL，則右子樹的深度為HcL-1；b插入后的平衡因子是-1，則b的左子樹的深度為HcL，以b為根的子樹的深度是HcL+2。因插入后a的平衡因子是2，則a的右子樹的深度是HcL。abbLaRcLxcRxc②插入后c的平衡因子是0：c本身是插入結(jié)點(diǎn)。設(shè)c的左子樹的深度為HcL，則右子樹的深度也是HcL；因b插入后的平衡因子是-1，則b的左子樹的深度為HcL，以b為根的子樹的深度是HcL+2；插入后a的平衡因子是2，則a的右子樹的深度是HcL。

abbLaRcLxcRxc③插入后c的平衡因子是-1：即在c的右子樹上插入。設(shè)c的左子樹的深度為HcL，則右子樹的深度為HcL+1，以c為根的子樹的深度是HcL+2；因b插入后的平衡因子是-1，則b的左子樹的深度為HcL+1，以b為根的子樹的深度是HcL+3；則a的右子樹的深度是HcL+1。abbLaRcLxcRxc⑶平衡化旋轉(zhuǎn)方法

先以b進(jìn)行一次逆時(shí)針旋轉(zhuǎn)(將以b為根的子樹旋轉(zhuǎn)為以c為根)，再以a進(jìn)行一次順時(shí)針旋轉(zhuǎn)，如圖所示。將整棵子樹旋轉(zhuǎn)為以c為根，b是c的左子樹，a是c的右子樹；c的右子樹移到a的左子樹位置，c的左子樹移到b的右子樹位置。圖LR型平衡化旋轉(zhuǎn)示意圖abbLaRcLxcRxcacbLaRcLxcRxb⑷旋轉(zhuǎn)后各結(jié)點(diǎn)(a,b,c)平衡因子分析

①

旋轉(zhuǎn)前(插入后)c的平衡因子是1：

a的左子樹深度為HcL-1，其右子樹沒(méi)有變化，深度是HcL，則a的平衡因子是-1；b的左子樹沒(méi)有變化，深度為HcL，右子樹是c旋轉(zhuǎn)前的左子樹，深度為HcL，則b的平衡因子是0；c的左、右子樹分別是以b和a為根的子樹，則c的平衡因子是0

。

②

旋轉(zhuǎn)前

(插入后)c的平衡因子是0：旋轉(zhuǎn)后a，b，c的平衡因子都是0

。

③

旋轉(zhuǎn)前

(插入后)c的平衡因子是-1：旋轉(zhuǎn)后a，b，c的平衡因子分別是0，-1，0

。綜上所述，即整棵樹旋轉(zhuǎn)后是平衡的。⑸旋轉(zhuǎn)算法publicBBSTNode<Integer>LR_rotate(BBSTNode<Integer>a){BBSTNode<Integer>b=newBBSTNode<Integer>();BBSTNode<Integer>c=newBBSTNode<Integer>();b=a.Lchild;c=b.Rchild;/*初始化*/a.Lchild=c.Rchild;b.Rchild=c.Lchild;c.Lchild=b;c.Rchild=a;if(c.Bfactor==1){a.Bfactor=-1;b.Bfactor=0;}elseif(c.Bfactor==0)a.Bfactor=b.Bfactor=0;else{a.Bfactor=0;b.Bfactor=1;}returnc;}3RL型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的右孩子的左子樹上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡，與LR型正好對(duì)稱。對(duì)于結(jié)點(diǎn)a，插入前的平衡因子是-1，插入后a的平衡因子是-2。設(shè)b是a的右孩子，c為b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同樣，c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點(diǎn)。abbRaLcLxcRxc⑵插入后結(jié)點(diǎn)c的平衡因子的變化分析

①插入后c的平衡因子是1：在c的左子樹上插入。設(shè)c的左子樹的深度為HcL，則右子樹的深度為HcL-1。因b插入后的平衡因子是1，則其右子樹的深度為HcL，以b為根的子樹的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹的深度是HcL。abbRaLcLxcRxc

②插入后c的平衡因子是0：c本身是插入結(jié)點(diǎn)。設(shè)c的左子樹的深度為HcL，則右子樹的深度也是HcL；因b插入后的平衡因子是1，則b的右子樹的深度為HcL，以b為根的子樹的深度是HcL+2；因插入后a的平衡因子是-2，則a的左子樹的深度是HcL。

abbRaLcLxcRxc③插入后c的平衡因子是-1：在c的右子樹上插入。設(shè)c的左子樹的深度為HcL，則右子樹的深度為HcL+1，以c為根的子樹的深度是HcL+2；因b插入后的平衡因子是1，則b的右子樹的深度為HcL+1，以b為根的子樹的深度是HcL+3；則a的右子樹的深度是HcL+1。abbRaLcLxcRxc⑶平衡化旋轉(zhuǎn)方法

先以b進(jìn)行一次順時(shí)針旋轉(zhuǎn)，再以a進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，如圖所示。即將整棵子樹(以a為根)旋轉(zhuǎn)為以c為根，a是c的左子樹，b是c的右子樹；c的右子樹移到b的左子樹位置，c的左子樹移到a的右子樹位置。圖RL型平衡化旋轉(zhuǎn)示意圖abbRaLcLxcRxcbcbRaLcLxcRxa⑷旋轉(zhuǎn)后各結(jié)點(diǎn)(a,b,c)的平衡因子分析①

旋轉(zhuǎn)前

(插入后)c的平衡因子是1：

a的左子樹沒(méi)有變化，深度是HcL，右子樹是c旋轉(zhuǎn)前的左子樹，深度為HcL，則a的平衡因子是0；b的右子樹沒(méi)有變化，深度為HcL，左子樹是c旋轉(zhuǎn)前的右子樹，深度為HcL-1

，則b的平衡因子是-1；c的左、右子樹分別是以a和b為根的子樹，則c的平衡因子是0

。

②

旋轉(zhuǎn)前

(插入后)c的平衡因子是0：旋轉(zhuǎn)后a，b，c的平衡因子都是0

。

③

旋轉(zhuǎn)前

(插入后)c的平衡因子是-1：旋轉(zhuǎn)后a，b，c的平衡因子分別是1，0，0

。綜上所述，即整棵樹旋轉(zhuǎn)后是平衡的。⑸旋轉(zhuǎn)算法

假設(shè)關(guān)鍵字的類型是整型，算法如下。publicBBSTNode<Integer>RL_rotate(BBSTNode<Integer>a){ BBSTNode<Integer>b=newBBSTNode<Integer>(); BBSTNode<Integer>c=newBBSTNode<Integer>(); b=a.Rchild; c=b.Lchild;/*初始化*/ a.Rchild=c.Lchild; b.Lchild=c.Rchild; c.Lchild=a; c.Rchild=b; if(c.Bfactor==1){ a.Bfactor=0; b.Bfactor=-1; }elseif(c.Bfactor==0) a.Bfactor=b.Bfactor=0; else{ a.Bfactor=1; b.Bfactor=0; } returnc;}4

RR型平衡化旋轉(zhuǎn)⑴失衡原因在結(jié)點(diǎn)a的右孩子的右子樹上進(jìn)行插入，插入使結(jié)點(diǎn)a失去平衡。要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)，和LL型平衡化旋轉(zhuǎn)正好對(duì)稱。⑵平衡化旋轉(zhuǎn)方法

設(shè)b是a的右孩子，通過(guò)逆時(shí)針旋轉(zhuǎn)實(shí)現(xiàn)，如圖所示。用b取代a的位置，a作為b的左子樹的根結(jié)點(diǎn)，b原來(lái)的左子樹作為a的右子樹。圖RR型平衡化旋轉(zhuǎn)示意圖babLaLbRxabbLaLbRx⑶旋轉(zhuǎn)算法假設(shè)關(guān)鍵字的類型是整型，算法如下。publicBBSTNode<Integer>RR_rotate(BBSTNode<Integer>a){BBSTNode<Integer>b=newBBSTNode<Integer>();b=a.Rchild;a.Rchild=b.Lchild;b.Lchild=a;a.Bfactor=b.Bfactor=0;returnb;}

對(duì)于上述四種平衡化旋轉(zhuǎn)，其正確性容易由“遍歷所得中序序列不變”來(lái)證明。并且，無(wú)論是哪種情況，平衡化旋轉(zhuǎn)處理完成后，形成的新子樹仍然是平衡二叉排序樹，且其深度和插入前以a為根結(jié)點(diǎn)的平衡二叉排序樹的深度相同。所以，在平衡二叉排序樹上因插入結(jié)點(diǎn)而失衡，僅需對(duì)失衡子樹做平衡化旋轉(zhuǎn)處理。8.4.3平衡二叉排序樹的插入平衡二叉排序樹的插入操作實(shí)際上是在二叉排序樹插入的基礎(chǔ)上完成以下工作：⑴：判別插入結(jié)點(diǎn)后的二叉排序樹是否產(chǎn)生不平衡?⑵：找出失去平衡的最小子樹；⑶：判斷旋轉(zhuǎn)類型，然后做相應(yīng)調(diào)整。失衡的最小子樹的根結(jié)點(diǎn)a在插入前的平衡因子不為0，且是離插入結(jié)點(diǎn)最近的平衡因子不為0的結(jié)點(diǎn)的。若a失衡，從a到插入點(diǎn)的路徑上的所有結(jié)點(diǎn)的平衡因子都會(huì)發(fā)生變化，在該路徑上還有一個(gè)結(jié)點(diǎn)的平衡因子不為0且該結(jié)點(diǎn)插入后沒(méi)有失衡，其平衡因子只能是由1到0或由-1到0，以該結(jié)點(diǎn)為根的子樹深度不變。該結(jié)點(diǎn)的所有祖先結(jié)點(diǎn)的平衡因子也不變，更不會(huì)失衡。1

算法思想(插入結(jié)點(diǎn)的步驟)①：按照二叉排序樹的定義，將結(jié)點(diǎn)s插入；②：在查找結(jié)點(diǎn)s的插入位置的過(guò)程中，記錄離結(jié)點(diǎn)s最近且平衡因子不為0的結(jié)點(diǎn)a，若該結(jié)點(diǎn)不存在，則結(jié)點(diǎn)a指向根結(jié)點(diǎn)；③：修改結(jié)點(diǎn)a到結(jié)點(diǎn)s路徑上所有結(jié)點(diǎn)的平衡因子；④：判斷是否產(chǎn)生不平衡，若不平衡，則確定旋轉(zhuǎn)類型并做相應(yīng)調(diào)整。2

算法實(shí)現(xiàn)8.4.4平衡二叉排序樹構(gòu)造實(shí)例例：設(shè)要構(gòu)造的平衡二叉樹中各結(jié)點(diǎn)的值分別是(3,14,25,81,44)，平衡二叉樹的構(gòu)造過(guò)程如圖所示。3314(a)插入不超過(guò)兩個(gè)結(jié)點(diǎn)(b)插入新結(jié)點(diǎn)失衡,RR平衡旋轉(zhuǎn)31425314253142581(c)插入新結(jié)點(diǎn)未失衡(d)插入結(jié)點(diǎn)失衡,RL平衡旋轉(zhuǎn)314258144314448125圖

平衡二叉樹的構(gòu)造過(guò)程8.5

索引查找索引技術(shù)是組織大型數(shù)據(jù)庫(kù)的重要技術(shù)，索引結(jié)構(gòu)的基本組成是索引表和數(shù)據(jù)表兩部分，如下圖所示?！魯?shù)據(jù)表：存儲(chǔ)實(shí)際的數(shù)據(jù)記錄；◆索引表：存儲(chǔ)記錄的關(guān)鍵字和記錄(存儲(chǔ))地址之間的對(duì)照表，每個(gè)元素稱為一個(gè)索引項(xiàng)。索引表數(shù)據(jù)表圖

索引結(jié)構(gòu)的基本形式

關(guān)鍵字存儲(chǔ)地址

263

275

386

…

…

1046關(guān)鍵字…

386

263

1046

…

275通過(guò)索引表可實(shí)現(xiàn)對(duì)數(shù)據(jù)表中記錄的快速查找。索引表的組織有線性結(jié)構(gòu)和樹形結(jié)構(gòu)兩種。8.5.1順序索引表

是將索引項(xiàng)按順序結(jié)構(gòu)組織的線性索引表，而表中索引項(xiàng)一般是按關(guān)鍵字排序的，其特點(diǎn)是：優(yōu)點(diǎn)：◆

可以用折半查找方法快速找到關(guān)鍵字，進(jìn)而找到數(shù)據(jù)記錄的物理地址，實(shí)現(xiàn)數(shù)據(jù)記錄的快速查找；◆

提供對(duì)變長(zhǎng)數(shù)據(jù)記錄的便捷訪問(wèn)；◆

插入或刪除數(shù)據(jù)記錄時(shí)不需要移動(dòng)記錄，但需要對(duì)索引表進(jìn)行維護(hù)。缺點(diǎn)：◆

索引表中索引項(xiàng)的數(shù)目與數(shù)據(jù)表中記錄數(shù)相同，當(dāng)索引表很大時(shí)，檢索記錄需多次訪問(wèn)外存；◆

對(duì)索引表的維護(hù)代價(jià)較高，涉及到大量索引項(xiàng)的移動(dòng)，不適合于插入和刪除操作。8.5.2樹形索引表

平衡二叉排序樹便于動(dòng)態(tài)查找，因此用平衡二叉排序樹來(lái)組織索引表是一種可行的選擇。當(dāng)用于大型數(shù)據(jù)庫(kù)時(shí)，所有數(shù)據(jù)及索引都存儲(chǔ)在外存，因此，涉及到內(nèi)、外存之間頻繁的數(shù)據(jù)交換，這種交換速度的快慢成為制約動(dòng)態(tài)查找的瓶頸。若以二叉樹的結(jié)點(diǎn)作為內(nèi)、外存之間數(shù)據(jù)交換單位，則查找給定關(guān)鍵字時(shí)對(duì)磁盤平均進(jìn)行㏒2n次訪問(wèn)是不能容忍的，因此，必須選擇一種能盡可能降低磁盤I/O次數(shù)的索引組織方式。樹結(jié)點(diǎn)的大小盡可能地接近頁(yè)的大小。

R.Bayer和E.McCreight在1972年提出了一種多路平衡查找樹，稱為B_樹(其變型體是B+樹)。1B_樹

B_樹主要用于文件系統(tǒng)中，在B_樹中，每個(gè)結(jié)點(diǎn)的大小為一個(gè)磁盤頁(yè)，結(jié)點(diǎn)中所包含的關(guān)鍵字及其孩子的數(shù)目取決于頁(yè)的大小。1B_樹一棵m階B_樹，或者是空樹，或者是滿足以下性質(zhì)的m叉樹：⑴根結(jié)點(diǎn)或者是葉子，或者至少有兩棵子樹，至多有m棵子樹；⑵除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有

m/2

棵子樹，至多有m棵子樹；⑶所有葉子結(jié)點(diǎn)都在樹的同一層上；一棵4階的B_樹⑷每個(gè)結(jié)點(diǎn)應(yīng)包含如下信息：

(n，A0，K1，A1，K2，A2，…

，Kn，An)其中Ki(1≤i≤n)是關(guān)鍵字，且Ki<Ki+1(1≤i≤n-1)；Ai(i=0，1，…

，n)為指向孩子結(jié)點(diǎn)的指針，且Ai-1所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都小于Ki，Ai所指向的子樹中所有結(jié)點(diǎn)的關(guān)鍵字都大于Ki；n是結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)，且

m/2

-1≤n≤m-1，n+1為子樹的棵數(shù)。

一棵4階的B_樹根據(jù)m階B_樹的定義，結(jié)點(diǎn)的類型定義如下：publicclassBTNode<T>{ intm;/*b_樹的階數(shù)*/ intkeynum;/*結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)*/ BTNode<T>parent;/*指向父結(jié)點(diǎn)的引用*/ T[]key;/*關(guān)鍵字向量,key[0]未用*/

BTNode<T>[]ptr;/*子樹引用向量*/}2B_樹的查找

由B_樹的定義可知，在其上的查找過(guò)程和二叉排序樹的查找相似。⑴算法思想①?gòu)膓=樹的根結(jié)點(diǎn)開始，在q所指向的結(jié)點(diǎn)的關(guān)鍵字向量key[1…keynum]中查找給定值K（用折半查找）：若key[i]=K（1≤i≤keynum），則查找成功，返回結(jié)點(diǎn)及關(guān)鍵字位置；否則，轉(zhuǎn)②；②將K與向量key[1…keynum]中的各個(gè)分量的值進(jìn)行比較，以選定查找的子樹：◆若K<key[1]：q=q.ptr[0]；◆若key[i]<K<key[i+1]（i=1，2，…，keynum-1）：q=q.ptr[i]；◆若K>key[keynum]：q=q.ptr[keynum]；轉(zhuǎn)①，直到q是F結(jié)點(diǎn)且未找到相等的關(guān)鍵字，則查找失敗。(2)

算法實(shí)例在下圖的B_樹上查找關(guān)鍵字47的過(guò)程如下：首先從根結(jié)點(diǎn)a開始，因?yàn)閍結(jié)點(diǎn)中只有一個(gè)關(guān)鍵字，且給定值47>關(guān)鍵字35，若存在必在指針A1所指的子樹中。同樣，順指針找到c結(jié)點(diǎn)，在該結(jié)點(diǎn)中有兩個(gè)關(guān)鍵字（43和78），因?yàn)?3<47<78，若存在必在指針A1所指的子樹中。同樣，順指針找到g結(jié)點(diǎn)，在該結(jié)點(diǎn)中順序查找到關(guān)鍵字47，由此，查找成功。(2)

算法實(shí)例查找不成功的過(guò)程也類似，例如在同一棵樹中查找23，從根開始，因?yàn)?3<35，則順該結(jié)點(diǎn)中指針A0找到b結(jié)點(diǎn)，又因?yàn)閎結(jié)點(diǎn)中只有一個(gè)關(guān)鍵字18，且23>18，所以順結(jié)點(diǎn)中的第二個(gè)指針A1找到e結(jié)點(diǎn)。同理因?yàn)?3<27，則順指針往下找，此時(shí)因指針?biāo)笧镕結(jié)點(diǎn)，說(shuō)明此棵B_樹中不存在關(guān)鍵字23，查找因失敗而告終。由此可見，在B_樹上進(jìn)行查找的過(guò)程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)的關(guān)鍵字中進(jìn)行查找交叉進(jìn)行的過(guò)程。(3)

算法實(shí)現(xiàn)假設(shè)關(guān)鍵字的類型是整型，算法如下。intBT_search(BTNode<Integer>Tree,intK,BTNode<Integer>p)/*在B_樹中查找關(guān)鍵字K,查找成功返回在結(jié)點(diǎn)中的位置及結(jié)點(diǎn)指針p;否則返回0及最后一個(gè)結(jié)點(diǎn)指針*/{//Tree是樹的根結(jié)點(diǎn)，K是要查找的關(guān)鍵字，p用來(lái)記錄結(jié)點(diǎn)指針BTNode<Integer>q;inti;p=q=Tree;while(q!=null){p=q;q.key[0]=K;/*設(shè)置查找哨兵*/for(i=q.keynum;K<q.key[i];i--){if(i>0&&q.key[i]==K)returni;q=q.ptr[i];}return0;}(4)算法分析

在B_樹上的查找有兩中基本操作：◆

在B_樹上查找結(jié)點(diǎn)(查找算法中沒(méi)有體現(xiàn))；◆

在結(jié)點(diǎn)中查找關(guān)鍵字：在磁盤上找到指針ptr所指向的結(jié)點(diǎn)后，將結(jié)點(diǎn)信息讀入內(nèi)存后再查找。因此，磁盤上的查找次數(shù)(待查找的記錄關(guān)鍵字在B_樹上的層次數(shù))是決定B_樹查找效率的首要因素。根據(jù)m階B_樹的定義，第一層上至少有1個(gè)結(jié)點(diǎn)，第二層上至少有2個(gè)結(jié)點(diǎn)；除根結(jié)點(diǎn)外，所有非終端結(jié)點(diǎn)至少有

m/2

棵子樹，…，第h層上至少有

m/2

h-2個(gè)結(jié)點(diǎn)。在這些結(jié)點(diǎn)中：根結(jié)點(diǎn)至少包含1個(gè)關(guān)鍵字，其它結(jié)點(diǎn)至少包含

m/2

-1個(gè)關(guān)鍵字，設(shè)s=

m/2

，則總的關(guān)鍵字?jǐn)?shù)目n滿足：n≧1+(s-1)∑2si=i=2h=2sh-1-1s-1sh-1-12(s-1)因此有：

h≦1+㏒s((n+1)/2)=1+㏒

m/2

((n+1)/2)

即在含有n個(gè)關(guān)鍵字的B_樹上進(jìn)行查找時(shí)，從根結(jié)點(diǎn)到待查找記錄關(guān)鍵字的結(jié)點(diǎn)的路徑上所涉及的結(jié)點(diǎn)數(shù)不超過(guò)1+㏒

m/2

((n+1)/2)。3B_樹的插入

B_樹的生成也是從空樹起，逐個(gè)插入關(guān)鍵字。插入時(shí)不是每插入一個(gè)關(guān)鍵字就添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)葉子結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，然后有可能“分裂”。⑴插入思想①在B_樹的中查找關(guān)鍵字K，若找到，表明關(guān)鍵字已存在，返回；否則，K的查找操作失敗于某個(gè)葉子結(jié)點(diǎn)，轉(zhuǎn)

②；②將K插入到該葉子結(jié)點(diǎn)中，插入時(shí)，若：◆

葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)<m-1：直接插入；◆

葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)=m-1：將結(jié)點(diǎn)“分裂”

。⑵結(jié)點(diǎn)“分裂”方法設(shè)待“分裂”結(jié)點(diǎn)包含信息為：

(m，A0，K1，A1，K2，A2，…

，Km，Am)，從其中間位置分為兩個(gè)結(jié)點(diǎn)：(

m/2

-1，A0，K1，A1，…

，K

m/2

-1，A

m/2

-1)(m-

m/2

，A

m/2

，K

m/2

+1，A

m/2

+1，…

，Km，Am)

并將中間關(guān)鍵字K

m/2

插入到p的父結(jié)點(diǎn)中，以分裂后的兩個(gè)結(jié)點(diǎn)作為中間關(guān)鍵字K

m/2

的兩個(gè)子結(jié)點(diǎn)。當(dāng)將中間關(guān)鍵字K

m/2

插入到p的父結(jié)點(diǎn)后，父結(jié)點(diǎn)也可能不滿足m階B_樹的要求(分枝數(shù)大于m)，則必須對(duì)父結(jié)點(diǎn)進(jìn)行“分裂”，一直進(jìn)行下去，直到?jīng)]有父結(jié)點(diǎn)或分裂后的父結(jié)點(diǎn)滿足m階B_樹的要求。當(dāng)根結(jié)點(diǎn)分裂時(shí)，因沒(méi)有父結(jié)點(diǎn)，則建立一個(gè)新的根，B_樹增高一層。

⑶插入實(shí)例

例：在一個(gè)3階B_樹(2-3樹)上插入結(jié)點(diǎn)，其過(guò)程如下所示。fhmb(a)一棵2-3樹fhmbd(b)插入d后fhmpbd分裂(c)插入p后并進(jìn)行分裂hfmbdphlfmbdp(d)插入l后分裂ghlfmbdp(e)插入g后并進(jìn)行分裂lfhmbdpg分裂圖

在B_樹中進(jìn)行插入的過(guò)程lfhmbdpglbdpghfm(f)繼續(xù)進(jìn)行分裂

4）算法實(shí)現(xiàn)

要實(shí)現(xiàn)插入，首先必須考慮結(jié)點(diǎn)的分裂。設(shè)待分裂的結(jié)點(diǎn)是p，分裂時(shí)先開辟一個(gè)新結(jié)點(diǎn)，依此將結(jié)點(diǎn)p中后半部分的關(guān)鍵字和指針移到新開辟的結(jié)點(diǎn)中。分裂之后，而需要插入到父結(jié)點(diǎn)中的關(guān)鍵字在p的關(guān)鍵字向量的p.keynum+1位置上。

利用m階B_樹的插入操作，可從空樹起，將一組關(guān)鍵字依次插入到m階B_樹中，從而生成一個(gè)m階B_樹。4B_樹的刪除在B_樹上刪除一個(gè)關(guān)鍵字K，首先找到關(guān)鍵字所在的結(jié)點(diǎn)N，然后在N中進(jìn)行關(guān)鍵字K的刪除操作。若N不是葉子結(jié)點(diǎn)，設(shè)K是N中的第i個(gè)關(guān)鍵字，則將指針Ai-1所指子樹中的最大關(guān)鍵字(或最小關(guān)鍵字)K’放在(K)的位置，然后刪除K’，而K’一定在葉子結(jié)點(diǎn)上。如下圖(a)(b)所示，刪除關(guān)鍵字h，用關(guān)鍵字g代替h的位置，然后再?gòu)娜~子結(jié)點(diǎn)中刪除關(guān)鍵字g。

圖

在B_樹中進(jìn)行刪除的過(guò)程刪除qlmbdqeghfplbdpeghfm刪除h(a)刪除elbdpegfmlbpegfm刪除dlpgmbf(b)(c)(d)

從葉子結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字的情況是：⑴若結(jié)點(diǎn)N中的關(guān)鍵字個(gè)數(shù)>

m/2

-1：在結(jié)點(diǎn)中直接刪除關(guān)鍵字K，如圖(b)(c)所示。圖

在B_樹中進(jìn)行刪除的過(guò)程刪除qlmbdqeghfplbdpeghfm刪除h(a)刪除elbdpegfmlbpegfm刪除dlpgmbf(b)(c)(d)從葉子結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字的情況是：⑵若結(jié)點(diǎn)N中的關(guān)鍵字個(gè)數(shù)=

m/2

-1：若結(jié)點(diǎn)N的左(右)兄弟結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)>

m/2

-1，則將結(jié)點(diǎn)N的左(或右)兄弟結(jié)點(diǎn)中的最大(或最小)關(guān)鍵字上移到其父結(jié)點(diǎn)中，而父結(jié)點(diǎn)中大于(或小于)且緊靠上移關(guān)鍵字的關(guān)鍵字下移到結(jié)點(diǎn)N，如圖(a)。圖

在B_樹中進(jìn)行刪除的過(guò)程刪除qlmbdqeghfplbdpeghfm刪除h(a)刪除elbdpegfmlbpegfm刪除dlpgmbf(b)(c)(d)從葉子結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字的情況是：⑶若結(jié)點(diǎn)N和其兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)=

m/2

-1：刪除結(jié)點(diǎn)N中的關(guān)鍵字，再將結(jié)點(diǎn)N中的關(guān)鍵字、指針與其兄弟結(jié)點(diǎn)以及分割二者的父結(jié)點(diǎn)中的某個(gè)關(guān)鍵字Ki，合并為一個(gè)結(jié)點(diǎn)，若因此使父結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)<

m/2

-1

，則依此類推，如圖(d)。圖

在B_樹中進(jìn)行刪除的過(guò)程刪除qlmbdqeghfplbdpeghfm刪除h(a)刪除elbdpegfmlbpegfm刪除dlpgmbf(b)(c)(d)5B+樹

在實(shí)際的文件系統(tǒng)中，基本上不使用B_樹，而是使用B_樹的一種變體，稱為m階B+樹。

它與B_樹的主要不同是葉子結(jié)點(diǎn)中存儲(chǔ)記錄。在B+樹中，所有的非葉子結(jié)點(diǎn)可以看成是索引，而其中的關(guān)鍵字是作為“分界關(guān)鍵字”，用來(lái)界定某一關(guān)鍵字的記錄所在的子樹。一棵m階B+樹與m階B_樹的主要差異是：⑴若一個(gè)結(jié)點(diǎn)有n棵子樹，則必含有n個(gè)關(guān)鍵字；⑵所有葉子結(jié)點(diǎn)中包含了全部記錄的關(guān)鍵字信息以及這些關(guān)鍵字記錄的指針，而且葉子結(jié)點(diǎn)按關(guān)鍵字的大小從小到大順序鏈接；⑶所有的非葉子結(jié)點(diǎn)可以看成是索引的部分，結(jié)點(diǎn)中只含有其子樹的根結(jié)點(diǎn)中的最大(或最小)關(guān)鍵字。如圖是一棵3階B+樹。

圖

一棵3階B+樹35961735587696512176376798496192335414958

與B_樹相比，對(duì)B+樹不僅可以從根結(jié)點(diǎn)開始按關(guān)鍵字隨機(jī)查找，而且可以從最小關(guān)鍵字起，按葉子結(jié)點(diǎn)的鏈接順序進(jìn)行順序查找。在B+樹上進(jìn)行隨機(jī)查找、插入、刪除的過(guò)程基本上和B_樹類似。在B+樹上進(jìn)行隨機(jī)查找時(shí)，若非葉子結(jié)點(diǎn)的關(guān)鍵字等于給定的K值，并不終止，而是繼續(xù)向下直到葉子結(jié)點(diǎn)(只有葉子結(jié)點(diǎn)才存儲(chǔ)記錄)，即無(wú)論查找成功與否，都走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。

B+樹的插入僅僅在葉子結(jié)點(diǎn)上進(jìn)行。當(dāng)葉子結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于m時(shí)，“分裂”為兩個(gè)結(jié)點(diǎn)，兩個(gè)結(jié)點(diǎn)中所含有的關(guān)鍵字個(gè)數(shù)分別是

(m+1)/2

和

(m+1)/2

，且將這兩個(gè)結(jié)點(diǎn)中的最大關(guān)鍵字提升到父結(jié)點(diǎn)中，用來(lái)替代原結(jié)點(diǎn)在父結(jié)點(diǎn)中所對(duì)應(yīng)的關(guān)鍵字。提升后父結(jié)點(diǎn)又可能會(huì)分裂，依次類推。8.6

哈希(散列)查找基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系；這樣，不經(jīng)過(guò)比較，一次存取就能得到所查元素的查找方法。例30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表以編號(hào)作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1，H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的序號(hào)作哈希函數(shù)：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19編號(hào)省、市(區(qū))總?cè)丝跐h族回族…...1北京2上?！?..…...8.6.1基本概念

哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對(duì)應(yīng)關(guān)系叫哈希函數(shù)。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲(chǔ)地址空間的一種映象?？蓪懗桑篴ddr(ai)=H(ki)，其中i是表中一個(gè)元素，addr(ai)是ai的地址，ki是ai的關(guān)鍵字。

哈希表：應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫哈希表。

哈希查找(又叫散列查找)：利用哈希函數(shù)進(jìn)行查找的過(guò)程叫哈希查找。

沖突：對(duì)于不同的關(guān)鍵字ki、kj，若kikj，但H(ki)=H(kj)的現(xiàn)象叫沖突(collision)。

同義詞：具有相同函數(shù)值的兩個(gè)不同的關(guān)鍵字，稱為該哈希函數(shù)的同義詞。哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；當(dāng)沖突發(fā)生時(shí)，應(yīng)該有處理沖突的方法。設(shè)計(jì)一個(gè)散列表應(yīng)包括：①散列表的空間范圍，即確定散列函數(shù)的值域；②構(gòu)造合適的散列函數(shù)，使得對(duì)于所有可能的元素(記錄的關(guān)鍵字)，函數(shù)值均在散列表的地址空間范圍內(nèi)，且出現(xiàn)沖突的可能盡量??；③處理沖突的方法。即當(dāng)沖突出現(xiàn)時(shí)如何解決。8.6.2哈希函數(shù)的構(gòu)造

哈希函數(shù)是一種映象，其設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可。哈希函數(shù)“好壞”的主要評(píng)價(jià)因素有：◆

散列函數(shù)的構(gòu)造簡(jiǎn)單；◆

能“均勻”地將散列表中的關(guān)鍵字映射到地址空間。所謂“均勻”(uniform)是指發(fā)生沖突的可能性盡可能最少。1直接定址法

取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b(a,b為常數(shù))

特點(diǎn)：直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會(huì)發(fā)生沖突，但實(shí)際中很少使用。2數(shù)字分析法對(duì)關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或組合作為哈希地址。適用于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況。例：設(shè)有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)。┇8134653281372242813874228130136781322817813389678136853781419355

分析：只取8

只取1

只取3、4

只取2、7、5

數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位與另兩位的疊加作哈希地址3平方取中法將關(guān)鍵字平方后取中間幾位作為哈希地址。一個(gè)數(shù)平方后中間幾位和數(shù)的每一位都有關(guān)，則由隨機(jī)分布的關(guān)鍵字得到的散列地址也是隨機(jī)的。散列函數(shù)所取的位數(shù)由散列表的長(zhǎng)度決定。這種方法適于不知道全部關(guān)鍵字情況，是一種較為常用的方法。4折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分可以不同)，然后取這幾部分的疊加和作為哈希地址。數(shù)位疊加有移位疊加和間界疊加兩種?！?/p>

移位疊加：將分割后的幾部分低位對(duì)齊相加?！?/p>

間界疊加：從一端到另一端沿分割界來(lái)回折迭，然后對(duì)齊相加。適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況。例：設(shè)關(guān)鍵字為0442205864，哈希地址位數(shù)為4。兩種不同的地址計(jì)算方法如下：586442200410088H(key)=0088移位疊加5864022404

6092H(key)=6092間界疊加5除留余數(shù)法

取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng)m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=keyMODp(pm)

是一種簡(jiǎn)單、常用的哈希函數(shù)構(gòu)造方法。利用這種方法的關(guān)鍵是p的選取，p選的不好，容易產(chǎn)生同義詞。p的選取的分析：◆

選取p=2i(p

m)：運(yùn)算便于用移位來(lái)實(shí)現(xiàn)，但等于將關(guān)鍵字的高位忽略而僅留下低位二進(jìn)制數(shù)。高位不同而低位相同的關(guān)鍵字是同義詞。

◆

選取p=q

f(q、f都是質(zhì)因數(shù)，p

m)：則所有含有q或f因子的關(guān)鍵字的散列地址均是q或f的倍數(shù)。

◆選取p為素?cái)?shù)或p=q

f(q、f是質(zhì)數(shù)且均大于20，p

m)：常用的選取方法，能減少?zèng)_突出現(xiàn)的可能性。6隨機(jī)數(shù)法

取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)當(dāng)散列表中關(guān)鍵字長(zhǎng)度不等時(shí)，該方法比較合適。選取哈希函數(shù)，考慮以下因素◆

計(jì)算哈希函數(shù)所需時(shí)間；◆

關(guān)鍵字的長(zhǎng)度；◆

哈希表長(zhǎng)度（哈希地址范圍）；◆

關(guān)鍵字分布情況；◆

記錄的查找頻率。8.6.3沖突處理的方法沖突處理：當(dāng)出現(xiàn)沖突時(shí)，為沖突元素找到另一個(gè)存儲(chǔ)位置。1開放定址法基本方法：當(dāng)沖突發(fā)生時(shí)，形成某個(gè)探測(cè)序列；按此序列逐個(gè)探測(cè)散列表中的其他地址，直到找到給定的關(guān)鍵字或一個(gè)空地址(開放的地址)為止，將發(fā)生沖突的記錄放到該地址中。散列地址的計(jì)算公式是：Hi(key)=(H(key)+di)MODm，i=1,2,…,k(km-1)其中：H(key)：哈希函數(shù)；m：散列表長(zhǎng)度；di：第i次探測(cè)時(shí)的增量序列；Hi(key)：經(jīng)第i次探測(cè)后得到的散列地址。⑴

線性探測(cè)法

將散列表T[0…m-1]看成循環(huán)向量。當(dāng)發(fā)生沖突時(shí)，從初次發(fā)生沖突的位置依次向后探測(cè)其他的地址。增量序列為：di=1,2,3,…,m-1

設(shè)初次發(fā)生沖突的地址是h，則依次探測(cè)T[h+1]，T[h+2]…，直到T[m-1]時(shí)又循環(huán)到表頭，再次探測(cè)T[0]，T[1]…，直到T[h-1]。探測(cè)過(guò)程終止的情況是：◆

探測(cè)到的地址為空：表中沒(méi)有記錄。若是查找則失??；若是插入則將記錄寫入到該地址；◆

探測(cè)到的地址有給定的關(guān)鍵字：若是查找則成功；若是插入則失??；◆直到T[h]：仍未探測(cè)到空地址或給定的關(guān)鍵字，散列表滿。例1：設(shè)散列表長(zhǎng)為7，記錄關(guān)鍵字組為：15,14,28,26,56,23，散列函數(shù)：H(key)=keyMOD7，沖突處理采用線性探測(cè)法。解：H(15)=15MOD7=1H(14)=14MOD7=0H(28)=28MOD7=0沖突

H1(28)=1又沖突H2(28)=2H(26)=26MOD7=5H(56)=56MOD7=0沖突

H1(56)=1又沖突H2(56)=2又沖突

H3(56)=3H(23)=23MOD7=2沖突

H1(23)=3又沖突H3(23)=4線性探測(cè)法的特點(diǎn)◆

優(yōu)點(diǎn)：只要散列表未滿，總能找到一個(gè)不沖突的散列地址；◆

缺點(diǎn)：每個(gè)產(chǎn)生沖突的記錄被散列到離沖突最近的空地址上，從而又增加了更多的沖突機(jī)會(huì)(這種現(xiàn)象稱為沖突的“聚集”)。⑵二次探測(cè)法增量序列為：di=12,-12,22,-22,32,……±k2(k?m/2?)當(dāng)Hi(key)是負(fù)數(shù)時(shí)，取Hi(key)=Hi(key)+7上述例題若采用二次探測(cè)法進(jìn)行沖突處理，則：H(15)=15MOD7=1H(14)=14MOD7=0

0123456141528

56

2326H(28)=28MOD7=0沖突

H1(28)=1又沖突H2(28)=-1，取H2(28)=-1+7=6H(26)=26MOD7=5H(56)=56MOD7=0沖突

H1(56)=1又沖突H2(56)=6又沖突

H3(56)=4

H(23)=23MOD7=2沖突

H1(23)=3二次探測(cè)法的特點(diǎn)◆

優(yōu)點(diǎn)：探測(cè)序列跳躍式地散列到整個(gè)表中，不易產(chǎn)生沖突的“聚集”現(xiàn)象；◆

缺點(diǎn)：不能保證探測(cè)到散列表的所有地址。141523562628

0123456⑶偽隨機(jī)探測(cè)法增量序列使用一個(gè)偽隨機(jī)函數(shù)來(lái)產(chǎn)生一個(gè)落在閉區(qū)間[1，m-1]的隨機(jī)序列。例2：表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄，散列函數(shù)為H(key)=keyMOD11?，F(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中。(1)H(38)=38M