數(shù)據(jù)結(jié)構(gòu)(第9章)-清華大學(xué)_第1頁
數(shù)據(jù)結(jié)構(gòu)(第9章)-清華大學(xué)_第2頁
數(shù)據(jù)結(jié)構(gòu)(第9章)-清華大學(xué)_第3頁
數(shù)據(jù)結(jié)構(gòu)(第9章)-清華大學(xué)_第4頁
數(shù)據(jù)結(jié)構(gòu)(第9章)-清華大學(xué)_第5頁
已閱讀5頁,還剩113頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

第九章查找⒈教學(xué)內(nèi)容:9.1基本概念與術(shù)語9.2靜態(tài)查找表9.3動態(tài)查找表9.4哈希表查找(雜湊法)

⒉教學(xué)目的:⑴了解查找的基本思想及查找成功和不成功的概念;⑵掌握在各種查找表上的查找方法和算法,并能求出相應(yīng)的平均查找長度;⑶理解并掌握二叉排序樹、平衡二叉樹B-樹的各種算法。⒊教學(xué)重點(diǎn):⑴查找表的基本概念及查找原理;⑵查找表的順序存儲結(jié)構(gòu)、順序表及其類型說明;⑶查找運(yùn)算在查找表和有序表上的實(shí)現(xiàn);⑷二叉排序樹的定義、性質(zhì)及各結(jié)點(diǎn)間的鍵值關(guān)系;⑸二叉排序樹的查找算法和基本思想;⑹平衡二叉排序樹的概念;⑺B-樹和B+樹的概念;⑻散列表及散列存儲和散列查找的基本思想;⑼各種散列表的組織、解決沖突的方法;⑽在散列表上實(shí)現(xiàn)查找、插入和刪除運(yùn)算的算法。⒋教學(xué)難點(diǎn):⑴理解查找表的邏輯結(jié)構(gòu)是集合,它的運(yùn)算以查找為核心;⑵二叉排序樹上的插入算法;⑶平衡二叉樹的旋轉(zhuǎn)平衡算法;⑷散列表上的有關(guān)算法⒌學(xué)時(shí)安排:

10學(xué)時(shí)2/5/20231數(shù)據(jù)結(jié)構(gòu)講義

在英漢字典中查找某個(gè)英文單詞的中文解釋;在新華字典中查找某個(gè)漢字的讀音、含義;在對數(shù)表、平方根表中查找某個(gè)數(shù)的對數(shù)、平方根;郵遞員送信件要按收件人的地址確定位置等等??梢哉f查找是為了得到某個(gè)信息而常常進(jìn)行的工作。計(jì)算機(jī)、計(jì)算機(jī)網(wǎng)絡(luò)使信息查詢更快捷、方便、準(zhǔn)確。要從計(jì)算機(jī)、計(jì)算機(jī)網(wǎng)絡(luò)中查找特定的信息,就需要在計(jì)算機(jī)中存儲包含該特定信息的表。如要從計(jì)算機(jī)中查找英文單詞的中文解釋,就需要存儲類似英漢字典這樣的信息表,以及對該表進(jìn)行的查找操作。本章將討論的問題即是“信息的存儲和查找”。查找是許多程序中最消耗時(shí)間的一部分操作。因而,一個(gè)好的查找方法可以大大提高運(yùn)行速度。另外,由于計(jì)算機(jī)的特性,象對數(shù)、平方根等是通過函數(shù)求解,無需存儲相應(yīng)的信息表。2/5/20232數(shù)據(jù)結(jié)構(gòu)講義9.1基本概念與術(shù)語2/5/20233數(shù)據(jù)結(jié)構(gòu)講義以學(xué)校招生錄取登記表為例,來討論計(jì)算機(jī)中表的概念。

學(xué)號姓名性別出生日期來源總分錄取專業(yè)年月日┆200109832001098420010985┆┆趙劍平蔣偉峰郭娜┆┆男男女┆┆198219821983┆┆110901┆┆051225┆┆石家莊一中保定三中易縣中學(xué)┆┆593601598┆┆計(jì)算機(jī)計(jì)算機(jī)計(jì)算機(jī)┆圖9.1學(xué)校招生錄取登記表2/5/20234數(shù)據(jù)結(jié)構(gòu)講義1.數(shù)據(jù)項(xiàng)(也稱項(xiàng)或字段)

項(xiàng)是具有獨(dú)立含義的標(biāo)識單位,是數(shù)據(jù)不可分割的最小單位。如表中“學(xué)號”、“姓名”、

“年”等。項(xiàng)有名和值之分,項(xiàng)名是一個(gè)項(xiàng)的標(biāo)識,用變量定義,而項(xiàng)值是它的一個(gè)可能取值,表中“20010983”是項(xiàng)“學(xué)號”的一個(gè)取值。項(xiàng)具有一定的類型,依項(xiàng)的取值類型而定。2.組合項(xiàng)

由若干項(xiàng)、組合項(xiàng)構(gòu)成,表中“出生日期”就是組合項(xiàng),它由“年”、“月”、“日”三項(xiàng)組成。2/5/20235數(shù)據(jù)結(jié)構(gòu)講義3.數(shù)據(jù)元素(記錄)數(shù)據(jù)元素是由若干項(xiàng)、組合項(xiàng)構(gòu)成的數(shù)據(jù)單位,是在某一問題中作為整體進(jìn)行考慮和處理的基本單位。數(shù)據(jù)元素有型和值之分,表中項(xiàng)名的集合,也即表頭部分就是數(shù)據(jù)元素的類型;而一個(gè)學(xué)生對應(yīng)的一行數(shù)據(jù)就是一個(gè)數(shù)據(jù)元素的值,表中全體學(xué)生即為數(shù)據(jù)元素的集合。4.關(guān)鍵碼

關(guān)鍵碼是數(shù)據(jù)元素(記錄)中某個(gè)項(xiàng)或組合項(xiàng)的值,用它可以標(biāo)識一個(gè)數(shù)據(jù)元素(記錄)。能唯一確定一個(gè)數(shù)據(jù)元素(記錄)的關(guān)鍵碼,稱為主關(guān)鍵碼;而不能唯一確定一個(gè)數(shù)據(jù)元素(記錄)的關(guān)鍵碼,稱為次關(guān)鍵碼。表中“學(xué)號”即可看成主關(guān)鍵碼,“姓名”則應(yīng)視為次關(guān)鍵碼,因可能有同名同姓的學(xué)生。2/5/20236數(shù)據(jù)結(jié)構(gòu)講義5.查找表

是由具有同一類型(屬性)的數(shù)據(jù)元素(記錄)組成的集合。分為靜態(tài)查找表和動態(tài)查找表兩類。靜態(tài)查找表:僅對查找表進(jìn)行查找操作,而不能改變的表;動態(tài)查找表:對查找表除進(jìn)行查找操作外,可能還要進(jìn)行向表中插入數(shù)據(jù)元素,或刪除表中數(shù)據(jù)元素的表。6.查找

按給定的某個(gè)值kx,在查找表中查找關(guān)鍵碼為給定值kx的數(shù)據(jù)元素(記錄)。關(guān)鍵碼是主關(guān)鍵碼時(shí):由于主關(guān)鍵碼唯一,所以查找結(jié)果也是唯一的,一旦找到,查找成功,結(jié)束查找過程,并給出找到的數(shù)據(jù)元素(記錄)的信息,或指示該數(shù)據(jù)元素(記錄)的位置。要是整個(gè)表檢測完,還沒有找到,則查找失敗,此時(shí),查找結(jié)果應(yīng)給出一個(gè)“空”記錄或“空”指針。關(guān)鍵碼是次關(guān)鍵碼時(shí):需要查遍表中所有數(shù)據(jù)元素(記錄),或在可以肯定查找失敗時(shí),才能結(jié)束查找過程。2/5/20237數(shù)據(jù)結(jié)構(gòu)講義

