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

第九章查找第九章和第十章介紹數(shù)據(jù)處理中常用的兩種操作：查找和排序。許多軟件都為用戶提供了查找和排序功能。

例如：文本編輯軟件Word，

各種信息管理軟件。在前面討論的數(shù)據(jù)結(jié)構(gòu)：線性表、樹、圖等，都可以根據(jù)實際情況（需要），將查找或排序作為它們的基本操作。

查找和排序操作應(yīng)用面廣，使用頻率高，所以對查找和排序算法的質(zhì)量，如時間效率，空間效率要求比較高。事實上任何軟件系統(tǒng)的核心程序，如操作系統(tǒng),使用頻率高，因此操作系統(tǒng)的各種算法，無論是文件管理、內(nèi)存管理程序也都需要有很高的質(zhì)量。下面兩章專門討論查找和排序，討論應(yīng)用中常用的幾種查找方法，排序方法，它們的特點及適用場合。

第九章查找9.1靜態(tài)表查找表9.2動態(tài)表查找表9.3哈希表

查找，也稱為檢索。在我們?nèi)粘Ｉ钪?，隨處可見查找的實例。如查找某人的地址、電話號碼；查某單位45歲以上職工等，都屬于查找范疇。在這里，我們規(guī)定查找是按關(guān)鍵字進(jìn)行的，所謂關(guān)鍵字(key)是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值，用它可以標(biāo)識(或識別)一個或一組數(shù)據(jù)元素。

一、查找表的概念1.查找表：由同一類型數(shù)據(jù)元素（或記錄）構(gòu)成的集合。在查找表中數(shù)據(jù)元素除了同屬一個集合，不考慮元素之間其它關(guān)系。2.查找表基本操作1）構(gòu)造查找表Create(&ST,n)2）銷毀查找表Destroy(&ST)3）各種查找操作二、查找的有關(guān)概念1.靜態(tài)查找表、動態(tài)查找表查找表最基本的操作是查找，常用的查找操作：

1）查詢某個“特定”元素是否在表中；

2）檢索某個“特定”元素的各種屬性；

3）查找某個“特定”元素是否在表中，若不在，則將該元素插入表中；

4）從查找表中刪除某個“特定”元素；

若對查找表只有1）、2）兩種查找，稱為靜態(tài)查找表；

若查找表提供3）、4）兩種查找操作，稱為動態(tài)查找表；2記錄、關(guān)鍵字記錄：由若干數(shù)據(jù)項構(gòu)成的數(shù)據(jù)元素稱為記錄關(guān)鍵字：數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項,可以標(biāo)識數(shù)據(jù)元素。

學(xué)號姓名專業(yè)年齡

01 王洪 計算機17

02孫文計算機18

03謝軍計算機18

04 李輝 計算機20

05沈祥福計算機25

06余斌 計算機19

07 鞏力計算機17

08 王輝計算機18例：學(xué)生管理系統(tǒng)，若想按姓名查找，可將姓名作為關(guān)鍵字，若想按學(xué)號查找，可將學(xué)號作為關(guān)鍵字。說明：

①記錄的任何數(shù)據(jù)項都可作為關(guān)鍵字；

②若此關(guān)鍵字的值能唯一標(biāo)識記錄，則稱該關(guān)鍵字為

主關(guān)鍵字，否則次關(guān)鍵字；例：學(xué)號是主關(guān)鍵字，姓名不重名時可以作為主關(guān)鍵字。其他數(shù)據(jù)項都可以作為次關(guān)鍵字。3查找

應(yīng)用中有各種各樣的查找，本章討論的查找操作定義如下：查找：給定某個值，在查找表中查找關(guān)鍵字值等于給定值的記錄，若表存在這樣的記錄，則稱查找成功，查找結(jié)果為該記錄（在表中）的位置，否則稱為查找不成功，查找結(jié)果為0或nu11。

4平均查找長度(ASL:AverageSearchLength)

要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量一個查找算法好壞的標(biāo)準(zhǔn)，對于一個含有n個元素的表，查找成功時的平均查找長度可表示為ASL=，其中Ｐi為查找第i個元素的概率，且=1。一般情形下我們認(rèn)為查找每個元素的概率相等，Ｃi為查找第i個元素所需要的比較次數(shù)。三、查找表的組織與查找如何在查找表中查找？取決于如何組織查找表

例1：

查找索引號為TP312.12的圖書

1)若圖書館中的圖書無序地擺放，則只能順序查找；

2)若圖書按索引號順序擺放，則可先找到TP類圖書，再找到TP3

例2

在詞典中查找單詞

are

1)先找到a打頭的單詞，再在a打頭的單詞中找

2)若詞典中無序排列，則只能順序查找；

本章介紹：

靜態(tài)查找表的組織方法與查找動態(tài)查找表的組織方法與查找哈希表的組織方法與查找

約定：假設(shè)1)本章查找是關(guān)于主關(guān)鍵字查找；2）假設(shè)本章涉及的關(guān)鍵字為整型類型；3）為使查找的圖示簡潔，對于查找表中的每一記錄，只寫出其關(guān)鍵字；

關(guān)鍵字類型定義為

typedef

int

KeyType;

記錄類型定義為：

stypedef

