算法與數(shù)據(jù)結構查找課件

1、內查找 整個查找過程都在內存中進行。外查找 在查找過程中需要訪問外存。平均查找長度ASL查找方法時效的度量 為確定記錄在查找表中的位置，需將關鍵字和給定值比較次數(shù)的期望值。 查找成功時的ASL計算方法： n：記錄的個數(shù) pi：查找第i個記錄的概率， ( 不特別聲明時認為等概率 pi =1/n ) ci：找到第i個記錄所需的比較次數(shù)約定：無特殊說明，一般默認關鍵字的類型為整型BUPTBUPT SCST8.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 )

2、int i = 0; an = K; while (ai != K) i+; return i;BUPTBUPT SCST程序設計技巧 設置監(jiān)視哨，提高算法效率。性能分析空間：一個輔助空間。時間： 1) 查找成功時的平均查找長度 設表中各記錄查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/2 2)查找不成功時的平均查找長度 ASLf =n+1算法特點算法簡單，對表結構無任何要求n很大=查找效率較低改進措施：非等概率查找時，可將查找概率高的記錄盡量排在表前部。BUPTBUPT SCST8.3 二分查找滿足 ri.key ri+1.key, 0 i n-1 仍可用順序查找，

3、但在找不到時不需比較到表尾，只需比較到比給定值大的記錄就可終止。折半(二分)查找法 1 2 3 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 9BUPTBUPT SCST算法描述int binsearch ( int K, int v , int n ) int low, high, mid; low = 1; high = n; while ( low

4、 = high ) mid = ( low + high ) / 2; if ( K vmid ) low = mid + 1; else /* 找到了匹配的值*/ return mid; return -1; /* 沒有查到*/BUPTBUPT SCST性能分析 h=log2n+1 同完全二叉樹，二叉樹性質4成功查找時的平均查找長度（等概率）： ASLs= 例：ASLS=(1*1+2*2+3*4+4*4)/11=3不成功查找時的查找長度：h-1或h次 -13-46-79-101-22-34-55-67-88-910-1111-639147 102581112h判定樹（描述查找過程的二叉樹）外

