數(shù)據(jù)結(jié)構(gòu)-第八章

1、 所謂查找查找( (Search)Search)又稱檢索，就是在一個(gè)數(shù)據(jù)元素集合中尋找滿足某種條件的數(shù)據(jù)元素。 查找在計(jì)算機(jī)數(shù)據(jù)處理中是經(jīng)常使用的操作。查找算法的效率高低直接關(guān)系到應(yīng)用系統(tǒng)的性能。 查找的方法很多，本章將介紹一些常用的查找算法，主要有：線性表的查找、樹表的查找和散列表的查找，并對(duì)有關(guān)的算法進(jìn)行性能分析和對(duì)比。 1數(shù)據(jù)表數(shù)據(jù)表：就是指數(shù)據(jù)元素的有限集合。例如，為統(tǒng)計(jì)職工工作業(yè)績(jī)，建立一個(gè)包括：職工編號(hào)、職工姓名、業(yè)績(jī)等信息的表格。這個(gè)表格中的每一個(gè)職工的信息就是一個(gè)數(shù)據(jù)元素。對(duì)此表格可以根據(jù)職工編號(hào)查找職工的業(yè)績(jī)等信息；也可以根據(jù)職工的姓名查找職工的業(yè)績(jī)等信息。2關(guān)鍵字關(guān)鍵字：數(shù)

2、據(jù)表中數(shù)據(jù)元素一般有多個(gè)屬性域（字段），即由多個(gè)數(shù)據(jù)成員組成，其中有一個(gè)屬性域可用來(lái)區(qū)分元素，作為查找或排序的依據(jù)，該域即為關(guān)鍵字。每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為關(guān)鍵字，要視具體的應(yīng)用需要而定。即使是同一個(gè)表，在解決不同問(wèn)題的場(chǎng)合也可能取不同的域做關(guān)鍵字。如果在數(shù)據(jù)表中各個(gè)元素的關(guān)鍵字互不相同，這種關(guān)鍵字即主關(guān)鍵字。3查找查找：查找(Search)是數(shù)據(jù)處理中最常用的一種運(yùn)算。最常見(jiàn)的一種方式是事先給定一個(gè)值，在數(shù)據(jù)表中找到其關(guān)鍵字等于給定值的數(shù)據(jù)元素。查找的結(jié)果通常有兩種可能：一種可能是查找成功查找成功，即找到關(guān)鍵字等于給定值的數(shù)據(jù)元素，這時(shí)作為查找結(jié)果，可報(bào)告該數(shù)據(jù)元素在數(shù)據(jù)表中的位置，還可進(jìn)

3、一步給出該數(shù)據(jù)元素的具體信息，后者在數(shù)據(jù)庫(kù)技術(shù)中叫做檢索；另一種可能是查找不成功查找不成功（查找失?。ú檎沂。?，即數(shù)據(jù)表中找不到其關(guān)鍵字等于給定值的數(shù)據(jù)元素，此時(shí)查找的結(jié)果可給出一個(gè)“空”記錄或“空”指針。4靜態(tài)查找表和動(dòng)態(tài)查找表靜態(tài)查找表和動(dòng)態(tài)查找表：數(shù)據(jù)表的組織有兩種不同方式。其一，數(shù)據(jù)表的結(jié)構(gòu)固定不變，當(dāng)查找失敗時(shí)，作為查找結(jié)果只報(bào)告一些信息，如失敗標(biāo)志、失敗位置等，這類數(shù)據(jù)表稱為靜態(tài)查找表；其二，數(shù)據(jù)表的結(jié)構(gòu)在插入或刪除數(shù)據(jù)元素過(guò)程中會(huì)得到調(diào)整，當(dāng)查找失敗時(shí)，則把給定值的數(shù)據(jù)元素插入到數(shù)據(jù)表中，這類組織方式稱為動(dòng)態(tài)查找表動(dòng)態(tài)查找表。相比較而言，靜態(tài)查找表的結(jié)構(gòu)較為簡(jiǎn)單，操作較為方便

4、，但查找的效率較低，而且需要考慮表的溢出問(wèn)題。5查找的效率查找的效率：查找是經(jīng)常使用的一種運(yùn)算，因此，查找的時(shí)間復(fù)雜度是人們關(guān)心的一個(gè)重要因素。查找的時(shí)間復(fù)雜度一般用平均查找長(zhǎng)度（ASL）來(lái)衡量。平均查找長(zhǎng)度是指在數(shù)據(jù)表中查找各數(shù)據(jù)元素所需進(jìn)行的關(guān)鍵字比較次數(shù)的期望值，其數(shù)學(xué)定義為：n1iiC*iPASL其中，Pi表示待查找數(shù)據(jù)元素在數(shù)據(jù)表中出現(xiàn)的概率，Ci表示查找此數(shù)據(jù)元素所需進(jìn)行關(guān)鍵字的比較次數(shù)。6裝載因子裝載因子：設(shè)數(shù)據(jù)表的長(zhǎng)度為m，表中數(shù)據(jù)元素個(gè)數(shù)為n，則數(shù)據(jù)表的裝載因子=n/m。的查找 采用順序存儲(chǔ)結(jié)構(gòu)的數(shù)據(jù)表稱為順序表。順序表適合作靜態(tài)查找。 順序表查找的基本思想是：設(shè)有n個(gè)數(shù)據(jù)元

5、素的順序表，從表的一端開始，用給定的值依次和表中各數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較，若在表中找到某個(gè)數(shù)據(jù)元素的關(guān)鍵字和給定值相等，則查找成功，給出該數(shù)據(jù)元素在表中的位置；若查遍整個(gè)表，不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素，則查找失敗，給出失敗信息。const int MaxSize=20/數(shù)據(jù)表中元素的最大個(gè)數(shù)template class dataList; /數(shù)據(jù)表類的前視定義template class Node /數(shù)據(jù)表中的結(jié)點(diǎn)類定義friend class dataList;public: Node ( const Type & value ) : key ( value ) /構(gòu)造函數(shù)

6、Type getKey ( ) const return key; /取關(guān)鍵字 void setKey ( Type k ) key = k; /關(guān)鍵字的賦值private: Type key; /關(guān)鍵字 other; /其它信息;template class dataList /數(shù)據(jù)表類的定義public: dataList ( ) : CurrentSize (0), Table (new Node MaxSize) virtual dataList ( ) delete Table; protected: Type *Table; int CurrentSize;template cla

7、ss searchList : public dataList /作為dataList派生類的順序表類的定義public: searchList ( ) : dataList ( ) virtual searchList ( ) virtual int Search ( const Type & k ) const;在順序存儲(chǔ)結(jié)構(gòu)下的順序查找算法如下：template int searchList :Search ( const Type & k ) const /在順序表中查找關(guān)鍵字為k的數(shù)據(jù)元素 int i = CurrentSize; Table0.setKey ( k

8、); /在0號(hào)位置設(shè)置監(jiān)視哨 while (Tablei.getKey ( ) != k ) i -; return i; 在等概率情形下查找成功的平均查找長(zhǎng)度為：n1i21i*n1n1iiC*iPASLn查找失敗的平均查找長(zhǎng)度為n+1。 有序表的折半查找 對(duì)有序表通常可用折半查找的方法來(lái)進(jìn)行查找。設(shè)有n個(gè)數(shù)據(jù)元素按其關(guān)鍵字從小到大的順序存放在一個(gè)順序表中（開始時(shí)，查找區(qū)間的下限low=0，上限hight=n-1），折半查找的算法思想為：（1）如果查找區(qū)間長(zhǎng)度小于1（lowhight），則表示查找失敗，返回-1；否則繼續(xù)以下步驟。（2）求出查找區(qū)間中間位置的數(shù)據(jù)元素下標(biāo)mid（mid=（low