struct{

KeyTypekey;//關(guān)鍵字域

…//其它域}ElemType;

R={01,02,03,04,05,06,07,08}4)本章所討論的查找方法，只要稍加修改即可用于其他類型的查找例學(xué)號姓名專業(yè)年齡

01 王洪 計算機17

02孫文計算機18

03謝軍計算機18

04 李輝 計算機20

05沈祥福計算機25

06余斌 計算機19

07 鞏力計算機17

08 王輝計算機189.1靜態(tài)查找表只提供如下兩種查找的查找表，稱為靜態(tài)查找表

1）

查詢某個“特定”元素是否在表中；

2）

檢索某個“特定”元素的各種屬性；對靜態(tài)查找表介紹三種組織與查找方法順序表及查找

有序表及查找索引表及查找9.1.1順序表及查找（線性表及查找）查找表組織：查找表用線性表表示。即將查找表的記錄排成一個記錄序列。L1=(45,53,12,3,37,24,100,61,90,78)

順序查找法1）基本思想：從表的最后一個記錄（或第一個記錄）開始，依次將記錄的關(guān)鍵字與給定值比較，若相等：查找成功，否則，繼續(xù)查找。設(shè)查找表用順序表存儲，其類型定義如下：Typedef

struct{

ElemType*elem;

intlength;}SSTable2)算法int

Search_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為//該元素在表中的位置，否則為0。ST.elem[0].key=key;//ST.elem[0].key為“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].key);-

-i)//從后向前找returni;//若表中不存在待查元素，i=0

}//Search_Seq

3)平均查找長度

假設(shè)在每個位置查找的概率相等，即有pi=1/n，由于查找是從后往前掃描，則有每個位置的查找比較次數(shù)Cn=1，Cn-1=2，…，C1=n，于是，查找成功的平均查找長度ASL====,即它的時間復(fù)雜度為O(n)。這就是說，查找成功的平均比較次數(shù)約為表長的一半。若k值不在表中，則必須進(jìn)行n+1次比較之后才能確定查找失敗。另外，從ASL可知，當(dāng)n較大時，ASL值較大，查找的效率較低。順序查找的優(yōu)點是算法簡單，對表結(jié)構(gòu)無任何要求，無論是用向量還是用鏈表來存放結(jié)點，也無論結(jié)點之間是否按關(guān)鍵字有序或無序，它都同樣適用。順序查找的缺點是查找效率低，當(dāng)n較大時，不宜采用順序查找，而必須尋求更好的查找方法。順序查找對存儲結(jié)構(gòu)無要求，算法也很簡單，所以在元素較少時，算法還是很有效的。因此，平時應(yīng)用較為廣泛。*已知每個元素的Pi不等且其順序已知

p1<p2……<pn

按pi的大小存儲元素，即可節(jié)省時間。如：哈夫曼編碼。*已知每個元素的pi不等，但不知其順序。對每個r[i]，記錄r[i]的查找次數(shù)，每次查找與它后面記錄r[i+1]的次數(shù)比較，大于就后移。9.1.2有序表的查找

有序表：若線性表中的記錄按關(guān)鍵字有序，則稱為有序表查找表組織：查找表用有序表表示。即將查找表的記錄排成按關(guān)鍵字有序的序列。二分查找法（也稱為折半查找法）1）基本思想：將查找范圍中間位置的記錄關(guān)鍵字與給定值比較：

＜：繼續(xù)在前半個表中用二分查找法查找

=：查找成功，返回記錄位置

＞：繼續(xù)在后半個表中中用二分查找法查找

例1

L2=(3,12,24,37,45,53,61,78,90,100)，查找

Key=24的記錄

12345678910

31224374553617890100lowmid

high

12345678910

31224374553617890100lowmid

high

24＜45繼續(xù)在前半個表中用二分查找法查找

12345678910

31224374553617890100Lowmidhigh

24＞12繼續(xù)在后半個表中用二分查找法查找查找成功算法int

Search_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為//該元素在表中的位置，否則為0。Low=1;high=ST.length;While(low<=high){mid=(low+high)/2;ifEQ(key,ST.elem[mid].key)returnmid;//找到待查元素elseifLT(key,ST.elem[mid].key)high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找elselow=mid+1;//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找}return0;//表中不存在待查元素

}//Search_Bin設(shè)查找每一個記錄的概率相同，即均為1/10，平均查找長度ASL

=在查找過程中與給定值比較的關(guān)鍵字個數(shù)的數(shù)學(xué)期望值

PiCi=（1+2

2+4

3+3

4）/10二分查找法查找過程可用判定樹描述

12345678910

例

L2=(3,12,24,37,45,53,61,78,90,100)，查找過程可用如下判定樹描述

5

4

3

1

6

7

9

8

210Key=24的查找路徑為5,2,3,所需的比較次數(shù)為3查找第5個記錄需的比較次數(shù)為1查找第2、8個記錄需的比較次數(shù)均為2 說明：折半查找法效率比順序查找高;平均查找長度ASLbs=log2（n+1）-1要求表中的記錄按關(guān)鍵字有序；表中的記錄要用順序結(jié)構(gòu)存儲； 例在有1000個記錄的查找表查找，順序查找法平均要比較500次，折半查找法平均要比較9次，可見折半查找法效率比順序查找高。9.1.3分塊查找（索引表查找）順序查找簡單并且對存儲結(jié)構(gòu)無要求，折半查找有效但要求表有序，將二者結(jié)合起來，取各自的優(yōu)點，就是分塊查找。將表分為若干子表，子表內(nèi)部無序，子表之間有序。（后續(xù)表中任一關(guān)鍵字均大于前驅(qū)表中的最大關(guān)鍵字。k1k2k3…….