5、結點內結點lc,flag)；/ 中序遍歷左子樹 if(pre=NULL) pre=t；/ 中序的第一個結點不判斷 else if(pre-datadata) pre=t；/前驅指針指向當前結點 else flag=FLASE； /不是完全二叉樹 JudgeBST(t-rc,flag)；/ 中序遍歷右子樹 BUPTBUPT SCST方法2：照定義，二叉排序樹的左右子樹都是二叉排序樹，根結點的值大于左子樹中所有值而小于右子樹中所有值，即根結點大于左子樹的最大值而小于右子樹的最小值。 bool JudgeBST(BTree t) if(t=NULL) return TRUE； if (JudgeBS

6、T(t-lc) & JudgeBST(t-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； BUPTBUPT SCST在二叉排序樹上的操作1.查找例 K=28 K=32bst45241228bst455390241228325390 查找

7、步驟：若根結點的關鍵字值等于查找的關鍵字，成功。 否則，若小于根結點的關鍵字值，查其左子樹。 若大于根結點的關鍵字值，查其右子樹。 在左右子樹上的操作類似。BUPTBUPT SCSTBitree SearchBST ( BiTree T, KeyType key ) / 在二叉分類樹查找關鍵字之值為 key 的結點，找到返回該結 / 點的地址，否則返回空。T 為根結點的指針。 if ( ( T=NULL) | ( key=T -data) ) return ( T ) ; else if (key data. key ) return (SearchBST (T -lc, key ); els

8、e return (SearchBST ( T - rc, key ); 查找算法BUPTBUPT SCST2.插入首先執(zhí)行查找算法，找出被插結點的父親結點。 判斷被插結點是其父親結點的左、右兒子。將被 插結點作為葉子結點插入。 若二叉樹為空。則首先單獨生成根結點。注意：新插入的結點總是葉子結點。3.生成算法步驟 反復執(zhí)行以下操作 a. 讀入一個記錄，設其關鍵字為K； b. 調用查找算法，確定插入位置； c. 調用插入算法，實施插入結點的操作；BUPTBUPT SCST例：將序列122、99、250、110、300、280 作為二叉排序樹的結點的關鍵字值，生成二叉排序樹。12212299122

9、250991222501109912225030011099BUPTBUPT SCST4.刪除依據(jù)被刪除結點p的不同情況分析：1. p是葉子結點：修改其雙親指針即可2. p只有左孩子：用p的左子樹代替以p為根的子樹 p只有右孩子：用p的右子樹代替以p為根的子樹3. p有兩個孩子：找到p的中序后繼(或前趨)結點q， q的數(shù)據(jù)復制給p， 刪除只有右子(或左子)/無孩子的qBUPTBUPT SCST例：(1)(2)(2)(3)5320901050869541241528891304539878992BUPTBUPT SCSTvoid Delete(BSTree T, keytype X) /在二叉排

10、序樹T上，刪除為X的結點。 BSTree f, p=T; while (p & p-key!=X) /查找值為X的結點 if (p-keyX) f=p; p=p-lc;/f為p的雙親 else f=p; p=p-rc; if (p=NULL) printf(“無關鍵字為X的結點n”); exit(0); if (p-lc=NULL) /被刪結點無左子樹 if (f-lc=p) f-lc=p-rc;/將被刪結點的右子樹接到其雙親上 else f-rc=p-rc; else /被刪結點有左子樹 q=p; s=p-lc; while (s-rc !=NULL) /查左子樹中最右下的結點（中序最后結點

11、） q=s; s=s-rc; p-key=s-key; /結點值用其左子樹最右下的結點的值代替 if (q=p) p-lc=s-lc;/被刪結點左子樹的根結點無右子女 else q-rc=s-lc; /s是被刪結點左子樹中序序列最后一個結點 free(s); BUPTBUPT SCST4. 性能分析給定樹的形態(tài)，等概率查找成功時的ASL=ci /n最差(單支樹)：(n+1)/2最好(類似折半查找的判定樹)：log2(n+1)-1隨機：1+4log2n關鍵字有序出現(xiàn)時，構造出“退化”的二叉排序樹，樹深為n，各種操作代價O(n)。避免方法：采用平衡二叉樹BUPTBUPT SCST8.7 平衡二叉樹

12、(AVL樹)1. 定義平衡二叉樹或者是空樹，或者是滿足如下性質的二叉排序樹： 1)它的左、右子樹的高度之差的絕對值不超過1； 2)其左右子樹本身又各是一棵平衡二叉樹。二叉樹上結點的平衡因子： 該結點的左子樹高度減去右子樹的高度。平衡二叉樹非平衡二叉樹302010252235383020353233001-10-1100-12-2平衡二叉樹：每個結點的平衡因子都為 1、1、0 的二叉排序樹。BUPTBUPT SCST2.結點的存儲結構 lc bf key otherinfo rc lc：左孩子指針 rc：右孩子指針 bf：平衡因子 key：記錄的關鍵字 otherinfo：記錄的其它數(shù)據(jù)成分BU

13、PTBUPT SCST4. 在平衡二叉樹上的操作查找查找方法同二叉排序樹。插入 插入新結點之后仍應保持平衡二叉樹的性質不變。例 平衡二叉樹的生成過程15001525-1-2-1000000-1-1001-2-20000-11525353525152515359015253590651525653590BUPTBUPT SCST調整范圍的確定 插入結點后，找到離插入結點最近且平衡因子絕對值超過1的祖先結點（危機節(jié)點），則以該危機節(jié)點為根的子樹將是可能不平衡的最小子樹，可將重新平衡的范圍局限于這棵子樹。調整的類型 LL型-表示新插入結點在危機結點的左子的左子樹上LR型-表示新插入結點在危機結點的左

14、子的右子樹上RL型-表示新插入結點在危機結點的右子的左子樹上RR型-表示新插入結點在危機結點的右子的右子樹上BUPTBUPT SCST調整的方法LL型平衡旋轉一次順時針旋轉AB+1h-10+2+1hh-1h-1LL 型調整BLBRARBA0h0h-1h-1BLBRAR危機結點調整前：高度為 h + 1 中序序列：ABBLBRAR調整后：高度為 h + 1 中序序列：ABBLBR注意：調整后 平衡因子為 0ABARBUPTBUPT SCSTLR型平衡旋轉一次逆時針旋轉+一次順時針旋轉AB+1h-10+2-1h-1LR 型調整BLAR危機結點CBCCLCRh-2h-2h-10+1CB0h-1BLA

15、RACRh-2CLh-1-10ABBLARCCLCR調整后： 高度為 h + 1 中序序列：ABBLARCCLCRA調整前： 高度為 h + 1 中序序列：h-1情形A注意：調整后 平衡因子為 +1,0,0BUPTBUPT SCSTLR型平衡旋轉一次逆時針旋轉+一次順時針旋轉AB+1h-10+2-1h-1LR 型調整BLAR危機結點調整前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 +1,0,0CBCCRCLh-1h-2h-20-1CB0h-1BLARACRh-1CLh-2+10ABBLARCCRCL調整后： 高度為 h + 1 中序序列：AABBLARCCRCL情形BBUPTBU

16、PT SCST注意：調整后 平衡因子為 0,0,0LR型平衡旋轉一次逆時針旋轉+一次順時針旋轉AB+10+2-1LR 型調整危機結點調整前： 高度為 2 中序序列：CBC0ABCA新插入結點ABC調整后： 高度為 2 中序序列：ca0b00情形CBUPTBUPT SCSTRR型平衡旋轉一次逆時針旋轉AB-1h-10-2-1hh-1h-1RR 型調整BLBRALBA0h0h-1h-1BLAL危機結點調整前：高度為 h + 1 中序序列：BAALBLBR調整后：高度為 h + 1 中序序列：注意：調整后 平衡因子為 0ABBRBAALBLBRBUPTBUPT SCSTRL型平衡旋轉一次順時針旋轉+

17、一次逆時針旋轉AALCRCLBRALCRCLBRALCLBRCRBCABCACB-100h-1h-2h-1 h-211(-1)00(1)-1(0)危機結點BUPTBUPT SCST刪除 （思路同插入）將刪除結點q轉化為q最多有一個孩子的情形，即若q有兩個孩子，則以其中序前驅/后繼結點r取代它，刪除r；若樹的平衡性被破壞，利用單一/雙重旋轉恢復。性能定理：一個具有n個結點的平衡二叉樹形，其高度h為 log2(n+1) h 1.4404log2(n+2)-0.328 結論：最壞情況下，AVL樹的高度約為1.44log2n，而完全平衡的二叉樹高度約為log2n，因此AVL樹是接近最優(yōu)的，其平均查找長

18、度與log2n同數(shù)量級。BUPTBUPT SCST8.7 B+樹與B-樹采用B+與B-樹的意義大量數(shù)據(jù)存放在外存中，由于是海量數(shù)據(jù)，不可能一次調入內存。因此，要多次訪問外存，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。內存BUPTBUPT SCST用用二叉樹組織文件，需訪問外存次數(shù)太多。如：當文件的記錄個數(shù)為 100，000時，要找到給定關鍵字的記錄，需訪問外存17次（log100,000）,太長了！502510751535609020304055708095索引文件數(shù)據(jù)文件文件頭，可常駐內存文件訪問示意圖：索引文件存在內存、數(shù)據(jù)文件存在盤上BUPTBUPT SCSTB-樹B-樹是一種平衡的多路查

19、找樹。應用于文件系統(tǒng)。1. 定義 一棵 m 階B -樹，或為空樹，或為滿足下列特性的 m 叉樹： 1、樹中每個結點最多有 m 棵子樹； 2、若根結點不是葉子結點，則最少有兩棵子樹； 3、除根之外的所有非終端結點最少有 m / 2 棵子樹； 4、所有非終端結點包含 （n,A0,K1,A1,K2,Kn,An）信息數(shù)據(jù)；其中n為結點中關鍵字個數(shù)，Ai為指向子樹的指針，Ki為關鍵字。 5、所有葉子結點在同一層上，且不帶信息。BUPTBUPT SCST例如：m = 4 階 B_ 樹。除根結點和葉子結點之外，每個結點的兒子個數(shù)至少為 m/2 = 2 個；結點的關鍵字個數(shù)至少為 1 。該 B_ 樹的深度為

20、4。葉子結點都在第 4 層上。1，993，47，58，641，391，271，112，43，781，181，35FFFFFFFFFFFF第 1 層第 2 層第 3 層(L層)第 4 層(L1層)m/2 m棵子樹葉BUPTBUPT SCST2. B-樹結點結構(n, A0, K1, A1, K2, A2,., Kn, An)n: 關鍵字的個數(shù)A0： K1 且 Kn 的結點的地址（指在該 B_ 樹中）K1 =K2 = . = KnBUPTBUPT SCST127階B-樹中每個結點最多有_個關鍵字；除根結點外所有非終端結點至少有_棵子樹；65階B+樹中除根結點外所有結點至少有_個關鍵字；最多有_棵子

21、樹。高度為5（除葉子層之外）的三階B-樹至少有_個結點。31126643365思考：高度為h的m階B-樹（除葉子層）至少有多少個結點？ BUPTBUPT SCST3.B-樹查找過程類似于二叉樹的查找。如查找關鍵字為 KEY 的記錄。 從根開始查找，如果 Ki = KEY 則查找成功。 若 Ki KEY Ki+1; 查找 Ai 指向的結點若 KEY Kn; 查找 An指向的結點若 找到葉子，則查找失敗。BUPTBUPT SCST設關鍵字的總數(shù)為 N ，求 m階 B_ 樹的最大層次 L。層次 結點數(shù)關鍵字的個數(shù)（最少） 1 1 1 2 2 2(m/2 -1) 3 2(m/2) 2 (m/2) (m

22、/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(m/2)L-1 所以，N= 2 (m/2)L-1 -1故：Llog m/2(N+1)/2)+ 1設 N 1000，000 且 m256 ，則 L m-1, 則該結點滿。必須分裂成兩個結點。否則不滿結束。如結點原為： (m-1, A0, K1, A1, K2, A2, Km-1, Am-1)插入一個關鍵字之后變?yōu)椋?m, A0, K1, A1, K2, A2, Km, Am)該結點以K m/2為界，進行分裂： .(K m/2 , p ) .(m/2-

23、1,A0, (K1,A1)(K m/2-1, A m/2-1) (m- m/2,A m/2, K m/2+1 Km, Am)生成新結點 p, 將原結點的后半部分復制過去。若分裂一直進行到根結點，樹可能長高一層。(K m/2 , p ) 數(shù)據(jù)項插入上層結點之中PPBUPTBUPT SCST例：3 階 B_ 樹的插入key=73，127 24 3024，3045，7053902610039506185345，70539026100395061851230324 45 7053902610039506185127 3032453902610039506185127 45 707插入BUPTBUPT

24、SCST5.B-樹刪除過程1、查找具有給定鍵值的關鍵字 Ki 2、如果 在第 L 層，可直接刪除（注意：第 L+1 層為葉子結點），轉 4 。3、否則，則首先生成 “替身”。用該關鍵字的右邊子樹中的最左面的結點的關鍵字取代。然后，刪除第 L 層上的該關鍵字。4、從第 L 層開始進行刪除。 A、不動：若刪除關鍵字值的那個結點的關鍵字的個數(shù)仍處于m/2 -1和 m-1之間。則結束。 B、借：若刪除關鍵字值的那個結點的關鍵字的個數(shù)原為 m/2 -1 。而它們左右兄弟結點的關鍵字個數(shù) m/2 -1; 則借一關鍵字過來，結束。 C、并：若該結點的左右兄弟結點的關鍵字的個數(shù)為m/2 -1; 則執(zhí)行合并結點

25、的操作。如結點原為：（ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1 第 L 層：找到了被刪結點的替身。BUPTBUPT SCST例如：3 階 B_ 樹的刪除操作。3244553 90371005061，70被刪關鍵字3244561 90371005370借：向被刪結點方向旋轉假定再刪除該關鍵字32445 903710061，703，2445 9010061，703，24 45 9010061，70并并并并：和父結點的一個關鍵字、及兄弟合并。有可能進行到根，使B_ 樹的深度降低一層！假定再刪除該關鍵字B

26、UPTBUPT SCSTB+樹B+樹是一種B-樹的變形樹。應用于索引順序文件系統(tǒng)。1. m階B+ 樹與 B- 樹的不同之處1)有 n 棵子樹的結點中有 n 個關鍵字；2)非葉結點可以看成是索引部分 索引集Ai ：第i個子結點的指針Ki ：第i個子結點的最大（或最?。╆P鍵字3)所有葉子結點中包含了全部關鍵字的信息及指向這些關鍵字記錄的指針，且葉子結點以關鍵字大小自小至大順序鏈接；數(shù)據(jù)集BUPTBUPT SCST結點結構非葉結點 ( A1, K1, .,Ai, Ki, ., An,Kn) 索引集Ai ：第i個子結點的指針Ki ：第i個子結點的最大（或最?。╆P鍵字葉結點 全部關鍵字及指向關鍵字記錄的

