數(shù)據(jù)結(jié)構(gòu)課件第8章 查找

\第8章查找.

ISJI^H

f’數(shù)據(jù)結(jié)構(gòu)（C++描述）

目錄

8.1查找的基本概念

8.1杳找的基本概念

查找，也稱(chēng)為檢索。在我們?nèi)粘Ｉ钪?，隨處可見(jiàn)查找

的實(shí)例。如查找某人的地址、電話號(hào)碼；查某單位45歲

以上職工等，都屬于查找范疇。本書(shū)中，我們規(guī)定查找

是按關(guān)鍵字進(jìn)行的，所謂關(guān)鍵字（key）是數(shù)據(jù)元素（或記

錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（或識(shí)別）一個(gè)數(shù)據(jù)

元素。例如，描述一個(gè)考生的信息，可以包含：考號(hào)、

姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵

字。但有些關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而有的

關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如剛才的考生信息

中，姓名不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（因有同名同姓的

人），而考號(hào)可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素（每個(gè)考生考號(hào)

是唯一的，不能相同）。我們將能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素

的關(guān)鍵字稱(chēng)為主關(guān)鍵字，而其它關(guān)鍵字稱(chēng)為輔助關(guān)鍵字

或從關(guān)鍵字。

用了主關(guān)鍵字及關(guān)鍵字后，我們可以給查找下一個(gè)完整

的定義。所謂查找，就是根據(jù)給定的值，在一個(gè)表中查

找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素，若表中有這樣的

元素，則稱(chēng)查找是成功的，此時(shí)查找的信息為給定整個(gè)

數(shù)據(jù)元素的輸出或指出該元素在表中的位置；若表中不

存在這樣的記錄，則稱(chēng)查找是不成功的，或稱(chēng)查找失敗,

并可給出相應(yīng)的提示。

因?yàn)椴檎沂菍?duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的操作，所

以采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來(lái)

表示“表”，即表中結(jié)點(diǎn)是按何種方式組織的。為了提

高查找速度，我們經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來(lái)組織

表。因此在研究各種查找算法時(shí)，我們首先必須弄清這

些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)。

查找有內(nèi)查找和外查找之分。若整個(gè)查找過(guò)程全部在內(nèi)

存進(jìn)行，則稱(chēng)這樣的查找為內(nèi)查找；反之，若在查找過(guò)

程中還需要訪問(wèn)外存，則稱(chēng)之為外查找。我們僅介紹內(nèi)

查找。

要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字

的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的

平均值來(lái)作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，對(duì)于一個(gè)含

有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為

ASL=E”,，其中Pi為查找第i個(gè)元素的概率，且Zp,=1

一般情形下我們認(rèn)為查找每個(gè)元素的概率相等，Ci為查找

第i個(gè)元素所用到的比較次數(shù)。

要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字

的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的

平均值來(lái)作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，對(duì)于一個(gè)含

有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為

ASL=,其中Pi為查找第i個(gè)元素的概率，且=1。一般情

形下我們認(rèn)為查找每個(gè)元素的概率相等，Ci為查找第i個(gè)

元素所用到的比較次數(shù)。

8.2線性表的查找

8.2.1順序查找

L順序查找的基本思想

順序查找是一種最簡(jiǎn)單的查找方法，它的基本思想是:

從表的一端開(kāi)始，順序掃描線性表，依次將掃描到的

結(jié)點(diǎn)關(guān)鍵字和待找的值K相比較，若相等，則查找成

功，若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于K的元

素，則查找失敗。

順序查找既適用于順序表，也適用于鏈表。若用順序

表，查找可從前往后掃描，也可從后往前掃描，但若

采用單鏈表，則只能從前往后掃描。另外，順序查找

的表中元素可以是無(wú)序的。

F面以順序表的形式來(lái)描述算法。

2.順序查找算法實(shí)現(xiàn)

constintn=maxn〃口為表的最大長(zhǎng)度

structnode

{...

elemtypekey;//key為關(guān)鍵字，類(lèi)型設(shè)定為elemtype

)；

intseqsearch(nodeR[n+l]?elemtypek)〃在表R

中查找關(guān)鍵字值為K的元素

{R[0].key=k;inti=n;〃從表尾開(kāi)始向前掃描

while(R[i].key!=k)i—;

returni;}

在函數(shù)seqsearch中，若返回的值為0表示查找不成功,

否則查找成功。函數(shù)中查找的范圍從R[n]到R[l],

「注R[0]為監(jiān)視哨，起兩個(gè)作用，其一，是為了省去判

定while循環(huán)中下標(biāo)越界的條件以1,從而節(jié)省比較時(shí)

：1間，其二，保存要找值的副本，若查找時(shí)，遇到它，

表示查找不成功。若算法中不設(shè)立監(jiān)視哨R[0],程序

A花費(fèi)的時(shí)間將會(huì)增加，這時(shí)的算法可寫(xiě)為下面形式。

intseqsearch(nodeR[n+1],elemtypek)