…k1

…k2

…k3……

索引表的項數(shù)與主表的塊數(shù)相等，每一個表項對應(yīng)主表的一個子表。索引表有序。查找方法：

1)在索引表中查找給定值對應(yīng)的子表（可以順序查找，也可以折半查找）。2)在相應(yīng)子表中順序查找。也稱為索引順序查找。存儲結(jié)構(gòu)：索引表可用順序或鏈?zhǔn)健Ｖ鞅恚鹤颖碇杏庙樞?，子表之間用鏈?zhǔn)健?/p>

索引表當(dāng)索引表較大時，可以采用二分查找在數(shù)據(jù)量極大時，索引可能很多，可考慮建立索引表的索引，即二級索引，原則上索引不超過三級12345678910111213141516171822121389203342443824486058745786532248861713查38

平均查找長度：假設(shè)表長為n，分為b塊，子表長：s=n/b,索引表長為b

則：ASL=(b+1)/2+(s+1)/2

當(dāng)s為n開平方時，效率最高。

三種查找方法比較順序查找折半查找分塊查找表的存儲結(jié)構(gòu)順序、鏈?zhǔn)巾樞蛩饕?--順序、鏈?zhǔn)街鞅?---順序、鏈?zhǔn)?、順序、鏈?zhǔn)交旌详P(guān)鍵字的有序性無有序索引有序主表分塊有序ASL最大最小居中9.2動態(tài)查找表動態(tài)查找表

如果應(yīng)用問題涉及的數(shù)據(jù)量很大，而且數(shù)據(jù)經(jīng)常發(fā)生變化，如圖書館經(jīng)常購進(jìn)圖書，每購進(jìn)新書，需將新書記錄插入圖書表中，對這類表除了提供1）、2）兩種查找外，還要提供動態(tài)查找功能：3）

查找某個“特定”元素是否在表中，若不在，則將該元素插入表中；

4）

查找某個“特定”元素是否在表中，若在，從表中刪除該元素；如何組織動態(tài)查找表？線性表：順序查找效率低有序表：二分查找法須用順序結(jié)構(gòu)存儲有序表，插入刪除操作要移動元素；本節(jié)介紹動態(tài)查找表的一種組織形式——二叉排序樹9.2.1

二叉排序樹和平衡二叉樹

1.二叉排序樹二叉排序樹（BinarySortTree）或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹分別為二叉排序樹；二叉排序樹4537245310061907831245372453100619078312根據(jù)二叉排序樹的定義，對二叉樹進(jìn)行LDR遍歷得到是遞增序列。3,12,24,37,45,53,61,78,90,1002二叉排序樹的查找在二叉排序樹中查找關(guān)鍵字為key的記錄基本思想若二叉排序樹為空樹，查找失敗，返回null或0；否則，將key與根結(jié)點的關(guān)鍵字比較：若key=根結(jié)點的關(guān)鍵字,查找成功，返回該記錄在二叉排序樹中的位置；若key

根結(jié)點的關(guān)鍵字，繼續(xù)在左子樹中查找；若key

根結(jié)點的關(guān)鍵字，繼續(xù)在右子樹中查找；例在如下二叉排序樹中查找關(guān)鍵字為24的記錄24

45繼續(xù)在左子樹中查找24

12繼續(xù)在右子樹中查找24

37繼續(xù)在左子樹中查找Key=24查找成功！45372453100619078312例在如下二叉排序樹中查找關(guān)鍵字為60的記錄查找失敗！查找路徑左子樹為空45372453100619078312算法BiTree