7.數(shù)據(jù)元素類型說明

在手工繪制表格時(shí),總是根據(jù)有多少數(shù)據(jù)項(xiàng),每個(gè)數(shù)據(jù)項(xiàng)應(yīng)留多大寬度來確定表的結(jié)構(gòu),即表頭的定義。然后,再根據(jù)需要的行數(shù),畫出表來。在計(jì)算機(jī)中存儲的表與手工繪制的類似,需要定義表的結(jié)構(gòu),并根據(jù)表的大小為表分配存儲單元。以圖9.1為例,用C語言的結(jié)構(gòu)類型描述之。

/*出生日期類型定義*/typedefstruct{charyear[5];/*年:用字符型表示,寬度為4個(gè)字符*/

charmonth[3];

/*月:字符型,寬度為2*/

chardate[3];

/*日:字符型,寬度為2*/

}BirthDate;2/5/20238數(shù)據(jù)結(jié)構(gòu)講義/*數(shù)據(jù)元素類型定義*/typedefstruct{charnumber[7];

/*學(xué)號:字符型,寬度為6*/

charname[9];

/*姓名:字符型,寬度為8*/

charsex[3];

/*性別:字符型,寬度為2*/

BirthDatebirthdate;

/*出生日期:構(gòu)造類型,由該類型的寬度確定*/

charcomefrom[21];

/*來源:字符型,寬度為20*/

intresults;

/*成績:整型,寬度由“程序設(shè)計(jì)C語言工具軟件”決定*/

}ElemType;2/5/20239數(shù)據(jù)結(jié)構(gòu)講義以上定義的數(shù)據(jù)元素類型,相當(dāng)于手工繪制的表頭。要存儲學(xué)生的信息,還需要分配一定的存儲單元,即給出表長度??梢杂脭?shù)組分配,即順序存儲結(jié)構(gòu);也可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)動態(tài)分配。本章以后討論中,涉及的關(guān)鍵碼類型和數(shù)據(jù)元素類型統(tǒng)一說明如下:typedefstruct{KeyTypekey;

/*關(guān)鍵碼字段,可以是整型、字符串型、構(gòu)造類型等*/

……

/*其它字段*/}ElemType;2/5/202310數(shù)據(jù)結(jié)構(gòu)講義9.2靜態(tài)查找表

靜態(tài)查找表結(jié)構(gòu)順序查找有序表的折半查找2/5/202311數(shù)據(jù)結(jié)構(gòu)講義

靜態(tài)查找表是數(shù)據(jù)元素的線性表,可以是基于數(shù)組的順序存儲或以線性鏈表存儲。

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

typedefstruct{ElemType*elem;

/*數(shù)組基址*/

intlength;

/*表長度*/}S_TBL;

9.2.1靜態(tài)查找表結(jié)構(gòu)2/5/202312數(shù)據(jù)結(jié)構(gòu)講義/*鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)類型*/

typedefstructNODE{ElemTypeelem;

/*結(jié)點(diǎn)的值域*/

tructNODE*next;

/*下一個(gè)結(jié)點(diǎn)指針域*/}NodeType;

2/5/202313數(shù)據(jù)結(jié)構(gòu)講義9.2.2順序查找順序查找又稱線性查找,是最基本的查找方法之一。其查找方法為:從表的一端開始,向另一端逐個(gè)按給定值kx與關(guān)鍵碼進(jìn)行比較,若找到,查找成功,并給出數(shù)據(jù)元素在表中的位置;若整個(gè)表檢測完,仍未找到與kx相同的關(guān)鍵碼,則查找失敗,給出失敗信息。2/5/202314數(shù)據(jù)結(jié)構(gòu)講義【算法9.1】以順序存儲為例,數(shù)據(jù)元素從下標(biāo)為1的數(shù)組單元開始存放,0號單元留空。

ints_search(S_TBLtbl,KeyTypekx){/*在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素,若找到返回該元素在數(shù)組中的下標(biāo),否則返回0*/

tbl.elem[0].key=kx;/*存放監(jiān)測,這樣在從后向前查找失敗時(shí),不必判表是否檢測完,從而達(dá)到算法統(tǒng)一*/

for(i=tbl.length;tbl.elem[i].key<>kx;i--);

/*從標(biāo)尾端向前找*/

returni;}2/5/202315數(shù)據(jù)結(jié)構(gòu)講義【性能分析】

分析查找算法的效率,通常用平均查找長度ASL來衡量。

定義:在查找成功時(shí),平均查找長度ASL是指為確定數(shù)據(jù)元素在表中的位置所進(jìn)行的關(guān)鍵碼比較次數(shù)的期望值。

對一個(gè)含n個(gè)數(shù)據(jù)元素的表,查找成功時(shí)

其中:Pi為表中第i個(gè)數(shù)據(jù)元素的查找概率,

Ci為表中第i個(gè)數(shù)據(jù)元素的關(guān)鍵碼與給定值kx相等時(shí),按算法定位時(shí)關(guān)鍵碼的比較次數(shù)。顯然,不同的查找方法,Ci可以不同。ASL=Pi·Cin∑i=1n∑i=1Pi=12/5/202316數(shù)據(jù)結(jié)構(gòu)講義Ci為表中第i個(gè)數(shù)據(jù)元素的關(guān)鍵碼與給定值kx相等時(shí),按算法定位時(shí)關(guān)鍵碼的比較次數(shù)。顯然,不同的查找方法,Ci可以不同。

就上述算法而言,對于n個(gè)數(shù)據(jù)元素的表,給定值kx與表中第i個(gè)元素關(guān)鍵碼相等,即定位第i個(gè)記錄時(shí),需進(jìn)行n-i+1次關(guān)鍵碼比較,即Ci=n-i+1。則查找成功時(shí),順序查找的平均查找長度為:

設(shè)每個(gè)數(shù)據(jù)元素的查找概率相等,則等概率情況下有

查找不成功時(shí),關(guān)鍵碼的比較次數(shù)總是n+1次。

算法中的基本工作就是關(guān)鍵碼的比較,因此,查找長度的量級就是查找算法的時(shí)間復(fù)雜度,其為O(n)。ASL=Pi·(n-i+1)n∑i=1n∑i=1ASL=(n-i+1)=1─nn+1───22/5/202317數(shù)據(jù)結(jié)構(gòu)講義

許多情況下,查找表中數(shù)據(jù)元素的查找概率是不相等的。為了提高查找效率,查找表需依據(jù)查找概率越高,比較次數(shù)越少;查找概率越低,比較次數(shù)就較多的原則來存儲數(shù)據(jù)元素。

順序查找缺點(diǎn)是當(dāng)n很大時(shí),平均查找長度較大,效率低;優(yōu)點(diǎn)是對表中數(shù)據(jù)元素的存儲沒有要求。另外,對于線性鏈表,只能進(jìn)行順序查找。2/5/202318數(shù)據(jù)結(jié)構(gòu)講義有序表即是表中數(shù)據(jù)元素按關(guān)鍵碼升序或降序排列。