{inti=n;

while(R[i].key!=k)&&(i>=1)i—;

returni;

\｝當(dāng)然上面算法也可以改成從表頭向后掃描，將監(jiān)視哨設(shè)在右

A邊，這種方法請(qǐng)讀者自己完成。

’3,順序查找性能分析

假設(shè)在每個(gè)位置查找的概率相等,即有p=l/n,由于查

找是從后往前掃描，則有每個(gè)位置的查找比較次數(shù)C『l,

Cn4=2,…，G=n,于是，查找成功的平均查找ASL=

口〃]"1>7-4-1、，

=Xpici=Z…+1)]=-，即它的時(shí)間復(fù)雜度為0(n)。

這就是說(shuō)；查找成功的平均比較次數(shù)約為表長(zhǎng)的一半。

I若k值不在表中，則必須進(jìn)行n+1次比較之后才能確定查

\找失敗。另處，從ASL可知，當(dāng)n較大時(shí)，ASL值較大,

Q查找的效率較低。

順序查找的優(yōu)點(diǎn)是算法簡(jiǎn)單，對(duì)表結(jié)構(gòu)無(wú)任何要求，無(wú)

論是用向量還是用鏈表來(lái)存放結(jié)點(diǎn)，也無(wú)論結(jié)點(diǎn)之間是

否按關(guān)鍵字有序或無(wú)序，它都同樣適用。順序查找的缺

點(diǎn)是查找效率低，當(dāng)n較大時(shí)，不宜采用順序查找，而

必須尋求更好的查找方法。

822二分查找

1.二分查找的基本思想

二分查找，也稱(chēng)折半查找，它是一種高效率的查找方法。

但二分查找有條件限制：要求表必須用向量作存貯結(jié)構(gòu)，

且表中元素必須按關(guān)鍵字有序（升序或降序均可）。我們不

妨假設(shè)表中元素為升序排列。二分查找的基本思想是：

首先將待查值K與有序表R[l]到R[n]的中點(diǎn)mid上的關(guān)鍵

字R[mid].key進(jìn)行比較，若相等，則查找成功；否則，若

R[mid].key>k,則在R[l]到R[mid-1]中繼續(xù)查找，若有

R[mid].key<k,則在R[mid+1]到R[n]中繼續(xù)查找。每通

過(guò)一次關(guān)鍵字的比較，區(qū)間的長(zhǎng)度就縮小一半，區(qū)間的

個(gè)數(shù)就增加一倍，如此不斷進(jìn)行下去，直到找到關(guān)鍵字

為K的元素；若當(dāng)前的查找區(qū)間為空（表示查找失?。?/p>

從上述查找思想可知，每進(jìn)行一次關(guān)鍵字比較，區(qū)間數(shù)

目增加一倍，故稱(chēng)為二分（區(qū)間一分為二），而區(qū)間長(zhǎng)

度縮小一半，故也稱(chēng)為折半（查找的范圍縮小一半）。

2.二分查找算法實(shí)現(xiàn)

intbinsearch（nodeR[n+1],elemtypek）

vl

{intlow=1,high=n;

while(low<=high)

{intmid=(low+high)/2;〃取區(qū)間中點(diǎn)

if(R[mid].key==k)returnmid;〃查找成功

elseif(R[mid].key>k)

high=mid-1;〃在左子區(qū)間中查找

elselow=mid+l;}〃在右子區(qū)間中查找

return0;}〃查找失敗

例如，假設(shè)給定有序表中關(guān)鍵字為

8,17,25,44,68,77,98,100,115,125,將查找K=17和K=120

的情況描述為圖8-1及圖8-2形式。

[817254468779810115125]

loWhigh

(a)初始情形

684498100115125

lowhighmid

(b)經(jīng)過(guò)一次比較后的情形

]687798100115125

Iowmidhigh

(c)經(jīng)過(guò)二次比較后的情形(R[mid].key=17)

圖8-1查找K=17的示意圖(查找成功)

17254468779810011512.5]

A

lowhigh

(a)初始情形

81725446[7,7981001151

midlowhigh

(b)經(jīng)過(guò)一次比較后的情形

8172544687798100115125]

midlowhigh

(c)經(jīng)過(guò)二次比較后的情形

8172544687798100115125]

肯midIowhigh

(d)經(jīng)過(guò)三次比較后的情形

1725447798100115125

highlowmid

（e）經(jīng)過(guò)四次比較后的情形（highvlow）

圖8-2查找K=120的示意圖（查找不成功）

,3.二分查找的性能分析

為了分析二分查找的性能，可以用二叉樹(shù)來(lái)描述二分查找

f|過(guò)程。把當(dāng)前查找區(qū)間的中點(diǎn)作為根結(jié)點(diǎn)，左子區(qū)間和右

I子區(qū)間分別作為根的左子樹(shù)和右子樹(shù)，左子區(qū)間和右子區(qū)

V間再按類(lèi)似的方法，由此得到的二叉樹(shù)稱(chēng)為二分查找的判

/定樹(shù)。例如，圖8-1給定的關(guān)鍵字序列

U8,17,25,44,68,77,98,100,115,125,的判定樹(shù)見(jiàn)圖8-3。

圖8-3具有10個(gè)關(guān)鍵字序列的二分查找判定樹(shù)

'從圖8-3可知，查找根結(jié)點(diǎn)68,需一次查找，查找17和

100,各需二次查找，查找8、25、77、115各需三次查

窯找，查找44、98、125各需四次查找。于是，可以得到