SearchBST(BiTreeT,KeyTypekey){//二叉排序樹用二叉鏈表存儲。在根指針T所指二叉排序樹中遞歸地查找//關(guān)鍵字等于key的記錄，若查找成功，則返回該記錄結(jié)點的指針，否則//返回空指針

if(!T)||EQ(key,T->data.key)return(T);//若T為空或查找成功，返回elseifLT(key,T->data.key)

return(SearchBST(T->1child,key));//在左子樹中繼續(xù)查找

return(SearchBST(T->rchild,key))//在右子樹中繼續(xù)查找}//SearchBST性能分析：二叉排序樹的查找效率與樹的形態(tài)有關(guān)，若樹的形態(tài)為“單枝”，二叉排序樹的查找就“退化”為順序查找；若樹的形態(tài)比較“平衡”，二叉排序樹的查找與二分查找類似；為獲得較高的查找效率，需要構(gòu)造“平衡”的二叉排序樹。關(guān)于如何構(gòu)造平衡二叉樹，后面介紹。5345372410061907831253453724613123二叉排序樹的插入、刪除二叉排序樹是動態(tài)查找表的組織形式,動態(tài)查找表要提供插入刪除數(shù)據(jù)元素的操作。在一般二叉樹的基本操作中只有插入、刪除子樹操作，沒有插入、刪除結(jié)點操作。原因是:除了葉子結(jié)點外，在二叉樹中插入、刪除結(jié)點將破壞樹的結(jié)構(gòu)。下面介紹如何在二叉排序樹中插入、刪除。二叉排序樹是作為動態(tài)查找表的組織形式，目的是獲得較高的查找效率并且能方便地進(jìn)行插入刪除操作。因此在二叉排序樹中插入、刪除結(jié)點的原則是：插入、刪除結(jié)點后仍是二叉排序樹。1）二叉排序樹的插入

新插入的結(jié)點為葉子結(jié)點，并且是查找不成功時，查找路徑上最后一個結(jié)點的左孩子或右孩子。

將新結(jié)點插入二叉排序樹基本步驟：

從二叉排序樹的根結(jié)點開始，若二叉排序樹為空樹，新插入結(jié)點作為根結(jié)點，否則，若當(dāng)前結(jié)點為葉子結(jié)點，若新插入結(jié)點的關(guān)鍵字

當(dāng)前結(jié)點的關(guān)鍵字，則將新結(jié)點作為當(dāng)前結(jié)點的左孩子，否則作為右孩子；否則，若新插入結(jié)點的關(guān)鍵字

根結(jié)點的關(guān)鍵字，將新結(jié)點插入左子樹；否則插入右子樹45372453100619078312算法(先改寫前面的查找算法,以便查找不成功時返回插入位置)StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//在根指針T所指二叉排序樹中遞歸地查找關(guān)鍵字等于key的記錄，若查找成功，則//用P返回該記錄結(jié)點的指針，并返回TRUE,否則P指向查找路徑上訪問的最后一個結(jié)點//并返回FLASE,指針f指向T的雙親,其初始調(diào)用值為NULL

if(!T){p=f;returnFLASE;}//查找不成功elseifEQ(key,T->data.key){p=T;returnTRUE;}

//若T為空或查找成功，返回elseifLT(key,T->data.key)return(SearchBST(T->lchild,key,T,p));

//在左子樹中繼續(xù)查找elsereturn(SearchBST(T->rchild,key,T,p))

//在右子樹中繼續(xù)查找}//SearchBST插入算法

StatusInsertBST(BiTree&T,ElemTypee){

//指針T所指二叉排序樹中不存在關(guān)鍵字等于key的記錄時插入，并返回TRUE；否則返回FLASE

if(!SearchBST(T,key,NULL,p){

//查找不成功s=(BiTree)malloc(sizeof(BITNode));

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

if(!p)T=s;//被插入的結(jié)點為根結(jié)點elseifLT(e,p->data.key)p->lchild=s;elsep->rchild=s;returnTRUE;}

return

FLASE;}//InsertBST例在如下二叉排序樹中插入結(jié)點40為查找插入位置走過的路徑插入結(jié)點40！4537245310061907831240插入首先執(zhí)行查找算法，找出被插結(jié)點的雙親結(jié)點。判斷被插結(jié)點是其雙親結(jié)點的左、右孩子。將被插結(jié)點作為葉子結(jié)點插入。若二叉樹為空。則首先單獨生成根結(jié)點。注意：新插入的結(jié)點總是葉子結(jié)點。例：將序列：122、99、250、110、300、280作為二叉排序樹的結(jié)點的關(guān)鍵字值，生成二叉排序樹。122992503002801102）二叉排序樹的刪除在二叉排序樹中刪除結(jié)點的原則是：刪除結(jié)點后仍是二叉排序樹。對二叉排序樹進(jìn)行中序遍歷，所得到的中序序列是一有序序列。如對如圖所示的二叉排序樹進(jìn)行中序遍歷，其中序序列為：3，12，24，37，45，53，61，78，90，100，在二叉排序樹中刪除一個結(jié)點相當(dāng)于在有序序列刪除一個結(jié)點，只要刪除結(jié)點后仍保持二叉排序樹的特性。如何在二叉排序樹中刪除一個結(jié)點?？45372453100619078312在二叉排序樹中刪除一個結(jié)點，分三種情況：(1)p僅有一個結(jié)點（被刪除的結(jié)點是葉子），新樹t=null(2)p僅有一棵子樹。T=p->lchild

或t=p->rchild(3)p有兩棵子樹，情況比較復(fù)雜，問題可以歸結(jié)為在一棵子樹中刪除根結(jié)點，根結(jié)點刪除后，二叉排序樹變成兩棵子樹。最后的問題是將兩棵二叉排序樹合成一棵新的二叉排序樹。有兩種方法解決，我們分別討論。tPPLPRPPPRPLPR

CCLSL

Q

SQL

F(a)

F

C

SPRCL

QQLSL(b)SL

F

C

PPRCL

Q

SQL刪除P前的二叉排序樹P既有左子樹PL也有右子樹PR

,如圖，二叉排序樹的中序序列為(…FCLC…QLQSLSPPR…)S是P的直接前趨，S是P的左子樹的最右下結(jié)點，S至少沒有右子樹。在刪除P后,為保持中序序列中其它元素之間的相對位置不變，可有兩種方法(a)令P的左子樹的根C作為新樹的根，而P的右子樹為S的右子樹；（b)用P的直接前趨S代替P，然后從二叉排序樹刪除P的直接前趨S；方法（a):t=p->lchild;s=t;while(s->rchild)s=s->rchilds->rchild=p->rchild

同理，可將p的右子樹的根作為新樹的根，將PL

插入p的右子樹的適當(dāng)位置。這種方法，刪除后樹的深度增加了。會降低查找效率。方法(b)：找到PL的右支末端結(jié)點s將p->data=s->data。然后刪除s,s可能無左右子樹，也可能有一個左子樹。S刪除后，它的左子樹應(yīng)連在s的雙親右子樹上。但是，若PL無右子樹，可將PL的左子樹連在p的左子樹上。

t=p;q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}p->data=s->data;if(q!=p)q->rchild=s->lchild

