第九章查找教學(xué)課件

人第冼漳查找學(xué)習(xí)提示

V反*教學(xué)目的

1、理解查找表的定義、分類和各類的特點。

2、熟練掌握順序查找，二分查找和索引查找的方法，并

能靈活應(yīng)用；

3、熟練掌握二叉排序樹的概念和有關(guān)運算的構(gòu)造方法；

4、熟練掌握哈希表、哈希函數(shù)的構(gòu)造方法、以及處理沖

突的方法。

5、熟練掌握按定義查找方法的等概率情況下查找成功時

的平均查找長度，理解哈希表在查找不成功時的平均查

找長度的計算方法。

求教學(xué)重點

順序查葩和二分查找的方法及實現(xiàn)，索引表的定義、索引查

球的方濤及券現(xiàn)"哈建春奧定義，利陵留余壑達根造嗆

希函教的方法，利用陽性探查法和鏈接H法處理沖突為方法;

||率教學(xué)難點pH

二叉排序樹的刪除操作、平衡二叉樹、B樹

」第冼漳查找綱要

長東9.1概述

東9.2靜態(tài)查找表

次9.2.1順序查找

力922折半查找

次923分塊查找（索引順序查找）

求9.3動態(tài)查找表

^9.3.1二叉排序樹

次932高度平衡的二叉排序樹

求9.4哈希表（哈希表）

次9?4?1哈希表

^9.4.2哈希函數(shù)的構(gòu)造方法

次9.4.3解決沖突的方法

，I\

」第冼漳查找9.1概述

六9」」查找的基本概念

查找：在具有相同類型的記錄構(gòu)成的集合中找出滿足

給定條件的記錄。

查找的結(jié)果：若在查找集合中找到了與給定值相匹配

的記錄,則稱查找成功；否則，稱查找失敗。

學(xué)

姓名

號課程成績

王文

o1洪

數(shù)據(jù)結(jié)構(gòu)75

o2李紅

數(shù)據(jù)結(jié)構(gòu)90

謝武

o3軍

O4張輝數(shù)據(jù)結(jié)構(gòu)52

me結(jié)構(gòu)82

」浮漳查找9.1概述

六9.L1查找的基本概念

查找結(jié)構(gòu)：面向查找操作的數(shù)據(jù)結(jié)構(gòu)，即查找基于的

I數(shù)據(jù)結(jié)構(gòu)。

I查找結(jié)構(gòu)I—I查找方法

集合中元素之間不存在明顯的組織規(guī)律，不便查找。

II「線性表_一

集合=>Y樹表

<哈希表

」第冼漳查找9.1概述

^9.1.1查找的基本概念

本章討論的查找結(jié)構(gòu)：

線性表：適用于靜態(tài)查找，主要采用順序查找技術(shù)、

折半查找技術(shù)。

樹表：適用于動態(tài)查找，主要采用二叉排序樹的查找

技術(shù)。

哈希表：靜態(tài)查找和動態(tài)查找均適用，主要采用哈希

技術(shù)。

第冼漳查找9.1概述

.1.1查找的基本概念

靜態(tài)查找：不涉及插入和刪除操作的查找，此類查

找表稱為靜態(tài)查找表?！?/p>

動態(tài)查找：涉及插入和刪除操作的查找，此類查找

表稱為動態(tài)查找表。

靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對其進行

查找，而不進行插入和刪除操作，或經(jīng)過一段時間的

查找之后，集中地進行插入和刪除等修改操作；

動態(tài)查找適用于：查找與插入和刪除操作在同一個階

段進行，例如當查找成功時，要刪除查找到的記錄3

當查找不成功時，要插入被查找的記錄。」八弓

」第通漳查找9.1概述

^9.1.1查找的基本概念

本查找表的常用操作：

1、查詢某個“特定的”數(shù)據(jù)元素是否在查找表

中。

2、0檢索某個“特定的”數(shù)據(jù)元素的各種屬性。

3、在查找表中插入一個數(shù)據(jù)元素。

4、從查找表中刪去某個數(shù)據(jù)元素。

」第冼漳查找

9.1概述

個％1.1查找的基本概念

關(guān)鍵碼：可以標識一個記錄的某個數(shù)據(jù)項。

鍵值：關(guān)鍵碼的值。

主關(guān)鍵碼：可以唯一地標識一個記錄的關(guān)鍵碼。

次關(guān)鍵碼：不能唯一地標識一個記錄的關(guān)鍵碼。

姓名

學(xué)

號課程成績

王文

o1洪

數(shù)據(jù)結(jié)構(gòu)75

o2李紅

數(shù)據(jù)結(jié)構(gòu)

謝武90

o3軍

O4張輝數(shù)據(jù)結(jié)構(gòu)52

數(shù)據(jù)結(jié)構(gòu)82

」第冼漳查找LrtTT、、

9.1概述

六9.L1查找的基本概念

求基于關(guān)鍵碼的查找概念--根據(jù)給定的某個值X,

在含有n個數(shù)據(jù)元素的查找表中找出關(guān)鍵碼等于

給定值x的記錄或數(shù)據(jù)元素，若找到，則查找成功,