n結(jié)論：二叉樹(shù)第K層結(jié)點(diǎn)的查找次數(shù)各為k次(根結(jié)點(diǎn)為

第1層)，而第k層結(jié)點(diǎn)數(shù)最多為2-個(gè)。假設(shè)該二叉樹(shù)的

深度為h,則二分查找的成功的平均查找長(zhǎng)度為(假設(shè)

每個(gè)結(jié)點(diǎn)的查找概率相等)：

n

2h1

ASL=ZP￡=l/nyCi<l/n(l+2x2+3x2+...+hx2-)

i=1

因此，在最壞情形下，上面的不等號(hào)將會(huì)成立，并根據(jù)

二叉樹(shù)的性質(zhì)，最大的結(jié)點(diǎn)數(shù)n=2M,h=log2(n+l),于是

可以得到平均查找長(zhǎng)度ASL=(n+l)/nlog2(n+l)-lo該公式

可以按如下方法推出：

:設(shè)5=Z“2=20+2,2i+3.22+...+(h-l).2h-2+h.2h-i

<k=\

貝U2s=242.22+…+(h?2).2h-2+h/).2h-i+h.2h

“s=2s-s

=h.2七(20+21+22+...+2>2+2>1)

■

=h.2h-(2h-l)

=log2(n+l).(n+l)-n

所以，ASL=s/n=(n+l)/nlog2(n+l)-lo

當(dāng)n很大時(shí)，ASL^log2(n+l)-l可以作為二分查找成功

時(shí)的平均查找長(zhǎng)度，它的時(shí)間復(fù)雜度為0(1"2口)。

8.2.3索引查找

1.索引查找的思想

索引查找，又稱(chēng)分級(jí)查找，它既是一種查找方法，又是

一種存貯方法，稱(chēng)為索引存貯。它在我們的日常生活中

有著廣泛的應(yīng)用。例如，在漢語(yǔ)字典中查找某個(gè)漢字時(shí),

若知道某個(gè)漢字讀者，則可以先在音節(jié)表中查找到對(duì)應(yīng)

正文中的頁(yè)碼，然后再在正文中所對(duì)應(yīng)的頁(yè)中查出待查

的漢字；若知道該漢字的字形，但不知道讀者，則可以

先在部首表中根據(jù)字的部首查找到對(duì)應(yīng)檢字表中的頁(yè)碼,

再在檢字表中根據(jù)字的筆畫(huà)找到該漢字所在的頁(yè)碼。在

這里，整個(gè)字典就是索引查找的對(duì)象，字典的正文是字

典的主要部分，被稱(chēng)之為主表，而檢字表，部首表和音

節(jié)表都有是為了方便查找主表而建立的索引，所以被稱(chēng)

之為索引表。

.?腔二■在索引查找中，主表只有一個(gè)，其中包含的是待查找的

內(nèi)容，而索引表可以有多個(gè)，包含一級(jí)索引，二級(jí)索

引……，所需的級(jí)數(shù)可根據(jù)具體問(wèn)題而定。如剛才的利

用讀音查找漢字為一級(jí)索引，而利用字形查找漢字為二

n級(jí)索引（部首表一檢字表一漢字）。在此，我們僅討論

\：一級(jí)索引。

’索引查找是在線性表（主表）的索引存貯結(jié)構(gòu)上進(jìn)行的，

而索引存貯的基本思想是：首先將一個(gè)線性表（主表）按

照一定的規(guī)則分成若干個(gè)邏輯上的子表，并為每個(gè)子表分

別建立一個(gè)索引項(xiàng)，由所有這些索引項(xiàng)得到主表的一個(gè)索

引表，然后，可采用順序或鏈接的方法來(lái)存儲(chǔ)索引表和各

個(gè)子表。索引表中的每個(gè)索引項(xiàng)通常包含三個(gè)域：一是索

引值域，用來(lái)存儲(chǔ)標(biāo)識(shí)對(duì)應(yīng)子表的索引值，它相當(dāng)于記錄

的關(guān)鍵字，在索引表中由此索引值來(lái)唯一標(biāo)識(shí)一個(gè)索引項(xiàng)

（子表）；二是子表的開(kāi)始位置，用來(lái)存儲(chǔ)對(duì)應(yīng)子表的第

一個(gè)元素的存儲(chǔ)位置；三是子表的長(zhǎng)度，用來(lái)存儲(chǔ)對(duì)應(yīng)子

!表的元素個(gè)數(shù)。

例如，設(shè)有一個(gè)學(xué)校部分教師檔案表如表8-1所示，設(shè)

編號(hào)為主關(guān)鍵字，則該表可以用一個(gè)線性表L=_(金噢,

a3,a4,a59a6,a7?a89a95a10)來(lái)表示，其中正(iSign)表示第"立

教師的信息(包含有編號(hào)，姓名，部門(mén)，職稱(chēng))，而

它的索引表可以按部門(mén)進(jìn)行，也可以按職稱(chēng)進(jìn)行，按

部門(mén)的索引表中有4個(gè)子表，分別為：

計(jì)算機(jī)系J=(包/2閏3戶(hù)4)

電工系D=(a5,a65a7)

管理系6=但8擔(dān)9)

成教部C=(aio)

該4個(gè)子表示成一個(gè)索引表如表8-2所示。