elseq->lchild=s->lchild

該方法，算法復(fù)雜一些，但樹的深度沒有增加。

Pqspq=psPqs算法

StatusDeleBST(BiTree&T,KeyTypekey){//在根指針T所指二叉排序樹中存在key,則刪除并返回TRUE,否則返回FLASE

if(!T)returnFLASE;//查找不成功else{ifEQ(key,T->data.key){returnDelete(T)}

;//若T為空或查找成功，返回elseifLT(key,T->data.key)return(DeleBST(T->lchild,key));elsereturn(DeleBST(T->rchild,key));}//DeleBSTDelete算法

StatusDelete(BiTree&p){//從二叉排序樹刪除結(jié)點p，并重接它的左或右子樹

if(!p->rchild){q=p;p=p->lchild;free(q);}//右子樹空elseif{(!p->lchild){q=p;p=p->rchild;free(q);}

//左子樹空else{

//左右子樹均不空

q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;

free(s)}returntrue}//Delete二叉排序樹的刪除操作例子

葉子結(jié)點：直接刪除。如：刪除數(shù)據(jù)為15、70的結(jié)點。1560703020506030205012225030011020099105230216400450500若被刪結(jié)點的左孩子為空或者右孩子為空。如下圖所示，刪除結(jié)點的數(shù)據(jù)值為200的結(jié)點。刪除20012225030023021640045050011099105被刪結(jié)點的左、右子樹皆不空1222503001102009910523021640045050011025030010520099230216400450500二叉排序樹的查找效率與樹的形態(tài)有關(guān)，而樹的形態(tài)取決于建立二叉排序樹時的輸入序列。例：{8，12，3，10，18，2，7}

ASL=(n+1)/nlog2(n+1)-1{8,18,7,10,2,12,3}{2,3,7,8,10,12,18}

ASL=(n+1)/2由此，二叉排序樹的查找效率相差比較大，平均性能ASL=1+4log2n183210718128238718101223課堂練習(xí)1222503001102009910523021640045050011025030010520099230216400450500刪除250、230刪除400、230平衡二叉樹1.定義：平衡二叉樹(BalancedBinaryTree或Hight-BalancdeTree)，是由阿德爾森一維爾斯和蘭迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又稱為AVL樹。若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕對值不超過1，則稱這樣的二叉樹為平衡二叉樹。2.平衡因子：將該結(jié)點的左子樹深度減去右子樹深度的值，稱為該結(jié)點的平衡因子(balancefactor)。

這就是說，一棵二叉排序樹中，所有結(jié)點的平衡因子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹。如下圖(a)所示二叉排序樹，是一棵平衡二叉樹，而下圖(b)

所示二叉

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

圖(a)53453724100619078312圖(b)53453724619078312二叉排序樹的查找效率與樹的形態(tài)有關(guān)，而樹的形態(tài)取決于建立二叉排序樹時的輸入序列。如果對任何的輸入序列建成的二叉排序樹都是AVL樹。要用建立二叉排序樹的方法，建立平衡二叉樹，在樹不平衡時做適當(dāng)?shù)恼{(diào)整。3.修改二叉排序樹的插入算法*判定樹的不平衡性，每個結(jié)點增加一個表示平衡因子的數(shù)據(jù)項bf。*平衡操作，確定平衡處理的范圍并進(jìn)行平衡處理。

9

53

9

53

9

5353453724100907812924912平衡處理的范圍：最小的一個不平衡子樹。4.平衡操作

(1)RR旋轉(zhuǎn)（單向左旋平衡處理）：設(shè)a指向最小不平衡子樹的根。在a的右子樹的右子樹插入新結(jié)點，造成a子樹的不平衡。a的bf由-1變?yōu)?2。設(shè)a的左子樹AL高為h-1,b子樹高為h,b的左子樹BL和b的右子樹BR高均為h-1。在樹中有AL<a<BL<b<BR，平衡后仍然要保持這個關(guān)系。進(jìn)行一次向左的逆時針旋轉(zhuǎn)，可以將不平衡的樹平衡，并且保持旋轉(zhuǎn)前的大小關(guān)系。abALBLBRabALBLBR

(2)LL旋轉(zhuǎn)（單向右旋平衡處理）：設(shè)a指向最小不平衡子樹的根。在a的左子樹的左子樹插入新結(jié)點，造成a子樹的不平衡。a的bf由1變?yōu)?。

進(jìn)行一次向右的順時針旋轉(zhuǎn)。abARBLBRabARBLBR