輸出該元素在表中的位置或該元素信息，否則查

找失敗，輸出查找失敗的信息。

姓名

學(xué)

號專業(yè)成績

王文

o1洪

計算科學(xué)75

o2李紅

計算科學(xué)90

謝武

o3軍

計算科學(xué)

O4張輝52

計算科學(xué)62

■使用基于關(guān)鍵碼的查找，查找結(jié)果應(yīng)是惟一的。

」第冼漳查找9.1概述

S查找的基本概念

求但在實際應(yīng)用時，查找條件是多方面的（但查找

結(jié)果可能不惟一）:

我屬性查找

次精確匹配查找：查找關(guān)鍵字值（屬性值）與

特定值匹配的記錄。

次模糊查找

次范圍查找：檢索關(guān)鍵字值在某個范圍內(nèi)的所

有記錄

I次組合查找

求以下均楨用關(guān)鍵碼查找，當數(shù)據(jù)對象只有一個數(shù)

據(jù)項時（如整數(shù)對象），其關(guān)鍵碼即為該數(shù)據(jù)對

象的值

■

」第冼漳查找9.1概述

^9.1.2查找算法的性能

|查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。

您關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？

⑴算法；

⑵問題規(guī)模；

⑶待查關(guān)鍵碼在查找集合中的位置；

⑷查找頻率。

I番及頻率與算法無關(guān)，取決于具體應(yīng)用。1

通常假設(shè)Pj是已知的。,

」第冼漳查找9.1概述

31.2查找算法的性能

|查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。

質(zhì)同一查找集合、同一查找算法，關(guān)鍵碼的比較

"”次數(shù)與哪些因素有關(guān)呢？

查找算法的時間復(fù)雜度是問題規(guī)?！ê痛殛P(guān)鍵碼

在查找集合中的位置A的函數(shù)，記為7(",k)o

第冼漳查找概述

—，'一9.1

平均查找長度：將查找算法進行的關(guān)鍵碼的比較次數(shù)

的數(shù)學(xué)期望值定義為平均查找長度。對于查找成功的

情況，計算公式為:

ASL=EPfci

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

Pi:查找第，個記錄的概率；一

卬查找第i個記錄所需的關(guān)鍵碼的比較次數(shù)。

結(jié)論：q取決于算法；P,與算法族決于具體應(yīng)用0|

如物是已足的，則度只是問題規(guī)模的函姆A

」第冼漳查找

9.2靜態(tài)查找表

飛序查找（線性查找）

基本思想：從線性表的一端向另一端逐個將關(guān)鍵碼與

給定值進行比較，若相等，則查找成功，給出該記錄

在表中的位置；若整個表檢測完仍未找到與給定值相

等的關(guān)鍵碼，則查找失敗，給出失敗信息。

例：查找k=35

0123456789

10152461235409855

%%%%

■二次數(shù)=Z

」第冼漳查找

9.2靜態(tài)查找表

卡查找表用順序表存儲結(jié)構(gòu)

#defineMaxSize30〃查找表最大尺寸

typedefintElemType;〃查找數(shù)據(jù)的類型

typedefstruct{〃元素的結(jié)構(gòu)

ElemTypekey;〃關(guān)鍵碼域

ElemTypeother;〃其他數(shù)據(jù)域

}ListNode;

typedefstruct{//查找表類型定義

ListNodeelem[MaxSize];//數(shù)據(jù)存儲數(shù)組

intlength;//數(shù)組當前長度

}SSList香

1!\

第冼漳查找9.2靜態(tài)查找表

次順序查找(線性查找)

，

\1intSqSearchl(SSList&L*,intkey)

i=L.length;

；while(i>0&&L.elem[i].key!=key)

l|卜-；

，returni;

1/\

」第冼漳查找

9.2靜態(tài)查找表

飛進的順序查找

基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放

在查找方向的盡頭處，免去了在查找過程中每一次比

較后都要判斷查找位置是否越界，從而提高查找速度

例：查找k=35

0123456789

3510152461235409855

tztztztz

哨兵

查找方向------,我A

第冼漳查找9.2靜態(tài)查找表

?:進的順序查找\.

基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放

在查找方向的盡頭處，免去了在查找過程中每一次比

較后都要判斷查找位置是否越界，從而提高查找速度

例：查找k=25

0123456789

2510152461235409855

tztztztztztztztztztz

查找方向

人第冼漳查找9.2靜態(tài)查找表

打改進的順序查找

intLinearSearch(SSTableLintkey){

L.elem[O].key=key;〃作為卷9制搜索自動結(jié)束的

“監(jiān)視哨”使用

i=L.length;

While(L.elem[i].key!=key)i-〃從后往前找,找

不到時，i為0

returni;

」第冼漳查找9.2靜態(tài)查找表

大性能分析

順序查找的平均查找長度

nn

ASLsucc=EPiCi-（ZPi=I）

在等概率情形,Pi=l/%i=l,2,則

1111n(n+1)n+1

ASL=V—(n-i+1)=——?-------------=--------

SUCC/J'

n22

i=in

在查找不成功情形,ASLunsucc=n+1.

」第冼漳查找9.2靜態(tài)查找表

去順序查找的優(yōu)點：

I算法簡單而且使用面廣。k

?對表中記錄的存儲沒有任何要求，順序存儲和鏈接

存儲均可；

A對表中記錄的有序性也沒有要求，無論記錄是否按

關(guān)鍵碼有序均可。

順序查找的缺點：

A平均查找長度較大，特別是當待巧找集合中元素較

多時，查找效率較低。

A對于線性鏈表，只能進行順序查找。

第冼漳查找9.2靜態(tài)查找表

☆9.2.2折半查找、

使用條件：

A線性表中的記錄必須按關(guān)鍵碼有序（稱為有序表）；

?線性表必須采用順序存儲。

基本思想：在有序表中，取中間記錄作為比較對象，

若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若

給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半

區(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在

中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直

到查找成功，或所查找的區(qū)域無記錄，查找失敗。

人第冼漳查找9.2靜態(tài)查找表

卡

折半查找的基本思想

t

In.....................‘midT1mid,fnid+1%]

-----V-----'

如果h%以如果A>%〃

查找左半?yún)^(qū)查找右半?yún)^(qū)