折半查找的思想為:在有序表中,取中間元素作為比較對象,若給定值與中間元素的關(guān)鍵碼相等,則查找成功;若給定值小于中間元素的關(guān)鍵碼,則在中間元素的左半?yún)^(qū)繼續(xù)查找;若給定值大于中間元素的關(guān)鍵碼,則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過程,直到查找成功,或所查找的區(qū)域無數(shù)據(jù)元素,查找失敗。9.2.3有序表的折半查找2/5/202319數(shù)據(jù)結(jié)構(gòu)講義

【步驟】

low=1;high=length;

//設(shè)置初始區(qū)間

當(dāng)low>high時(shí),返回查找失敗信息//表空,查找失敗

low≤high,mid=(low+high)/2;//取中點(diǎn)

a.若kx<tbl.elem[mid].key,high=mid-1;轉(zhuǎn)②

//查找在左半?yún)^(qū)進(jìn)行

b.若kx>tbl.elem[mid].key,low=mid+1;轉(zhuǎn)②

//查找在右半?yún)^(qū)進(jìn)行

c.若kx=tbl.elem[mid].key,返回?cái)?shù)據(jù)元素在表中位置//查找成功

2/5/202320數(shù)據(jù)結(jié)構(gòu)講義【例9.1】有序表按關(guān)鍵碼排列如下:7,14,18,21,23,29,31,35,38,42,46,49,52在表中查找關(guān)鍵碼為14和22的數(shù)據(jù)元素。

2/5/202321數(shù)據(jù)結(jié)構(gòu)講義⑴

查找關(guān)鍵碼為14的過程

low=1①設(shè)置初始區(qū)間

high=13

───────────────────────────

②表空測試,非空;

mid=7③得到中點(diǎn),比較測試為a情形

low=1high=6high=mid-1,調(diào)整到左半?yún)^(qū)

───────────────────────────

01234567891011121371418212329313538424649522/5/202322數(shù)據(jù)結(jié)構(gòu)講義0123456789101112137141821232931353842464952

②表空測試,非空;

mid=3③得到中點(diǎn),比較測試為a情形

low=1

high=2high=mid-1,調(diào)整到左半?yún)^(qū)

───────────────────────────

②表空測試,非空;

mid=1③得到中點(diǎn),比較測試為b情形

↑↑

low=2high=2low=mid+1,調(diào)整到右半?yún)^(qū)

2/5/202323數(shù)據(jù)結(jié)構(gòu)講義0123456789101112137141821232931353842464952

②表空測試,非空;

mid=2③得到中點(diǎn),比較測試為c情形

查找成功,返回找到的數(shù)據(jù)元素位置為2

查找關(guān)鍵碼為22的過程2/5/202324數(shù)據(jù)結(jié)構(gòu)講義0123456789101112137141821232931353842464952

low=1①設(shè)置初始區(qū)間

high=13

───────────────────────────

②表空測試,非空;

mid=7③得到中點(diǎn),比較測試為a情形

low=1

high=6high=mid-1,調(diào)整到左半?yún)^(qū)

──────────────────────────

②表空測試,非空;

mid=3

③得到中點(diǎn),比較測試為b情形

low=4high=6low=mid+1,調(diào)整到右半?yún)^(qū)

───────────────────────────2/5/202325數(shù)據(jù)結(jié)構(gòu)講義0123456789101112137141821232931353842464952

②表空測試,非空;

mid=5

③得到中點(diǎn),比較測試為a情形

↑↑

low=4high=4high=mid-1,調(diào)整到左半?yún)^(qū)

────────────────────────────

②表空測試,非空;

mid=4③得到中點(diǎn),比較測試為b情形

high=4low=5low=mid+1,調(diào)整到右半?yún)^(qū)

────────────────────────────

②表空測試,為空;查找失敗,返回查找失敗信息為0

────────────────────────────2/5/202326數(shù)據(jù)結(jié)構(gòu)講義【算法9.2】intBinary_Search(S_TBLtbl,KEYkx){/*在表tbl中查找關(guān)鍵碼為kx的數(shù)據(jù)元素,若找到返回該元素在表中的位置,否則,返回0*/

intmid,flag=0;low=1;high=length;/*①設(shè)置初始區(qū)間*/

while(low<=high)/*②表空測試*/{/*非空,進(jìn)行比較測試*/

mid=(low+high)/2;/*③得到中點(diǎn)*/

if(kx<tbl.elem[mid].key)high=mid-1;/*調(diào)整到左半?yún)^(qū)*/

else if(kx>tbl.elem[mid].key)

low=mid+1;

/*調(diào)整到右半?yún)^(qū)*/

else{flag=mid;break;}

/*查找成功,元素位置設(shè)置到flag中*/}

returnflag;}2/5/202327數(shù)據(jù)結(jié)構(gòu)講義【性能分析】

從折半查找過程看,以表的中點(diǎn)為比較對象,并以中點(diǎn)將表分割為兩個(gè)子表,對定位到的子表繼續(xù)這種操作。所以,對表中每個(gè)數(shù)據(jù)元素的查找過程,可用二叉樹來描述,稱這個(gè)描述查找過程的二叉樹為判定樹。4938291874252312346351421圖9.2例9.1描述折半查找過程的判定樹2/5/202328數(shù)據(jù)結(jié)構(gòu)講義可以看到,查找表中任一元素的過程,即是判定樹中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵碼的比較次數(shù),也即該元素結(jié)點(diǎn)在樹中的層次數(shù)。對于n個(gè)結(jié)點(diǎn)的判定樹,樹高為k,則有2k-1-1<n≤2k-1,即k-1<log2(n+1)≤k,所以k=。因此,折半查找在查找成功時(shí),所進(jìn)行的關(guān)鍵碼比較次數(shù)至多為。接下來討論折半查找的平均查找長度。為便于討論,以樹高為k的滿二叉樹(n=2k-1)為例。假設(shè)表中每個(gè)元素的查找是等概率的,則樹的第i層有2i-1個(gè)結(jié)點(diǎn),因此,折半查找的平均查找長度為:

2/5/202329數(shù)據(jù)結(jié)構(gòu)講義ASL=Pi·Cin∑i=1

=(1/n)[1×20+2×21+…+k×2k-1]=((n+1)/n)log2(n+1)-1≈log2(n+1)-1所以,折半查找的時(shí)間效率為O(log2n)。

2/5/202330數(shù)據(jù)結(jié)構(gòu)講義9.3動態(tài)查找表

2/5/202331數(shù)據(jù)結(jié)構(gòu)講義一.二叉排序樹定義

二叉排序樹(BinarySortTree)或者是一棵空樹;或者是具有下列性質(zhì)的二叉樹:

若左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值;若右子樹不空,則

右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。⑵左右子樹也都是二叉排序樹。9.3.1二叉排序樹2/5/202332數(shù)據(jù)結(jié)構(gòu)講義由圖中可以看出,對二叉排序樹進(jìn)行中序遍歷,便可得到一個(gè)按關(guān)鍵碼有序的序列,因此,一個(gè)無序序列,可通過構(gòu)一棵二叉排序樹而成為有序序列。5842987090634555836710二.二叉排序樹查找過程

從其定義可見,二叉排序樹的查找過程為:①若查找樹為空,查找失敗。②查找樹非空,將給定值kx與查找樹的根結(jié)點(diǎn)關(guān)鍵碼比較。2/5/202333數(shù)據(jù)結(jié)構(gòu)講義③

若相等,查找成功,結(jié)束查找過程,否則,

a.當(dāng)給kx小于根結(jié)點(diǎn)關(guān)鍵碼,查找將在以左子女為根的子樹上繼續(xù)進(jìn)行,轉(zhuǎn)①