(3)RL旋轉(zhuǎn)（雙向旋轉(zhuǎn)先右后左）：設(shè)a指向最小不平衡子樹的根。在a的右子樹的左子樹插入新結(jié)點，造成a子樹的不平衡。a的bf由-1變?yōu)?2。

先向右的順時針旋轉(zhuǎn)，后向左的逆時針旋轉(zhuǎn)。abALBLBRabALCLBRcCRRL平衡處理后的二叉樹abALCLBRcCR

(4)LR旋轉(zhuǎn)（雙向旋轉(zhuǎn)先左后右）：設(shè)a指向最小不平衡子樹的根。在a的左子樹的右子樹插入新結(jié)點，造成a子樹的不平衡。

平衡處理方法：與RL旋轉(zhuǎn)對稱，先向左的逆時針旋轉(zhuǎn)，后向右順時針旋5.平衡操作小結(jié)：

1)LL和RR，LR和RL在操作方法上分別是對稱的。2)在bf不等于0的結(jié)點下插入新結(jié)點，或者破壞平衡，或者不破壞平衡。3)插入破壞平衡時，最小不平衡子樹插入前的樹高和插入后并做平衡處理后樹高一樣，因此，該子樹外的結(jié)點平衡因子不受影響4)在插入路徑上，從a到插入點（除a以外），新結(jié)點的祖先的平衡因子要重新確定。5)a,b(或含c)，他們的互相連接關(guān)系改變，但是不改變他們的大小順序。

為了從任何的輸入關(guān)鍵字序列得到二叉排序樹均為AVL樹,需要對二叉排序樹的插入算法做如下修改。（1）判別插入結(jié)點之后是否產(chǎn)生不平衡（2）找到失去平衡的最小子樹（3）判別旋轉(zhuǎn)類型并做相應(yīng)平衡處理由此，算法分下面三步：（1）插入，找插入點的同時檢查每個結(jié)點的bf，記錄

bf不等于0的結(jié)點（有可能成為不平衡子樹的根）,插入結(jié)點。（2）判定平衡性，不平衡則做相應(yīng)的平衡處理（3）修改a到新插入點路徑上的bf注：找a的同時，要記錄a的雙親，以便a子樹平衡后的子樹可以插入在a原來的位置。在平衡二叉樹上插入一個新的數(shù)據(jù)元素的算法見P2379.11左平衡處理算法9.12,右平衡處理算法類似9.12，算法9.9和9.10在平衡處理中進(jìn)行右旋操作和左旋操作時修改指針的情況。

在平衡二叉樹上進(jìn)行查找的時間復(fù)雜度為O(logn)例：avl樹例題..\avl樹例題1.ppt課堂練習(xí):

關(guān)鍵字序列為{8，6，4，10，12，9，7}，畫出生成AVL樹的步驟并指出平衡操作的類型。9.2.2B-樹

B-樹是一種平衡多叉樹。在文件系統(tǒng)中非常有用，數(shù)據(jù)庫系統(tǒng)的文件組織很多系統(tǒng)用B-樹。1.B-樹的定義一個m階的B-樹，或為空樹，或為滿足下列特性的m叉樹(1)樹中每個結(jié)點至多有m棵子樹；(2)若根結(jié)點不是葉結(jié)點，則至少有兩棵子樹；(3)除根之外的所有的非終端結(jié)點至少有

m/2棵子樹(4)所有的非終端結(jié)點中包含下列信息(n,A0,K1,A1,K2,A2,……Kn,An)

其中：Ki(i=1,2,……,n)為關(guān)鍵字，且Ki<Ki+1(i=1,2,……,n-1);Ai(i=0,1,2,……,n)為指向子樹根結(jié)點的指針，且Ai-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki(i=1,2,……,n),An所指子樹中所有的關(guān)鍵字均大Kn,n(

m/2-1nm-1)為關(guān)鍵字的個數(shù)(n+1為子樹個數(shù)。)(5)所有的葉子結(jié)點都出現(xiàn)在同一層次上，并不帶信息。3階B-樹（又叫2-3樹）70852440977177515735122.B-樹的查找在一個結(jié)點中可以折半查找（key有序），也可以順序查找（key較少），整個查找按樹查找。

結(jié)點的類型說明：#definem3//B-樹的階

typedef

struct

BTNode{

int

keynum;//結(jié)點中關(guān)鍵字個數(shù)

struct

BTNode*parent;//指向雙親結(jié)點的指針

keytypekey[m+1];//關(guān)鍵字向量，0單元未用

struct

BTNode*ptr[m+1];//子樹指針向量

record*recptr[m+1];//記錄指針向量，0單元未用}BTNode,*Btree;//B樹結(jié)點，B樹類型

查找結(jié)果的類型說明：

typedef

struct{

BTNode*pt;//指向找到的結(jié)點

inti;//結(jié)點中關(guān)鍵字的序號

inttag;//1查找成功，0查找失敗}Result;//B樹的查找結(jié)果類型

查找步驟：(1)若樹為空，查找失敗(2)將給定值與指定結(jié)點的關(guān)鍵字組比較，確定kiK<Ki+1(3)Ki=K。查找成功，P指向該結(jié)點，i返回結(jié)點中關(guān)鍵字的序號tag=1(4)Ai==null,查找失敗，P=Ai,i,tag=0(5)取Ai所指結(jié)點，轉(zhuǎn)(2)。ResultSearchBTree(BTree

T,keyTypek){p=T;q=null;found=FlASE;i=0;//初始化，p指向待查結(jié)點，//q指向p的雙親While(p&&!found){i=Search(p,k);//在p->key[1..keynum]中查找if(i>0&&p->key[i]==k)found=TRUE;//找到kelse{q=p;p=p->ptr[i];}}if(found)return(p,i,1);elsereturn(q,i,0);}//SearchBTree

在B-樹上查找所需時間取決與兩個因素：1)要查找的關(guān)鍵字所在的層次2)結(jié)點中的關(guān)鍵字?jǐn)?shù)目