mid=L(low+high)/2j

」第冼漳查找

9.2靜態(tài)查找表

六例123456789

五|-1|0I1I3|4|6|8|10|12

查找Howmid||6||high

5678

681012

mid=L(low+high)/2j

lowmid||||high

5

66

/J

lowmidhigh

查找成功的例子

」第冼漳查找9.2靜態(tài)查找表

卡123456789

區(qū)|-1|0I1I3|4|6|8|10|12

查找|lowmid]|high

5678

681012

lowmid115]I叫“

5

l,ow/mtid\h.ighh

查找失敗的例子.殺力、

*一

」第通漳查找9.2靜態(tài)查找表

卡9.2.2折半查找

算法步驟??(偽代碼)

①low=l；high=R.length；〃設(shè)置初始區(qū)間

②當low>high時，返回查找失敗信息〃表空，查找失

敗

③low<high,mid=(low+high)/2;〃取中點

乩若乂〈&610111[1111(1]?1<0丫，high=mid-1；轉(zhuǎn)②〃查

找在左半?yún)^(qū)進行

b.若X>R.elem[mid].key,low=mid+l；轉(zhuǎn)②〃查

找在右半?yún)^(qū)進行

c.若x==R.elem[mid].key,返回數(shù)據(jù)元素在表中

位置〃查找成功上

第冼漳查找9.2靜態(tài)查找表

去9.2.2折半查找

算法如下：

intSearch_Bin(SSListR,intX){

low=l;high=R.length;〃上、卞界初始化

while(low<=high)

{mid=L(Iow+high)/2」；//區(qū)間中間元素的位置

if(X==R.elem[mid].key)

returnmid;//我到該元素

else

{if(X<R.elem[mid].Key)

high=mid-l;〃左縮查找區(qū)間

elselow=mid+l;//右縮查找區(qū)間

}一

return0;//表中不存在待查兀素與匕

}//Search_Bin'

」第通漳查找9.2靜態(tài)查找表

折半查找判定樹

判定樹：折半查找的過程可以用二叉樹來描述，樹中

的每個結(jié)點對應(yīng)有序表中的一個記錄，結(jié)點的值為該

記錄在表中的位置。通常稱這個描述折半查找過程的

二叉樹為折半查找判定樹，簡稱判定樹。

第冼漳查找9.2靜態(tài)查找表

_

際半查找判定樹的構(gòu)造方法

L⑴當〃=()時，折半查找判定樹為空；

⑵當〃>0時，折半查找判定樹的根結(jié)點是有序表中

|序號為mid=(n+l)/2的記錄，根結(jié)點的左子樹是與有

序表r[l]?r[mid-1]相對應(yīng)的折半查找判定樹，根結(jié)

U點的右子樹是與r[mid+l]?r[n]相對應(yīng)的折半查找判

定樹。

第決漳查找9.2靜態(tài)查找表

」第通漳查找9.2靜態(tài)查找表

☆折半查找性能分析

具有〃個結(jié)點的折半查找判定樹的深度為［logzT+i。

查找成功：在表中查找任一記錄的過程，即是折半查

找判定樹中從根結(jié)點到該記錄結(jié)點的路徑，和給定值

的比較次數(shù)等于該記錄結(jié)點在樹中的層數(shù)。

查找不成功：查找失敗的過程就是走了一條從根結(jié)

點到外部結(jié)點的路徑，和給定值進行的關(guān)鍵碼的比

較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。

」第冼漳查找9.2靜態(tài)查找表

卡123456789

」第冼漳查找9.2靜態(tài)查找表

力^習(xí)已知有序表(5,13,19,21,37,56,64,75,

80,88,92),試寫出用折半查找法在表中查找21的查

找過程,并畫出它的判定樹，求出查找成功和不成功時

的ASL

123456891011

第通漳查找

—，'一9.2靜態(tài)查找表

內(nèi)|生能分析

/1234567891011

第冼漳查找9.2靜態(tài)查找表

六923分塊查找(索引順序查找)

求算法思想

次用裝笳存放待查記錄,每個數(shù)據(jù)元素至少含有

關(guān)鍵字域

次建立索引表，每個索引表結(jié)點含有最大關(guān)鍵字

域和指向本塊第一個結(jié)點的指針

南查找過程

求將表分成幾塊，塊內(nèi)可有序也可無序，但塊間有

序；

次(1)先確定待查記錄所在塊

次⑵再在塊內(nèi)順序查找待查元素

本適用條件：分塊有序表

求一般適用于數(shù)據(jù)量比較大的查找處理六

但

1!'

」第冼漳查找

9.2靜態(tài)查找表

卡

索引表：有序查找

瓦據(jù)塊；根據(jù)元素的排列情況采用順序或有序查找

」第冼漳查找9.2靜態(tài)查找表

六南分塊查找方法評價

ASLbs=Lb+L

其中：4——查找索引表確定所在塊的平均查找長度

?！趬K中查找元素的平均查找長度

ns

ASL二+—

log2（一+D

2s2

n—-表的長度S—一塊的大小（長度為n的表均勻地分

成b塊，每塊含有s個記錄）

分塊查找的效率介于順序查找和折半查找之間，在

數(shù)據(jù)量較大的情況下，分塊查找更有效

缺點：在進行數(shù)據(jù)塊劃分時，需了解數(shù)據(jù)元素的先以

布情況*'

」第冼漳查找9.2靜態(tài)查找表

查找方法比較

順序查找折半查找分塊查找

ASL最大最小兩者之間

表結(jié)構(gòu)有序表、無序菜t有序表分塊有序表

存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)