27、指針 數(shù)據(jù)集2 15 334 40 47 58 672 79 853 90 96 1052 85 1323 33 67 852 105 1322 114 1324階B+樹rootsqtBUPTBUPT SCST2. B+樹上的基本運算1)查找方式1：從根結點開始，利用索引集結構，向下查找直到葉子結點方式2：從最小關鍵字開始，沿葉結點數(shù)據(jù)集的鏈結構順序查找2)插入 僅在葉子結點上進行，關鍵字個數(shù)大于m則分裂3)刪除 也僅在葉子結點上進行，關鍵字個數(shù)小于m/2時，需進行合并BUPTBUPT SCST8.8 哈希表哈希表的基本思想 在記錄的存儲地址和它的關鍵字之間建立一個確定的對應關系；這樣，理想狀

28、態(tài)不經(jīng)過比較，一次存取就能得到所查元素。術語 哈希表 一個有限的連續(xù)的地址空間，用以容納按哈希地址存儲的記錄。 哈希函數(shù) 記錄的存儲位置與它的關鍵字之間存在的一種對應關系。 Loc(ri)=H(keyi) 沖突 對于keyikeyj， i j，出現(xiàn)的H(keyi) = H(keyj)的現(xiàn)象。BUPTBUPT SCST 同義詞 在同一地址出現(xiàn)沖突的各關鍵字。 哈希(散列)地址 根據(jù)設定的哈希函數(shù)H(key)和處理沖突的方法確定的記錄的存儲位置。 裝填因子 表中填入的記錄數(shù)n和哈希表表長 m之比。 =n/m設計哈希表的過程 1)明確哈希表的地址空間范圍。即確定哈希函數(shù)的值域。 2)選擇合理的哈希函