3.B-樹的插入1）在B-樹中從根開始查找，找到插入碼所在的位置，若該碼已經(jīng)存在，則出錯，否則就找到了應(yīng)插入的最底層的某個非終端結(jié)點。

2）在插入后，若被插入結(jié)點中項數(shù)<m，則插入操作完成。如果被插入的結(jié)點項數(shù)=m，則分裂結(jié)點，并繼續(xù)向上一級插入，這是一個遞歸的過程，從最底層的某個非終端結(jié)點沿著原來的查找路徑反向進(jìn)行。

插入步驟：1）若樹為空，建立新結(jié)點2）查找關(guān)鍵字的插入位置3）插入，且keynum+14）如果keynum<m，插入結(jié)束5）分裂結(jié)點1—m/2-1,放在原結(jié)點中，X=key[

m/2],向上一級插入，

m/2+1—m申請新結(jié)點。6）以雙親為當(dāng)前結(jié)點，插入X，若雙親存在轉(zhuǎn)2），否則轉(zhuǎn)1）

例子見P242圖9.16(a)---(j)算法見P2449.144.刪除在B-樹上刪除一個關(guān)鍵字K，找到K所在的結(jié)點P1）P為葉子結(jié)點，則刪除K，若keynum

m/2，則刪除結(jié)束，否則合并結(jié)點。2）P為非終端結(jié)點，若K=Ki,Ki為要刪除的關(guān)鍵字，則以指針Ai所指子樹中最小的關(guān)鍵字Kx代替Ki，刪除Kx（Kx所在的結(jié)點P為葉子結(jié)點）歸結(jié)為1）。因此，僅討論刪除葉結(jié)點中的關(guān)鍵字。設(shè)被刪除關(guān)鍵字所在的結(jié)點為P1）P中keynum

m/2，則刪除Ki和相應(yīng)的指針Ai。例:P245圖9.17(a)刪除122）P中keynum=

m/2-1，P的左兄弟或右兄弟中keynum>

m/2-1，則將其左兄弟中最大的關(guān)鍵字或右兄弟中最小的關(guān)鍵字Kx移到雙親結(jié)點中，而將其雙親中小于或大于Kx的關(guān)鍵字Ky下移到P中。例:P245圖9.17(b)刪除503）P和P的左右兄弟結(jié)點中的keynum=

m/2-1，沒有關(guān)鍵字可借，進(jìn)行結(jié)點的合并。設(shè)P有右兄弟（無右兄弟時和左兄弟合并）。把P結(jié)點中剩余的關(guān)鍵字和指針，加上雙親結(jié)點中的那個關(guān)鍵字（P和右兄弟之間的）一起放到右兄弟結(jié)點中。這樣雙親結(jié)點中刪除了一個關(guān)鍵字，則又需要做借關(guān)鍵字或合并處理，這個過程是遞歸的，最壞情況可能波及到根，此時，整個B-樹減少一層。例:P245圖9.17(c)、(d)刪除53，379.3哈希表

上兩節(jié)介紹的查找表查找方法的共同特點：通過比較查找，即通過將記錄關(guān)鍵字值與給定值比較，來進(jìn)行查找。查找算法的時間效率取決于查找過程中所進(jìn)行的比較次數(shù)。理想的方法是：不需要比較，根據(jù)給定值能直接定位記錄的存儲位置。顯然，要想根據(jù)給定值能直接定位記錄的存儲位置。需要在記錄的存儲位置與該記錄的關(guān)鍵字之間建立一種確定的對應(yīng)關(guān)系，使每個記錄的關(guān)鍵字與一個存儲位置相對應(yīng)。例1949-2000年某地區(qū)人口統(tǒng)計表

各年度人口統(tǒng)計記錄的存儲位置=年度-1948年份人數(shù)

123515219491950195119992000200021002200440044209.3.1什么是哈希表：

哈希函數(shù)用來定義記錄的關(guān)鍵字與記錄存儲位置的對應(yīng)關(guān)系的函數(shù)其自變量是記錄的關(guān)鍵字，函數(shù)值是記錄存儲位置。

哈希地址：由哈希函數(shù)求出的記錄存儲位置稱為哈希地址

哈希表：也叫散列表，是將記錄按哈希函數(shù)確定的位置存放而構(gòu)成的表例

1949-2000年某地區(qū)人口統(tǒng)計表關(guān)鍵字：年份哈希函數(shù)：H（KEY）=KEY-1948哈希表年份人數(shù)

12351521949195019511999200020002100220044004420

