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

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

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

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

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

6、Type getKey ( ) const return key; /取關鍵字 void setKey ( Type k ) key = k; /關鍵字的賦值private: Type key; /關鍵字 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;在順序存儲結構下的順序查找算法如下：template int searchList :Search ( const Type & k ) const /在順序表中查找關鍵字為k的數(shù)據(jù)元素 int i = CurrentSize; Table0.setKey ( k

8、); /在0號位置設置監(jiān)視哨 while (Tablei.getKey ( ) != k ) i -; return i; 在等概率情形下查找成功的平均查找長度為：n1i21i*n1n1iiC*iPASLn查找失敗的平均查找長度為n+1。 有序表的折半查找 對有序表通?？捎谜郯氩檎业姆椒▉磉M行查找。設有n個數(shù)據(jù)元素按其關鍵字從小到大的順序存放在一個順序表中（開始時，查找區(qū)間的下限low=0，上限hight=n-1），折半查找的算法思想為：（1）如果查找區(qū)間長度小于1（lowhight），則表示查找失敗，返回-1；否則繼續(xù)以下步驟。（2）求出查找區(qū)間中間位置的數(shù)據(jù)元素下標mid（mid=（low

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

10、次關鍵字比較。圖(b)給出了查找關鍵字為52的數(shù)據(jù)元素時的查找過程，直到確認查找失敗也執(zhí)行了3次關鍵字比較。折半查找的算法可以用遞歸的形式和迭代的形式實現(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;在二叉查找樹上，每個結點表示有序表中的一個數(shù)據(jù)元素。設二叉查找樹有

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

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

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

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

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

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

19、ndex +ASLSubListlog2(m+1)-1+(k+1)/2log2(1+n/k)+k/2 有時除主關鍵字外，可以把一些在查找時經(jīng)常用到的屬性設定為次關鍵字，并以每一個屬性作為次關鍵字建立次索引表，并稱為倒排索引表。 倒排索引表有鏈式和單元式兩種結構。在鏈式倒排索引表中，列出了作為次關鍵字屬性的所有取值，并對每一個取值建立有序鏈表，把所有具有相同屬性值的主關鍵字按其遞增的順序或按其在主索引表中的存儲地址遞增的順序鏈接在一起。因此，鏈式倒排索引表包括三個部分：次關鍵字、鏈表長度和有序鏈表。 在單元式倒排索引表的各個索引項中存放表示各外存區(qū)域是否存有相應數(shù)據(jù)元素的標識（以0或1表示）。于

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

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

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

23、hild (NULL) /構造函數(shù) BstNode (const Type d) : data (d),leftChild (NULL), rightChild (NULL) /構造函數(shù) BstNode ( ) /析構函數(shù)protected: Type data ;/數(shù)據(jù)域（在此為關鍵字） BSTreeNode *leftChild, *rightChild; ;template class BSTree : public : BinaryTree /二叉排序樹的類定義public: BSTree ( ) : root (NULL) /構造函數(shù) BSTree ( ); /析構函數(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 ); 二 叉排序樹的查找算法可以用遞歸和迭代兩種方法實現(xiàn)。template BSTreeNode * BSTree :Find (const Type & k, BSTreeNode * p ) const/在p為根的二叉排序樹上進行查找的遞歸算法 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為根的二叉排序樹上進行查找的迭代算法 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; /查找失敗 為了向二叉排序樹中插入一個新元素，必須先檢查這個元素在二叉排序樹中是否已經(jīng)存在。 因此，在插入之前，首先在二叉排序樹中檢查待插入的數(shù)據(jù)元素，如果查找成功，說明樹中已經(jīng)存在這個數(shù)據(jù)元素，則不再插入； 如果查找不成功，說明樹中不存在關鍵字等于給定值的數(shù)據(jù)元素，把新元素插到查找操作失敗的地方。在二叉排序樹中插入一個新元素的算法描述在二叉排序樹中插入一個新元素的算法描述: :template void BSTree:Insert (const

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

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

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

31、（x沒有右子樹）。 template void BSTree :Delete (const Type &k, BSTree Node * &p) /在p為根的二叉排序樹上刪除關鍵字為k的結點 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; 在二叉排序樹上的查找過程實在二叉排序樹上的查找過程實際上是走了一條從根到所查結點的際上是走了一條從根到所查結點的路徑，所需的比較次數(shù)為該結點所路徑，所需的比較次數(shù)為該結點所在的層次數(shù)。因此，查找成功時，在的層次數(shù)。因此，查找成功時，關鍵字的比較次數(shù)不超過樹的高度。關鍵字的比較次數(shù)不超過樹的高度。但是含有但是含有n個結點的二叉排序樹不個結點的二叉

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58、種符號分布得越均勻。例如，有一組關鍵字：6732598、6723708、6716388、6727418、6729168、6726698、6731588、6711128。其各位(從左到右)的符號分布均勻度計算為：第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ù)字組成，則可取各關鍵字的4、5、6位作為數(shù)據(jù)元素的散列地址；也可以把第1、2、3、4和第7位相加，舍去進位位，變成一位數(shù)，與第5、6位合起來作為散列地址。 顯然，數(shù)字分析法僅適用于事先明確知道數(shù)據(jù)表中所有關鍵字每一位上數(shù)值符號的分布情況，它完全依賴于關鍵字集合。如果換一個關鍵字集合，選擇哪

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