《數(shù)據(jù)結(jié)構(gòu)JAVA語言版》課件 孫愛香 第8、9章 查找、排序

第8章查找

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

8.1

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

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

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

8.2

靜態(tài)查找

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

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

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

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

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

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

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

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

用Low、High和Mid表示待查找區(qū)間的下界、上界和中間位置指針，初值為Low=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算法示例

查找成功實例

已知11個數(shù)據(jù)元素的有序表（關(guān)鍵字即為數(shù)據(jù)元素的值），如下所示。現(xiàn)查找關(guān)鍵字為21的元素。3.算法實現(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算法分析①查找時每經(jīng)過一次比較，查找范圍就縮小一半，該過程可用一棵二叉樹表示：◆

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

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

㏒2(n+1)

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

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

分塊查找

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

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

先確定待查記錄所在塊，再在塊內(nèi)查找(順序查找)。3算法實現(xiàn)classIndex<T>{publicTmaxkey;/*塊中最大的關(guān)鍵字*/publicintstartpos;/*塊的起始位置指針*/} intBlock_search(SeqList<Integer>sqList,Index<Integer>[]ind,intkey,intn,intb){ /*在分塊索引表中查找關(guān)鍵字為key的數(shù)據(jù)元素*/ /*表長為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è)表長為n個記錄，均分為b塊，每塊記錄數(shù)為s，則b=?n/s?。設(shè)記錄的查找概率相等，每塊的查找概率為1/b，塊中記錄的查找概率為1/s，則平均查找長度ASL：ASL=Lb+Lw=∑j+j=1b∑i=i=1ss―12b+12s+1+8.3

動態(tài)查找

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

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

BST仍然可以用二叉鏈表來存儲，結(jié)點類型定義如下：

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

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

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

插入思想

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

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

1刪除操作過程分析

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

(b)所示。

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

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

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

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

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

平衡二叉樹(AVL)

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

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

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

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

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時，Nh=Fh+2-1，…而這樣，含有n個結(jié)點的平衡二叉排序樹的最大深度為h≈√5㏒φ(

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

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

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

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

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

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

⑶插入后各結(jié)點的平衡因子分析①旋轉(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的右子樹沒有變，而左子樹是b的右子樹，則平衡因子是：HaL-HaR=(HbL-1)-(HbL-1)=0

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

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

即b也是平衡的，以b為根的子樹的深度是HbL+1，與插入前a的子樹的深度相同，則該子樹的上層各結(jié)點的平衡因子沒有變化，即整棵樹旋轉(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é)點a的左孩子的右子樹上進行插入，插入使結(jié)點a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。設(shè)b是a的左孩子，c為b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點。abbLaRcLxcRxc2LR型平衡化旋轉(zhuǎn)⑵插入后結(jié)點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é)點。設(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進行一次逆時針旋轉(zhuǎn)(將以b為根的子樹旋轉(zhuǎn)為以c為根)，再以a進行一次順時針旋轉(zhuǎn)，如圖所示。將整棵子樹旋轉(zhuǎn)為以c為根，b是c的左子樹，a是c的右子樹；c的右子樹移到a的左子樹位置，c的左子樹移到b的右子樹位置。圖LR型平衡化旋轉(zhuǎn)示意圖abbLaRcLxcRxcacbLaRcLxcRxb⑷旋轉(zhuǎn)后各結(jié)點(a,b,c)平衡因子分析

①

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

a的左子樹深度為HcL-1，其右子樹沒有變化，深度是HcL，則a的平衡因子是-1；b的左子樹沒有變化，深度為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é)點a的右孩子的左子樹上進行插入，插入使結(jié)點a失去平衡，與LR型正好對稱。對于結(jié)點a，插入前的平衡因子是-1，插入后a的平衡因子是-2。設(shè)b是a的右孩子，c為b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同樣，c在插入前的平衡因子只能是0，否則，c就是失衡結(jié)點。abbRaLcLxcRxc⑵插入后結(jié)點c的平衡因子的變化分析

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

②插入后c的平衡因子是0：c本身是插入結(jié)點。設(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進行一次順時針旋轉(zhuǎn)，再以a進行一次逆時針旋轉(zhuǎn)，如圖所示。即將整棵子樹(以a為根)旋轉(zhuǎn)為以c為根，a是c的左子樹，b是c的右子樹；c的右子樹移到b的左子樹位置，c的左子樹移到a的右子樹位置。圖RL型平衡化旋轉(zhuǎn)示意圖abbRaLcLxcRxcbcbRaLcLxcRxa⑷旋轉(zhuǎn)后各結(jié)點(a,b,c)的平衡因子分析①

旋轉(zhuǎn)前

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

a的左子樹沒有變化，深度是HcL，右子樹是c旋轉(zhuǎn)前的左子樹，深度為HcL，則a的平衡因子是0；b的右子樹沒有變化，深度為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é)點a的右孩子的右子樹上進行插入，插入使結(jié)點a失去平衡。要進行一次逆時針旋轉(zhuǎn)，和LL型平衡化旋轉(zhuǎn)正好對稱。⑵平衡化旋轉(zhuǎn)方法

設(shè)b是a的右孩子，通過逆時針旋轉(zhuǎn)實現(xiàn)，如圖所示。用b取代a的位置，a作為b的左子樹的根結(jié)點，b原來的左子樹作為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;}

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

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

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

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

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

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

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

263

275

386

…

…

1046關(guān)鍵字…

386

263

1046

…

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

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

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

提供對變長數(shù)據(jù)記錄的便捷訪問；◆

插入或刪除數(shù)據(jù)記錄時不需要移動記錄，但需要對索引表進行維護。缺點：◆

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

對索引表的維護代價較高，涉及到大量索引項的移動，不適合于插入和刪除操作。8.5.2樹形索引表

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

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

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

m/2

棵子樹，至多有m棵子樹；⑶所有葉子結(jié)點都在樹的同一層上；一棵4階的B_樹⑷每個結(jié)點應(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é)點的指針，且Ai-1所指向的子樹中所有結(jié)點的關(guān)鍵字都小于Ki，Ai所指向的子樹中所有結(jié)點的關(guān)鍵字都大于Ki；n是結(jié)點中關(guān)鍵字的個數(shù)，且

m/2

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

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

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

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

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

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

算法實現(xiàn)假設(shè)關(guān)鍵字的類型是整型，算法如下。intBT_search(BTNode<Integer>Tree,intK,BTNode<Integer>p)/*在B_樹中查找關(guān)鍵字K,查找成功返回在結(jié)點中的位置及結(jié)點指針p;否則返回0及最后一個結(jié)點指針*/{//Tree是樹的根結(jié)點，K是要查找的關(guān)鍵字，p用來記錄結(jié)點指針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é)點(查找算法中沒有體現(xiàn))；◆

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

m/2

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

m/2

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

m/2

-1個關(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個關(guān)鍵字的B_樹上進行查找時，從根結(jié)點到待查找記錄關(guān)鍵字的結(jié)點的路徑上所涉及的結(jié)點數(shù)不超過1+㏒

m/2

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

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

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

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

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

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

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

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

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é)點中，以分裂后的兩個結(jié)點作為中間關(guān)鍵字K

m/2

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

m/2

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

⑶插入實例

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

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

4）算法實現(xiàn)

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

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

圖

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

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

m/2

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

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

m/2

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

m/2

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

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

m/2

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

m/2

-1

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

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

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

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

圖

一棵3階B+樹35961735587696512176376798496192335414958

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

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

(m+1)/2

和

(m+1)/2

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

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

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

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

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

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

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

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

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

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

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

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

分析：只取8

只取1

只取3、4

只取2、7、5

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

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

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

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

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

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

選取p=2i(p

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

◆

選取p=q

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

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

◆選取p為素數(shù)或p=q

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

m)：常用的選取方法，能減少沖突出現(xiàn)的可能性。6隨機數(shù)法

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

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

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

哈希表長度（哈希地址范圍）；◆

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

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

線性探測法

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

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

探測到的地址為空：表中沒有記錄。若是查找則失敗；若是插入則將記錄寫入到該地址；◆

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

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

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

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

缺點：不能保證探測到散列表的所有地址。141523562628

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

H1=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突(2)H(38)=38MOD11=5沖突

H1=(5+12)MOD11=6沖突

H2=(5-12)MOD11=4不沖突(3)H(38)=38MOD11=5沖突設(shè)偽隨機數(shù)序列為9，則H1=(5+9)MOD11=3