9、+hight）/2）；（ 3 ） 區(qū) 間 中 間 位 置 的 數(shù) 據(jù) 元 素 的 關(guān) 鍵 字Tablemid.getKey()與給定值x進(jìn)行比較，比較的結(jié)果有三種可能：1）若Tablemid.getKey()x，則查找成功，報(bào)告成功信息并返回其下標(biāo)mid；2）若Tablemid.getKey()x，則說(shuō)明如果數(shù)據(jù)表中存在要找的數(shù)據(jù)元素，該數(shù)據(jù)元素一定在mid的左側(cè)。可把查找區(qū)間縮小到數(shù)據(jù)表的前半部分（hight=mid-1），再繼續(xù)進(jìn)行折半查找（轉(zhuǎn)步驟1）。設(shè)有序表為8，11，23，34，46，68，71，86，下圖(a)給出了查找關(guān)鍵字為23的數(shù)據(jù)元素時(shí)的查找過(guò)程，找到所查數(shù)據(jù)元素一共做了3

10、次關(guān)鍵字比較。圖(b)給出了查找關(guān)鍵字為52的數(shù)據(jù)元素時(shí)的查找過(guò)程，直到確認(rèn)查找失敗也執(zhí)行了3次關(guān)鍵字比較。折半查找的算法可以用遞歸的形式和迭代的形式實(shí)現(xiàn)：template class orderedList : public dataList /作為dataList派生類的有序表類的定義public: orderedList ( ) : dataList ( ) virtual orderedList ( ) virtual int BinarySearch ( const Type & k, const int low, const int high ) const ; /折半查找

11、的遞歸算法 virtual int BinarySearch ( const Type & k ) const ; /折半查找的迭代算法 ;template int orderedList :BinarySearch ( const Type & k, const int low, const int high ) const /折半查找的遞歸算法 int mid ; if ( low high ) mid = -1; else mid = ( low + high ) / 2; if ( Tablemid.getKey( ) x ) mid = BinarySearch (

12、x, low, mid -1 ); return mid;template in orderedList : BinarySearch ( const Type & x ) const /折半查找的迭代算法 int high = CurrentSize-1, low = 0, mid; while ( low = high ) mid = ( low + high ) / 2; if ( Tablemid.getKey ( ) x ) high = mid - 1; else return mid; return -1;在二叉查找樹上，每個(gè)結(jié)點(diǎn)表示有序表中的一個(gè)數(shù)據(jù)元素。設(shè)二叉查找樹有

13、n個(gè)結(jié)點(diǎn)，可用如下的方法來(lái)構(gòu)造它：（1）當(dāng)n=0時(shí)，二叉查找樹為空樹；（2）當(dāng)n0時(shí)，二叉查找樹的根結(jié)點(diǎn)是有序表中序號(hào)為mid為(n-1)2的數(shù)據(jù)元素，根結(jié)點(diǎn)的左子樹是與有序表Table0Tablemid-1相對(duì)應(yīng)的二叉查找樹，根結(jié)點(diǎn)的右子樹是與有序表Tablemid+1Tablen-1相對(duì)應(yīng)的二叉查找樹。 對(duì)上面的二叉查找樹進(jìn)行擴(kuò)充，讓樹中所有結(jié)點(diǎn)的空指針都指向一個(gè)外部結(jié)點(diǎn)（用方框表示，相應(yīng)原來(lái)的數(shù)據(jù)元素結(jié)點(diǎn)稱為內(nèi)結(jié)點(diǎn)），它們代表了那些進(jìn)行關(guān)鍵字比較不成功的結(jié)點(diǎn)。在此稱這樣的二叉查找樹為擴(kuò)充二叉樹。 若設(shè)n2h-1，則描述折半查找的擴(kuò)充二叉樹是高度為h的滿二叉樹，hlog2(n十1)。第1層

14、結(jié)點(diǎn)有1個(gè)，查找第1層結(jié)點(diǎn)要比較1次；第2層結(jié)點(diǎn)有2個(gè)，查找第2層結(jié)點(diǎn)要比較2次；，第i(1ih)層結(jié)點(diǎn)有2i-1個(gè)，查找第i層結(jié)點(diǎn)要比較i次，。假定每個(gè)結(jié)點(diǎn)的查找概率相等，即Piln，則查找成功的平均查找長(zhǎng)度為: ninihiiinhnCnCPASL1121) 1(log)2*.4*32*21*1 (1*1*對(duì) 于 有 序 表 ， 除 了 折 半 查 找 外 還 可 以 有 斐 波 那 契（fibonacii）查找和插值查找。斐波那契查找也是基于有序表的逐步縮小查找區(qū)間的查找方法。該方法的查找區(qū)間端點(diǎn)和中間點(diǎn)都與斐波那契數(shù)列有關(guān)。斐波那契數(shù)列的定義為：1，1，2，3，5，8，13，。即f(1

15、)=1，f(2)=1，f(i)=f(i-1)+f(i-2)（當(dāng)i2時(shí)）。若有一個(gè)具有n個(gè)數(shù)據(jù)元素的有序表，nf(k)-1，即比某個(gè)斐波那契數(shù)少1。斐波那契查找的算法思想為（開始時(shí)，查找區(qū)間的下限low=0，上限hight=n-1）：（1）如果查找區(qū)間長(zhǎng)度小于1（lowhight），則表示查找失敗，返回-1；否則繼續(xù)以下步驟。（2）求出查找區(qū)間中間位置的數(shù)據(jù)元素下標(biāo)midf(k-1)-1。；（ 3 ） 區(qū) 間 中 間 位 置 的 數(shù) 據(jù) 元 素 的 關(guān) 鍵 字Tablemid.getKey()與給定值x進(jìn)行比較，比較的結(jié)果有三種可能：1）若Tablemid.getKey()x，則查找成功，報(bào)告成

16、功信息并返回其下標(biāo)mid；2）若Tablemid.getKey()x，則說(shuō)明如果數(shù)據(jù)表中存在要找的數(shù)據(jù)元素，該數(shù)據(jù)元素一定在mid的左側(cè)?？砂巡檎覅^(qū)間縮小到數(shù)據(jù)表的前半部分，得到的子表的長(zhǎng)度正好為f(k-1)-1，再繼續(xù)進(jìn)行折半查找（轉(zhuǎn)步驟1）。 插值查找的算法思想同折半查找類似，其求中間點(diǎn)的公式為： ) 1().().().1lowhighgetKeylowTablegetKeyhighTablegetKeylowTableklowmid 其中，k為給定值，Tablelow和Tablehigh分別為查找區(qū)間中具有最小關(guān)鍵字和最大關(guān)鍵字的數(shù)據(jù)元素，它們分別在查找區(qū)間的兩端。插值查找的查找方法類

17、似于折半查找，它的查找性能在關(guān)鍵字分布比較均勻的情況下優(yōu)于折半查找。 索引順序表一般由主表和索引表兩個(gè)部分組成，兩者均采用順序存儲(chǔ)結(jié)構(gòu)。主表中存放數(shù)據(jù)元素的全部信息，索引表中存放數(shù)據(jù)元素的主關(guān)鍵字和索引信息。一個(gè)學(xué)生信息的數(shù)據(jù)表如下圖所示 ：對(duì)二級(jí)索引結(jié)構(gòu)進(jìn)行查找時(shí)，一般分為二次查找。先在二級(jí)索引表中按給定值k進(jìn)行查找，以確定待查子表的序號(hào)i，然后再在第i個(gè)子表中按給定值查找關(guān)鍵字等于k的索引項(xiàng)。如果找到關(guān)鍵字等于k的索引項(xiàng)，則可以根據(jù)索引項(xiàng)內(nèi)的地址直接從外存中讀取相應(yīng)的數(shù)據(jù)元素；否則，表示查找失敗。二級(jí)索引查找成功時(shí)的平均查找長(zhǎng)度：ASLIndexSeq=ASLIndex + ASLSubL

