第九章查找數據結構9.1查找的基本概念9.2基于線性表的查找法9.3基于樹的查找法9.4散列表的查找—哈希法主要內容列表：由同一類型的數據元素（或記錄）構成的集合，可利用任意數據結構實現。關鍵碼：可以標識一個記錄的某個數據項。鍵值：關鍵碼的值。主關鍵碼：可以唯一地標識一個記錄的關鍵碼。次關鍵碼：不能唯一地標識一個記錄的關鍵碼。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念查找：在具有相同類型的記錄構成的集合中找出滿足給定條件的記錄。查找的結果：若在查找集合中找到了與給定值相匹配的記錄，則稱查找成功；否則，稱查找失敗。50女李爽000525女齊梅000447女劉楠000325男張亮000238男王剛0001年齡性別姓名職工號1972年9月2003年7月1979年9月2003年7月1990年4月參加工作基本概念靜態(tài)查找：不涉及插入和刪除操作的查找。動態(tài)查找：涉及插入和刪除操作的查找。

靜態(tài)查找適用于：查找集合一經生成，便只對其進行查找，而不進行插入和刪除操作，或經過一段時間的查找之后，集中地進行插入和刪除等修改操作。動態(tài)查找適用于：查找與插入和刪除操作在同一個階段進行，例如當查找成功時，要刪除查找到的記錄，當查找不成功時，要插入被查找的記錄?；靖拍罹€性表：適用于靜態(tài)查找，主要采用順序查找技術、折半查找技術。樹

表：適用于動態(tài)查找，主要采用二叉排序樹的查找技術。散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術。結構線性表樹表散列表基本概念查找算法時間性能通過關鍵碼的比較次數來度量。關鍵碼的比較次數與哪些因素有關呢？⑴算法；⑵問題規(guī)模；⑶待查關鍵碼在查找集合中的位置；查找算法的時間復雜度是問題規(guī)模n

和待查關鍵碼在查找集合中的位置k

的函數，記為T(n，k)。同一查找集合、同一查找算法，關鍵碼的比較次數與哪些因素有關呢？基本概念平均查找長度：將查找算法進行的關鍵碼的比較次數的數學期望值定義為平均查找長度。計算公式為：

其中：n

：問題規(guī)模，查找集合中的記錄個數；

pi

：查找第i個記錄的概率；

ci

：查找第i個記錄所需的關鍵碼的比較次數。結論：ci取決于算法；pi與算法無關，取決于具體應用。如果pi是已知的，則平均查找長度只是問題規(guī)模的函數。查找算法的性能ASL?==niiicp1基本思想：從線性表的一端向另一端逐個將關鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的關鍵碼，則查找失敗，給出失敗信息。

101524612354098550123456789i例：查找key＝35iii

靜態(tài)查找表——順序表的查找以順序表或線性鏈表表示靜態(tài)查找表typedefstruct{keyTypekey;//關鍵字域

……//其它屬性域}ElemType;typedefstruct{ElemType*elem;intlength;}SSTable;intSearch(SSTableST,KeyTypekey){for(i=ST.length;i>0&&ST.elem[i].key!=key;--i);returni;}

順序查找法(線性查找)基本思想：設置“哨兵”。哨兵就是所要查找的值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。

101524612354098550123456789i例：查找k＝35iii哨兵35查找方向

改進的順序查找法intSearch(SSTableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i);returni;}

改進的順序查找法

列表長度為n，查找第i個數據元素時需進行n-i+1次比較，即ci=n-i+1。又假設查找每個數據元素的概率相等，即pi=1/n。

平均查找長度較大，特別是當待查找集合中元素較多時，查找效率較低。順序查找的缺點：算法簡單而且使用面廣。對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；對表中記錄的有序性也沒有要求，無論記錄是否按關鍵碼有序均可。順序查找的優(yōu)點：

順序查找法的優(yōu)缺點使用條件：