b.當(dāng)給kx大于根結(jié)點(diǎn)關(guān)鍵碼,查找將在以右子女為根的子樹上繼續(xù)進(jìn)行,轉(zhuǎn)①

以二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu),則查找過程算法程序描述如下:typedefstructNODE{ElemType elem; /*數(shù)據(jù)元素字段*/

structNODE *lc,*rc; /*左、右指針字段*/}NodeType; /*二叉樹結(jié)點(diǎn)類型*/2/5/202334數(shù)據(jù)結(jié)構(gòu)講義【算法9.4】IntSearchElem(NodeType*t,NodeType*p,NodeType*q,KeyTypekx){/*在二叉排序樹t上查找關(guān)鍵碼為kx的元素,若找到,返回1,且q指向該結(jié)點(diǎn),p指向其父結(jié)點(diǎn);否則,返回0,且p指向查找失敗的最后一個(gè)結(jié)點(diǎn)*/

intflag=0;*q=t;while(*q) /*從根結(jié)點(diǎn)開始查找*/

if(kx>(*q)->elem.key)/*kx大于當(dāng)前結(jié)點(diǎn)*q的元素關(guān)鍵碼*/{*p=*q;*q=(*q)->rc;}/*將當(dāng)前結(jié)點(diǎn)*q的右子女置為新根*/

elseif(kx<(*q)->elem.key)

/*kx小于當(dāng)前結(jié)點(diǎn)*q的關(guān)鍵碼*/ {*p=*q;*q=(*q)->lc;}

/*將當(dāng)前結(jié)點(diǎn)*q的左子女置為新根*/

else{flag=1;break;} /*查找成功,返回*/

returnflag;}2/5/202335數(shù)據(jù)結(jié)構(gòu)講義三.二叉排序樹插入操作和構(gòu)造一棵二叉排序樹

先討論向二叉排序樹中插入一個(gè)結(jié)點(diǎn)的過程:設(shè)待插入結(jié)點(diǎn)的關(guān)鍵碼為kx,為將其插入,先要在二叉排序樹中進(jìn)行查找,若查找成功,按二叉排序樹定義,待插入結(jié)點(diǎn)已存在,不用插入;查找不成功時(shí),則插入之。因此,新插入結(jié)點(diǎn)一定是作為葉子結(jié)點(diǎn)添加上去的。構(gòu)造一棵二叉排序樹則是逐個(gè)插入結(jié)點(diǎn)的過程。2/5/202336數(shù)據(jù)結(jié)構(gòu)講義【算法9.5】intInsertNode(NodeType*t,KeyTypekx){/*在二叉排序樹*t上插入關(guān)鍵碼為kx的結(jié)點(diǎn)*/

NodeType*p=t,*q,*s;intflag=0;if(!SearchElem(t,&p,&q,kx));/*在*t為根的子樹上查找*/{s=(NodeType*)malloc(sizeof(NodeType));/*申請結(jié)點(diǎn),并賦值*/

s->elem.key=kx;s->lc=NULL;s->rc=NULL;flag=1; /*設(shè)置插入成功標(biāo)志*/

if(!p)t=s; /*向空樹中插入時(shí)*/

elseif(kx>p->elem.key) p->rc=s;/*插入結(jié)點(diǎn)為p的右子女*/

elsep->lc=s; /*插入結(jié)點(diǎn)為p的左子女*/}

returnflag;}2/5/202337數(shù)據(jù)結(jié)構(gòu)講義【例9.3】記錄的關(guān)鍵碼序列為:63,90,70,55,67,42,98,83,10,45,58,則構(gòu)造一棵二叉排序樹的過程如下:φ6370556742988363906390706390557063906755706390426755706390984267557063902/5/202338數(shù)據(jù)結(jié)構(gòu)講義839842675570639010455883984267557063901045839842675570639010從空樹開始建立二叉排序樹的過程2/5/202339數(shù)據(jù)結(jié)構(gòu)講義四.二叉排序樹刪除操作

從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)之后,使其仍能保持二叉排序樹的特性即可。

設(shè)待刪結(jié)點(diǎn)為*p(p為指向待刪結(jié)點(diǎn)的指針),其雙親結(jié)點(diǎn)為*f,以下分三種情況進(jìn)行討論。⒈*p結(jié)點(diǎn)為葉結(jié)點(diǎn),由于刪去葉結(jié)點(diǎn)后不影響整棵樹的特性,所以,只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域改為空指針。如右圖所示。FP*f*pF2/5/202340數(shù)據(jù)結(jié)構(gòu)講義⒉*p結(jié)點(diǎn)只有右子樹pr

或只有左子樹pl,此時(shí),只需將pr或pl替換*f結(jié)點(diǎn)的*p子樹即可。如下圖所示。FP*f*pP1FP1*fFP*f*pPrFPr*f2/5/202341數(shù)據(jù)結(jié)構(gòu)講義⒊*p結(jié)點(diǎn)既有左子樹Pl又有右子樹Pr,可按中序遍歷保持有序進(jìn)行調(diào)整。

設(shè)刪除*p結(jié)點(diǎn)前,中序遍歷序列為:

①P為F的左子女時(shí)有:…,Pl子樹,P,Pj

,S子樹,Pk,Sk子樹,…,P2,S2子樹,P1,S1子樹,F,…

②P為F的右子女時(shí)有:…,F,Pl

子樹,P,Pj

,S子樹,Pk,Sk子樹,…,P2,S2子樹,P1,S1子樹,…則刪除*p結(jié)點(diǎn)后,中序遍歷序列應(yīng)為:

①P為F的左子女時(shí)有:…,Pl

子樹,Pj

,S子樹,Pk,Sk子樹,…,P2,S2子樹,P1,S1子樹,F,…

②P為F的右子女時(shí)有:…,F,Pl

子樹,Pj

,S子樹,Pk,Sk子樹,…,P2,S2子樹,P1,S1子樹,…2/5/202342數(shù)據(jù)結(jié)構(gòu)講義有兩種調(diào)整方法:①

直接令pl為*f相應(yīng)的子樹,以pr為pl中序遍歷的最后一個(gè)結(jié)點(diǎn)

pk的右子樹;②

令*p結(jié)點(diǎn)的直接前驅(qū)Pr或直接后繼(對Pl子樹中序遍歷的最后一個(gè)結(jié)點(diǎn)Pk)替換*p結(jié)點(diǎn),再按⒉的方法刪去Pr或Pk。圖9.8所示的就是以*p結(jié)點(diǎn)的直接前驅(qū)Pr替換*p。