18、ist其中，ASLIndex 是在二級(jí)索引表中查找成功的平均查找長(zhǎng)度，ASLSubList 是在子表內(nèi)查找成功的平均查找長(zhǎng)度。設(shè)完全索引表的長(zhǎng)度為n ，分成均等的m個(gè)子表，每個(gè)子表k個(gè)對(duì)象，則m=n/k 。在等概率的情況下，每個(gè)子表的查找概率為1/m，子表內(nèi)各對(duì)象的查找概率為1/k。若二級(jí)索引表和子表都用順序查找，則二級(jí)索引查找成功時(shí)的平均查找長(zhǎng)度為：ASLIndexSeq =(m+1)/2+(k+1)/2=(m+k)/2+1=(n/k+k)/2+1=(n+k2)/(2k)+1若對(duì)二級(jí)索引表采用折半查找；對(duì)子表都用順序查找，則二級(jí)索引查找成功時(shí)的平均查找長(zhǎng)度為：ASLIndexSeq=ASLI

19、ndex +ASLSubListlog2(m+1)-1+(k+1)/2log2(1+n/k)+k/2 有時(shí)除主關(guān)鍵字外，可以把一些在查找時(shí)經(jīng)常用到的屬性設(shè)定為次關(guān)鍵字，并以每一個(gè)屬性作為次關(guān)鍵字建立次索引表，并稱為倒排索引表。 倒排索引表有鏈?zhǔn)胶蛦卧絻煞N結(jié)構(gòu)。在鏈?zhǔn)降古潘饕碇校谐隽俗鳛榇侮P(guān)鍵字屬性的所有取值，并對(duì)每一個(gè)取值建立有序鏈表，把所有具有相同屬性值的主關(guān)鍵字按其遞增的順序或按其在主索引表中的存儲(chǔ)地址遞增的順序鏈接在一起。因此，鏈?zhǔn)降古潘饕戆ㄈ齻€(gè)部分：次關(guān)鍵字、鏈表長(zhǎng)度和有序鏈表。 在單元式倒排索引表的各個(gè)索引項(xiàng)中存放表示各外存區(qū)域是否存有相應(yīng)數(shù)據(jù)元素的標(biāo)識(shí)（以0或1表示）。于

20、是，整個(gè)單元式倒排索引表將形成一個(gè)(二進(jìn)制數(shù)的)位矩陣。 若要查找上海籍通信專業(yè)的男生，可以對(duì)“男性”、“上海”、“通信”三個(gè)二進(jìn)制位串進(jìn)行按位“與”運(yùn)算，就可求得所查數(shù)據(jù)元素在外存區(qū)域的區(qū)號(hào)。 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 0 AND 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0根據(jù)上述運(yùn)算結(jié)果可以知道：上海籍通信專業(yè)男生的數(shù)據(jù)元素在0號(hào)、3號(hào)等外存區(qū)域，此時(shí)可以把相應(yīng)外存區(qū)域的數(shù)據(jù)元素讀入內(nèi)存再進(jìn)行查找就可以得到所需要的結(jié)果。 二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）左子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵字都小于根結(jié)點(diǎn)的關(guān)鍵字

21、。（ 2）右子樹(如果存在)上所有結(jié)點(diǎn)的關(guān)鍵字都大于根結(jié)點(diǎn)的關(guān)鍵字。（3）左子樹和右子樹也是二叉排序樹。ADT BSTree isData 二叉排序樹的根結(jié)點(diǎn)指針Operation BSTree 初始化值：無(wú) 動(dòng)作：構(gòu)造空二叉排序樹find 輸入： 給定的一個(gè)關(guān)鍵字k 前置條件：無(wú) 動(dòng)作： 在二叉排序樹中查找關(guān)鍵字為k的結(jié)點(diǎn) 輸出： 查找成功返回結(jié)點(diǎn)的指針；否則返回空指針 后置條件：無(wú)insert 輸入： 數(shù)據(jù)元素x 前置條件：無(wú) 動(dòng)作： 在二叉排序樹中插入數(shù)據(jù)元素x的結(jié)點(diǎn) 輸出：無(wú) 后置條件：無(wú)delete 輸入：給定關(guān)鍵字k 前置條件：無(wú) 動(dòng)作： 在二叉排序樹中刪除關(guān)鍵字為k的結(jié)點(diǎn) 輸出：

22、無(wú) 后置條件：無(wú)Min 輸入：無(wú) 前置條件：無(wú) 動(dòng)作： 給出二叉排序樹中關(guān)鍵字值最小的數(shù)據(jù)元素 輸出：數(shù)據(jù)元素 后置條件：無(wú)Max 輸入：無(wú) 前置條件：無(wú) 動(dòng)作： 給出二叉排序樹中關(guān)鍵字值最大的數(shù)據(jù)元素 輸出：數(shù)據(jù)元素 后置條件：無(wú)end ADT BSTree#include template class BSTree; /二叉排序樹類的前視定義template class BSTreeNode : public BinTreeNode /二叉排序樹結(jié)點(diǎn)類的定義friend class BSTree ;public: BstNode ( ) : leftChild (NULL), rightC

23、hild (NULL) /構(gòu)造函數(shù) BstNode (const Type d) : data (d),leftChild (NULL), rightChild (NULL) /構(gòu)造函數(shù) BstNode ( ) /析構(gòu)函數(shù)protected: Type data ;/數(shù)據(jù)域（在此為關(guān)鍵字） BSTreeNode *leftChild, *rightChild; ;template class BSTree : public : BinaryTree /二叉排序樹的類定義public: BSTree ( ) : root (NULL) /構(gòu)造函數(shù) BSTree ( ); /析構(gòu)函數(shù) int Fi

24、nd ( const Type & k ) const return Find ( k, root ) != NULL; /查找 Type Min ( ) ; /求最小 Type Max ( ) ; /求最大 void Insert ( const Type & x ) Insert ( x, root ); void Delete ( const Type & k ) Delete ( k, root ); private: BSTreeNode *root; /二叉排序樹的根指針 BSTreeNode *Find (const Type & k,BSTree

25、Node*ptr ) const; void Insert ( const Type & x, BSTreeNode *& p ); void Delete ( const Type & k, BSTreeNode *& p ); 二 叉排序樹的查找算法可以用遞歸和迭代兩種方法實(shí)現(xiàn)。template BSTreeNode * BSTree :Find (const Type & k, BSTreeNode * p ) const/在p為根的二叉排序樹上進(jìn)行查找的遞歸算法 if ( p = NULL ) return NULL; /查找失敗 else if

26、 ( k ptrdata ) /在右子樹上遞歸查找 return Find ( k, prightChild ); else return p; /相等,查找成功template BSTreeNode * BSTree :Find(const Type & k, BSTreeNode* p)const /在p為根的二叉排序樹上進(jìn)行查找的迭代算法 BSTreeNode * temp = p; if ( p != NULL ) while ( temp != NULL ) if ( tempdata = k ) return temp; /查找成功 if ( tempdata k ) te