哈希表是查找表的又一種組織形式，其記錄在哈希表的存儲位置，由哈希函數(shù)決定。根據(jù)關(guān)鍵字及實際應(yīng)用，確定哈希表表長，并構(gòu)造哈希函數(shù)。為獲得較高的查找效率，哈希函數(shù)應(yīng)是一些便于計算的簡單函數(shù)。然而，由于應(yīng)用中的關(guān)鍵字形形色色，很難保證所構(gòu)造出的哈希函數(shù)都是一對一（或叫單射函數(shù)）。實際上，除了特別簡單的應(yīng)用，在大多數(shù)情況下，所構(gòu)造出的哈希函數(shù)是多對一的（非單射函數(shù)）。即可能有多個不同的關(guān)鍵字，它們對應(yīng)的哈希函數(shù)值是相同的，這意味著不同記錄由哈希函數(shù)確定的存儲位置是相同的。這種情況被稱為沖突。例某年全國各城市人口統(tǒng)計表關(guān)鍵字：城市名哈希函數(shù)

H（key）=key的第一個字母在字母表中的序號

key北京天津石家莊保定吉林哈爾濱長春H(key)2201921083具有相同哈希函數(shù)值的關(guān)鍵字稱為同義詞構(gòu)造哈希表要解決兩方面的問題：1）構(gòu)造哈希函數(shù)2）處理沖突9.3.2哈希函數(shù)的構(gòu)造方法“好”的哈希函數(shù)的條件：簡單：易于計算

均勻：減少沖突若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)哈希函數(shù)映象到地址集合中，任何一個地址的概率是相等的，則稱此類哈希函數(shù)為均勻的。常用的構(gòu)造哈希函數(shù)的方法有：1）直接定址法：哈希函數(shù)為關(guān)鍵字的某個線性函數(shù)H（key)=a*key+b

例1949-2000年某地區(qū)人口統(tǒng)計表哈希函數(shù)H（KEY）=KEY-1948年份人數(shù)

123515219491950195119992000200021002200440044202）數(shù)字分析法對關(guān)鍵字序列進(jìn)行分析，取那些位上數(shù)字變化多的、頻率大的作為散列函數(shù)地址。例如，對如下的關(guān)鍵字序列：430104681015355430101701128352430103720818350430102690605351430105801226356．．．．．．通過對上述關(guān)鍵字序列分析，發(fā)現(xiàn)前5位相同，第6、8、10位上的數(shù)字變化多些，若規(guī)定地址取3位，則散列函數(shù)可取它的第6、8、10位。于是有：H（430104681015355）＝480H（430101701128352）＝101H（430103620805351）＝328H（430102690605351）＝296H（430105801226356）＝5023）平方取中法

取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。這是一種比較常用的散列函數(shù)構(gòu)造方法，但在選定散列函數(shù)時不一定知道關(guān)鍵字的全部信息，取其中哪幾位也不一定合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，因此，可以使用隨機分布的關(guān)鍵字得到函數(shù)地址。如圖8-16中，隨機給出一些關(guān)鍵字，并取平方后的第2到4位為函數(shù)地址。

4）折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為散列函數(shù)地址，稱為折疊法。例如，假設(shè)關(guān)鍵字為某人身份證號碼430104681015355，則可以用4位為一組進(jìn)行疊加，即有5355＋8101＋1046＋430＝14932，舍去高位，則有H（430104681015355）＝4932為該身份證關(guān)鍵字的散列函數(shù)地址。5）除留余數(shù)法哈希函數(shù)為H（key)=keyMODpm為哈希表表長。p為小于等于m的素數(shù)除留余數(shù)法計算簡單，適用范圍廣，是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的p值，使得每一個關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發(fā)生沖突的可能性。一般情形下，p取為一個素數(shù)較理想，并且要求裝填因子α最好是在0.6∽0.9之間，所以p最好取1.1n∽1.7n之間的一個素數(shù)較好，其中n為散列表中待裝元素個數(shù)。9.3.3解決沖突的方法：當(dāng)不同記錄由哈希函數(shù)確定的存儲位置相同，發(fā)生沖突。這時需用某種方法解決沖突。常用的解決沖突的方法：1）開放地址法用函數(shù)Hi(key)=(H(KEY)+di)mod

m(i=1,2,3…)為發(fā)生沖突的記錄再求一存儲位置。

Hi(key)（i=1,2,3…)是一系列函數(shù)，若H1(key)計算出的地址仍沖突，用H2(key)求“下一地址”…,在函數(shù)Hi(key)=(H(KEY)+di)mod

m(i=1,2,3…)中：H(KEY)為哈希函數(shù)；m為哈希表表長；di為增量序列，有三種取法

a)di=1,2,3…；稱為線性探測再散列

b)di=12，-12，22，-2,…,+k2,(k<=m/2)稱為二次探測再散列

c)di=偽隨機數(shù)序列稱為偽隨機數(shù)探測再散列例：設(shè)哈希表HT表長為11，哈希函數(shù)H(key)=keymod11,試用開放地址法中線性探測再散列解決沖突Hi(key)=(H(KEY)+di)mod11(d1=1,d2=2,d3=3,…),試對下列關(guān)鍵字序列（19，13，33，02，16，29，24）構(gòu)造哈希表