在有序表中，取中間元素作為比較對象，1、若給定值與中間記錄的關鍵字相等，則查找成功；2、若給定值小于中間記錄的關鍵字，則在中間記錄的左半區(qū)繼續(xù)查找；3、若給定值大于中間記錄的關鍵字，則在中間記錄的右半區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄（low>high），查找失敗。

有序表的查找——折半查找

線性表中的記錄必須按關鍵字有序；必須采用順序存儲。基本思想：例：查找值為14的記錄的過程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=2

mid=1

31>1418>147<14low=2mid=2

14=14例：查找值為22的記錄的過程：012345678910111213

7141821232931353842464952low=1high=13mid=7

high=6mid=3

high=4

mid=5

31>2218<2223>22low=4mid=4

21<22low=5low>highintSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(key==ST.elem[mid].key)returnmid;elseif(key<ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;}

折半查找的算法折半查找成功時的平均查找長度為：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1優(yōu)點：

比較次數少，查找速度快，平均性能好。缺點：

要求待查的表為有序表。

折半查找的性能分析動態(tài)查找表：結構本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在其關鍵字等于key的記錄，則查找成功返回，否則插入關鍵字等于key的記錄。動態(tài)查找表二叉排序樹平衡二叉樹B樹

動態(tài)查找表二叉排序樹(二叉查找樹)：或者是一棵空的二叉樹，或者是具有下列性質的二叉樹：⑴若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；⑵若它的右子樹不空，則右子樹上所有結點的值均大于根結點的值；⑶它的左右子樹也都是二叉排序樹。二叉排序樹的定義采用的是遞歸方法。

二叉排序樹二叉排序樹非二叉排序樹6390554258104567837063605582581045678370中序遍歷二叉排序樹可以得到一個關鍵碼有序序列。

二叉排序樹typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;

二叉排序樹—存儲結構通常，取二叉鏈表作為二叉排序樹的存儲結構。在二叉排序樹中查找給定值的過程是：⑴若二叉排序樹是空樹，則查找失敗；(2)若給定值等于根結點的關鍵字，則查找成功；(3)若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找；(4)若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。

二叉排序樹的查找50308020908540358832例如:二叉排序樹查找關鍵字==50,505035,503040355090,50809095,BitTreeSearchBST(BiTreeT,KeyTypekey){

if((!T)||(key==T->data.key))return(T);

else

if(key<T->data.key

)return(SearchBST(T->lchild,key));

elsereturn(SearchBST(T->rchild,key));}二叉排序樹的查找二叉排序樹的查找性能分析由序列{3,1,2,5,4}得到二叉排序樹：由序列{1,2,3,4,5}得到二叉排序樹：ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.21234531254二叉排序樹的查找性能分析由此可見，在二叉排序樹上進行查找時的平均查找長度和二叉排序樹的形態(tài)有關。最壞情況：二叉排序樹是通過把一個有序表的n個結點一次插入生成的，由此得到的二叉排序樹為一顆深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，也是(n+1)/2。最好情況：二叉排序樹在生成過程中，樹的形態(tài)比較均勻，即樹中各結點的左右子樹的深度差距不大的樹，此時他的平均查找長度大約是log2n。1、若二叉排序樹是空樹，結點s成為二叉排序樹的根；2、若二叉樹排序樹非空，則將s的關鍵字值key與二叉樹排序樹的根進行比較，①如果s的值等于根結點的值，則停止插入；②如果s的值小于根結點的值，則將s插入左子樹；③如果s的值大于根結點的值，則將s插入右子樹。插入一個關鍵字值為key的結點s，插入的方法：

二叉排序樹的插入6355905870985563root∧9058∧∧70∧∧98∧∧sroot∧

二叉排序樹的插入

給定一個元素序列，可以利用插入算法創(chuàng)建一棵二叉排序樹。將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就建立一個新的結點插入到當前已生成的二叉排序樹中，即調用上述二叉排序樹的插入算法將新結點插入。直到所有結點插入完成，二叉排序樹就構造完成了。分析：若二叉排序樹為空樹，則新插入的結點為新的根結點；否則，新插入的結點必為一個新的葉子結點，其插入位置由查找過程得到。