FP*f*pP1FPr*fSPrP1S2/5/202343數(shù)據(jù)結(jié)構(gòu)講義SJPj*f*PFPPlS1P1S2P2SPr*f*PFPrPlP1P1P2P2SjPjS2/5/202344數(shù)據(jù)結(jié)構(gòu)講義對給定序列建立二叉排序樹,若左右子樹均勻分布,則其查找過程類似于有序表得折半查找。但若給定序列原本有序,則建立得二叉排序樹就蛻化為單鏈表,其查找效率同順序查找一樣。因此,對均勻得二叉排序樹進(jìn)行插入或刪除結(jié)點(diǎn)后,應(yīng)對其調(diào)整,使其依然保持均勻。2/5/202345數(shù)據(jù)結(jié)構(gòu)講義【算法9.6】intDeleteNode(NodeType*t,KeyTypekx){NodeType*p=t,*q,*s,*f;

intflag=0;if(SearchElem(*t,&p,&q,kx));{flag=1; /*查找成功,置刪除成功標(biāo)志*/

if(p==q)f=t; /*待刪結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)*/

else /*待刪結(jié)點(diǎn)非根結(jié)點(diǎn)時(shí)*/{f=p->lc;if(kx>p->elem.key) f=p->rc;} /*f指向待刪結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)指針域*/

if(!q->rc)f=q->lc; /*若待刪結(jié)點(diǎn)無右子樹,以左子樹替換待刪結(jié)點(diǎn)*/

else {if(!q->lc) f=q->rc; /*若待刪結(jié)點(diǎn)無左子樹,以右子樹替換待刪結(jié)點(diǎn)*/2/5/202346數(shù)據(jù)結(jié)構(gòu)講義

else /*既有左子樹又有右子樹*/ {p=q->rc;s=p; while(p->lc)

{s=p;p=p->lc;}/*在右子樹上搜索待刪結(jié)點(diǎn)的前驅(qū)p*/ f=p;p->lc=q->lc; /*替換待刪結(jié)點(diǎn)q,重接左子樹*/

if(s!=p) { s->lc=p->rc; /*待刪結(jié)點(diǎn)的右子女有左子樹時(shí),還要重接右子樹*/

p->rc=q->rc;}

} } free(q);

} returnflag;}2/5/202347數(shù)據(jù)結(jié)構(gòu)講義9.3.2平衡二叉樹(AVL)樹平衡二叉樹或者是一棵空樹,或者是具有下列性質(zhì)的二叉排序樹:它的左子樹和右子樹都是平衡二叉樹,且左子樹和右子樹高度之差的絕對值不超過1。

91000065504741853060727842-330-202141853060727842-1110010a.非平衡二叉樹b.平衡二叉樹2/5/202348數(shù)據(jù)結(jié)構(gòu)講義上圖給出了兩棵二叉排序樹,每個(gè)結(jié)點(diǎn)旁邊所注數(shù)字是以該結(jié)點(diǎn)為根的樹中,左子樹與右子樹高度之差,這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子。由平衡二叉樹定義,所有結(jié)點(diǎn)的平衡因子只能取-1,0,1三個(gè)值之一。若二叉排序樹中存在這樣的結(jié)點(diǎn),其平衡因子的絕對值大于1,這棵樹就不是平衡二叉樹。如圖9.9(a)所示的二叉排序樹。在平衡二叉樹上插入或刪除結(jié)點(diǎn)后,可能使樹失去平衡,因此,需要對失去平衡的樹進(jìn)行平衡化調(diào)整。設(shè)a結(jié)點(diǎn)為失去平衡的最小子樹根結(jié)點(diǎn),對該子樹進(jìn)行平衡化調(diào)整歸納起來有以下四種情況:

2/5/202349數(shù)據(jù)結(jié)構(gòu)講義一、左單旋轉(zhuǎn)BhahEcDh0-1xBhaEcDhh+1-2-1xEh+1cDaBh+100a.插入前b.插入后,調(diào)整前c.調(diào)整后圖(a)為插入前的子樹。其中,B為結(jié)點(diǎn)a的左子樹,D、E分別為結(jié)點(diǎn)c的左右子樹,B、D、E三棵子樹的高均為h。圖(a)所示的子樹是平衡二叉樹。在圖(a)所示的樹上插入結(jié)點(diǎn)x,如圖(b)所示。結(jié)點(diǎn)x插入在結(jié)點(diǎn)c的右子樹E上,導(dǎo)致結(jié)點(diǎn)a的平衡因子絕對值大于1,以結(jié)點(diǎn)a為根的子樹失去平衡。

2/5/202350數(shù)據(jù)結(jié)構(gòu)講義【調(diào)整策略】

