版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、算法以及數(shù)據(jù)基本結(jié)構(gòu)8.1 基本概念與術(shù)語同一類型的記錄(數(shù)據(jù)元素)的集合。指定某個(gè)值,在查找表中確定是否存在一個(gè)記錄,該記錄的等于給定值。記錄(數(shù)據(jù)元素)中的某個(gè)數(shù)據(jù)項(xiàng)的值。 主關(guān)鍵字 該關(guān)鍵字可以唯一地標(biāo)識(shí)一個(gè)記錄。 次關(guān)鍵字 該關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)記錄。靜態(tài)查找表 對查找表的查找僅是以查詢?yōu)槟康?,不改?dòng)查找表中的數(shù)據(jù)。動(dòng)態(tài)查找表 在查找的過程中同時(shí)插入不存在的記錄,或刪除某個(gè)已存在的記錄。 查找表中存在滿足查找條件的記錄。查找不成功 查找表中不存在滿足查找條件的記錄。BUPT SCSTBUPT內(nèi)查找 整個(gè)查找過程都在內(nèi)存中進(jìn)行。外查找 在查找過程中需要訪問外存。平均查找長度ASL查找方
2、法時(shí)效的度量 為確定記錄在查找表中的位置,需將關(guān)鍵字和給定值比較次數(shù)的期望值。 查找成功時(shí)的ASL計(jì)算方法: n:記錄的個(gè)數(shù) pi:查找第i個(gè)記錄的概率, ( 不特別聲明時(shí)認(rèn)為等概率 pi =1/n ) ci:找到第i個(gè)記錄所需的比較次數(shù)約定:無特殊說明,一般默認(rèn)關(guān)鍵字的類型為整型BUPT SCSTBUPT8.2 順序表的查找 0 1 n-1 n r0.n a0 a1 an-1 rn.key=K算法描述int seqsearch (int *a, const int n, const int K ) int i = 0; an = K; while (ai != K) i+; return i
3、;BUPT SCSTBUPT程序設(shè)計(jì)技巧 設(shè)置監(jiān)視哨,提高算法效率。性能分析空間:一個(gè)輔助空間。時(shí)間: 1) 查找成功時(shí)的平均查找長度 設(shè)表中各記錄查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/2 2)查找不成功時(shí)的平均查找長度 ASLf =n+1算法特點(diǎn)算法簡單,對表結(jié)構(gòu)無任何要求n很大=查找效率較低改進(jìn)措施:非等概率查找時(shí),可將查找概率高的記錄盡量排在表前部。BUPT SCSTBUPT8.3 二分查找滿足 ri.key ri+1.key, 0 i n-1 仍可用順序查找,但在找不到時(shí)不需比較到表尾,只需比較到比給定值大的記錄就可終止。折半(二分)查找法 1 2 3
4、 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid high =(low+high)/2 K=21 l h m K=85 l h m 1 11 6 1 11 6 1 5 3 7 11 9 4 5 4 10 11 10 10 9BUPT SCSTBUPT算法描述int binsearch ( int K, int v , int n ) int low, high, mid; low = 1; high = n; while ( low = high ) mid = ( low + high ) / 2; if ( K vmid
5、 ) low = mid + 1; else /* 找到了匹配的值*/ return mid; return -1; /* 沒有查到*/BUPT SCSTBUPT性能分析 h=log2n+1 同完全二叉樹,二叉樹性質(zhì)4成功查找時(shí)的平均查找長度(等概率): ASLs= 例:ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找時(shí)的查找長度:h-1或h次BUPT SCSTBUPT -13-46-79-101-22-34-55-67-88-910-1111-639147 102581112h判定樹(描述查找過程的二叉樹)外結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)lc,flag);/ 中序遍歷左子樹 if(pre=NUL
6、L) pre=t;/ 中序的第一個(gè)結(jié)點(diǎn)不判斷 else if(pre-datadata) pre=t;/前驅(qū)指針指向當(dāng)前結(jié)點(diǎn) else flag=FLASE; /不是完全二叉樹 JudgeBST(t-rc,flag);/ 中序遍歷右子樹 BUPT SCSTBUPT方法2:照定義,二叉排序樹的左右子樹都是二叉排序樹,根結(jié)點(diǎn)的值大于左子樹中所有值而小于右子樹中所有值,即根結(jié)點(diǎn)大于左子樹的最大值而小于右子樹的最小值。 BUPT SCSTBUPTbool JudgeBST(BTree t) if(t=NULL) return TRUE; if (JudgeBST(t-lc) & JudgeBST(t-
7、rc) m=max(t-llink); n=min(t-rlink);/左子樹中最大值和右子樹中最小值 return (t-datam & t-datarc!=null) p=p-rc; return p-data; int min(BTree p)/求右子最小值 if (p=NULL) return maxint; else while(p-lc!=NULL) p=p-lc; return p-data; 在二叉排序樹上的操作1.查找例 K=28 K=32BUPT SCSTBUPTbst45241228bst455390241228325390 查找步驟:若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字,
8、成功。 否則,若小于根結(jié)點(diǎn)的關(guān)鍵字值,查其左子樹。 若大于根結(jié)點(diǎn)的關(guān)鍵字值,查其右子樹。 在左右子樹上的操作類似。BUPT SCSTBUPTBitree SearchBST ( BiTree T, KeyType key ) / 在二叉分類樹查找關(guān)鍵字之值為 key 的結(jié)點(diǎn),找到返回該結(jié) / 點(diǎn)的地址,否則返回空。T 為根結(jié)點(diǎn)的指針。 if ( ( T=NULL) | ( key=T -data) ) return ( T ) ; else if (key data. key ) return (SearchBST (T -lc, key ); else return (SearchBST (
9、 T - rc, key ); 查找算法2.插入首先執(zhí)行查找算法,找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。注意:新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。3.生成算法步驟 反復(fù)執(zhí)行以下操作 a. 讀入一個(gè)記錄,設(shè)其關(guān)鍵字為K; b. 調(diào)用查找算法,確定插入位置; c. 調(diào)用插入算法,實(shí)施插入結(jié)點(diǎn)的操作;BUPT SCSTBUPT例:將序列122、99、250、110、300、280 作為二叉排序樹的結(jié)點(diǎn)的關(guān)鍵字值,生成二叉排序樹。BUPT SCSTBUPT12212299122250991222501109912225
10、0300110994.刪除依據(jù)被刪除結(jié)點(diǎn)p的不同情況分析:1. p是葉子結(jié)點(diǎn):修改其雙親指針即可2. p只有左孩子:用p的左子樹代替以p為根的子樹 p只有右孩子:用p的右子樹代替以p為根的子樹3. p有兩個(gè)孩子:找到p的中序后繼(或前趨)結(jié)點(diǎn)q, q的數(shù)據(jù)復(fù)制給p, 刪除只有右子(或左子)/無孩子的qBUPT SCSTBUPT例:BUPT SCSTBUPT(1)(2)(2)(3)5320901050869541241528891304539878992void Delete(BSTree T, keytype X) /在二叉排序樹T上,刪除為X的結(jié)點(diǎn)。 BSTree f, p=T; while
11、 (p & p-key!=X) /查找值為X的結(jié)點(diǎn) if (p-keyX) f=p; p=p-lc;/f為p的雙親 else f=p; p=p-rc; if (p=NULL) printf(“無關(guān)鍵字為X的結(jié)點(diǎn)n”); exit(0); if (p-lc=NULL) /被刪結(jié)點(diǎn)無左子樹 if (f-lc=p) f-lc=p-rc;/將被刪結(jié)點(diǎn)的右子樹接到其雙親上 else f-rc=p-rc; else /被刪結(jié)點(diǎn)有左子樹 q=p; s=p-lc; while (s-rc !=NULL) /查左子樹中最右下的結(jié)點(diǎn)(中序最后結(jié)點(diǎn)) q=s; s=s-rc; p-key=s-key; /結(jié)點(diǎn)值用其
12、左子樹最右下的結(jié)點(diǎn)的值代替 if (q=p) p-lc=s-lc;/被刪結(jié)點(diǎn)左子樹的根結(jié)點(diǎn)無右子女 else q-rc=s-lc; /s是被刪結(jié)點(diǎn)左子樹中序序列最后一個(gè)結(jié)點(diǎn) free(s); BUPT SCSTBUPT4. 性能分析給定樹的形態(tài),等概率查找成功時(shí)的ASL=ci /n最差(單支樹):(n+1)/2最好(類似折半查找的判定樹):log2(n+1)-1隨機(jī):1+4log2n關(guān)鍵字有序出現(xiàn)時(shí),構(gòu)造出“退化”的二叉排序樹,樹深為n,各種操作代價(jià)O(n)。避免方法:采用平衡二叉樹BUPT SCSTBUPT8.7 平衡二叉樹(AVL樹)1. 定義平衡二叉樹或者是空樹,或者是滿足如下性質(zhì)的二叉
13、排序樹: 1)它的左、右子樹的高度之差的絕對值不超過1; 2)其左右子樹本身又各是一棵平衡二叉樹。二叉樹上結(jié)點(diǎn)的平衡因子: 該結(jié)點(diǎn)的左子樹高度減去右子樹的高度。BUPT SCSTBUPT平衡二叉樹非平衡二叉樹302010252235383020353233001-10-1100-12-2平衡二叉樹:每個(gè)結(jié)點(diǎn)的平衡因子都為 1、1、0 的二叉排序樹。2.結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) lc bf key otherinfo rc lc:左孩子指針 rc:右孩子指針 bf:平衡因子 key:記錄的關(guān)鍵字 otherinfo:記錄的其它數(shù)據(jù)成分BUPT SCSTBUPT4. 在平衡二叉樹上的操作查找查找方法同二叉排
14、序樹。插入 插入新結(jié)點(diǎn)之后仍應(yīng)保持平衡二叉樹的性質(zhì)不變。例 平衡二叉樹的生成過程BUPT SCSTBUPT15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590調(diào)整范圍的確定 插入結(jié)點(diǎn)后,找到離插入結(jié)點(diǎn)最近且平衡因子絕對值超過1的祖先結(jié)點(diǎn)(危機(jī)節(jié)點(diǎn)),則以該危機(jī)節(jié)點(diǎn)為根的子樹將是可能不平衡的最小子樹,可將重新平衡的范圍局限于這棵子樹。調(diào)整的類型 LL型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子的左子樹上LR型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子的右子樹上RL型-表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子的左子樹上RR型-
15、表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子的右子樹上BUPT SCSTBUPT調(diào)整的方法LL型平衡旋轉(zhuǎn)一次順時(shí)針旋轉(zhuǎn)BUPT SCSTBUPTAB+1h-10+2+1hh-1h-1LL 型調(diào)整BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)調(diào)整前:高度為 h + 1 中序序列:ABBLBRAR調(diào)整后:高度為 h + 1 中序序列:ABBLBR注意:調(diào)整后 平衡因子為 0ABARLR型平衡旋轉(zhuǎn)一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)BUPT SCSTBUPTAB+1h-10+2-1h-1LR 型調(diào)整BLAR危機(jī)結(jié)點(diǎn)CBCCLCRh-2h-2h-10+1CB0h-1BLARACRh-2CLh-1-10ABBLAR
16、CCLCR調(diào)整后: 高度為 h + 1 中序序列:ABBLARCCLCRA調(diào)整前: 高度為 h + 1 中序序列:h-1情形A注意:調(diào)整后 平衡因子為 +1,0,0LR型平衡旋轉(zhuǎn)一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)BUPT SCSTBUPTAB+1h-10+2-1h-1LR 型調(diào)整BLAR危機(jī)結(jié)點(diǎn)調(diào)整前: 高度為 h + 1 中序序列:注意:改組后 平衡度為 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL調(diào)整后: 高度為 h + 1 中序序列:AABBLARCCRCL情形BLR型平衡旋轉(zhuǎn)一次逆時(shí)針旋轉(zhuǎn)+一次順時(shí)針旋轉(zhuǎn)BUPT
17、SCSTBUPT注意:調(diào)整后 平衡因子為 0,0,0AB+10+2-1LR 型調(diào)整危機(jī)結(jié)點(diǎn)調(diào)整前: 高度為 2 中序序列:CBC0ABCA新插入結(jié)點(diǎn)ABC調(diào)整后: 高度為 2 中序序列:ca0b00情形CRR型平衡旋轉(zhuǎn)一次逆時(shí)針旋轉(zhuǎn)BUPT SCSTBUPTAB-1h-10-2-1hh-1h-1RR 型調(diào)整BLBRALBA0h0h-1h-1BLAL危機(jī)結(jié)點(diǎn)調(diào)整前:高度為 h + 1 中序序列:BAALBLBR調(diào)整后:高度為 h + 1 中序序列:注意:調(diào)整后 平衡因子為 0ABBRBAALBLBRRL型平衡旋轉(zhuǎn)一次順時(shí)針旋轉(zhuǎn)+一次逆時(shí)針旋轉(zhuǎn)BUPT SCSTBUPTAALCRCLBRALCRC
18、LBRALCLBRCRBCABCACB-100h-1h-2h-1 h-211(-1)00(1)-1(0)危機(jī)結(jié)點(diǎn)刪除 (思路同插入)將刪除結(jié)點(diǎn)q轉(zhuǎn)化為q最多有一個(gè)孩子的情形,即若q有兩個(gè)孩子,則以其中序前驅(qū)/后繼結(jié)點(diǎn)r取代它,刪除r;若樹的平衡性被破壞,利用單一/雙重旋轉(zhuǎn)恢復(fù)。性能定理:一個(gè)具有n個(gè)結(jié)點(diǎn)的平衡二叉樹形,其高度h為 log22 結(jié)論:最壞情況下,AVL樹的高度約為2n,而完全平衡的二叉樹高度約為log2n,因此AVL樹是接近最優(yōu)的,其平均查找長度與log2n同數(shù)量級。BUPT SCSTBUPT8.7 B+樹與B-樹采用B+與B-樹的意義大量數(shù)據(jù)存放在外存中,由于是海量數(shù)據(jù),不可能
19、一次調(diào)入內(nèi)存。因此,要多次訪問外存,速度慢。所以,主要矛盾變?yōu)闇p少訪外次數(shù)。BUPT SCSTBUPT內(nèi)存用用二叉樹組織文件,需訪問外存次數(shù)太多。如:當(dāng)文件的記錄個(gè)數(shù)為 100,000時(shí),要找到給定關(guān)鍵字的記錄,需訪問外存17次(log100,000),太長了!BUPT SCSTBUPT502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭,可常駐內(nèi)存文件訪問示意圖:索引文件存在內(nèi)存、數(shù)據(jù)文件存在盤上B-樹B-樹是一種平衡的多路查找樹。應(yīng)用于文件系統(tǒng)。1. 定義 一棵 m 階B -樹,或?yàn)榭諛?,或?yàn)闈M足下列特性的 m 叉樹: 1、樹中每個(gè)結(jié)點(diǎn)最多有 m 棵子樹; 2
20、、若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn),則最少有兩棵子樹; 3、除根之外的所有非終端結(jié)點(diǎn)最少有 m / 2 棵子樹; 4、所有非終端結(jié)點(diǎn)包含 (n,A0,K1,A1,K2,Kn,An)信息數(shù)據(jù);其中n為結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù),Ai為指向子樹的指針,Ki為關(guān)鍵字。 5、所有葉子結(jié)點(diǎn)在同一層上,且不帶信息。BUPT SCSTBUPT例如:m = 4 階 B_ 樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外,每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)至少為 m/2 = 2 個(gè);結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為 1 。該 B_ 樹的深度為 4。葉子結(jié)點(diǎn)都在第 4 層上。BUPT SCSTBUPT1,993,47,58,641,391,271,112,43,781,181,35
21、FFFFFFFFFFFF第 1 層第 2 層第 3 層(L層)第 4 層(L1層)m/2 m棵子樹葉2. B-樹結(jié)點(diǎn)結(jié)構(gòu)(n, A0, K1, A1, K2, A2,., Kn, An)n: 關(guān)鍵字的個(gè)數(shù)A0: K1 且 Kn 的結(jié)點(diǎn)的地址(指在該 B_ 樹中)K1 =K2 = . = KnBUPT SCSTBUPT127階B-樹中每個(gè)結(jié)點(diǎn)最多有_個(gè)關(guān)鍵字;除根結(jié)點(diǎn)外所有非終端結(jié)點(diǎn)至少有_棵子樹;65階B+樹中除根結(jié)點(diǎn)外所有結(jié)點(diǎn)至少有_個(gè)關(guān)鍵字;最多有_棵子樹。高度為5(除葉子層之外)的三階B-樹至少有_個(gè)結(jié)點(diǎn)。BUPT SCSTBUPT31126643365思考:高度為h的m階B-樹(除葉子
22、層)至少有多少個(gè)結(jié)點(diǎn)? 樹查找過程類似于二叉樹的查找。如查找關(guān)鍵字為 KEY 的記錄。 從根開始查找,如果 Ki = KEY 則查找成功。 若 Ki KEY Ki+1; 查找 Ai 指向的結(jié)點(diǎn)若 KEY Kn; 查找 An指向的結(jié)點(diǎn)若 找到葉子,則查找失敗。BUPT SCSTBUPT設(shè)關(guān)鍵字的總數(shù)為 N ,求 m階 B_ 樹的最大層次 L。層次 結(jié)點(diǎn)數(shù)關(guān)鍵字的個(gè)數(shù)(最少) 1 1 1 2 2 2(m/2 -1) 3 2(m/2) 2 (m/2) (m/2 -1) 4 2 (m/2) 2 2(m/2)2(m/2 -1) L 2(m/2)L-2 2 ( m/2)L-2 (m/2 -1) L+1 2
23、(m/2)L-1 所以,N= 2 (m/2)L-1 -1故:Llog m/2(N+1)/2)+ 1BUPT SCSTBUPT設(shè) N 1000,000 且 m256 ,則 L m-1, 則該結(jié)點(diǎn)滿。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿結(jié)束。如結(jié)點(diǎn)原為: (m-1, A0, K1, A1, K2, A2, Km-1, Am-1)插入一個(gè)關(guān)鍵字之后變?yōu)椋?m, A0, K1, A1, K2, A2, Km, Am)該結(jié)點(diǎn)以K m/2為界,進(jìn)行分裂: .(K m/2 , p ) .(m/2-1,A0, (K1,A1)(K m/2-1, A m/2-1) (m- m/2,A m/2, K m/2+1 Km, A
24、m)生成新結(jié)點(diǎn) p, 將原結(jié)點(diǎn)的后半部分復(fù)制過去。若分裂一直進(jìn)行到根結(jié)點(diǎn),樹可能長高一層。BUPT SCSTBUPT(K m/2 , p ) 數(shù)據(jù)項(xiàng)插入上層結(jié)點(diǎn)之中PP例:3 階 B_ 樹的插入key=7BUPT SCSTBUPT3,127 24 3024,3045,7053902610039506185345,70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入樹刪除過程1、查找具有給定鍵值的關(guān)鍵字 Ki 2、如果 在第 L 層,可直接刪除(注意:第 L+1 層為葉子結(jié)點(diǎn)
25、),轉(zhuǎn) 4 。3、否則,則首先生成 “替身”。用該關(guān)鍵字的右邊子樹中的最左面的結(jié)點(diǎn)的關(guān)鍵字取代。然后,刪除第 L 層上的該關(guān)鍵字。4、從第 L 層開始進(jìn)行刪除。 A、不動(dòng):若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于m/2 -1和 m-1之間。則結(jié)束。 B、借:若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為 m/2 -1 。而它們左右兄弟結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) m/2 -1; 則借一關(guān)鍵字過來,結(jié)束。 C、并:若該結(jié)點(diǎn)的左右兄弟結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為m/2 -1; 則執(zhí)行合并結(jié)點(diǎn)的操作。如結(jié)點(diǎn)原為:( . (Ki, Ai), (Ki+1, Ai+1), . ) ( A0, (K1, A1 ) ) ( A0
26、, (K1, A1 ) ) K1 BUPT SCSTBUPT第 L 層:找到了被刪結(jié)點(diǎn)的替身。例如:3 階 B_ 樹的刪除操作。BUPT SCSTBUPT3244553 90371005061,70被刪關(guān)鍵字3244561 90371005370借:向被刪結(jié)點(diǎn)方向旋轉(zhuǎn)假定再刪除該關(guān)鍵字32445 903710061,703,2445 9010061,703,24 45 9010061,70并并并并:和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及兄弟合并。有可能進(jìn)行到根,使B_ 樹的深度降低一層!假定再刪除該關(guān)鍵字B+樹B+樹是一種B-樹的變形樹。應(yīng)用于索引順序文件系統(tǒng)。1. m階B+ 樹與 B- 樹的不同之處1)有
27、 n 棵子樹的結(jié)點(diǎn)中有 n 個(gè)關(guān)鍵字;2)非葉結(jié)點(diǎn)可以看成是索引部分 索引集Ai :第i個(gè)子結(jié)點(diǎn)的指針Ki :第i個(gè)子結(jié)點(diǎn)的最大(或最?。╆P(guān)鍵字3)所有葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向這些關(guān)鍵字記錄的指針,且葉子結(jié)點(diǎn)以關(guān)鍵字大小自小至大順序鏈接;數(shù)據(jù)集BUPT SCSTBUPT結(jié)點(diǎn)結(jié)構(gòu)非葉結(jié)點(diǎn) ( A1, K1, .,Ai, Ki, ., An,Kn) 索引集Ai :第i個(gè)子結(jié)點(diǎn)的指針Ki :第i個(gè)子結(jié)點(diǎn)的最大(或最小)關(guān)鍵字葉結(jié)點(diǎn) 全部關(guān)鍵字及指向關(guān)鍵字記錄的指針 數(shù)據(jù)集BUPT SCSTBUPT2 15 334 40 47 58 672 79 853 90 96 1052 85 13
28、23 33 67 852 105 1322 114 1324階B+樹rootsqt2. B+樹上的基本運(yùn)算1)查找方式1:從根結(jié)點(diǎn)開始,利用索引集結(jié)構(gòu),向下查找直到葉子結(jié)點(diǎn)方式2:從最小關(guān)鍵字開始,沿葉結(jié)點(diǎn)數(shù)據(jù)集的鏈結(jié)構(gòu)順序查找2)插入 僅在葉子結(jié)點(diǎn)上進(jìn)行,關(guān)鍵字個(gè)數(shù)大于m則分裂3)刪除 也僅在葉子結(jié)點(diǎn)上進(jìn)行,關(guān)鍵字個(gè)數(shù)小于m/2時(shí),需進(jìn)行合并BUPT SCSTBUPT8.8 哈希表哈希表的基本思想 在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系;這樣,理想狀態(tài)不經(jīng)過比較,一次存取就能得到所查元素。術(shù)語 哈希表 一個(gè)有限的連續(xù)的地址空間,用以容納按哈希地址存儲(chǔ)的記錄。 哈希函數(shù) 記錄的
29、存儲(chǔ)位置與它的關(guān)鍵字之間存在的一種對應(yīng)關(guān)系。 Loc(ri)=H(keyi) 沖突 對于keyikeyj, i j,出現(xiàn)的H(keyi) = H(keyj)的現(xiàn)象。BUPT SCSTBUPT 同義詞 在同一地址出現(xiàn)沖突的各關(guān)鍵字。 哈希(散列)地址 根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲(chǔ)位置。 裝填因子 表中填入的記錄數(shù)n和哈希表表長 m之比。 =n/m設(shè)計(jì)哈希表的過程 1)明確哈希表的地址空間范圍。即確定哈希函數(shù)的值域。 2)選擇合理的哈希函數(shù)。該函數(shù)要保證所有可能的記錄的哈希地址均在指定的值域內(nèi),并使沖突的可能性盡量小。 3)設(shè)定處理沖突的方法。BUPT SCSTB
30、UPT哈希表bb+(m-1)L哈希函數(shù)的基本構(gòu)造方法構(gòu)造原則: 算法簡單,運(yùn)算量小; 均勻分布,減少?zèng)_突。1. 直接定址法H(key)=a *key + b a、b為常數(shù)e.g: 令:a、b為1,有兩個(gè)關(guān)鍵字k1, k2 值為 10 、1000;選10 、1000 作為存放地址。特點(diǎn):計(jì)算簡單,沖突最少。2. 數(shù)字分析法/基數(shù)轉(zhuǎn)換法取關(guān)鍵字在某種進(jìn)制下的若干數(shù)位作為哈希地址。e.g: key = 236076 基數(shù)為10,看成是 13 進(jìn)制的。則:(236075)13 = 8 4154 7;選取 4154 作為散列地址(假設(shè) 表長m =10000)。BUPT SCSTBUPT3. 平方取中法取
31、關(guān)鍵字平方后的中間幾位作為哈希地址。e.g: (4731)2 = 223 82 361 ;選取 82 (假設(shè) m = 100)。4. 隨機(jī)數(shù)法 H(key) = random(key)特點(diǎn):較適于關(guān)鍵字長度不等時(shí)的情況。5. 折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同),然后取這幾部分的疊加和(舍去進(jìn)位)作為哈希地址。e.g: key = 381,412,975選取 768 或 570 作為散列地址( 假設(shè) m =1000 )。BUPT SCSTBUPT 381 412 9751 768 975 214 381 1 5706. 除留余數(shù)法H(key) = key MOD
32、p (pm)m: 哈希表的表長; p: 最好為素?cái)?shù)最常用,余數(shù)總在 0 p-1 之間。通常p選 m 的最大質(zhì)數(shù)如:m = 1024, 則 p = 1019。e.g: 選取 p 為質(zhì)數(shù)的理由:設(shè) key 值都為奇數(shù),選 p 為偶數(shù);則 H(key) = key MOD p ,結(jié)果為奇數(shù),一半單元被浪費(fèi)掉。 設(shè) key 值都為 5 的倍數(shù),選 p 為 95;則 H(key) = key MOD p ,結(jié)果為:0、5、10、15、 90奇數(shù)。4/5 的單元被浪費(fèi)掉。BUPT SCSTBUPT處理沖突的常用方法1. 開放定址法 (空缺編址法)Hi = ( H(key)+di ) MOD m 0 H(k
33、ey) m-1 i=1,2, ., k (km-1) m:哈希表的表長; di:增量序列1)線性探測再散列 di= 1,2, ., m-1缺陷:有聚集(堆積)現(xiàn)象非同義詞地址沖突。BUPT SCSTBUPTe.g: 假定采用的 hashing 函數(shù)為:H(key) = key MOD 11 假定的關(guān)鍵字序列為:17、60、29、38 ;它們的散列過程為:H(17) = 6H(60) = 5H(29) = 7 H(38) = 5BUPT SCSTBUPT012345678910Hashing 表1760293838當(dāng)散列 38 時(shí)發(fā)生沖突,同 60 爭奪第 5 個(gè)單元解決辦法 :探測下一個(gè) 空單元Hi = ( H(ke
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024物流金融、信用保險(xiǎn)服務(wù)合同
- 2025年度市政道路改造工程設(shè)計(jì)與施工總承包合同書3篇
- 2025年IDC機(jī)房租賃合同及網(wǎng)絡(luò)安全評估協(xié)議3篇
- 二零二五版金融租賃合同抵押擔(dān)保與租賃資產(chǎn)處置協(xié)議2篇
- 2025廠房升級改造與設(shè)備更新一體化合同3篇
- 2024跨區(qū)域綠色能源開發(fā)與合作框架合同
- 2025版韻達(dá)快遞業(yè)務(wù)承包及運(yùn)營合同3篇
- 幼兒園2025年度綠化維護(hù)服務(wù)合同2篇
- 二零二五年房車托管與戶外運(yùn)動(dòng)俱樂部合作合同3篇
- 個(gè)人二手手機(jī)買賣合同(2024版)2篇
- 【傳媒大學(xué)】2024年新營銷
- 乳腺癌的綜合治療及進(jìn)展
- 【大學(xué)課件】基于BGP協(xié)議的IP黑名單分發(fā)系統(tǒng)
- 2025屆廣東省佛山市高三上學(xué)期普通高中教學(xué)質(zhì)量檢測(一模)英語試卷(無答案)
- 自身免疫性腦炎課件
- 人力資源管理各崗位工作職責(zé)
- 信陽農(nóng)林學(xué)院《新媒體傳播學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 2024建筑公司年終工作總結(jié)(32篇)
- 信息安全意識(shí)培訓(xùn)課件
- 2024年項(xiàng)目投資計(jì)劃書(三篇)
- 配電安規(guī)課件
評論
0/150
提交評論