二叉排序樹的構造從空的二叉排序樹開始，依次插入一個個結點。例：關鍵碼集合為

{63，90，70，55，58}7.3樹表的查找技術6355905870

二叉排序樹的構造1、關鍵字的輸入順序為：45,24,53,12,28,90，構造二叉排序樹4524531228902、關鍵字的輸入順序為：24,53,

90,

12,

28,

45

，構造二叉排序樹241228539045結論：對同樣一組數據元素，如果輸入的順序不同，則所建的二叉樹形態(tài)也不同。一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列;每次插入的新結點都是二叉排序樹上新的葉子結點;找到插入位置后，不必移動其它結點，僅需修改某個結點的指針；在左子樹/右子樹的查找過程與在整棵樹上查找過程相同；新插入的結點沒有破壞原有結點之間的關系。小結：

二叉排序樹的構造二叉排序樹的刪除

在二叉排序樹上刪除某個結點之后，仍然保持二叉排序樹的特性。分三種情況討論：被刪除的結點是葉子；被刪除的結點只有左子樹或者只有右子樹；被刪除的結點既有左子樹，也有右子樹。

二叉排序樹的刪除1.若結點p是葉子，則直接刪除結點p；2.若p結點只有左子樹，或只有右子樹，則因為該結點只有左子樹或只有右子樹，也就是說，其后繼只有一個分支。刪除該結點時，只要將被刪除結點的唯一后繼（左子樹或右子樹）直接鏈接到被刪除結點的位置即可。3.若結點p的左右子樹均不空：首先找到p結點在中序序列中的直接前驅s結點，然后用s結點的值，替代p結點的值，再將s結點刪除,因為s的右指針一定為空，所以只要把s的左孩子鏈接到s結點本身的位置即可。

二叉排序樹的刪除50308020403590858832（2）被刪除的結點只有左子樹或者只有右子樹

其雙親結點的相應指針域的值改為“指向被刪除結點的左子樹或右子樹”。被刪關鍵字=3580503080209085883532（3）被刪除的結點既有左子樹，也有右子樹4040以其前驅替代之，然后再刪除該前驅結點被刪關鍵字=50StatusDeleteBST(BiTree&T,KeyTypekey){if(!T)returnFALSE;else{if(key==T->data.key){Delete(T);returnTRUE;} elseif(key<T->data.key)DeleteBST(T->lchild,key);elseDeleteBST(T->rchild,key);}}平衡二叉樹：或者是一棵空的二叉排序樹，或者是具有下列性質的二叉排序樹：⑴根結點的左子樹和右子樹的深度最多相差1;⑵根結點的左子樹和右子樹也都是平衡二叉樹。平衡因子：結點的平衡因子是該結點的左子樹的深度與右子樹的深度之差。在平衡二叉樹中，結點的平衡因子可以是1，0，-1。

平衡二叉樹548254821

平衡樹非平衡樹在平衡樹中，結點的平衡因子可以是1，0，-1。結點的平衡因子＝HL-HR

平衡二叉樹最小不平衡子樹：

在平衡二叉樹的構造過程中，以距離插入結點最近的、且平衡因子絕對值大于1的祖先結點為根的子樹。542814

最小不平衡子樹

在構造二叉排序樹的過程中，每插入一個結點時，首先檢查是否因插入新結點而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調整最小不平衡子樹中各結點之間的鏈接關系，進行相應的旋轉，使之成為新的平衡子樹。

平衡二叉樹構造【基本思想】

設結點A為最小不平衡子樹的根結點，則失去平衡后進行調整的規(guī)律可歸納為下列四種情況：

1.LL型：由于在A的左子樹根結點B的左子樹上插入結點，A的平衡因子由1變?yōu)?。

2.RR型：由于在A的右子樹根結點B的右子樹上插入結點，A的平衡因子由-1變?yōu)?2。

3.LR型：由于在A的左子樹根結點B的右子樹上插入結點，A的平衡因子由1變?yōu)?。