調(diào)整后的子樹除了各結(jié)點(diǎn)的平衡因子絕對值不超過1,還必須是二叉排序樹。由于結(jié)點(diǎn)c的左子樹D可作為結(jié)點(diǎn)a的右子樹,將結(jié)點(diǎn)a為根的子樹調(diào)整為左子樹是B,右子樹是D,再將結(jié)點(diǎn)a為根的子樹調(diào)整為結(jié)點(diǎn)c的左子樹,結(jié)點(diǎn)c為新的根結(jié)點(diǎn),如圖(c)?!酒胶饣{(diào)整操作判定】沿插入路徑檢查三個(gè)點(diǎn)a、c、E,若它們處于“\”直線上的同一個(gè)方向,則要作左單旋轉(zhuǎn),即以結(jié)點(diǎn)c為軸逆時(shí)針旋轉(zhuǎn)。2/5/202351數(shù)據(jù)結(jié)構(gòu)講義

二、右單旋轉(zhuǎn)a.插入前b.插入后,調(diào)整前c.調(diào)整后

右單旋轉(zhuǎn)與左單旋轉(zhuǎn)類似,沿插入路徑檢查三個(gè)點(diǎn)a、c、E,若它們處于“/”直線上的同一個(gè)方向,則要作右單旋轉(zhuǎn),即以結(jié)點(diǎn)c為軸順時(shí)針旋轉(zhuǎn),如圖所示。h+1h+1EcBaDx00hBaDcEhh01hxhBaDcEh+1212/5/202352數(shù)據(jù)結(jié)構(gòu)講義

三、先左后右雙向旋轉(zhuǎn)

右圖為插入前的子樹,根結(jié)點(diǎn)a的左子樹比右子樹高度高1,待插入結(jié)點(diǎn)x將插入到結(jié)點(diǎn)b的右子樹上,并使結(jié)點(diǎn)b的右子樹高度增1,從而使結(jié)點(diǎn)a的平衡因子的絕對值大于1,導(dǎo)致結(jié)點(diǎn)a為根的子樹平衡被破壞。hDbh-1GcFh-1hEa0012/5/202353數(shù)據(jù)結(jié)構(gòu)講義2h-1GchEaDhbFxh02hDbh-1GcFh-1hEax12-1h-1GhEacDhbFxh00-1a.插入后,調(diào)整前b.先左旋轉(zhuǎn)c.再右旋轉(zhuǎn)2/5/202354數(shù)據(jù)結(jié)構(gòu)講義d.插入后,調(diào)整前e.先左旋轉(zhuǎn)f.再右旋轉(zhuǎn)h-1cGhEaDhbFxh001h-1GchEaDhbFxh11-2hDbh-1GcFh-1hEax2-1-1hDbh-1GcFh-1hEax2-1-12/5/202355數(shù)據(jù)結(jié)構(gòu)講義

沿插入路徑檢查三個(gè)點(diǎn)a、b、c,若它們呈“<”字形,需要進(jìn)行先左后右雙向旋轉(zhuǎn):1.首先,對結(jié)點(diǎn)b為根的子樹,以結(jié)點(diǎn)c為軸,向左逆時(shí)針旋轉(zhuǎn),結(jié)點(diǎn)c成為該子樹的新根,如圖(b、e);2.由于旋轉(zhuǎn)后,待插入結(jié)點(diǎn)x相當(dāng)于插入到結(jié)點(diǎn)b為根的子樹上,這樣a、c、b三點(diǎn)處于“/”直線上的同一個(gè)方向,則要作右單旋轉(zhuǎn),即以結(jié)點(diǎn)c為軸順時(shí)針旋轉(zhuǎn),如圖(c、f)。2/5/202356數(shù)據(jù)結(jié)構(gòu)講義四.先右后左雙向旋轉(zhuǎn)

先右后左雙向旋轉(zhuǎn)和先左后右雙向旋轉(zhuǎn)對稱,請讀者自行補(bǔ)充整理。

在平衡的二叉排序樹T上插入一個(gè)關(guān)鍵碼為kx的新元素,遞歸算法可描述如下:

⒈若T為空樹,則插入一個(gè)數(shù)據(jù)元素為kx的新結(jié)點(diǎn)作為T的根結(jié)點(diǎn),樹的深度增1;

⒉若kx和T的根結(jié)點(diǎn)關(guān)鍵碼相等,則不進(jìn)行插入;

⒊若kx小于T的根結(jié)點(diǎn)關(guān)鍵碼,而且在T的左子樹中不存在與kx有相同關(guān)鍵碼的結(jié)點(diǎn),

則將新元素插入在T的左子樹上,并且當(dāng)插入之后的左子樹深度增加1時(shí),分別就下列情況進(jìn)行處理:2/5/202357數(shù)據(jù)結(jié)構(gòu)講義

T的根結(jié)點(diǎn)平衡因子為-1(右子樹的深度大于左子樹的深度),則將根結(jié)點(diǎn)的平衡因子更改為0,T的深度不變;

T的根結(jié)點(diǎn)平衡因子為0(左、右子樹的深度相等),則將根結(jié)點(diǎn)的平衡因子更改為1,T的深度增加1;

T的根結(jié)點(diǎn)平衡因子為1(左子樹的深度大于右子樹的深度),則

若T的左子樹根結(jié)點(diǎn)的平衡因子為1,需進(jìn)行單向右旋平衡處理,并且在右旋處理之后,將根結(jié)點(diǎn)和其右子樹根結(jié)點(diǎn)的平衡因子更改為0,樹的深度不變;

若T的左子樹根結(jié)點(diǎn)平衡因子為-1,需進(jìn)行先左后右雙向旋轉(zhuǎn)平衡處理,并且在旋轉(zhuǎn)處理之后,修改根結(jié)點(diǎn)和其左、右子樹根結(jié)點(diǎn)的平衡因子,樹的深度不變。2/5/202358數(shù)據(jù)結(jié)構(gòu)講義

⒋若kx大于T的根結(jié)點(diǎn)關(guān)鍵碼,而且在T的右子樹中不存在與kx有相同關(guān)鍵碼的結(jié)點(diǎn),則將新元素插入在T的右子樹上,并且當(dāng)插入之后的右子樹深度增加1時(shí),分別就不同情況處理之。其處理操作和(3.)中所述相對稱,讀者可自行補(bǔ)充整理?!舅惴?.7】typedefstructNODE{ ElemTypeelem;/*數(shù)據(jù)元素*/

intbf;/*平衡因子*/

structNODE*lc,*rc;/*左右子女指針*/ }NodeType;/*結(jié)點(diǎn)類型*/2/5/202359數(shù)據(jù)結(jié)構(gòu)講義

voidR_Rotate(NodeType**p){ /*對以*p指向的結(jié)點(diǎn)為根的子樹,作右單旋轉(zhuǎn)處理,處理之后,*p指向的結(jié)點(diǎn)為子樹的新根*/

lp=(*p)->lc;/*lp指向*p左子樹根結(jié)點(diǎn)*/(*p)->lc=lp->rc;/*lp的右子樹掛接*p的左子樹*/

lp->rc=*p;*p=lp;/**p指向新的根結(jié)點(diǎn)*/}

voidL_Rotate(NodeType**p){ /*對以*p指向的結(jié)點(diǎn)為根的子樹,作左單旋轉(zhuǎn)處理,處理之后,*p指向的結(jié)點(diǎn)為子樹的新根*/

lp=(*p)->rc;/*lp指向*p右子樹根結(jié)點(diǎn)*/(*p)->rc=lp->lc;/*lp的左子樹掛接*p的右子樹*/

lp->lc=*p;*p=lp;/**p指向新的根結(jié)點(diǎn)*/}2/5/202360數(shù)據(jù)結(jié)構(gòu)講義

#defineLH1/*左高*/#defineEH0/*等高*/#defineRH1/*右高*/

void LeftBalance((NodeType**p){ /*對以*p指向的結(jié)點(diǎn)為根的子樹,作左平衡旋轉(zhuǎn)處理,處理之后,*p指向的結(jié)點(diǎn)為子樹的新根*/

lp=(*p)->lc;/*lp指向*p左子樹根結(jié)點(diǎn)*/

switch((*p)->bf) /*檢查*p平衡度,并作相應(yīng)處理*/{caseLH: /*新結(jié)點(diǎn)插在*p左子女的左子樹上,需作單右旋轉(zhuǎn)處理*/

(*p)->bf=lp->bf=EH;R_Rotate(p);break;

caseEH: /*原本左、右子樹等高,因左子樹增高使樹增高*/

(*p)->bf=LH; *paller=TRUE;break;2/5/202361數(shù)據(jù)結(jié)構(gòu)講義

caseRH: /*新結(jié)點(diǎn)插在*p左子女的右子樹上,需作先左后右雙旋處理*/

rd=lp->rc;/*rd指向*p左子女的右子樹根結(jié)點(diǎn)*/

switch(rd->bf) /*修正*p及其左子女的平衡因子*/ {case LH:(*p)->bf=RH;lp->bf=EH;break; case EH:(*p)->bf=lp->bf=EH;break; case RH:(*p)->bf=EH;lp->bf=LH;break; }/*switch(rd->bf)*/ rd->bf=EH; L_Rotate(&((*p)->lc)); /*對*p的左子樹作左旋轉(zhuǎn)處理*/

R_Rotate(p); /*對*t作右旋轉(zhuǎn)處理*/ }/*switch((*p)->bf)*/}/*LeftBalance*/2/5/202362數(shù)據(jù)結(jié)構(gòu)講義

intInsertAVL(NodeType**t,ElemTypee,Boolean*taller){ /*若在平衡的二叉排序樹t中不存在和e有相同關(guān)鍵碼的結(jié)點(diǎn),則插入一個(gè)數(shù)據(jù)元素為e的*//*新結(jié)點(diǎn),并反回1,否則反回0。若因插入而使二叉排序樹失去平衡,則作平衡旋轉(zhuǎn)處理,*//*布爾型變量taller反映t長高與否*/

if(!(*t))/*插入新結(jié)點(diǎn),樹“長高”,置taller為TURE*/ { *t=(NodeType*)malloc(sizeof(NodeType));(*T)->elem=e; (*t)->lc=(*t)->rc=NULL;(*t)->bf=EH;*taller=TRUE; }/*if*/2/5/202363數(shù)據(jù)結(jié)構(gòu)講義

else { if(e.key==(*t)->elem.key)/*樹中存在和e有相同關(guān)鍵碼的結(jié)點(diǎn),不插入*/ { taller=FALSE;return0;} if(e.key<(*t)->elem.key) { /*應(yīng)繼續(xù)在*t的左子樹上進(jìn)行*/

if(!InsertAVL(&((*t)->lc)),e,&taller)) return0;/*未插入*/

if(*taller) /*已插入到(*t)的左子樹中,且左子樹增高*/

switch((*t)->bf) /*檢查*t平衡度*/ {caseLH: /*原本左子樹高,需作左平衡處理*/

LeftBalance(t); *taller=FALSE;break;2/5/202364數(shù)據(jù)結(jié)構(gòu)講義

caseEH: /*原本左、右子樹等高,因左子樹增高使樹增高*/ (*t)->bf=LH; *taller=TRUE;break; caseRH: /*原本右子樹高,使左、右子樹等高*/ (*t)->bf=EH; *taller=FALSE;break; } }/*if*/ else /*應(yīng)繼續(xù)在*t的右子樹上進(jìn)行*/ { if(!InsertAVL(&((*t)->rc)),e,&taller)) return0;/*未插入*/

if(*taller) /*已插入到(*t)的左子樹中,且左子樹增高*/2/5/202365數(shù)據(jù)結(jié)構(gòu)講義

switch((*t)->bf) /*檢查*t平衡度*/ {caseLH: /*原本左子樹高,使左、右子樹等高*/ (*t)->bf=EH; *taller=FALSE;break; caseEH: /*原本左、右子樹等高,因右子樹增高使樹增高*/ (*t)->bf=RH; *taller=TRUE;break; caseRH:/*原本右子樹高,需作右平衡處理

RightBalance(t); *taller=FALSE;break; } }/*else*/ }/*else*/ return1;}/*InsertAVL*/2/5/202366數(shù)據(jù)結(jié)構(gòu)講義

【平衡樹的查找分析】

在平衡樹上進(jìn)行查找的過程和二叉排序樹相同,因此,在查找過程中和給定值進(jìn)行比較的關(guān)鍵碼個(gè)數(shù)不超過樹的深度。那么,含有n個(gè)關(guān)鍵碼的平衡樹的最大深度是多少呢?為解答這個(gè)問題,我們先分析深度為h的平衡樹所具有的最少結(jié)點(diǎn)數(shù)。假設(shè)以Nh表示深度為h的平衡樹中含有的最少結(jié)點(diǎn)數(shù)。顯然,N0=0,N1=1,N2=2,并且Nh=Nh-1+Nh-2+1。這個(gè)關(guān)系和斐波那契序列極為相似。利用歸納法容易證明:當(dāng)h≥0時(shí)Nh

=Fh+2–1,而約等于其中2/5/202367數(shù)據(jù)結(jié)構(gòu)講義

則Nh約等于反之,含有n個(gè)結(jié)點(diǎn)得平衡樹得最大深度為因此,在平衡樹上進(jìn)行查找的時(shí)間復(fù)雜度為O(logn)。上述對二叉排序樹和二叉平衡樹的查找性能的討論都是在等概率的前提下進(jìn)行的。2/5/202368數(shù)據(jù)結(jié)構(gòu)講義

則Nh約等于反之,含有n個(gè)結(jié)點(diǎn)得平衡樹得最大深度為2/5/202369數(shù)據(jù)結(jié)構(gòu)講義9.3.3B-樹和B+樹

B-樹是一種平衡的多路查找樹,它在文件系統(tǒng)中很有用,是大型數(shù)據(jù)庫文件的一種組織結(jié)構(gòu)。數(shù)據(jù)庫文件是同類型記錄的值的集合,是存儲在外存儲器上的數(shù)據(jù)結(jié)構(gòu)。因此,在數(shù)據(jù)庫文件中按關(guān)鍵碼查找記錄,對數(shù)據(jù)庫文件進(jìn)行記錄的插入和刪除,就要對外存進(jìn)行讀、寫操作。由于外存讀、寫較慢,因而在對大的數(shù)據(jù)庫文件進(jìn)行操作時(shí),為了減少外存的讀、寫次數(shù),應(yīng)按關(guān)鍵碼對其建立索引,即組織成索引文件。索引文件由索引表和數(shù)據(jù)區(qū)兩部分組成。索引表是按關(guān)鍵碼建立的記錄的邏輯結(jié)構(gòu),并與數(shù)據(jù)區(qū)的物理記錄建立對應(yīng)關(guān)系的表。索引表也是文件,是以索引項(xiàng)為記錄的集合,其數(shù)據(jù)結(jié)構(gòu)按關(guān)鍵碼可以是線性的或是樹型的。2/5/202370數(shù)據(jù)結(jié)構(gòu)講義一、B-樹及其查找

定義:一棵m階的B-樹,或者為空樹,或?yàn)闈M足下列特性的m叉樹:

⑴樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹;

⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn),則至少有兩棵子樹;

⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2

棵子樹;

⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù):(n,A0,K1,A1,K2,…,Kn,An)

其中:Ki(i=1,2,…,n)為關(guān)鍵碼,且Ki<Ki+1,Ai為指向子樹根結(jié)點(diǎn)的指針(i=0,1,…,n),且指針Ai所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Ki,小于Ki+1(i=1,2,…,n-1),A0所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于K1,An所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于Kn,m/2

1≤n≤m1,n為關(guān)鍵碼的個(gè)數(shù)。實(shí)際上,結(jié)點(diǎn)中還應(yīng)包含指向父結(jié)點(diǎn)的指針和指向關(guān)鍵碼對應(yīng)數(shù)據(jù)區(qū)記錄的指針。⑸所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上,并且不帶信息(可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn),實(shí)際上這些結(jié)點(diǎn)不存在,指向這些結(jié)點(diǎn)的指針為空)。2/5/202371數(shù)據(jù)結(jié)構(gòu)講義【例9.4】如圖9.15所示為一棵5階的B-樹,其深度為4。23722025379849343541515326668271762123026978154tFFFFFFFFFFFFFFFFFFFFFabcdeghfi一棵5階的B-樹2/5/202372數(shù)據(jù)結(jié)構(gòu)講義

B-樹的查找類似二叉排序樹的查找,所不同的是B-樹每個(gè)結(jié)點(diǎn)上是多關(guān)鍵碼的有序表,在到達(dá)某個(gè)結(jié)點(diǎn)時(shí),先在有序表中查找,若找到,則查找成功;否則,到按照對應(yīng)的指針信息指向的子樹中去查找,當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時(shí),則說明樹中沒有對應(yīng)的關(guān)鍵碼,查找失敗。即在B-樹上的查找過程是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找關(guān)鍵碼交叉進(jìn)行的過程。比如,在圖9.15中查找關(guān)鍵碼為93的元素。首先,從t指向的根結(jié)點(diǎn)(a)開始,結(jié)點(diǎn)(a)中只有一個(gè)關(guān)鍵碼,且93大于它,因此,按(a)結(jié)點(diǎn)指針域A1到結(jié)點(diǎn)(c)去查找,結(jié)點(diǎn)(c)有兩個(gè)關(guān)鍵碼,而93也都大于它們,應(yīng)按(c)結(jié)點(diǎn)指針域A2到結(jié)點(diǎn)(i)去查找,在結(jié)點(diǎn)(i)中順序比較關(guān)鍵碼,找到關(guān)鍵碼K3等于93。2/5/202373數(shù)據(jù)結(jié)構(gòu)講義ResultSearchBTree(NodeType*t,KeyTypekx){ /*在m階B樹t上查找關(guān)鍵碼kx,反回(pt,i,tag)。若查找成功,則特征值tag=1,指針pt所指結(jié)點(diǎn)中第i個(gè)關(guān)鍵碼等于kx;否則,特征值tag=0,查找失敗,若是為了插入結(jié)點(diǎn),則以kx為關(guān)鍵碼的記錄應(yīng)插入在指針pt所指結(jié)點(diǎn)中第i個(gè)和第i+1個(gè)關(guān)鍵碼之間*/Resultrs;NodeType*p=t,*q=NULL; /*初始化,p指向待查結(jié)點(diǎn),q指向p的雙親*/inti,found=FALSE; while(p&&!found) { i=Search(p,kx);/*在p-->key[1…keynum]中查找*/

if(i>0&&p->key[i]==kx)found=TRUE;/*找到*/

else {q=p;p=p->ptr[i];}/*沒找到,保存當(dāng)前結(jié)點(diǎn)指針到q中*/ }2/5/202374數(shù)據(jù)結(jié)構(gòu)講義rs.tag=found; /*查找成功與失敗信息*/

if(!found) p=q;/*查找不成功,反回kx的應(yīng)插入結(jié)點(diǎn)的指針信息*/

rs.pt=p;rs.i=i;/*查找成功,反回指向kx位置信息;查找不成功,反回kx的應(yīng)插入位置信息*/

returnrs; }2/5/202375數(shù)據(jù)結(jié)構(gòu)講義【查找分析】