表8-1教師檔案表表8-2按部門(mén)的索引表

編號(hào)姓名部門(mén)

職稱(chēng)indexstartlength

J001趙一計(jì)算機(jī)系教授

J04

J002錢(qián)二計(jì)算機(jī)系講師

D43

J003張三計(jì)算機(jī)系副教授

G72

J004李四計(jì)算機(jī)系助教

C91

D001王五電工系講師

D002孫六電工系助教

D003劉七電工系副教授

G001朱八管理系教授

G002楊九管理系講師

C001羅十成教部副教授

若按職稱(chēng)進(jìn)行索引，則得到的索引表中也有4個(gè)子表,

分別為：

Jiaosou=(a],a8)

FuJiaosou=(a3,a7,a10)

Jiangshi=(a2,a5,a9)

Zhiyiao=(a4,a6)

這時(shí)的主表用順序存貯不太方便，因相同職稱(chēng)的教師沒(méi)

有連在一起，故用鏈?zhǔn)酱鎯?chǔ)得到主表較方便。具體的存

貯如圖8-4所示。在圖8-4中，箭頭上面的數(shù)字表示該元

素在主表中的下標(biāo)位置（指針），每個(gè)子表中最后個(gè)元

素的指針為-1,表示為空指針。

07

教授a】a8.]

6

2a9

副教授3a7a?（）,_1

講師

35

助教a4

圖8-4按職稱(chēng)的鏈?zhǔn)酱尜A結(jié)構(gòu)

于是，可以得到如表8-3所示的職稱(chēng)索引表。

表8-3按職稱(chēng)的索引表

indexstartlength

教授02

副教授23

講師13

助教32

、從剛才的兩種索引表中，可以給出索引查找的基本思

想如下：

弟一步，在索引表中按index域查找所給值K1,這時(shí)可

得到子表起始位置start和長(zhǎng)度length,若找不到K1,結(jié)

束查找，表示查找不成功。第二步，在主表的start位置

開(kāi)始，長(zhǎng)度為length的范圍內(nèi)查找所給值K2,若找到，

查找不成功，否則，查找不成功。

例如，對(duì)于按部門(mén)的索引查找，主表可以用順序存貯，假設(shè)

K1="D”，“D”代電工系，K2="孫六”，則先在表8-2的索引

表中找到的index域?yàn)?D”的項(xiàng)，得到start=4,length=3,

然后從主表的第4個(gè)位置開(kāi)始(SPa5)找姓名為“孫六”的

人，則在主表的第5個(gè)位置可以找到，故查找成功。若假設(shè)

K1="D"，K2=“楊九”，則索引表的查找與上面相同，然后

在主表的第4個(gè)位置開(kāi)始查找，沒(méi)找到，進(jìn)入第5個(gè)位置查找,

還沒(méi)找到進(jìn)入第6位置查找，仍然沒(méi)找到，但查找的length=3,

既只允許3次查找，故查找不成功。若假設(shè)K1="F"，K2=”張

三”，則首先在索引表中就找不到“F”，故無(wú)需進(jìn)入主表進(jìn)

行查找，查找不成功。

J；：；’3.索引查找的性能分析

2"由于索引查找中涉及到兩方面查找，第一個(gè)是索引表的

r\查找，第二個(gè)是主表的查找，假設(shè)兩種查找都按順序查

\找方式進(jìn)行，則索引表的平均查找長(zhǎng)度為(m+l)/2,主表

7中的平均查找長(zhǎng)度為(s+1)/2,(m為索引表的長(zhǎng)度，S為

n主表中相應(yīng)子表的長(zhǎng)度)，則索引查找的平均查找長(zhǎng)度為:

\ASL=(m+l)/2+(s+1)/2o若假定每個(gè)子表具有相同的長(zhǎng)

度，而主表的長(zhǎng)度為n,則有n=m.s,這時(shí)當(dāng)s1；時(shí)，

U索引查找具有最小的平均查找長(zhǎng)度，即ASL=1亡o

A從該公式可以看出，索引查找的性能優(yōu)先順序*找，但

比二分查找要差，時(shí)間復(fù)雜度介于0(182口)?0(n)之間。

「824分塊查找

1.分塊查找的思想

分塊查找實(shí)際上就是一種索引查找，但查找的性能更優(yōu)

先于索引查找。原因是分塊查找的索引表是一個(gè)有序表,

故可以用二分查找來(lái)代替順序查找實(shí)現(xiàn)索引表的快速

查找。

具體實(shí)現(xiàn)如下：將一個(gè)含有n個(gè)元素的主表分成m個(gè)子表,

但要求子表之間元素是按關(guān)鍵字有序排列的，而子表中

元素可以無(wú)序的，然后建立索引表，索引表中索引域的

值用每個(gè)子表最大關(guān)鍵字代替，則可以按索引查找思想

找到表中元素。

例如，給定關(guān)鍵字序列如下：

"18,7,26,34,15,42,36,70,60,55,83,90,78,72,74,假設(shè)m=3,

2s=5,即將該序序分成3個(gè)子表，每個(gè)子表有5個(gè)元素，則

rI得到的主表和索引表如圖8-5所示。

01234567891011121314

18726341542367060558390787274

(a)15個(gè)關(guān)鍵字序列得到的主表