27、mp = temprightChild; /查找右子樹 else temp = templeftChild; /查找左子樹 return temp; /查找失敗 為了向二叉排序樹中插入一個(gè)新元素，必須先檢查這個(gè)元素在二叉排序樹中是否已經(jīng)存在。 因此，在插入之前，首先在二叉排序樹中檢查待插入的數(shù)據(jù)元素，如果查找成功，說(shuō)明樹中已經(jīng)存在這個(gè)數(shù)據(jù)元素，則不再插入； 如果查找不成功，說(shuō)明樹中不存在關(guān)鍵字等于給定值的數(shù)據(jù)元素，把新元素插到查找操作失敗的地方。在二叉排序樹中插入一個(gè)新元素的算法描述在二叉排序樹中插入一個(gè)新元素的算法描述: :template void BSTree:Insert (const

28、 Type & x, BSTreeNode * & p) /在p為根的二叉排序樹插入結(jié)點(diǎn)的遞歸算法 if ( p = NULL ) /空二叉樹 p = new BSTreeNode (x); /創(chuàng)建數(shù)據(jù)元素x的結(jié)點(diǎn) else if ( x ptrdata ) /在右子樹插入 Insert ( x, prightChild ); else /結(jié)點(diǎn)x已存在 cout There has node x endl; exit (1); 利用二叉排序樹的插入算法，建立二叉排序樹示例。 關(guān)鍵字的輸入序列39、11、68、46、75、23、71、8、86、34 對(duì)于同樣一組數(shù)據(jù)元素，由于輸入

29、順序不同，建立起來(lái)的二叉排序樹的形態(tài)也不同。例如，有3個(gè)數(shù)據(jù)元素39、11、68，圖8-11中的二叉排序樹(a)、(b)、(c)、(d)、(e)分別是由輸入序列：68、11、39、68、39、11、39、11、68、11、68、39、11、39、68得到的。 在二叉排序樹中刪除一個(gè)數(shù)據(jù)元素時(shí)，必須將因刪除元素而斷開的二叉鏈表重新鏈接起來(lái)，同時(shí)確保不會(huì)失去二叉排序樹的性質(zhì)。 此外，為了保證在執(zhí)行刪除后二叉排序樹的查找性能不至于降低，還需要做到重新鏈接后二叉排序樹的高度不能增加。 在二叉排序樹中刪除一個(gè)數(shù)據(jù)元素的算法思想如下：如果被刪除的數(shù)據(jù)元素是葉子，則只需將其雙親指向它的指針置空，再釋放該數(shù)據(jù)

30、元素的存儲(chǔ)空間即可； 如果被刪除的數(shù)據(jù)元素只有左子樹而沒(méi)有右子樹，則可以拿它的左孩子頂替它的位置，再釋放該數(shù)據(jù)元素的存儲(chǔ)空間即可； 如果被刪除的數(shù)據(jù)元素只有右子樹而沒(méi)有左子樹，可以拿它的右孩子頂替它的位置，再釋放該數(shù)據(jù)元素的存儲(chǔ)空間即可； 如果被刪除的數(shù)據(jù)元素左、右子樹都存在，則有兩種處理方法： 其一，可以在它的右子樹中尋找關(guān)鍵字值最小的數(shù)據(jù)元素（中序遍歷中第一個(gè)被訪問(wèn)的數(shù)據(jù)元素）x，用x的值代替被刪除數(shù)據(jù)元素的值，再來(lái)刪除數(shù)據(jù)元素x（x沒(méi)有左子樹）； 其二，可以在它的左子樹中尋找關(guān)鍵字值最大的數(shù)據(jù)元素（中序遍歷中最后一個(gè)被訪問(wèn)的數(shù)據(jù)元素）x，用x的值代替被刪除數(shù)據(jù)元素的值，再來(lái)刪除數(shù)據(jù)元素x

31、（x沒(méi)有右子樹）。 template void BSTree :Delete (const Type &k, BSTree Node * &p) /在p為根的二叉排序樹上刪除關(guān)鍵字為k的結(jié)點(diǎn) BSTree Node * temp; if ( p != NULL ) if ( k pdata ) Delete ( k, prightChild ); else if ( pleftChild != NULL & prightChild != NULL ) temp = Min ( prightChild ); pdata = tempdata; Delete ( pdata

32、, temp ); else temp = p; if ( pleftChild = NULL ) p = prightChild; else if ( prightChild = NULL ) p = pleftChild; delete temp; 在二叉排序樹上的查找過(guò)程實(shí)在二叉排序樹上的查找過(guò)程實(shí)際上是走了一條從根到所查結(jié)點(diǎn)的際上是走了一條從根到所查結(jié)點(diǎn)的路徑，所需的比較次數(shù)為該結(jié)點(diǎn)所路徑，所需的比較次數(shù)為該結(jié)點(diǎn)所在的層次數(shù)。因此，查找成功時(shí)，在的層次數(shù)。因此，查找成功時(shí)，關(guān)鍵字的比較次數(shù)不超過(guò)樹的高度。關(guān)鍵字的比較次數(shù)不超過(guò)樹的高度。但是含有但是含有n個(gè)結(jié)點(diǎn)的二叉排序樹不個(gè)結(jié)點(diǎn)的二叉

33、排序樹不是唯一的，從而樹的高度就不一定是唯一的，從而樹的高度就不一定相同。相同。 顯然，當(dāng)二叉排序樹是完全二叉樹時(shí)，其平均查找性能最佳為log2n，與有序表的折半查找相同。當(dāng)二叉排序樹退化為一棵單支樹時(shí)，二叉排序樹的平均查找性能最差為：（n+1）/2，與順序表的平均查找長(zhǎng)度相同。 一棵平衡二叉樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對(duì)值不超過(guò)1。 結(jié)點(diǎn)右子樹的高度減去左子樹的高度所結(jié)點(diǎn)右子樹的高度減去左子樹的高度所得的高度差，稱為該結(jié)點(diǎn)的平衡因子。根據(jù)得的高度差，稱為該結(jié)點(diǎn)的平衡因子。根據(jù)平衡二叉樹的定義，任一結(jié)點(diǎn)的平衡因子

34、只平衡二叉樹的定義，任一結(jié)點(diǎn)的平衡因子只能取能取-1-1、0 0和和1 1。如果一個(gè)結(jié)點(diǎn)的平衡因子的。如果一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于絕對(duì)值大于1 1，則這棵二叉排序樹就失去了平，則這棵二叉排序樹就失去了平衡，就不是平衡二叉樹了。衡，就不是平衡二叉樹了。 高度平衡的二叉排序樹和高度平衡不二叉排序樹示例 ： 一棵具有n個(gè)結(jié)點(diǎn)的平衡二叉樹，其平均查找長(zhǎng)度為O(log2n）。 假定向平衡樹中插入一個(gè)新結(jié)點(diǎn)后破壞了它的平衡性，首先需要找到插入新結(jié)點(diǎn)后失去平衡的最小子樹的根結(jié)點(diǎn)，然后對(duì)它進(jìn)行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。 設(shè)失去平衡的最小子樹的根為A，則平衡調(diào)整可有以下四種情況： 1LL平衡旋轉(zhuǎn)平

35、衡旋轉(zhuǎn) 如果是因?yàn)樵贏的左孩子B的左子樹上插入新結(jié)點(diǎn)，使A的平衡因子由-1變成-2，則需要進(jìn)行LL平衡旋轉(zhuǎn)。 2RR平衡旋轉(zhuǎn) 如果是因?yàn)樵贏的右孩子B的右子樹上插入新結(jié)點(diǎn)，使A的平衡因子由1變成2，則需要進(jìn)行RR平衡旋轉(zhuǎn)。 3LR平衡旋轉(zhuǎn) 如果是因?yàn)樵贏的左孩子B的右子樹上插入新結(jié)點(diǎn)，使A的平衡因子由-1變成-2，則需要進(jìn)行LR平衡旋轉(zhuǎn)。4 4RL平衡旋轉(zhuǎn) 如果是因?yàn)樵贏的右孩子B的左子樹上插入新結(jié)點(diǎn)，使A的平衡因子由1變成2，則需要進(jìn)行RL平衡旋轉(zhuǎn)。 平衡二叉樹插入結(jié)點(diǎn)的算法思想如下：平衡二叉樹插入結(jié)點(diǎn)的算法思想如下：（1）按二叉排序樹的性質(zhì)插入結(jié)點(diǎn)。（2）如果插入結(jié)點(diǎn)之后出現(xiàn)不平衡的結(jié)點(diǎn)，