線性鏈表線性鏈表

」第冼漳查找9.3動態(tài)查找表

☆

南靜態(tài)查找表一旦生成后，所含元素是固定

不變的，而動態(tài)查找表則可經(jīng)插入、刪除

運算而不斷改變。

求特點：表結(jié)構(gòu)本身是在查找過程中動態(tài)生

成的，即對于給定值X,若表中存在其關(guān)鍵

碼等于X的記錄，則查找成功返回，否則插

入關(guān)鍵碼等于X的記錄。

1X

?第冼漳查找9.3.1二叉排序樹

十一、定義

'二叉排序樹或者是一棵空樹，或者是具有

下列性質(zhì)的二叉樹：

■每個結(jié)點都有一個作為查找依據(jù)的關(guān)鍵碼

（key）,所有結(jié)點的關(guān)鍵碼互不相同。

■左子樹（如果存在）上所有結(jié)點

的關(guān)鍵葩都小于根結(jié)點的關(guān)鍵

碼。

■W子樹（如果存在）上所有結(jié)點

的關(guān)鍵葩都大于根結(jié)點的關(guān)鍵

碼。

■史子樹和右子樹也是二叉排序

Wo

?第冼漳查找9.3.1二叉排序樹

二叉排序樹非二叉排序樹

按中序遍歷：

10,42,45,55,58,63,67,70,83,9。

_A--A.

「中序遍歷二叉排序樹可以得到一個按關(guān)鍵碼直序?qū)煞Q

」第通漳查找

9.3.1二叉排序樹

☆二、二叉排序樹的存儲結(jié)構(gòu)

I以二叉鏈表形式存儲，其類型描述如下：

typedefcharElemType;〃樹結(jié)點數(shù)據(jù)類型

typedefstructnode{〃查找樹結(jié)點定義

ElemTypedata;

structnode*lChild,*rChild;

}BstNode;

typedefBstNode*BiTree;//二叉排序樹定義

U一A

1r\

人第冼漳查找9.3.1二叉排序樹

長三、二叉排序樹上的查找

在二叉排序樹上進行查找，是一個從根結(jié)

點開始，沿某一個分支逐層向下進行比較判

等的過程。它可以是一個遞歸的過程。

查找28查找45

查找失敗查找成功

????

(2/I0K):

第冼漳查找9.3.1二叉排序樹

長二叉排序樹的查戒

j?查找成功時檢測指針停留在樹中某個結(jié)點。

?查找不成功時檢測指針停留在某個外結(jié)點

（失敗結(jié)點）。

第冼漳查找9.3.1二叉排序樹

六二叉排序樹的查找

I在二叉排序樹中查找給定值k的過程是：

(^root是空淤-

(2)若k=root-〉data,則查找成功；否則

(3)若k<root->data,則在root的左子樹上查找；否則

U⑷在root的右子樹上查找。JL]

上述過程一直持續(xù)到k被找到或者待查找的子樹為

空，如果待查找的子樹為空，則查找失敗。

第冼漳查找9.3.1二叉排序樹

☆*二叉排序樹的查找算法

BiTreeSearchBST(BiTreeT,KeyTypekey)

L{〃二叉排序樹用二叉鏈表存儲。在根指針T所指二叉排序樹

中遞歸地查找

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

elseif(key<T->data.key)

return(SearchBST(T->1child,key));

elsereturn(SearchBST(T->rchild,key))

}//SearchBST

11二叉排序樹的查找效率在于只需查找兩個子樹之一。卜

」第冼漳查找

9.3.1二叉排序樹

六二叉排序樹查找性能分析

考慮如下兩種不同插入次序的序列構(gòu)成的二叉排序樹:

40,24,12,37,5512,24,37,40,55

含有n個結(jié)點的二叉排序樹不惟一，即二叉排序樹上

的查找長度不僅與結(jié)點數(shù)n有關(guān),

生成過程有關(guān)

士浮漳查找9.3.1二叉排序樹

*FWW查找性能分析—三

插入次序分別為：

顯然，第I層結(jié)點需比較I次。在等概率的前提下，：55

上述兩圖的查找成功時的平均查找長度為：J

n

￡p.c.=(1+2x2+3x2)75=2.2(左圖)

n

EPG(1+2+3+4+5)/5=3(右圖

Z=1

第冼漳查找9.3.1二叉排序樹

次由上例分析易知：、

在二叉排序樹中進行查找的平均查找長度和二叉樹

的形態(tài)有關(guān)，即，

最壞：（n+l）/2（單支樹）

最好：10g2ll（形態(tài)勻稱，與二分查找的判定樹相似）

一第次漳查找9.3.1二叉排序樹

長二叉排序樹的插入

分析：若二叉排序樹為空樹，則新插入的結(jié)點為新

的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子

結(jié)點，其插入位置由查找過程得到。

插入原則：必須保證插入一個結(jié)點之后仍為一棵

二叉排序樹

插入新結(jié)點98

人第冼漳查找9.3.1二叉排序樹

六例：插入值為98的結(jié)點

?插入一個新元素，要先查找這個元素是否在樹中已經(jīng)

存在。笥匕,

第冼漳查找9.3.1二叉排序樹

—，'一

衣-查找成功：樹中已有這個元素，不再插入。

.查找不成功：樹中原來沒有關(guān)鍵碼等于給定值的

結(jié)點，把新元素加到查找

操作停止的地方。

插入新結(jié)點98

」第冼漳查找9.3.1二叉排序樹

六修改后的查找算法:

StatusSearchBST(BiTreeT,KeyTypekey,key,BiTree

&f,BiTree&p){

if(!T){p=f;returnFALSE;}

elseif(key=T->data.key){p=T;returnTRUE;}

elseif(key<T->data.key)return(SearchBsT(T-

>lchild,key9T,p));

elsereturn(SearchBST(T->rchild9key,T9p));

}//SearchBST

I-

」第冼漳查找9.3.1二叉排序樹

衣插入算法：

StatusInsertBST(BiTree&T,ElemTypekey){

if(!SearchBST(T,key,NULL,p){//查找不成功

；s=(BiTree)malloc(sizeof(BiTNode));//生成一個新結(jié)點

,s->data=key;s->lchild=s->rchild=NULL;

uf(!p)T=s;//被插入結(jié)點*s為新的根結(jié)點

；elseif(key<p->data.key)p->lchild=s;

；//被插入結(jié)點*s為左孩子

；elsep->rchild=s;//被插入結(jié)點*s為右孩子

；returnTRUE;

elsereturnFALSE;//樹中已有關(guān)鍵字相同的結(jié)點，不再

插入

}//InsertBST

一第次漳查找9.3.1二叉排序樹

長二叉排序樹的構(gòu)造

從空的二叉排序樹開始，依次插入查找集合中的每

一個元素。

例：關(guān)鍵碼集合為

{63,90,70,55,58),

二叉排序樹的構(gòu)造過程為：

j第次漳查找9.3.1二叉排序樹

☆二叉排序樹的構(gòu)造算法

I---------------------------------------------------------^

，BiSortTree::BiSortTree(intr[],intn)

：{:

for(i=0;i<n;i++)

j{上

s=(BiTree)malloc(sizeof(BiTNode));

||s->data=r[i];

s->lchild=s->rchild=NULL;

iInsertBST(root,s);

I)

n\}

瓷

第冼漳查找9.3.1二叉排序樹

☆小結(jié)：^

?一個無序序列可以通過構(gòu)造一棵二叉排序樹而

變成一個有序序列；

■每次插入的新結(jié)點都是二叉排序樹上新的葉子

結(jié)點；

-找到插入位置后，不必移動其它結(jié)點，僅需修

改某個結(jié)點的指針；

?在左子樹/右子樹的查找過程與在整棵樹上查找

過程相同；

?新插入的結(jié)點沒有破壞原有結(jié)點之間的關(guān)系。

?第冼漳查找9.3.1二叉排序樹

六二叉排序樹的刪除

原則：在二叉排序樹上刪除某個結(jié)點之后，仍然保持

二叉排序樹的特性。

分三種情況討論：

■被刪除的結(jié)點是葉子；

?被刪除的結(jié)點只有左子

樹或者只有右子樹；

■被刪除的結(jié)點既有左子

樹，也有右子樹。

第冼漳查找二叉排序樹

―To-9.3.1

7京設(shè)：*P為待刪J結(jié)點,F為*P的雙親

3

」第冼漳查找9.3.1二叉排序樹

N青況1——被刪除的結(jié)點是葉子結(jié)點

/x

刪葉結(jié)點，U

刪除

修改其雙2

親指針

P

刪除前刪除后

操作：將雙親結(jié)點中相應(yīng)指針域的值改為空。

f->lchild=NULL或f->rchild=NULL不

?第冼漳查找9.3.1二叉排序樹

湍?況2——被刪除的結(jié)點只有左子樹或者只有右子

操作：將雙親結(jié)點的相應(yīng)指針域的值指向被刪除輯臉

左子樹（或右子樹）。本

1

?第冼漳查找9.3.1二叉排序樹

操作1:以其前驅(qū)（左子樹中的最大值）替代

之，然后再刪除該前驅(qū)結(jié)點。-個

第冼漳查找9.3.1二叉排序樹

個情況3——被冊U除的結(jié)點既有左子樹也有右子樹

操作2:在右子樹上找中序下第一個結(jié)點填補

第冼漳查找9.3.1二叉排序樹

二叉排序樹的刪除算法——偽代碼

L若結(jié)點p是葉子，則直接刪除結(jié)點p；

2.若結(jié)點p只有左子樹，則只需重接p的左子樹；

若結(jié)點p只有右子樹，則只需重接p的右子樹；

3.若結(jié)點p的左右子樹均不空，則

II3.1查找結(jié)點p的右子樹上的最左下結(jié)點s及其雙親結(jié)點par；

3.2將結(jié)點s數(shù)據(jù)域替換到被刪結(jié)點p的數(shù)據(jù)域；__u

3.3若結(jié)點p的右孩子無左子樹，

則將s的右子樹接到par的右子樹上；

否則，將s的右子樹接到結(jié)點par的左子樹上；

3.4刪除結(jié)點s；、「

第冼漳查找9.3.2平衡二叉樹

斗衡二叉樹

平衡二叉樹：或者是一棵空的二叉排序樹，或者是具

有下列性質(zhì)的二叉排序樹:■

⑴根結(jié)點的左子樹和右子樹的深度最多相差1;

⑵根結(jié)點的左子樹和右子樹也都是平衡二叉樹。

平衡因子：結(jié)點的平衡因子是該結(jié)點的左子樹的深度

與右子樹的深度之差。

」第冼漳查找9.3.2平衡二叉樹

，衡二叉樹

結(jié)點的平衡因子=HL?HR

是平衡樹非平衡樹

在平衡樹中，結(jié)點的平衡因子可以是1,0,-1。

第冼漳查找9.3.2平衡二叉樹

'衡二叉樹

最小不平衡子樹：在平衡二叉樹的構(gòu)造過程中，以距

離插入結(jié)點最近的、且平衡因子的絕對值大于1的結(jié)

點為根的子樹。

第冼漳查找9.3.2平衡二叉樹

下衡二叉樹

基本思想：在構(gòu)造二叉排序樹的過程中，每插入一個

結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，

若是，則找出最小不平衡子樹，在保持二叉排序樹特

性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈

接關(guān)系，進行相應(yīng)的旋轉(zhuǎn)，使之成為新的平衡子樹。

第冼漳查找9.3.2平衡二叉樹

―To-

★

例：設(shè)序列｛20,35,40,15,30,25),構(gòu)造平衡樹。

第冼漳查找9.3.2平衡二叉樹

―To-

★

例：設(shè)序列｛20,35,40,15,30,25），構(gòu)造平衡樹。

第冼漳查找9.3.2平衡二叉樹

■■■■^_

'衡二叉樹

I設(shè)結(jié)點A為最小不平衡子樹的根結(jié)點，對該子樹進行

調(diào)整歸納撕缺下四種情況：...

LLL型

2.RR型

3.LR型

4.RL型

」第冼漳查找

9.3.2平衡二叉樹

汽F衡二叉樹一LL型

A

整

后

插入前插入后，調(diào)整前調(diào)

旋轉(zhuǎn)：扁擔原理；沖突：旋轉(zhuǎn)優(yōu)先

」第冼漳查找9.3.2平衡二叉樹

第決漳查找9.3.2平衡二叉樹

飛衡二叉樹——RR型

AA

——

插入前插入后，調(diào)整前調(diào)整后

第冼漳查找9.3.2平衡二叉樹

力衡二叉樹?

LR型

插入后,調(diào)整前先順時針旋轉(zhuǎn)再逆時針

V

」第冼漳查找9.3.2平衡二叉樹

/衡二叉樹

插入后，調(diào)整前先順時針旋轉(zhuǎn)再逆時針

」第通漳查找9.4哈希表（哈希表）

9.4.1哈希表

9.4.2哈希函數(shù)的構(gòu)造方法

9.4.3解決沖突的方法

人第%查找9.4哈希表

圖查找操作要完成什么任務(wù)？

待查值71|=二＞1確定上在存儲結(jié)構(gòu)中的位置

?我們學(xué)過的查找技術(shù)有什么共性？

順序查找、折半查找、二叉排序樹查找等。

這些查找技術(shù)都是通過一系列的給定值與關(guān)鍵碼的

比較，查找效率依賴于查找過程中進行的給定值與

關(guān)鍵碼的比較次數(shù)。

您能否不用比較，通過關(guān)鍵碼直接確定存儲位置？

第冼漳查找9.4哈希表

六【例】11個元素的關(guān)鍵碼分別為18,27,1,20,22,6,10,

13,41,15,25o選取關(guān)鍵碼與元素位置間的函數(shù)為

f(key)=keymod11o

1、通過這個函數(shù)對n個元素建立查找表如下：

012345678910

22113251527618412010

■2.查找時，對給定值X依然通過這個函數(shù)計

算出地址，再將X與該地址單元中元素的關(guān)

鍵碼比較，若相等，查找成功。這種方法就

是哈希方法。工已

第冼漳查找9.4哈希表

長.哈希的基本思想：,

I■在記錄的存儲位置與其關(guān)鍵碼之間建立一

個確定的對應(yīng)關(guān)系H〃s〃()，這樣，不經(jīng)過

比較，一次讀取就能得到所查元素的查找

方法。

Address(ai)=Hash(Rec.key)

其中，

II?ai是表中的一個元素

II■addr(ai)是ai的存儲地址

■key是ai的關(guān)鍵字

第冼漳查找9.4哈希表

去幾個相關(guān)概念、

?■哈希函數(shù)：在哈希方法中使用的轉(zhuǎn)換函數(shù)hash

I■哈希表：按此方法構(gòu)造出來的表或結(jié)構(gòu)

」■哈希地址：哈希函數(shù)的值，即關(guān)鍵碼對應(yīng)記錄

的存儲位置

-哈希查找：利用哈希函數(shù)進行查找的過程

」第冼漳查找9.4哈希表

大例；以學(xué)生學(xué)號為關(guān)鍵碼建立的成績表，1號學(xué)生的記

錄位置在第一條，??10號學(xué)生的記錄位置在第10條,..

11若以學(xué)生姓名為關(guān)鍵碼，如何建立查找表，使得根據(jù)

姓名可以直接找到相應(yīng)記錄呢？

?*

abcdefgh1Jk1mn0PqrstuVwXyz

1111111i112222222

123456789

01234567890123456

劉麗劉宏英吳軍吳小艷李秋梅陳偉???

姓名中各字拼音首字母11IhywjwxyIqmCW???

用所有首字母編號值相247242

加求和463326

最小值可能為2最大3能為78可放76個學(xué)生華1

」第冼漳查找9.4哈希表

洲上述得到的數(shù)值作為對應(yīng)記錄在表中的位置如下:

成績一成績二…

2???

24劉麗8295

25???

26陳偉

??????

33吳軍

.\A(

」一???

:\

」第冼漳查找9.4哈希表

六從例子可見：

哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希

函數(shù)值都落在表長允許的范圍芝內(nèi)即可

-關(guān)鍵碼集合比哈希表地址集合大得多。哈希函數(shù)是

一個壓縮映象函數(shù)。因此有可能經(jīng)過哈希函數(shù)的計

算，把不同的關(guān)鍵碼映射到同一個哈希地址上，這

就產(chǎn)生了沖突：

keyl^keyl,但H(keyl)=H(key2)

?產(chǎn)生沖突的哈希地址相同的不同關(guān)鍵碼稱為

哈希函數(shù)的同義詞

＞由于關(guān)鍵碼集合比地址集合大得多，所以沖突不可避

免，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處

理沖突的方法

第冼漳查找9.4哈希表

☆哈希技術(shù)的關(guān)鍵問題：

您如何構(gòu)造（選擇）“均勻的”哈希函數(shù)？

對于給定的一個關(guān)鍵碼集合,選擇一個計算

簡單且地址分布比較均勻的哈希函數(shù)，避

免或盡量減少沖突；

您如何采取合適的處理沖突方法來解決沖突。

II如何采取合適的處理沖突方法來解決沖突，

即要擬定解決沖突的方案。

」第冼漳查找9.4哈希表

69.4.2哈希函數(shù)的構(gòu)造方法

|設(shè)計哈希函數(shù)一般應(yīng)遵循以下原則：

⑴計算簡單。哈希函數(shù)不應(yīng)該有很大的計算量，否

則會降低查找效率。

⑵函數(shù)值即哈希地址分布均勻。函數(shù)值要盡量均勻

散布在地址空間，這樣才能保證存儲空間的有效利

用并減少沖突。

」第冼漳查找9.4哈希表

7哈希函數(shù)——直接定址法

哈希函數(shù)是關(guān)鍵碼的線性函數(shù)，即：

H(key)=?xkey+b(a,b為常數(shù))

例：關(guān)鍵碼集合為{10,30,50,70,80,90},選取的哈

希函數(shù)為H(key)=key/10,則哈希表為：

103050

優(yōu)點：單調(diào)、均勻、不會產(chǎn)生沖突

您適用情況：

I事先知道關(guān)鍵碼，關(guān)鍵碼集合較小且連續(xù)性較好一*

」第冼漳查找9.4哈希表

哈希函數(shù)數(shù)字分析法

根據(jù)關(guān)鍵碼在各個位上的分布情況，選取分布比較

均勻的若干位組成哈希地址。

表第冼漳查找9.4哈希表

V合殺由數(shù)—套分析法

例有60個記錄，關(guān)鍵字為6位十進制數(shù)，哈希地址為

3位十進制數(shù)

942148優(yōu)點：關(guān)鍵碼的位數(shù)可以很大

941269

940527

941630⑦）適用情況:

94805

94558能預(yù)先估計出全部關(guān)鍵

94047碼的每一位上各種數(shù)字

出現(xiàn)的頻度，不同的關(guān)

94001鍵碼集合需要重新分庭

①。④⑤⑥

」第冼漳查找9.4哈希表

/哈希函數(shù)——平方取中法

對關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作

為哈希地址(平方后截取)。

例：哈希地址為2位，則關(guān)鍵碼1234的哈希地址為：

(1234)2=1522756

優(yōu)點：事先不知道關(guān)鍵碼的分布，計算簡單

⑨適用情況：

關(guān)鍵碼的位數(shù)不是很大。、

」第冼漳查找9.4哈希表

哈希函數(shù)——折疊法

將關(guān)鍵碼從左到右分割成位數(shù)相等的幾部分，將這幾

部分疊加求和，取后幾位作為哈希地址。

例：設(shè)關(guān)鍵碼為25346358705,哈希地址為三位。

253253

463364優(yōu)點：事先不知道關(guān)鍵碼的

587587

+05+50分布，計算簡單

⑦適用情況:

13081254

關(guān)鍵碼位數(shù)很多，與關(guān)鍵?

移位疊加間界疊加碼的分布是否均勻無關(guān)產(chǎn)工

---------------------——，，4------------

第冼漳查找9.4哈希表

卡哈希函數(shù)——除留余數(shù)法

(取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除

后所得余數(shù)作哈希地址，即

哈希函數(shù)為：H(key)=keymodp

您如何選取合適的p,產(chǎn)生較少同義詞?

例：p=21

關(guān)鍵碼14212835424156

哈希地/p>

」第冼漳查找

9.4哈希表

唳希函數(shù)——除留余數(shù)法

I一般情況下，選。為小于或等于表長（最好接近表長）

曲最小素小于20質(zhì)因子的合數(shù)5.

⑦適用情況？

除留余數(shù)法是一種最簡單、也是最常用的構(gòu)造哈希

函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。

」第冼漳查找9.4哈希表

六哈希函數(shù)一隨機數(shù)法

[取關(guān)鍵字的隨機函數(shù)值作哈希地址，即

H(key)=random(key)

您適用情況？

適于關(guān)鍵字長度不等的情況

第冼漳查找9.4哈希表

六。實際工作中需視不同的情況采用不同的哈希

函數(shù)，通常，考慮以下因素：

計算哈希函數(shù)所需時間

關(guān)鍵字長度

哈希表長度（哈希地址范圍）

?關(guān)鍵字分布情況

?記錄的查找頻率

」第冼漳查找9.4哈希表

☆9.4.3處理沖突的方法

I用均勻的哈希函數(shù)可以減少沖突，但任一種哈希函數(shù)

也不能避免產(chǎn)生沖突，因此，如何處理沖突是哈希表

不可缺小的一方面。

@常用處理沖突的方法：

?1.開放地址法1

■2.再哈希法

.3.鏈地址法,

■4.建立一個公共溢出區(qū)A、

」第冼漳查找9.4哈希表

線理沖突的方法——開放定址法

由關(guān)鍵碼得到的哈希地址一旦產(chǎn)生了沖突，就去尋找

下一個空的哈希地址，并將記錄存入。

@如何尋找下一個空的哈希地址？

(1)線性探測法

(2)二次探測法

(3)隨機探測法

」第冼漳查找9.4哈希表

六處理沖突的方法---開放定址法

方法：當沖突發(fā)生時，形成一個探查序列；沿此序

列逐個地址探查，直到找到一個空位置(開放的地

址)，將發(fā)生沖突的記錄放到該地址中，即

Hi=(H(key)+di)modm,i=l,2,...k(k<m-l)

其中：H(key)---哈希函數(shù)

m---哈希表表長

di——增量序列

次di的有三種取法：

-線性探測再哈希：di=1,2,3,……m-1

-二次探測再哈希：di=l2,-I2,22,-

22,32,....+k2(k<m/2)

-偽隨機探測再哈希：di二偽隨機數(shù)序列

」第冼漳查找9.4哈希表

4修廠走長為11的哈希表中已填有關(guān)鍵字為17,60,29的記錄,

''H(key)=keyMOD11,現(xiàn)有第4個記錄，其關(guān)鍵字為38,

按三種處理沖突的方法，將它填入表中

012345678910

383860172938

(1)H(38)=38MOD11=5沖突

Hl=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突

(2)H(38)=38MOD11=5沖突

Hl=(5+12)MOD11=6沖突

H2=(5-l2)MOD11=4不沖突

(3)H(38)=38MOD11=5沖突

設(shè)偽隨機數(shù)序列為9,貝IJ：色

Hl=(5+9)MOD11=3與沖突

入第冼漳查找9.4哈希表

''愧―已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

去哈希函數(shù)為：H(key尸keyMOD13,哈希裝長為m=16,

設(shè)每個記錄的查找概率相等，試構(gòu)造該哈希表

(1)用線性探測再哈希處理沖突，即Hi=(H(key)+di)MODm

0123456789101112131415

1416827551920