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

\第8章查找.

ISJI^H

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

目錄

8.1查找的基本概念

8.1杳找的基本概念

查找，也稱為檢索。在我們?nèi)粘Ｉ钪校S處可見查找

的實例。如查找某人的地址、電話號碼；查某單位45歲

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

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

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

元素。例如，描述一個考生的信息，可以包含：考號、

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

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

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

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

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

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

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

或從關(guān)鍵字。

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

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

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

元素，則稱查找是成功的，此時查找的信息為給定整個

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

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

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

因為查找是對已存入計算機中的數(shù)據(jù)所進行的操作，所

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

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

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

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

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

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

存進行，則稱這樣的查找為內(nèi)查找；反之，若在查找過

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

查找。

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

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

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

有n個元素的表，查找成功時的平均查找長度可表示為

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

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

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

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

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

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

有n個元素的表，查找成功時的平均查找長度可表示為

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

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

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

8.2線性表的查找

8.2.1順序查找

L順序查找的基本思想

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

從表的一端開始，順序掃描線性表，依次將掃描到的

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

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

素，則查找失敗。

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

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

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

的表中元素可以是無序的。

F面以順序表的形式來描述算法。

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

constintn=maxn〃口為表的最大長度

structnode

{...

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

)；

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

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

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

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

returni;}

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

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

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

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

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

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

A花費的時間將會增加，這時的算法可寫為下面形式。

intseqsearch(nodeR[n+1],elemtypek)

{inti=n;

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

returni;

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

A邊，這種方法請讀者自己完成。

’3,順序查找性能分析

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

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

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

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

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

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

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

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

Q查找的效率較低。

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

論是用向量還是用鏈表來存放結(jié)點，也無論結(jié)點之間是

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

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

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

822二分查找

1.二分查找的基本思想

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

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

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

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

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

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

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

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

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

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

為K的元素；若當(dāng)前的查找區(qū)間為空（表示查找失敗）。

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

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

度縮小一半，故也稱為折半（查找的范圍縮小一半）。

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

intbinsearch（nodeR[n+1],elemtypek）

vl

{intlow=1,high=n;

while(low<=high)

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

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)過一次比較后的情形

]687798100115125

Iowmidhigh

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

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

17254468779810011512.5]

A

lowhigh

(a)初始情形

81725446[7,7981001151

midlowhigh

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

8172544687798100115125]

midlowhigh

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

8172544687798100115125]

肯midIowhigh

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

1725447798100115125

highlowmid

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

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

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

為了分析二分查找的性能，可以用二叉樹來描述二分查找

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

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

V間再按類似的方法，由此得到的二叉樹稱為二分查找的判

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

U8,17,25,44,68,77,98,100,115,125,的判定樹見圖8-3。

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

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

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

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

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

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

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

每個結(jié)點的查找概率相等)：

n

2h1

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

i=1

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

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

可以得到平均查找長度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很大時，ASL^log2(n+l)-l可以作為二分查找成功

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

8.2.3索引查找

1.索引查找的思想

索引查找，又稱分級查找，它既是一種查找方法，又是

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

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

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

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

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

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

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

這里，整個字典就是索引查找的對象，字典的正文是字

典的主要部分，被稱之為主表，而檢字表，部首表和音

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

之為索引表。

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

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

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

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

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

\：一級索引。

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

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

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

別建立一個索引項，由所有這些索引項得到主表的一個索

引表，然后，可采用順序或鏈接的方法來存儲索引表和各

個子表。索引表中的每個索引項通常包含三個域：一是索

引值域，用來存儲標(biāo)識對應(yīng)子表的索引值，它相當(dāng)于記錄

的關(guān)鍵字，在索引表中由此索引值來唯一標(biāo)識一個索引項

（子表）；二是子表的開始位置，用來存儲對應(yīng)子表的第

一個元素的存儲位置；三是子表的長度，用來存儲對應(yīng)子

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

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

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

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

教師的信息(包含有編號，姓名，部門，職稱)，而

它的索引表可以按部門進行，也可以按職稱進行，按

部門的索引表中有4個子表，分別為：

計算機系J=(包/2閏3戶4)

電工系D=(a5,a65a7)

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

成教部C=(aio)

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

表8-1教師檔案表表8-2按部門的索引表

編號姓名部門

職稱indexstartlength

J001趙一計算機系教授

J04

J002錢二計算機系講師

D43

J003張三計算機系副教授

G72

J004李四計算機系助教

C91

D001王五電工系講師

D002孫六電工系助教

D003劉七電工系副教授

G001朱八管理系教授

G002楊九管理系講師

C001羅十成教部副教授

若按職稱進行索引，則得到的索引表中也有4個子表,

分別為：

Jiaosou=(a],a8)

FuJiaosou=(a3,a7,a10)

Jiangshi=(a2,a5,a9)

Zhiyiao=(a4,a6)

這時的主表用順序存貯不太方便，因相同職稱的教師沒

有連在一起，故用鏈?zhǔn)酱鎯Φ玫街鞅磔^方便。具體的存

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

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

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

07

教授a】a8.]

6

2a9

副教授3a7a?（）,_1

講師

35

助教a4

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

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

表8-3按職稱的索引表

indexstartlength

教授02

副教授23

講師13

助教32

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

想如下：

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

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

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

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

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

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

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

表中找到的index域為"D”的項，得到start=4,length=3,

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

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

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

在主表的第4個位置開始查找，沒找到，進入第5個位置查找,