36、則繼續(xù)步驟（3）；否則插入完成。（3）找到失去平衡的最小子樹。（4）判斷平衡旋轉(zhuǎn)的類型作相應(yīng)平衡化處理。在此算法中，有以下三個(gè)關(guān)鍵問(wèn)題：在此算法中，有以下三個(gè)關(guān)鍵問(wèn)題： 其一、如何發(fā)現(xiàn)插入后出現(xiàn)不平衡的結(jié)點(diǎn)呢？ 其二、如何確定失去平衡的最小子樹呢？ 其三、又如何判斷平衡旋轉(zhuǎn)的類型呢？ 由平衡二叉樹的定義可知，在插入之后由平衡二叉樹的定義可知，在插入之后如果樹上出現(xiàn)平衡因子絕對(duì)值大于如果樹上出現(xiàn)平衡因子絕對(duì)值大于1 1的結(jié)點(diǎn)，的結(jié)點(diǎn)，則說(shuō)明二叉排序樹已不平衡。這時(shí)失去平衡則說(shuō)明二叉排序樹已不平衡。這時(shí)失去平衡的最小子樹的根結(jié)點(diǎn)必為離插入結(jié)點(diǎn)最近，的最小子樹的根結(jié)點(diǎn)必為離插入結(jié)點(diǎn)最近，而且插入之前

37、平衡因子絕對(duì)值為而且插入之前平衡因子絕對(duì)值為1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 要解決上述三個(gè)問(wèn)題可以如下處理：（1 1）在查找結(jié)點(diǎn)）在查找結(jié)點(diǎn)x x的插入位置的過(guò)程中，記下從根結(jié)的插入位置的過(guò)程中，記下從根結(jié)點(diǎn)到插入位置的路徑上離插入位置最近的且平衡因子點(diǎn)到插入位置的路徑上離插入位置最近的且平衡因子絕對(duì)值為絕對(duì)值為1 1的結(jié)點(diǎn)，并令指針的結(jié)點(diǎn)，并令指針a a指向該結(jié)點(diǎn)；如果此路指向該結(jié)點(diǎn)；如果此路徑上不存在平衡因子絕對(duì)值為徑上不存在平衡因子絕對(duì)值為1 1的結(jié)點(diǎn)，則指針的結(jié)點(diǎn)，則指針a a指向指向根結(jié)點(diǎn)。根結(jié)點(diǎn)。（2 2）對(duì)于從）對(duì)于從a a結(jié)點(diǎn)到結(jié)點(diǎn)到x x結(jié)點(diǎn)的路徑上的每一個(gè)結(jié)點(diǎn)結(jié)點(diǎn)的路徑上的每一個(gè)結(jié)

38、點(diǎn)（不包括結(jié)點(diǎn)（不包括結(jié)點(diǎn)x x），根據(jù)結(jié)點(diǎn)中關(guān)鍵字和），根據(jù)結(jié)點(diǎn)中關(guān)鍵字和x x的大小比較的大小比較修改結(jié)點(diǎn)的平衡因子。如果結(jié)點(diǎn)關(guān)鍵字大于修改結(jié)點(diǎn)的平衡因子。如果結(jié)點(diǎn)關(guān)鍵字大于x x，則結(jié)，則結(jié)點(diǎn)平衡因子減點(diǎn)平衡因子減1 1；否則結(jié)點(diǎn)平衡因子加；否則結(jié)點(diǎn)平衡因子加1 1。（3 3）如果結(jié)點(diǎn)）如果結(jié)點(diǎn)a a的平衡因子絕對(duì)值為的平衡因子絕對(duì)值為2 2，則表示二叉，則表示二叉排序樹失去平衡，再根據(jù)結(jié)點(diǎn)排序樹失去平衡，再根據(jù)結(jié)點(diǎn)a a及其左右孩子的平衡及其左右孩子的平衡因子值來(lái)確定平衡旋轉(zhuǎn)的類型。因子值來(lái)確定平衡旋轉(zhuǎn)的類型。從空樹開始，不斷地用上述算法插入結(jié)點(diǎn)就可建立平衡二叉樹。例如，輸入 關(guān) 鍵

39、字 序 列 為11、39、23、68、85、8、3、46、27、50，右圖給出了從空樹開始按此順序插入結(jié)點(diǎn)并進(jìn)行調(diào)整的過(guò)程。在平衡二叉樹上進(jìn)行刪除操作時(shí)，同樣也需要考慮平衡化旋轉(zhuǎn)問(wèn)題。刪除算法的思想如下：（1）如果被刪結(jié)點(diǎn)x有左、右孩子，首先查找x在中序次序下的直接前驅(qū)y(同樣也可以找直接后繼)，再把結(jié)點(diǎn)y的內(nèi)容傳送給結(jié)點(diǎn)x，再刪除結(jié)點(diǎn)y（結(jié)點(diǎn)y最多有一個(gè)孩子）。（2）對(duì)于刪除最多有一個(gè)孩子的結(jié)點(diǎn)x，可以簡(jiǎn)單地把x的雙親結(jié)點(diǎn)中原來(lái)指向x的指針改指到x的孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)x沒(méi)有孩子，則其雙親結(jié)點(diǎn)的相應(yīng)指針置為空。（3）對(duì)于從結(jié)點(diǎn)x的雙親到根結(jié)點(diǎn)的路徑上的每一個(gè)結(jié)點(diǎn)P，當(dāng)布爾變量shorter的值

40、為true時(shí)，根據(jù)以下三種不同的情況繼續(xù)步驟，直到布爾變量shorter的值為false時(shí)，整個(gè)刪除算法結(jié)束。（4 4）情況一，當(dāng)結(jié)點(diǎn)）情況一，當(dāng)結(jié)點(diǎn)p p的平衡因子為的平衡因子為0 0，如，如果它的左子樹或右子樹果它的左子樹或右子樹被縮短（被縮短（shortershorter的值的值為為truetrue），則它的平），則它的平衡因子改為衡因子改為1 1或或-1-1，由，由于此時(shí)以結(jié)點(diǎn)于此時(shí)以結(jié)點(diǎn)p p為根的為根的子樹高度沒(méi)有縮短，所子樹高度沒(méi)有縮短，所以置以置shortershorter的值為的值為falsefalse。（5 5）情況二，結(jié)點(diǎn)）情況二，結(jié)點(diǎn)p p的平衡因子不為的平衡因子不為0

41、 0，且其較高的子樹被且其較高的子樹被縮短，則縮短，則P P的平衡因的平衡因子改為子改為0 0。由于此時(shí)。由于此時(shí)以結(jié)點(diǎn)以結(jié)點(diǎn)p p為根的子樹為根的子樹高度被縮短，所以高度被縮短，所以shortershorter的值仍為的值仍為truetrue。（6）情況三，結(jié)點(diǎn)p的平衡因子不為0，且較矮的子樹又被縮短，則在結(jié)點(diǎn)p發(fā)生不平衡。此時(shí)，將進(jìn)行平衡化旋轉(zhuǎn)來(lái)恢復(fù)平衡。令結(jié)點(diǎn)P的較高子樹的根結(jié)點(diǎn)為q，則根據(jù)結(jié)點(diǎn)p和q的平衡因子值，有如下三種平衡化操作。1 1）如果）如果q q的平衡因子的平衡因子為為0 0，則只要執(zhí)行一，則只要執(zhí)行一個(gè)單旋轉(zhuǎn)就可恢復(fù)結(jié)個(gè)單旋轉(zhuǎn)就可恢復(fù)結(jié)點(diǎn)點(diǎn)p p的平衡，由于旋的平衡，由于