4.RL型：由于在A的右子樹根結點B的左子樹上插入結點，A的平衡因子由1變?yōu)?。

平衡二叉樹的調整插入前插入后、調整前順時針平衡二叉樹——LL型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX

以B為軸，對A做了一次順時針旋轉，即將A改為B的右孩子，B原來的右孩子改為A的左孩子61→2例:LL型

108791291012876平衡二叉樹——RR型插入前插入后，調整前逆時針A-1BLhBRh0ALhBXA-2BLhBRh-1ALhBBALhBLh0BRh+1AX0

以B為軸，對A做了一次逆時針旋轉，即將A改為B的左孩子，B原來的左孩子改為A的右孩子插入后，調整前先逆時針旋轉再順時針旋轉A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh平衡二叉樹——LR型1、將B改為其右子樹根結點C的左孩子，而C原來的左孩子改為B的右孩子，相當于以C為軸，對B作了一次逆時針旋轉；

2、將A改為C的右孩子，C原來的右孩子改為A的左孩子，相當于以C為軸，對A進行了一次順時針旋轉。插入后，調整前先順時針旋轉再逆時針旋轉XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001平衡二叉樹——RL型1、將B改為其左子樹根結點C的右孩子，而C原來的右孩子改為B的左孩子，相當于以C為軸，對B作了一次順時針旋轉；

2、將A改為C的左孩子，C原來的左孩子改為A的右孩子，相當于以C為軸，對A進行了一次逆時針旋轉。課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹542LL型42586864256842585642課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹RL型旋轉1次RL型旋轉2次856429RR型846529課堂練習：設有關鍵碼序列{5,4,2,8,6,9}，構造平衡樹例：設序列{20，35，40，15，30，25}，構造平衡樹。203540352040153025352040153025202515354030354030202515例：設序列{20，35，40，15，30，25}，構造平衡樹。（1）查找應插位置，同時記錄離插入位置最近的可能失衡結點A（A的平衡因子不等于0）。（2）插入新結點S，并修改從A到S路徑上各結點的平衡因子。（3）根據A、B的平衡因子，判斷是否失衡以及失衡類型，并做相應處理。

平衡二叉樹的調整

綜上所述，在一個平衡二叉排序樹上插入一個新結點S時，主要包括以下三步：查找操作要完成什么任務？待查值k確定k在存儲結構中的位置

散列表的查找—哈希表若以下標為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關鍵字為學號，其值的范圍為xx000~xx999(前兩位為年份)。

則查找過程可以簡單進行：取給定值（學號）的后三位，不需要經過比較便可直接從順序表中找到待查關鍵字。哈希法：又稱散列法、雜湊法以及關鍵字地址計算法等，相應的表稱為哈希表。哈希法的基本思想：首先在元素的關鍵字k和元素的存儲位置p之間建立一個對應關系H，使得p=H(k)，H稱為哈希函數。創(chuàng)建哈希表時，把關鍵字為k的元素直接存入地址為H(k)的單元；以后當查找關鍵字為k的元素時，再利用哈希函數計算出該元素的存儲位置p=H(k)，從而達到按關鍵字直接存取元素的目的。

散列表的查找—哈希表設計哈希函數一般應遵循以下原則：⑴計算簡單。哈希函數不應該有很大的計算量，否則會降低查找效率。⑵函數值即哈希地址分布均勻。函數值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。沖突：對于兩個不同關鍵碼ki≠kj，有H(ki)＝H(kj)，即兩個不同的記錄需要存放在同一個存儲位置，ki和kj相對于f稱做同義詞。

哈希函數的構造【直接定址法】散列函數是關鍵碼的線性函數，即：H(key)=a

key+b（a，b為常數）例：關鍵碼集合為{10,30,50,70,80,90}，選取的散列函數為H(key)=key/10，則散列表為：0123456789103050708090適用情況？事先知道關鍵碼，關鍵碼集合不是很大且連續(xù)性較好。

哈希函數的構造方法H(key)=keymodp