還沒找到進入第6位置查找，仍然沒找到，但查找的length=3,

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

三”，則首先在索引表中就找不到“F”，故無需進入主表進

行查找，查找不成功。

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

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

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

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

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

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

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

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

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

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

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

「824分塊查找

1.分塊查找的思想

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

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

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

查找。

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

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

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

值用每個子表最大關(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個子表，每個子表有5個元素，則

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

01234567891011121314

18726341542367060558390787274

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

indexstartlength

3405

7055

90105

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

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

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

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

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

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

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

-8.3樹表查找

(8.3」二叉排序樹查找

號L什么是二叉排序樹

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

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

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

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

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

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

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

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

和第六章類似，可以用一個二叉鏈表來描述一棵二叉

排序樹，具體為：

structBtreenode

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

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

}；

3.二叉排序樹的基本運算

(1)二叉排序樹的插入

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

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

右子樹插入，算法描述為：

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);〃在左子樹中桿

入

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

(2)二叉排序樹的建立

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

為：

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

排序樹

{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,生成二叉排序樹過程如圖8-6所示。（注:

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

得到的二叉排序樹也不一樣）

(a)(e)

⑴

圖8-6二叉排序樹的生成過程

4.二叉排序樹上的杳找

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

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

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

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

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

結(jié)點時，還沒有找到待找結(jié)點，則查找不成功。

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

Btreenode*find(Btreenode*BST,elentypex)

〃在以BST為根指針的二叉排隊樹中查找值為x的結(jié)點

{if(BST==NULL)

returnNULL;〃查找失敗

else(

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

returnBST;

elseif(BST->data>x)〃進入左子樹查找

returnfind(BST->left,x);

else〃進入右子樹查找

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

5.二叉排序樹杳找的性能分析

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

的深度，而具有n個結(jié)點的二叉排序樹的深度，最好為

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

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

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

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

8.3.2平衡二叉樹查找

X.平衡二叉樹的概念

平衡二叉樹(balancedbinarytree)是由阿德爾森―維爾斯和

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

所以又稱為AVL樹。

<'若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕

對值不超過1,則稱這樣的二叉樹為平衡二叉樹。將該

結(jié)點的左子樹深度減去右子樹深度的值，稱為該結(jié)點的

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

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

排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉

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

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

圖8-8一棵平衡二叉樹

圖8-9一棵非平衡二叉樹

二F一0共平衡一▽樹的平衡Xz卜壬甲

六二,若一棵二叉排序樹是平衡二叉樹，托入某個結(jié)點后,

可能會變成非平衡二叉樹，這時，就可以對該二叉

樹進行平衡處理，使其變成一棵平衡二叉樹。處理

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

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

■處理

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

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

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

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

而原來B的右子樹則變成C的左子樹，待托入結(jié)點A作為B

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

因子）

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

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

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

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

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

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

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

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

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

而原來B的左子樹則變成A的右子樹，待托入結(jié)點C成為

B的右子樹。

-2

平衡處理

A

0

圖8-12RR型平衡處理

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

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

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

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

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

-2

平衡處理

圖8-13RL型平衡處理

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

平衡二叉樹。

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

以按建立二叉排序樹的思想建立，在建立的過程中，

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

成一棵平衡二叉樹。具體生成過程見圖8-14。

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

iQ2

入2

(e)插入1

型

圖8-14平衡二叉樹的生成過程

3.平衡二叉樹的查找及性能分析

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

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

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

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

為(Xkgn)。

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

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

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

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

排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見

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

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

二叉排序樹

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

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

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

找長度

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

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

序樹。

8.4散列查找

立卡8.4.1基本概念

散列查找，也稱為哈希查找。它既是一種查找方法，又

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

形式也稱為散列表。

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

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

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

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

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

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

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

元，可用一個一維數(shù)組(或鏈表)來表示。

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

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

15,則可以得到每個關(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個關(guān)鍵字序列存貯

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

0123456789101112131415

54431846607590

其中HT就是散列存貯的表，稱為散列表。從散列表中

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

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

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

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

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

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

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

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

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

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

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

來解決沖突問題，才能使散列查找能順利進行。雖然

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

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

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

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

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

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

將會造成大量存貯空間的浪費，因此必須兼顧存儲空

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

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

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

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

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

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

方法有如下幾種：

；1.直接定址法

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

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

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

*量存貯單元的浪費。

2.數(shù)字分析法

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

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

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

430104681015355

430101701128352

430103720818350

430102690605351

430105801226356

通過對上述關(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ù)

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

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

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

數(shù)地址。

（I如圖8-1；中，隨機給出一些關(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ù)可以不同)，然后取這幾部分的疊加和(舍去進位)

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

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

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

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

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

5.除留余數(shù)法

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

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

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

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

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

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

般情形下，m取為一個素數(shù)較理想，并且要求裝填因子

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

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

:'、8.4.3解決沖突的方法

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

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

\L開放定址法

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

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

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

、發(fā)生。

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

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

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

號屋散列地址不為K）,這些關(guān)鍵字稱為非同義詞關(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互為同義詞，這時，假

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

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

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

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

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

A3個位置，而第2個位置己放入了27,第3個位置己放入

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

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

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

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

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

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

二:Ui在開放定址法中，解決沖突時具體使用下面一些方法。

(1)線/陛探杳法

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

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

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

始探查)等地址，直到找到一個空閑位置來裝沖突處的

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

U時的地址為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