42、旋轉(zhuǎn)后被處理子樹的高轉(zhuǎn)后被處理子樹的高度沒(méi)有縮短，所以置度沒(méi)有縮短，所以置shortershorter的值為的值為falsefalse。2）如果q的平衡因子與p的平衡因子相同，則只要執(zhí)行一個(gè)單旋轉(zhuǎn)就可恢復(fù)結(jié)點(diǎn)p的平衡。由于此時(shí)被處理子樹的高度被縮短，所以shorter的值仍為true。最后，結(jié)點(diǎn)p和q的平衡因子均改為0。 3）如果p與q的平衡因子的符號(hào)相反，則需要執(zhí)行一個(gè)雙旋轉(zhuǎn)來(lái)恢復(fù)平衡，先圍繞q轉(zhuǎn)、再圍繞p轉(zhuǎn)。由于此時(shí)被處理子樹的高度被縮短，所以shorter的值仍為true，新的根結(jié)點(diǎn)的平衡因子置為0，其它結(jié)點(diǎn)的平衡因子作相應(yīng)處理。 二叉排序樹比較適合于在內(nèi)存中組織較小的索引。對(duì)于存放在外

43、存中的較大的文件系統(tǒng)，用二叉排序樹來(lái)組織索引就不太合適了。若以結(jié)點(diǎn)作為內(nèi)外存交換的單位，則在查找過(guò)程中需對(duì)外存進(jìn)行l(wèi)og2n次訪問(wèn)，顯然很費(fèi)時(shí)。因此在文件檢索系統(tǒng)中大量使用的是用B樹或B+樹做文件索引。 一棵m路查找樹，它或者是一棵空樹，或者是滿足如下性質(zhì)的樹：（1）根結(jié)點(diǎn)最多有m棵子樹，并具有如下的結(jié)構(gòu)：（n、p0、k1、p1、k2、p2、kn、pn）其中，Pi是指向子樹的指針，Ki是數(shù)據(jù)元素的關(guān)鍵字；1inm。（2）KiKi+1，1in。（3）在Pi所指的子樹中所有的數(shù)據(jù)元素的關(guān)鍵字都小于K i+1，且大于K i，0in。（4）在Pn所指的子樹中所有數(shù)據(jù)元素的關(guān)鍵字都大于kn，而子樹P0中

44、的所有數(shù)據(jù)元素的關(guān)鍵字都小于K1。（5）Pi所指的子樹也是m路查找樹，0in。 對(duì)于一棵m路查找樹，適當(dāng)提高查找樹的路數(shù)m，可以改善m路查找樹的查找性能。如果查找樹是平衡的，可以使m路查找樹的查找性能接近最佳。下面將討論B樹就一種平衡的m路查找樹。 B樹 一棵m階B樹是一棵平衡的m路查找樹，它具有如下的特性：（1）根結(jié)點(diǎn)至少有兩個(gè)孩子。（2）除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)(不包括失敗結(jié)點(diǎn))至少有m/2個(gè)孩子。 （3）所有的失敗結(jié)點(diǎn)都位于同一層。事實(shí)上，這些結(jié)點(diǎn)都是作為外部結(jié)點(diǎn)存在，不是B樹上的結(jié)點(diǎn)，可以視為查找失敗時(shí)才能到達(dá)的結(jié)點(diǎn)，指向它們的指針都為空值。 在上圖所示的B樹中查找關(guān)鍵字為53的數(shù)據(jù)元素

45、，首先通過(guò)根指針找到根結(jié)點(diǎn)a，經(jīng)過(guò)結(jié)點(diǎn)c，最后到達(dá)結(jié)點(diǎn)f，查找成功，報(bào)告結(jié)點(diǎn)地址及在結(jié)點(diǎn)中的關(guān)鍵字序號(hào)。如果查找的是關(guān)鍵字為58的數(shù)據(jù)元素，前面的過(guò)程和查找關(guān)鍵字為53的數(shù)據(jù)元素一樣，在結(jié)點(diǎn)f中做關(guān)鍵字比較：5853，沿53的右側(cè)指針向下一層查找，結(jié)果到達(dá)失敗結(jié)點(diǎn)，所以查找失敗。 由此可見(jiàn)，B樹的查找過(guò)程是一個(gè)在結(jié)點(diǎn)內(nèi)查找和按某一條路徑向下一層查找交替進(jìn)行的過(guò)程。顯然，如果提高B樹的階數(shù)m，可以減少樹的高度，從而減少讀入結(jié)點(diǎn)的次數(shù)，因而可減少讀磁盤的次數(shù)。 因此，B樹的查找時(shí)間與B樹的階數(shù)m和B樹的高度h直接有關(guān)，必須加以權(quán)衡。 在一棵m階B樹中，每個(gè)非失敗結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)都在（m/2-1）（

46、m-1）之間。如果在關(guān)鍵字插入后結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)未超出上述范圍的上界m-1，則可以直接插人；否則結(jié)點(diǎn)需要“分裂”。實(shí)現(xiàn)結(jié)點(diǎn)“分裂”的原則是：設(shè)結(jié)點(diǎn)p中已經(jīng)有m-1個(gè)關(guān)鍵字，當(dāng)再插入一個(gè)關(guān)鍵字后結(jié)點(diǎn)中的狀態(tài)為：(m,P0,K1,P1,K2,P2,Km,Pm)其中 KiKi+1, 1 i m。 這時(shí)必須把結(jié)點(diǎn)p分裂成兩個(gè)結(jié)點(diǎn)p和p，它們包含的信息分別為： 結(jié)點(diǎn)p：(m/2-1,P0,K1,P1,Km/2 -1,Pm/2 -1)； 結(jié)點(diǎn)p：(m-m/2,Pm/2,Km/2+1,Pm/2+1,Km,Pm)。 從空樹開始，按上述方法依次逐個(gè)插入關(guān)鍵字就可以建立B樹。例如，輸入關(guān)鍵字序列為35、26、7

47、4、60、49、17、41、53,如右圖所示給出了從空樹開始通過(guò)逐個(gè)插入關(guān)鍵字建立3階B樹的示例。 一般地，若在3階B樹中總的關(guān)鍵字個(gè)數(shù)為N，則樹的高度為hlog2(N+1)2)+1。當(dāng)N7時(shí)，hlog2(N+1)2)+13。 設(shè)B樹的高度為h，那么在自頂向下查找葉結(jié)點(diǎn)的過(guò)程中需要經(jīng)過(guò)h個(gè)結(jié)點(diǎn)。在最壞情況下需要自底向上分裂結(jié)點(diǎn)，從被插關(guān)鍵字所在葉結(jié)點(diǎn)到根的路徑上的所有結(jié)點(diǎn)都要分裂。因此，完成一次插入操作時(shí)，最多需要讀寫磁盤的次數(shù)（查找插入結(jié)點(diǎn)而進(jìn)行的讀盤次數(shù)）+（分裂結(jié)點(diǎn)而進(jìn)行的寫盤次數(shù)）2h。 B樹的刪除 如果想要在B樹上刪除一個(gè)關(guān)鍵字，首先需要找到這個(gè)關(guān)鍵字所在的結(jié)點(diǎn)，從中刪去這個(gè)關(guān)鍵字。