29、數(shù)。該函數(shù)要保證所有可能的記錄的哈希地址均在指定的值域內，并使沖突的可能性盡量小。 3)設定處理沖突的方法。哈希表bb+(m-1)LBUPTBUPT SCST哈希函數(shù)的基本構造方法構造原則： 算法簡單，運算量??； 均勻分布，減少沖突。1. 直接定址法H(key)=a *key + b a、b為常數(shù)e.g: 令：a、b為1，有兩個關鍵字k1, k2 值為 10 、1000；選10 、1000 作為存放地址。特點：計算簡單，沖突最少。2. 數(shù)字分析法/基數(shù)轉換法取關鍵字在某種進制下的若干數(shù)位作為哈希地址。e.g: key = 236076 基數(shù)為10，看成是 13 進制的。則：(236075)13

30、 = 8 4154 7；選取 4154 作為散列地址(假設 表長m =10000)。BUPTBUPT SCST3. 平方取中法取關鍵字平方后的中間幾位作為哈希地址。e.g: (4731)2 = 223 82 361 ；選取 82 （假設 m = 100）。4. 隨機數(shù)法 H(key) = random(key)特點：較適于關鍵字長度不等時的情況。5. 折疊法 將關鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進位)作為哈希地址。e.g: key = 381，412，975選取 768 或 570 作為散列地址（ 假設 m =1000 ）。 381 412