indexstartlength

3405

7055

90105

(b)按關(guān)鍵字序列遞增得到的索引表

圖8-5分塊查找的主表和索引表

廣二3.分塊杳找的性能分析

'分塊查找實(shí)際上就是索引查找，但分塊查找中索引的域

’的類(lèi)型與主表的關(guān)鍵字域的類(lèi)型相同，且索引表按索

了聲引域遞增(或遞減)有序，故它的平均查找長(zhǎng)度與索

I引查找接近，且優(yōu)于索引查找。

-8.3樹(shù)表查找

(8.3」二叉排序樹(shù)查找

號(hào)L什么是二叉排序樹(shù)

。二叉排序樹(shù)(BinarySortingTree),它或者是一棵空樹(shù),

A或者是一棵具有如下特征的非空二叉樹(shù)：

\(1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均

\小于根結(jié)點(diǎn)的關(guān)鍵字；

J(2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均

V大于等于根結(jié)點(diǎn)的關(guān)鍵字；

<(3)左、右子樹(shù)本身又都是一棵二叉排序樹(shù)。

2.二叉排序樹(shù)的數(shù)據(jù)類(lèi)型描述

和第六章類(lèi)似，可以用一個(gè)二叉鏈表來(lái)描述一棵二叉

排序樹(shù)，具體為：

structBtreenode

{elemtypedata;〃代表關(guān)鍵字

Btreenode*left/right;〃代表左、右孩子

}；

3.二叉排序樹(shù)的基本運(yùn)算

(1)二叉排序樹(shù)的插入

若二叉排序樹(shù)為空，則作為根結(jié)點(diǎn)插入，否則，若待

插入的值小于根結(jié)點(diǎn)值，則作為左子樹(shù)插入，否則作為

右子樹(shù)插入，算法描述為：

voidInsert(Btreenode*BST,elemtypeX)

{if(BST==NULL)

{Btreenode*p=newBtreenode;

p->data=X;

p->left=p->right=NULL;

BST=p;}

elseif(BST->data>=X)

Insert(BST->left,X);〃在左子樹(shù)中桿

入

elseInsert(BST->right,X);}〃在右子樹(shù)中打入

(2)二叉排序樹(shù)的建立

只要反復(fù)調(diào)用二叉排序樹(shù)的托入算法即可，算法描述

為：

Btreenode*Creat(intn)〃建立含有n個(gè)結(jié)點(diǎn)的二叉

排序樹(shù)

{Btreenode*BST=NULL;

for(inti=l;i〈=n;i++)

{cin?x;〃輸入關(guān)鍵字序列

Insert(BST,x);

)

returnBST;}

例如，結(jié)定關(guān)鍵字序列79,62,68,90,88,89,17,

5,100,120,生成二叉排序樹(shù)過(guò)程如圖8-6所示。（注:

二叉排序樹(shù)與關(guān)鍵字排列順序有關(guān)，排列順序不一樣,

得到的二叉排序樹(shù)也不一樣）

(a)(e)

⑴

圖8-6二叉排序樹(shù)的生成過(guò)程

4.二叉排序樹(shù)上的杳找

(1)二叉排序樹(shù)的查找思想

若二叉排樹(shù)為空，則查找失敗，否則，先拿根結(jié)點(diǎn)值與

待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大

于待查值，則進(jìn)入左子樹(shù)重復(fù)此步驟，否則，進(jìn)入右子

樹(shù)重復(fù)此步驟，若在查找過(guò)程中遇到二叉排序樹(shù)的葉子

結(jié)點(diǎn)時(shí)，還沒(méi)有找到待找結(jié)點(diǎn)，則查找不成功。

(2)二叉排序樹(shù)查找的算法實(shí)現(xiàn)

Btreenode*find(Btreenode*BST,elentypex)

〃在以BST為根指針的二叉排隊(duì)樹(shù)中查找值為x的結(jié)點(diǎn)

{if(BST==NULL)

returnNULL;〃查找失敗

else(

if(BST->data==x)〃查找成功

returnBST;

elseif(BST->data>x)〃進(jìn)入左子樹(shù)查找

returnfind(BST->left,x);

else〃進(jìn)入右子樹(shù)查找

returnfind(BST->right,x);}}

5.二叉排序樹(shù)杳找的性能分析

在二叉排序樹(shù)查找中，成功的查找次數(shù)不會(huì)超過(guò)二叉樹(shù)

的深度，而具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的深度，最好為

log2n,最壞為n。因此，二叉排序樹(shù)查找的最好時(shí)間復(fù)

雜度為O(log2n),最壞的時(shí)間復(fù)雜度為0(n),一般情形

下，其時(shí)間復(fù)雜度大致可看成O(log2n),比順序查找效

率要好，但比二分查找要差。

8.3.2平衡二叉樹(shù)查找

X.平衡二叉樹(shù)的概念

平衡二叉樹(shù)(balancedbinarytree)是由阿德?tīng)柹D維爾斯和

蘭迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，

所以又稱(chēng)為AVL樹(shù)。

<'若一棵二叉樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)的深度之差的絕

對(duì)值不超過(guò)1,則稱(chēng)這樣的二叉樹(shù)為平衡二叉樹(shù)。將該

結(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的值，稱(chēng)為該結(jié)點(diǎn)的

平衡因子(balancefactor)o也就是說(shuō)，一棵二叉排序樹(shù)

中，所有結(jié)點(diǎn)的平衡因子只能為0、1、-1時(shí)，則該二叉

排序樹(shù)就是一棵平衡二叉樹(shù)，否則就不是一棵平衡二叉

樹(shù)。如圖8-8所示二叉排序樹(shù)，是一棵平衡二叉樹(shù)，而

如圖8-9所示二叉排序樹(shù)，就不是一棵平衡二叉樹(shù)。

圖8-8一棵平衡二叉樹(shù)

圖8-9一棵非平衡二叉樹(shù)

二F一0共平衡一▽樹(shù)的平衡Xz卜壬甲

六二,若一棵二叉排序樹(shù)是平衡二叉樹(shù)，托入某個(gè)結(jié)點(diǎn)后,

可能會(huì)變成非平衡二叉樹(shù)，這時(shí)，就可以對(duì)該二叉

樹(shù)進(jìn)行平衡處理，使其變成一棵平衡二叉樹(shù)。處理

的原則應(yīng)該是處理與托入點(diǎn)最近的、而平衡因子又

比1大或比-1小的結(jié)點(diǎn)。下面將分四種情況討論平衡

■處理

（1）（L型的處理（左左型）

如圖8-10所示，在C的左孩子B上打入一個(gè)左孩子結(jié)點(diǎn)A,

使C的平衡因子由1變成了2,成為不平衡的二叉樹(shù)序樹(shù)。

這時(shí)的平衡處理為：將C順時(shí)針旋轉(zhuǎn)，成為B的右子樹(shù)，

而原來(lái)B的右子樹(shù)則變成C的左子樹(shù)，待托入結(jié)點(diǎn)A作為B

的左子樹(shù)。（注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該結(jié)點(diǎn)的平衡

因子）

(_2)LR型的處理(左右型)

如圖8-H所示，在C的左孩子A上打入一個(gè)右孩子B,

使的C的平衡因子由1變成了2,成為不平衡的二叉

排序樹(shù)。這是的平衡處理為：將B變到A與C之間,

使之成為L(zhǎng)L型，然后按第(1)種情形LL型處理。

r(3)RR型的處理(右右型)

如圖8-12所示，在A的右孩子B上打入一個(gè)右孩子C,使

A的平衡因子由-1變成-2,成為不平衡的二叉排序樹(shù)。

這時(shí)的平衡處理為：將A逆時(shí)針旋轉(zhuǎn)，成為B的左子樹(shù),

而原來(lái)B的左子樹(shù)則變成A的右子樹(shù)，待托入結(jié)點(diǎn)C成為

B的右子樹(shù)。

-2

平衡處理

A

0

圖8-12RR型平衡處理

(4)RL型的處理(右左型)

如圖8-13所示，在A的右孩子C上打入一個(gè)左孩子B,

使A的平衡因子由-1變成-2,成為不平衡的二叉排序

樹(shù)。這時(shí)的平衡處理為：將B變到A與C之間，使之

成為RR型，然后按第(3)種情形RR型處理。

-2

平衡處理

圖8-13RL型平衡處理

例8-2,給定一個(gè)關(guān)鍵字序列4,5,7,2,1,3,6,試生成一棵

平衡二叉樹(shù)。

分析：平衡二叉樹(shù)實(shí)際上也是一棵二叉排序樹(shù)，故可

以按建立二叉排序樹(shù)的思想建立，在建立的過(guò)程中，

若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建

成一棵平衡二叉樹(shù)。具體生成過(guò)程見(jiàn)圖8-14。

(a)插入4(b)插入5(c)插入7

iQ2

入2

(e)插入1

型

圖8-14平衡二叉樹(shù)的生成過(guò)程

3.平衡二叉樹(shù)的查找及性能分析

平衡二叉樹(shù)本身就是一棵二叉排序樹(shù)，故它的查找與二

叉排序樹(shù)完全相同。但它的查找性能優(yōu)于二叉排序樹(shù)，

不像二叉排序樹(shù)一樣，會(huì)出現(xiàn)最壞的時(shí)間復(fù)雜度0(n),

它的時(shí)間復(fù)雜度與二叉排序樹(shù)的最好時(shí)間復(fù)雜相同，都

為(Xkgn)。

:’例8-3,對(duì)例8-2給定的關(guān)鍵字序列4,5,7,2,1,3,6,試用二

叉排序樹(shù)和平衡二叉樹(shù)兩種方法查找，給出查找6的次

數(shù)及成功的平均查找長(zhǎng)度。

分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉

排序樹(shù)和平衡二叉樹(shù)都是唯一的。得到的平衡二叉樹(shù)見(jiàn)

圖8-14,得到區(qū)二叉排序樹(shù)見(jiàn)圖8-15。

圖8-15由關(guān)鍵字序列4,5,7,2,1,3,6生成的

二叉排序樹(shù)

從圖8-15的二叉排序樹(shù)可知，查找6需4次，平均查

找長(zhǎng)度ASL=(l+2+2+3+3+3+4)/7=18/7=2.57。

從圖8-14的平衡二叉樹(shù)可知，查找6需2次，平均查

找長(zhǎng)度

ASL=(l+2+2+3+3+3+3尸17/7=2.43。

從結(jié)果可知，平衡二叉樹(shù)的查找性能優(yōu)于二叉排

序樹(shù)。

8.4散列查找

立卡8.4.1基本概念

散列查找，也稱(chēng)為哈希查找。它既是一種查找方法，又

■是一種存貯方法，稱(chēng)為散列存貯。散列存貯的內(nèi)存存放

形式也稱(chēng)為散列表。

散列查找，與前面介紹的查找方法完全不同，前面介紹

的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而

實(shí)現(xiàn)的查找方法，而散列查找是通過(guò)構(gòu)造散列函數(shù)來(lái)得

到待查關(guān)鍵字的地址，按理論分析真正不需要用到比較

的一種查找方法。例如，要找關(guān)鍵字為k的元素，則只需

求出函數(shù)值H(k),H(k)為給定的散列函數(shù)，代表關(guān)

鍵字k在存貯區(qū)中的地址，而存貯區(qū)為一塊連續(xù)的內(nèi)存單

元，可用一個(gè)一維數(shù)組(或鏈表)來(lái)表示。

例8-4,假設(shè)有一批關(guān)鍵字序列18,75,60,43,54,90,46,

給定散列函數(shù)H(k)=k%13,存貯區(qū)的內(nèi)存地址從0到

15,則可以得到每個(gè)關(guān)鍵字的散列地址為：

H(18)=18%13=5

H(75)=75%13=10

H(60)=60%13=8

H(43)=43%13=4

H(54)=54%13=2

H(90)=90%13=12

H(46)=46%13=7

于是，根據(jù)散列地址，可以將上述7個(gè)關(guān)鍵字序列存貯

到一個(gè)一維數(shù)組HT(散列表)中，具體表示為：

0123456789101112131415

54431846607590

其中HT就是散列存貯的表，稱(chēng)為散列表。從散列表中

查找一個(gè)元素相當(dāng)方便，例如，查找75,只需計(jì)算出

H(75)=75%13=10,則可以在HT[10]中找到75。

上面討論的散列表是一種理想的情形，即每一個(gè)關(guān)鍵

字對(duì)應(yīng)一個(gè)唯一的地址。但是有可能出現(xiàn)這樣的情形,

兩個(gè)不同的關(guān)鍵字有可能對(duì)應(yīng)同一個(gè)內(nèi)存地址，這樣,

將導(dǎo)致后放的關(guān)鍵字無(wú)法存貯，我們把這種現(xiàn)象叫做

沖突(collision)o在散列存貯中，沖突是很難避免的,

除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比

較差，則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖

突的關(guān)鍵字互稱(chēng)為“同義詞”。

在散列存貯中，若發(fā)生沖突，則必須采取特殊的方法

來(lái)解決沖突問(wèn)題，才能使散列查找能順利進(jìn)行。雖然

沖突不可避免，但發(fā)生沖突的可能性卻與三個(gè)方面因

素有關(guān)。第一是與裝填因子口有關(guān)，所謂裝填因子是

指散列表中己存入的元素個(gè)數(shù)n與散列表的大小m的比

值，即a=n/m。當(dāng)a越小時(shí)，發(fā)生沖突的可能性越小，

a越大（最大為1）時(shí)，發(fā)生沖突的可能性就越大。但

是，為了減少?zèng)_突的發(fā)生，不能將a變得太小，這樣

將會(huì)造成大量存貯空間的浪費(fèi)，因此必須兼顧存儲(chǔ)空

間和沖突兩個(gè)方面。第二是與所構(gòu)造的散列函數(shù)有關(guān)

（前面己介紹）。第三是與解決沖突的方法有關(guān)，這些

內(nèi)容后面將再作進(jìn)一步介紹。

廣￡工38.4.2散列函數(shù)的構(gòu)造

’散列函數(shù)的構(gòu)造目標(biāo)是使散列地址盡可能均勻地分布在

勺士散列空間上，同時(shí)使計(jì)算盡可能簡(jiǎn)單。具體常用的構(gòu)造

方法有如下幾種：

；1.直接定址法

不可表示為H(k)=a.k+b,其中a、b均為常數(shù)。

J這種方法計(jì)算特別簡(jiǎn)單，并且不會(huì)發(fā)生沖突，但當(dāng)關(guān)

,\鍵字分布不連續(xù)時(shí)，會(huì)出現(xiàn)很多空閑單元，將造成大

*量存貯單元的浪費(fèi)。

2.數(shù)字分析法

對(duì)關(guān)鍵字序列進(jìn)行分析，取那些位上數(shù)字變化多的、頻率

大的作為散列函數(shù)地址。

例如，對(duì)如下的關(guān)鍵字序列：

430104681015355

430101701128352

430103720818350

430102690605351

430105801226356

通過(guò)對(duì)上述關(guān)鍵字序列分析，發(fā)現(xiàn)前5位相同，第6、

8、10位上的數(shù)字變化多些，若規(guī)定地址取3位，則散

列函數(shù)可取它的第6、8、10位。于是有：

H(430104681015355)=480

H(430101701128352)=101

H(430103620805351)=328

H(430102690605351)=296

H(430105801226356)=502

?二:一3?平方取中法

>|<'取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。這是一

7，.種比較常用的散列函數(shù)構(gòu)造方法，但在選定散列函數(shù)

"『時(shí)不一定知道關(guān)鍵字的全部信息，取其中哪幾位也不

!1一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一

位都相關(guān)，因此，可以使用隨機(jī)分布的關(guān)鍵字得到函

數(shù)地址。

（I如圖8-1；中，隨機(jī)給出一些關(guān)鍵字，并取平方后的第2到

A,4位為函數(shù)地址。_____________________________

2

關(guān)鍵字（關(guān)鍵字）函數(shù)地址

01000010000010

11001210000210

12001440000440

11601370400370

20614310541310

圖8-16利用平方取中法得到散列函數(shù)地址

4.折疊法

將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位

數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)

作為散列函數(shù)地址，稱(chēng)為折疊法。

例如，假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355,

則可以用4位為一組進(jìn)行疊加，即有5355+8101+1046

+430=14932,舍去高位，則有H(430104681015355)

=4932為該身份證關(guān)鍵字的散列函數(shù)地址。

5.除留余數(shù)法

該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以散列表長(zhǎng)度m所

得余數(shù)作為散列函數(shù)的地址，即有H(k)=k%m。

r除留余數(shù)法計(jì)算簡(jiǎn)單，適用范圍廣，是一種最常使用的

y!方法。這種方法的關(guān)鍵是選取較理想的m值，使得每一

個(gè)關(guān)鍵字通過(guò)該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址

1的概率都相等，從而盡可能減少發(fā)生沖突的可能性。一

般情形下，m取為一個(gè)素?cái)?shù)較理想，并且要求裝填因子