B-樹的查找是由兩個(gè)基本操作交叉進(jìn)行的過程,即⑴在B-樹上找結(jié)點(diǎn);⑵在結(jié)點(diǎn)中找關(guān)鍵碼。由于,通常B-樹是存儲在外存上的,操作⑴就是通過指針在磁盤相對定位,將結(jié)點(diǎn)信息讀入內(nèi)存,之后,再對結(jié)點(diǎn)中的關(guān)鍵碼有序表進(jìn)行順序查找或折半查找。因?yàn)?,在磁盤上讀取結(jié)點(diǎn)信息比在內(nèi)存中進(jìn)行關(guān)鍵碼查找耗時(shí)多,所以,在磁盤上讀取結(jié)點(diǎn)信息的次數(shù),即B-樹的層次樹是決定B-樹查找效率的首要因素。那么,對含有n個(gè)關(guān)鍵碼的m階B-樹,最壞情況下達(dá)到多深呢?可按二叉平衡樹進(jìn)行類似分析。首先,討論m階B-數(shù)各層上的最少結(jié)點(diǎn)數(shù)。2/5/202376數(shù)據(jù)結(jié)構(gòu)講義B-樹定義:第一層至少有1個(gè)結(jié)點(diǎn);第二層至少有2個(gè)結(jié)點(diǎn);由于除根結(jié)點(diǎn)外的每個(gè)非終端結(jié)點(diǎn)至少有棵子樹,則第三層至少有2()個(gè)結(jié)點(diǎn)依此類推,第k+1層至少有個(gè)結(jié)點(diǎn)而k+1層的結(jié)點(diǎn)為葉子結(jié)點(diǎn)。若m階B-樹有n個(gè)關(guān)鍵碼,則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為n+1,由此有:即這就是說,在含有n個(gè)關(guān)鍵碼的B-樹上進(jìn)行查找時(shí),從根結(jié)點(diǎn)到關(guān)鍵碼所在結(jié)點(diǎn)的路徑上涉及的結(jié)點(diǎn)數(shù)不超過2/5/202377數(shù)據(jù)結(jié)構(gòu)講義二.B-樹的插入

在B-樹上插入關(guān)鍵碼與在二叉排序樹上插入結(jié)點(diǎn)不同,關(guān)鍵碼的插入不是在葉結(jié)點(diǎn)上進(jìn)行的,而是在最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵碼。添加分兩種情況:1.若添加后,結(jié)點(diǎn)上關(guān)鍵碼個(gè)數(shù)小于等于m-1,則插入結(jié)束;2.若添加后,該結(jié)點(diǎn)上關(guān)鍵碼個(gè)數(shù)為m個(gè),因而使該結(jié)點(diǎn)的子樹超過了m棵,這與B-樹定義不符,所以要進(jìn)行調(diào)整,即結(jié)點(diǎn)的“分裂”。結(jié)點(diǎn)的“分裂”方法為:關(guān)鍵碼加入結(jié)點(diǎn)后,將結(jié)點(diǎn)中的關(guān)鍵碼分成三部分,使得前后兩部分關(guān)鍵碼個(gè)數(shù)均大于等于m/2,而中間部分只有一個(gè)結(jié)點(diǎn)。前后兩部分成為兩個(gè)結(jié)點(diǎn),中間的一個(gè)結(jié)點(diǎn)將其插入到父結(jié)點(diǎn)中。若插入父結(jié)點(diǎn)而使父結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)為m個(gè),則父結(jié)點(diǎn)繼續(xù)分裂,直到插入某個(gè)父結(jié)點(diǎn),其關(guān)鍵碼個(gè)數(shù)小于m??梢姡珺-樹是從底向上生長的。2/5/202378數(shù)據(jù)結(jié)構(gòu)講義

【算法9.9】NodeType*NewRoot(NodeType*t,NodeType*stptr,KeyTypekx,ElemType*xelem){/*根結(jié)點(diǎn)已分裂或*t是空樹,產(chǎn)生新根,返回新根的指針*//*stptr為B-樹中待插入關(guān)鍵碼kx相關(guān)的子樹指針,*/NodeType*p; p=(NodeType*)malloc(sizeof(NodeType));/*生成根結(jié)點(diǎn)*/

p->keynum=1;p->key[1]=kx;p->eptr[1]=xelem; p->nptr[0]=t;/*A0指向原根結(jié)點(diǎn)*/

p->nptr[1]=stptr;/*A1指向分裂結(jié)點(diǎn)時(shí)生成的結(jié)點(diǎn)*/2/5/202379數(shù)據(jù)結(jié)構(gòu)講義

p->parent=NULL;/*根結(jié)點(diǎn)的父結(jié)點(diǎn)為空*/

t->parent=p;/*原根結(jié)點(diǎn)中指向父結(jié)點(diǎn)的指針,指向新根*/

stptr->parent=p;/*原根結(jié)點(diǎn)分裂時(shí),生成的結(jié)點(diǎn)中指向父結(jié)點(diǎn)的指針,指向新根*/

returnp;}intInsertBTree(NodeType**t,ElemType*xelem){/*將xelem指向的結(jié)點(diǎn),按其關(guān)鍵碼插入到m階B-樹*t上,生成其索引。若引起結(jié)點(diǎn)過大,*//*則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整,使*t仍為m階B樹*/ints,finished=FALSE;2/5/202380數(shù)據(jù)結(jié)構(gòu)講義

NodeType*stptr;/*stptr為B-樹中待插入元素關(guān)鍵碼相關(guān)的子樹指針*/KeyTypekx=xelem->key;/*kx為待插入元素關(guān)鍵碼*/ElemType*elemptr=xelem;/*xelem為待插入元素?cái)?shù)據(jù)區(qū)指針*/Resultrs; rs=SearchBTree(*t,kx);/*在*t上查找kx關(guān)鍵碼*/

if(!rs.tag)/*查找不成功時(shí)進(jìn)行插入操作*/ { stptr=NULL;/*插入關(guān)鍵碼在最底層,該關(guān)鍵碼相關(guān)的子樹指針為空*/

while(rs.pt&&!finished)/*rs.pt指向關(guān)鍵碼插入的結(jié)點(diǎn),若rs.pt為空,將產(chǎn)生新根*/ {/*finished=TRUE表示無需產(chǎn)生新根便插入成功*/

Insert(rs.pt,rs.i,kx,elemptr,stptr);/*插入到rs.pt指向的結(jié)點(diǎn)rs.i處*/

if(rs.pt->keynum<m)finished=TRUE; /*插入完成*/2/5/202381數(shù)據(jù)結(jié)構(gòu)講義

else { /*分裂rs.pt指向的結(jié)點(diǎn)*/

s=(m+1)/2;/*s為結(jié)點(diǎn)中上升到父結(jié)點(diǎn)中的關(guān)鍵碼位置*/

kx=rs.pt->key[s];/*得到插入父結(jié)點(diǎn)中的關(guān)鍵碼kx*/elemptr=rs.pt->eptr[s];/*得到關(guān)鍵碼kx對應(yīng)的數(shù)據(jù)區(qū)記錄指針*/

stptr

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論