31、9751 768 975 214 381 1 570BUPTBUPT SCST6. 除留余數(shù)法H(key) = key MOD p (pm)m: 哈希表的表長； p: 最好為素數(shù)最常用，余數(shù)總在 0 p-1 之間。通常p選 m 的最大質數(shù)如：m = 1024, 則 p = 1019。e.g: 選取 p 為質數(shù)的理由：設 key 值都為奇數(shù)，選 p 為偶數(shù)；則 H(key) = key MOD p ，結果為奇數(shù)，一半單元被浪費掉。 設 key 值都為 5 的倍數(shù)，選 p 為 95；則 H(key) = key MOD p ，結果為：0、5、10、15、 90奇數(shù)。4/5 的單元被浪費掉。BUPT

32、BUPT SCST處理沖突的常用方法1. 開放定址法 (空缺編址法)Hi = ( H(key)+di ) MOD m 0 H(key) m-1 i=1,2, ., k (km-1) m:哈希表的表長； di:增量序列1)線性探測再散列 di= 1,2, ., m-1缺陷：有聚集(堆積)現(xiàn)象非同義詞地址沖突。BUPTBUPT SCSTe.g: 假定采用的 hashing 函數(shù)為：H(key) = key MOD 11 假定的關鍵字序列為：17、60、29、38 ；它們的散列過程為：H(17) = 6H(60) = 5H(29) = 7 H(38) = 5012345678910Hashing 表1760293838當散列 38 時發(fā)生沖突，同 60 爭奪第 5 個單元解決辦法 ：探測下一個 空單元Hi = ( H(key)+di) MOD 11其中： di 為 1、210沖突： 初級沖突：不同關鍵字值的結點得到同一個散列地址。 二次聚集：同不同散列地址的結點爭奪同一個單元。結果：沖突加劇，最壞時可能達到 O(n)級代價。思考：假定有k個關鍵字互為同義詞