a最好是在0.6s0.9之間，所以m最好取1.1ns1.7n之間

11的一個(gè)素?cái)?shù)較好，其中口為散列表中待裝元素個(gè)數(shù)。

:'、8.4.3解決沖突的方法

》由于散列存貯中選取的散列函數(shù)不是線性函數(shù)，故不可避

《免地會(huì)產(chǎn)生沖突，下面給出常見(jiàn)的解決沖突方法。

\L開(kāi)放定址法

開(kāi)放定址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始,按照一定

Y的次序，從散列表中找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生

Q沖突的待托入關(guān)鍵字存儲(chǔ)到該單元中，從而解決沖突的

、發(fā)生。

1一二?.在開(kāi)放定址法中，散列表中的空閑單元（假設(shè)地址為K）

Lj'J:'不僅向散列地址為K的同義詞關(guān)鍵字開(kāi)放，即允許它們

,?、使用，而且還向發(fā)生沖突的其它關(guān)鍵字開(kāi)放（它們的

號(hào)屋散列地址不為K）,這些關(guān)鍵字稱(chēng)為非同義詞關(guān)鍵字。

例如，設(shè)有關(guān)鍵字序列14,27,40,15,16,散列函

I數(shù)為H（k）=k%13,則14,27,40的散列地址都為1,