48、 若該結(jié)點(diǎn)不是葉結(jié)點(diǎn)，且被刪關(guān)鍵字為Ki（1in），則在刪去該關(guān)鍵字之后，可以用該結(jié)點(diǎn)的Pi所指子樹中的最小關(guān)鍵字k（Pi-1所指子樹中的最大關(guān)鍵字k）來(lái)代替被刪關(guān)鍵字Ki，然后在k所在的葉結(jié)點(diǎn)中刪除k。 在葉結(jié)點(diǎn)中刪除關(guān)鍵字有以下四種情況需要分別討論：（1）若被刪關(guān)鍵字所在葉結(jié)點(diǎn)同時(shí)又是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)n2，則直接刪去該關(guān)鍵字并將修改后的結(jié)點(diǎn)寫回磁盤，刪除結(jié)束。 （2）若被刪關(guān)鍵字所在葉結(jié)點(diǎn)不是根結(jié)點(diǎn)且刪除前該結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)nm2，則可直接從該葉結(jié)點(diǎn)中刪除該關(guān)鍵字。 （3）被刪關(guān)鍵字所在葉結(jié)點(diǎn)刪除前關(guān)鍵字個(gè)數(shù)nm2-1，若這時(shí)與該結(jié)點(diǎn)相鄰的左(或右)兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm

49、2，則可按以下步驟調(diào)整該結(jié)點(diǎn)、左(或右)兄弟結(jié)點(diǎn)以及其雙親結(jié)點(diǎn)，以達(dá)到新的平衡。1）將其雙親結(jié)點(diǎn)中大于(或小于)該被刪關(guān)鍵字的所有關(guān)鍵字最小（或最大）的一個(gè)關(guān)鍵字Ki下移到被刪關(guān)鍵字所在結(jié)點(diǎn)中；2）將左（或右）兄弟結(jié)點(diǎn)中的最大（或最小）關(guān)鍵字上移到雙親結(jié)點(diǎn)的ki位置； 3）將左（或右）兄弟結(jié)點(diǎn)中的最右(或最左)子樹指針刪除，并將結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)減1。 刪除關(guān)鍵字后從雙親和左（右）兄弟中調(diào)整關(guān)鍵字的示例 。（4）被刪關(guān)鍵字所在葉結(jié)點(diǎn)p刪除前關(guān)鍵字個(gè)數(shù)nm2-1，若這時(shí)與該結(jié)點(diǎn)相鄰的左、右兄弟結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)也都為m2-1，則必須按以下步驟合并這兩個(gè)結(jié)點(diǎn)。1）將雙親結(jié)點(diǎn)中大于(或小于)該被刪關(guān)

50、鍵字的所有關(guān)鍵字中最小（或最大）的一個(gè)關(guān)鍵字Ki下移到p結(jié)點(diǎn)中，將P和P的左（或右）兄弟結(jié)點(diǎn)合并；2）修改p結(jié)點(diǎn)和其雙親結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)。 3）在合并結(jié)點(diǎn)的過(guò)程中，雙親結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)減少了1。若p的雙親結(jié)點(diǎn)是根結(jié)點(diǎn)且結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)減到0，則該雙親結(jié)點(diǎn)應(yīng)從樹上刪去，合并后保留的p結(jié)點(diǎn)成為新的根結(jié)點(diǎn)； 若雙親結(jié)點(diǎn)f不是根結(jié)點(diǎn)，且關(guān)鍵字個(gè)數(shù)減到m2-2，則結(jié)點(diǎn)f又要與它自己的兄弟結(jié)點(diǎn)合并。重復(fù)上面的合并步驟，最壞情況下這種結(jié)點(diǎn)合并處理要自下向上直到根結(jié)點(diǎn)。 如下圖所示，給出了在圖（a）所示的3階B-樹中依次刪除關(guān)鍵字78、60和41后進(jìn)行關(guān)鍵字的替代、結(jié)點(diǎn)的合并和調(diào)整的過(guò)程。 一棵一棵m m階階B

51、+B+樹可以定義如下：樹可以定義如下：（1 1）樹中每個(gè)非葉結(jié)點(diǎn)最多有）樹中每個(gè)非葉結(jié)點(diǎn)最多有m m棵子樹；棵子樹；（2 2）根結(jié)點(diǎn)至少有）根結(jié)點(diǎn)至少有2 2棵子樹。除根結(jié)點(diǎn)外，其它的非葉結(jié)點(diǎn)棵子樹。除根結(jié)點(diǎn)外，其它的非葉結(jié)點(diǎn)至少有至少有 m m2 2 棵子樹；有棵子樹；有n n棵子樹的非葉結(jié)點(diǎn)中含有有棵子樹的非葉結(jié)點(diǎn)中含有有n n個(gè)關(guān)個(gè)關(guān)鍵字，且按由小到大的順序排列。鍵字，且按由小到大的順序排列。（3 3）所有的葉結(jié)點(diǎn)都處于同一層次上，包含了全部關(guān)鍵字）所有的葉結(jié)點(diǎn)都處于同一層次上，包含了全部關(guān)鍵字及指向相應(yīng)數(shù)據(jù)元素的指針，且葉結(jié)點(diǎn)本身按關(guān)鍵字從小到及指向相應(yīng)數(shù)據(jù)元素的指針，且葉結(jié)點(diǎn)本身按關(guān)

52、鍵字從小到大順序鏈接；大順序鏈接； （4）所有的非葉結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中關(guān)鍵）所有的非葉結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中關(guān)鍵字字Ki與指向子樹的指針與指向子樹的指針Pi構(gòu)成一個(gè)索引項(xiàng)（構(gòu)成一個(gè)索引項(xiàng)（Ki、Pi）。其中）。其中Ki是是Pi所指向的子樹中最大（或最?。┑年P(guān)鍵字。所指向的子樹中最大（或最?。┑年P(guān)鍵字。 通常在B+樹中有兩個(gè)頭指針：一個(gè)指向B+樹的根結(jié)點(diǎn)，一個(gè)指向關(guān)鍵字最小的葉結(jié)點(diǎn)。因此，可以對(duì)B+樹進(jìn)行兩種查找操作： 一種是對(duì)葉結(jié)點(diǎn)之間的鏈表進(jìn)行順序查找; 另一種是從根結(jié)點(diǎn)開始，進(jìn)行自頂向下，直至葉結(jié)點(diǎn)的隨機(jī)查找。 在B+樹上進(jìn)行隨機(jī)查找過(guò)程中，如果非葉結(jié)點(diǎn)中的某個(gè)關(guān)鍵字等

53、于給定值，查找并不停止，而是繼續(xù)沿相應(yīng)指針向下，一直查到葉結(jié)點(diǎn)上的這個(gè)關(guān)鍵字，然后才能根據(jù)相應(yīng)的地址指針找到數(shù)據(jù)元素。因此，在B+樹中，不論查找成功與否，每次查找都是走了一條從根到葉結(jié)點(diǎn)的路徑。 在B+樹上進(jìn)行插入和刪除的過(guò)程基本上與B樹類似,僅在葉結(jié)點(diǎn)上進(jìn)行。 所謂查找實(shí)際上就是要確定關(guān)鍵字（Key）等于給定值（k）的數(shù)據(jù)元素的存儲(chǔ)地址（Addr）。故查找問(wèn)題本質(zhì)上是確定關(guān)鍵字集合K到地址空間A的映射(即函數(shù))：H：KA 因而，任何查找算法，都是計(jì)算函數(shù)H(k)的值的過(guò)程。 在前面介紹的查找算法中，由于k與H(k)之間沒(méi)有簡(jiǎn)單直接的對(duì)應(yīng)關(guān)系，函數(shù)H完全是一個(gè)隱式函數(shù)。因此，求H(k)值的時(shí)間

54、不僅與數(shù)據(jù)表的存儲(chǔ)結(jié)構(gòu)有關(guān)，而且與數(shù)據(jù)表的大小n有關(guān)。 如果把函數(shù)H定義成簡(jiǎn)單的代數(shù)式，那么在查找時(shí)，只須計(jì)算H(k)之值，設(shè)H(k)=h，通過(guò)測(cè)試Ahkey是否等于k(假定數(shù)組A表示存儲(chǔ)空間)便可確定關(guān)鍵字為k的數(shù)據(jù)元素是否存在。這就能不經(jīng)查找，在“一步”之內(nèi)完成查找工作。 函數(shù)H把關(guān)鍵字轉(zhuǎn)換成一個(gè)地址，因此這種存儲(chǔ)技術(shù)稱為鍵變換。又稱雜湊(Hash)技術(shù)或散列技術(shù)。相應(yīng)地，存儲(chǔ)空間稱為散列表，函數(shù)H稱為雜湊(散列)函數(shù)。數(shù)據(jù)表的這種存儲(chǔ)方式叫散列存儲(chǔ)。 通過(guò)散列函數(shù)建立了從數(shù)據(jù)元素的關(guān)鍵字集合到散列表地址集合的一個(gè)映射。有了散列函數(shù)，就可以根據(jù)關(guān)鍵字確定數(shù)據(jù)元素在散列表中唯一的存放地址。

55、一般來(lái)說(shuō)，散列函數(shù)是一個(gè)壓縮映象函數(shù)。通常關(guān)鍵字集合比散列表地址集合大得多。因此有可能經(jīng)過(guò)散列函數(shù)的計(jì)算，把不同的關(guān)鍵字映射到同一個(gè)散列地址上，這就產(chǎn)生了沖突。散列地址相同的不同關(guān)鍵字被稱為同義詞。 例如，有一組數(shù)據(jù)元素，其關(guān)鍵字分別是59、26、81，我們采用的散列函數(shù)是hash（k)k11。其中，“”是除法取余操作，則有：hash（59)=hash（26)=hash（81)=4。對(duì)于散列方法，需要討論以下兩個(gè)問(wèn)題：（1）對(duì)于給定的一個(gè)關(guān)鍵字集合，選擇一個(gè)計(jì)算簡(jiǎn)單且地址分布比較均勻的散列函數(shù)，避免或盡量減少?zèng)_突；（2）制訂解決沖突的方案。 在構(gòu)造散列函數(shù)時(shí)有幾點(diǎn)需要加以注意： 其一、散列函數(shù)

56、的定義域必須包括需要存儲(chǔ)的全部數(shù)據(jù)元素的關(guān)鍵字，而如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間； 其二、散列函數(shù)計(jì)算出來(lái)的地址應(yīng)能均勻分布在整個(gè)地址空間中，若key是從關(guān)鍵字集合中隨機(jī)抽取的一個(gè)關(guān)鍵字，散列函數(shù)應(yīng)能以同等概率取0到m-1中的每一個(gè)值； 其三、散列函數(shù)應(yīng)是簡(jiǎn)單的，能在較短的時(shí)間內(nèi)計(jì)算出結(jié)果。下面我們介紹幾個(gè)散列函數(shù)。 1直接定址法此類函數(shù)取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址： Hash（key）=a*key+c （其中a、c是整常數(shù)）這類散列函數(shù)是一對(duì)一的映射，一般不會(huì)產(chǎn)生沖突，但是，它要求散列地址空間的大小與關(guān)鍵字集合的大小相同，這種要求是很苛刻的。特別是當(dāng)關(guān)鍵字集合

57、很大而且又不連續(xù)時(shí)，這種方法就不太適宜。 2數(shù)字分析法 設(shè)數(shù)據(jù)表的長(zhǎng)度為n，數(shù)據(jù)元素的關(guān)鍵字是一個(gè)d位數(shù)，關(guān)鍵字上每一位可能有r種不同的符號(hào)。 這r種不同的符號(hào)在各位上出現(xiàn)的概率不一定相同，可能在某些位上分布均勻，出現(xiàn)的機(jī)會(huì)均等；在某些位上分布不均勻，只有某幾種符號(hào)經(jīng)常出現(xiàn)。數(shù)字分析法就是根據(jù)散列表的大小，在關(guān)鍵字中選取某些分布均勻的若干位作為散列地址。 計(jì) 算 各 位 的 符 號(hào) 分 布 均 勻 度 的 公 式 為 ：dkrnariikk、 .1,)(12其中，aki表示在第k位上第i個(gè)符號(hào)出現(xiàn)的次數(shù)，nr表示各個(gè)符號(hào)在所有關(guān)鍵字中均勻出現(xiàn)的期望值。計(jì)算出的k值越小，表明在該位(第k位)上各

58、種符號(hào)分布得越均勻。例如，有一組關(guān)鍵字：6732598、6723708、6716388、6727418、6729168、6726698、6731588、6711128。其各位(從左到右)的符號(hào)分布均勻度計(jì)算為：第1位，僅6出現(xiàn)8次，1=(8810)2十(0810)2*957.6第2位，僅7出現(xiàn)8次，2=(8810)2十(0810)2*957.6第3位，1和3各出現(xiàn)2次，2出現(xiàn)4次，3=(2810)2*2+(4810)2*1+(0810)2*717.6第4位，1和6各出現(xiàn)2次，2、3、7、9各出現(xiàn)1次，4=(2810)2*2+(1810)2*4+(0810)2*415.6第5位，1和5各出現(xiàn)2次

59、，3、4、6、7各出現(xiàn)1次，5=(2810)2*2+(1810)2*4+(0810)2*415.6第6位，8和9各出現(xiàn)2次，0、1、2、6各出現(xiàn)1次，6=(2810)2*2+(1810)2*4+(0810)2*415.6第7位，僅8出現(xiàn)8次，7=(8810)2十(0810)2*957.6 如果散列地址由3位數(shù)字組成，則可取各關(guān)鍵字的4、5、6位作為數(shù)據(jù)元素的散列地址；也可以把第1、2、3、4和第7位相加，舍去進(jìn)位位，變成一位數(shù)，與第5、6位合起來(lái)作為散列地址。 顯然，數(shù)字分析法僅適用于事先明確知道數(shù)據(jù)表中所有關(guān)鍵字每一位上數(shù)值符號(hào)的分布情況，它完全依賴于關(guān)鍵字集合。如果換一個(gè)關(guān)鍵字集合，選擇哪

60、幾位要重新決定。 3除留余數(shù)法設(shè)散列表地址空間大小為m，取一個(gè)不大于m，但最接近于或等于m的質(zhì)數(shù)p，或者選取一個(gè)不含有小于20的質(zhì)因數(shù)的合數(shù)作為除數(shù)，除留余數(shù)法的散列函數(shù)為： Hash（key）=key % p （pm）其中，“”是整數(shù)除法取余運(yùn)算，且p應(yīng)避免取2的冪。 例如：設(shè)散列表的大小m=25，取質(zhì)數(shù)p=23，散列函數(shù)為： Hash（key）=key % 23。 則對(duì)于關(guān)鍵字為key7463，有Hash(7463)74632311。可以按此計(jì)算出的“地址”存放數(shù)據(jù)元素。需要注意的是，使用上面的散列函數(shù)計(jì)算出來(lái)的地址范圍是0到22，而23、24這兩個(gè)散列地址實(shí)際上在一開始是不可能用散列函數(shù)計(jì)算出來(lái)的，只可能在處理溢出時(shí)用到這些地址。 4乘余取整法使用此方法時(shí)，先讓關(guān)鍵字key乘上一個(gè)常數(shù)a(0a1)，提取乘積的小數(shù)部分，然后再用整數(shù)n乘以這個(gè)值，