V因此發(fā)生沖突，即14,27,40互為同義詞，這時(shí)，假

i\設(shè)處理沖突的方法是從沖突處順序往后找空閑位置，

V找到后放入沖突數(shù)據(jù)即可。則14放入第1個(gè)位置，27只

\\能放入第2個(gè)位置，40就只能放入第3個(gè)位置，接著往

/后有關(guān)鍵字15,16要放入散列表中，而15,16的散列

/地址分別為2和3,即15應(yīng)放入第2個(gè)位置，16應(yīng)放入第

A3個(gè)位置，而第2個(gè)位置己放入了27,第3個(gè)位置己放入

\\了40,故也發(fā)生沖突，但這時(shí)是非同義詞沖突，即15

\）和27、16和40相互之間是非同義詞。這時(shí)，解決沖突

V后，15應(yīng)放入第4個(gè)位置，16應(yīng)放入第5個(gè)位置。因此,

。在使用開(kāi)放定址法處理沖突的散列表中，地址為K的單

A元到底存儲(chǔ)的是同義詞中的一個(gè)關(guān)鍵字，還是非同義

.}詞關(guān)鍵字，這就要看誰(shuí)先占用它。

二:Ui在開(kāi)放定址法中，解決沖突時(shí)具體使用下面一些方法。

(1)線/陛探杳法

m假設(shè)散列表的地址為Osm-l,則散列表的長(zhǎng)度為m。若

一個(gè)關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1,

!d+2,…，m-1(當(dāng)達(dá)到表尾m-1時(shí)，又從0,1,2,....開(kāi)

始探查)等地址，直到找到一個(gè)空閑位置來(lái)裝沖突處的

)\關(guān)鍵字，將這一種方法稱(chēng)為線性探查法。假設(shè)發(fā)生沖突

U時(shí)的地址為d0=H(k),則探查下一位置的公式為4=((

最后將沖突位置的關(guān)鍵字存入地

(》\址i+l中)%。m(l<i<m-l),4

A例8-5給定關(guān)鍵字序列為19,14,23,1,68,20,84,27,

(\55,11,10,79,散到函數(shù)H(k)=k%13,散列表空間地

址為0si2,試用線性探查法建立散列存貯(散列表)結(jié)構(gòu)。

V得到的散列表如圖8-17所示

0123456789