二叉排序樹課件

1、2022/7/20查找也叫檢索，是根據(jù)給定的某個(gè)值，在表中確定一個(gè)關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，它可以標(biāo)識一個(gè)數(shù)據(jù)元素查找方法評價(jià)查找速度占用存儲空間多少算法本身復(fù)雜程度平均查找長度ASL(Average Search Length)：為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的期望值基本概念:2022/7/20查找成功在查找表中找到關(guān)鍵字值等于給定值的記錄。查找失敗對查找表常進(jìn)行的操作：查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性在查找表中插入一個(gè)數(shù)據(jù)元素從查找表中刪除某個(gè)元素靜態(tài)查找表：對查找表只前兩種“查找

2、”操作動態(tài)查找表：對查找表要進(jìn)行后兩種“查找”操作2022/7/20一 順序查找（線性查找）查找過程：從表的一端開始逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較算法描述i例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464監(jiān)視哨iiii比較次數(shù)=5比較次數(shù)：查找第n個(gè)元素： 1查找第n-1個(gè)元素：2.查找第1個(gè)元素： n查找第i個(gè)元素： n+1-i查找失?。?n+18.1 靜態(tài)查找表2022/7/20typedef int KeyType;typedef float ElemType;typedef struct KeyType

3、 key; /記錄的關(guān)鍵字 ElemType info; /記錄的其他信息JD;int seqsrch(JD r, int n, KeyType k) /設(shè)置監(jiān)視哨的算法 int i=n; r0.key=k; while(ri.key!=k) i-; return(i);2022/7/20int seqsrch(JD r,int n,KeyType k) /未設(shè)置監(jiān)視哨 int i=0; while (i=n) return(-1); else return(i);2022/7/20順序查找方法的ASL2022/7/20二 折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：順序存儲結(jié)構(gòu)

4、查找表按關(guān)鍵字排序算法實(shí)現(xiàn)設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)，k為給定值初始時(shí)，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較若k=rmid.key，查找成功若krmid.key，則low=mid+1重復(fù)上述操作，直至lowhigh時(shí)，查找失敗2022/7/20算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92

5、lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022/7/20例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10

6、 115 13 19 21 37 56 64 75 80 88 92lowhighmid2022/7/201 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定樹：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 926指在查找表中的位置r6，查找范圍為r1r1110指在查找表中的位置r10，查找范圍為r10r11注：判定樹的形態(tài)只與表記錄個(gè)數(shù)n有關(guān)，與記錄的內(nèi)容無關(guān)。2022/7/20int BinSearch(JD r,int n,KeyT

7、ype k) int low,high,mid,found; low=1; high=n; found=0; while (lowrmid.key) low=mid+1; else if(khith) return -1; else mid=(low+high)/2; if (k=rmid.key) return mid; else if (krmid.key) return (BinSearch(r,mid+1,high,k); else return (BinSearch(r,low,mid-1,k); 2022/7/208.2 動態(tài)查找表 動態(tài)查找表的特點(diǎn)：表結(jié)構(gòu)本身是在查找過程中動態(tài)生

8、成的，即對于給定值key，若表中存在其關(guān)鍵字等于key的紀(jì)錄，則返回查找成功，否則插入關(guān)鍵字等于key的紀(jì)錄。 本節(jié)主要介紹二叉排序樹和平衡二叉樹的有關(guān)概念和查找分析2022/7/20定義：二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值它的左、右子樹也分別為二叉排序樹二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，繼續(xù)在其左、右子樹上查找，直至某個(gè)葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子二叉排序樹生成：從

9、空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹二叉排序樹2022/7/20插入算法例 10， 18， 3， 8， 12， 2， 7， 31010181018310183810183812101838122101838122710183812273中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列2022/7/20二叉排序樹的刪除要刪除二叉排序樹中的p結(jié)點(diǎn)，分三種情況：p為葉子結(jié)點(diǎn)，只需修改p雙親f的指針f-lchild=NULL f-rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p (1)(2)p只有右子樹，用p的右孩子代替p (3)(4)p左、右子樹均非空

10、沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p (5)若C無右子樹，用C取代p (6)2022/7/20SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)2022/7/20中序遍歷：P PR S QSPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRP2022/7/20FPCPRCLQQLSSL中序遍歷：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍歷：CL C

11、 QL Q SL S PR F(5)FPCPRCL中序遍歷：CL C P PR FFCPRCL中序遍歷：CL C PR F(6)2022/7/20刪除算法例805012060110150557053刪除508060120110150557053刪除60805512011015053701042581354刪除1084255134刪除58425413二叉排序樹的查找分析在二叉樹上查找一個(gè)關(guān)鍵字的過程，恰是走了一條從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑，因此與給定值比較的次數(shù)不超過樹的深度。對相同數(shù)的集合構(gòu)成的二叉排序樹因?yàn)楦?jié)點(diǎn)不同而造成平均查找長度不同。452453371293ASL=(1+2*2+3*3)/

12、6=14/6122437455393ASL=(1+2+3+4+5+6)/6=21/62022/7/20含有n個(gè)節(jié)點(diǎn)的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。若插入的關(guān)鍵字有序時(shí)，構(gòu)成的二叉排序樹蛻變成單支樹，其平均查找長度為(n+1)/2。最好的情況為二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2n成正比。 要想使任何的關(guān)鍵字的集合構(gòu)成的二叉排序樹的平均查找長度均達(dá)到log2n數(shù)量級，需對二叉排序樹進(jìn)行“平衡化”處理，成為平衡二叉樹。2022/7/20 平衡二叉樹或者是一棵空樹，或者具有以下性質(zhì)：左子樹和右子樹的深度之差的絕對值不超過1；它的左子樹和右子樹又分別是平衡二叉樹。

13、二叉樹節(jié)點(diǎn)的平衡因子BF：該節(jié)點(diǎn)的左子樹深度減去右子樹的深度。 BFBalance Factor所以平衡二叉樹的平衡因子只可能為-1，0，1。否則不能成為平衡二叉樹。平衡二叉樹AVL樹2022/7/20下面舉例說明構(gòu)成平衡二叉樹的過程:有關(guān)鍵字序列（13，24，37，90，53），生成平衡二叉樹： 空（a）013024-113037-124-2130370240132022/7/20-137-124013090(1)(2)-237-224013190053-237-224013-153090(3)053-124013090037(4)2022/7/20若插入結(jié)點(diǎn)使平衡二叉樹失去平衡的最小子樹根

14、結(jié)點(diǎn)指針為a, 則:由于在*a的左子樹根節(jié)點(diǎn)的左子樹上插入接點(diǎn)，*a的平衡因子 由1增到2，致使以*a為根的子樹失去平衡，則需要進(jìn)行一次向右 的順時(shí)針旋轉(zhuǎn)操作。(LL型)由于在*a的右子樹根節(jié)點(diǎn)的右子樹上插入接點(diǎn)，*a的平衡因子 由-1變?yōu)?2，致使以*a為根的子樹失去平衡，需要進(jìn)行一次向左 的逆時(shí)針旋轉(zhuǎn)操作。(RR型)由于在*a的左子樹根節(jié)點(diǎn)的右子樹上插入接點(diǎn)，*a的平衡因子 由1變?yōu)?，致使以*a為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操 作（先左后右）。(LR型)由于在*a的右子樹根節(jié)點(diǎn)的左子樹上插入接點(diǎn)，*a的平衡因子 由-1變?yōu)?2，致使以*a為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn) 操作（

15、先右后左）。(RL型)調(diào)整的原則：一是滿足平衡二叉樹的要求； 二是保持排序二叉樹的性質(zhì)2022/7/20 (1) LL型調(diào)整LL型調(diào)整規(guī)則將A的左子女B提升為新二叉樹的根；原來的根A連同其右子樹向右下旋轉(zhuǎn)成為B的右子樹；B的原右子樹作為A的左子樹。 2022/7/20 (2) RR型調(diào)整RR型調(diào)整規(guī)則：將A的右子女B提升為新二叉樹的根；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為B的左子樹；B的原左子樹作為A的右子樹。 2022/7/20 (3) LR型調(diào)整LR型調(diào)整規(guī)則：設(shè)C為A的左子女的右子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹的根；原C的父結(jié)點(diǎn)B連同其左子樹向左下旋轉(zhuǎn)成為新根C的左子樹，原C的左子樹

16、成為B的右子樹；原根A連同其右子樹向右下旋轉(zhuǎn)成為新根C的右子樹，原C的右子樹成為A的左子樹。 2022/7/20 (4) RL型調(diào)整 RL型調(diào)整規(guī)則：設(shè)C為A的右子女的左子女，將A的孫子結(jié)點(diǎn)C提升為新二叉樹的根，原來C的父結(jié)點(diǎn)B連同其右子樹向右下旋轉(zhuǎn)成為新根C的右子樹，C的原右子樹成為B的左子樹；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為新根C的左子樹，原來C的左子樹成為A的右子樹。 2022/7/20如：輸入關(guān)鍵字序列16,3,7,11,9,26,18,14,15,給出構(gòu)造一棵AVL樹的步驟。2022/7/202022/7/201、B_樹定義： 一棵m階的B_樹，或?yàn)榭諛?，或?yàn)闈M足下列特征的m叉樹

17、：樹中每個(gè)節(jié)點(diǎn)至多有m棵子樹；（m=3)若根不是葉子(非單根樹)，則最少有兩棵子樹，最多有m棵子樹；除根之外的所有非終端節(jié)點(diǎn)最少有m/2棵子樹，最多m棵子樹；所有的非終端節(jié)點(diǎn)包含下列信息數(shù)據(jù) (n,A0,K1,A1,K2,A2,Kn,An)Ki為關(guān)鍵字，且Ki352、B_樹的查找2022/7/20查找47的過程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF4347782022/7/20查找47的過程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.ta

18、bcefghFFFFFFFFFFFF查找成功2022/7/20查找23的過程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23182022/7/20查找23的過程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF23272022/7/20查找23的過程d1.35.1.18.1.27.1.11.1.99.1.39.2.43.78.3.47.53.64.tabcefghFFFFFFFFFFFF查找失敗2022/7/2

19、03、B_樹的插入100h45a53 90e24b3 12c37d50f61 70gbt2022/7/20插入303 12c45a53 90e24b30 37d50f61 70g100hbt2022/7/20插入2645a53 90e24b3 12c26 30 37d50f61 70g100hbt2022/7/20插入2645a53 90e24 30b3 12c37d50f61 70g100hbt26d2022/7/20插入8545a53 90e24 30b3 12c37d50f61 70 85g100hbt26d2022/7/20bt插入8545a53 70 90e24 30b3 12c37

20、d50f61 g100h26d85 g2022/7/20100hbt插入8545 70a53e24 30b3 12c37d50f61 g26d85 g90e2022/7/20bt插入745 70a53e7 24 30b3c37d50f61 g100h26d85 g12c90e2022/7/20插入7bt24 45 70a53e7b3c37d50f61 g100h26d85 g12c30b90e2022/7/20bt插入745m53e7b3c37d50f61 g100h26d85 g12c30b90e70a24a2022/7/20B+樹B樹是B_樹的一種變形，一棵m階B樹和B樹的區(qū)別：有n棵子樹

21、的節(jié)點(diǎn)中含有n個(gè)關(guān)鍵字。所有的葉子節(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向這些關(guān) 鍵字的指針，且葉子節(jié)點(diǎn)本身以關(guān)鍵字的大小自小到大順序 連接。所有的非終端節(jié)點(diǎn)可以看成是索引部分，節(jié)點(diǎn)中僅包含有其 子樹中的最大(或最小)關(guān)鍵字。2022/7/20如：一棵3階B+樹59 9772 9715 44 5910 1521 37 4451 5963 7285 91 97bt葉子節(jié)點(diǎn)有序子樹根的最大值子樹根的最大值2022/7/208.4 哈希查找Hash查找基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法定義哈希函數(shù)記錄的關(guān)鍵字與記錄的存儲

22、地址之間建立的一種對應(yīng)關(guān)系哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象哈希函數(shù)可寫成：addr(ai)=H(ki)ai是表中的一個(gè)元素addr(ai)是ai的存儲地址ki是ai的關(guān)鍵字關(guān)鍵字集合存儲地址集合hash2022/7/20哈希表應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址。該表叫哈希查找又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程叫例1 30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表編號 地區(qū)別 總?cè)丝?漢族 回族.1 北京2 上海.以編號作關(guān)鍵字，構(gòu)造哈希函數(shù)：H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的序號作哈希函數(shù)：H

23、(Beijing)=2 H(Shanghai)=19 H(Shenyang)=192022/7/20例2: 對于一組關(guān)鍵字序列 (25，74，36，15，40，29，82，19，65，33，57，47，50), 選取函數(shù) h(key)key%13 建立記錄與其在查找表中存儲位置之間的關(guān)系，可得到如下表所示的一張查找表：當(dāng)對該表檢索時(shí)，只需用給定關(guān)鍵字值k通過這個(gè)函數(shù)計(jì)算出地址，以該地址從檢索表的對應(yīng)位置取出記錄的有關(guān)信息即可，不需要進(jìn)行關(guān)鍵字值的比較操作。如檢索key=57的記錄，通過h(57)=57%13=5知關(guān)鍵字值為57的記錄在檢索表的存儲位置5處，從而得到關(guān)鍵字值為57的記錄的有關(guān)信息

24、。 2022/7/20從例子可見：哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法產(chǎn)生散列沖突相關(guān)的主要因素： 裝填因子：散列表中已存入元素n與散列表空間大小m的比。 裝填因子越小，產(chǎn)生的沖突就越?。环駝t，就越大。 散列函數(shù) 散列函數(shù)選擇適當(dāng)，使散列地址盡可能均勻地分布在散列空間中，產(chǎn)生的沖突就少；否則，就大。 沖突的解決方法20

25、22/7/20哈希函數(shù)的構(gòu)造方法直接定址法方法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址。 H(key)=key 或 H(key)=akey+b特點(diǎn)：直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突。若有沖突，說明關(guān)鍵字錯誤。實(shí)際中能用這種哈希函數(shù)的情況很少適用于關(guān)鍵字分布基本連續(xù)的情況。若不連續(xù)，空號較多，將造成存儲空間的嚴(yán)重浪費(fèi)。2022/7/20數(shù)字分析法方法：對關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址適用于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且關(guān)鍵字事先知道的情況例： 有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2

26、2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 位只取8 位只取1 位只取3、4 位只取2、7、5 位數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位 與另兩位的疊加作哈希地址2022/7/20平方取中法方法：取關(guān)鍵字平方后中間幾位作哈希地址適用于不知道全部關(guān)鍵字情況折疊法方法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加適于關(guān)鍵字

27、位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例 關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加2022/7/20除留余數(shù)法方法：取關(guān)鍵字被某個(gè)不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key MOD p，pm特點(diǎn)簡單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞隨機(jī)數(shù)法方法：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址。 H(key)=random(key)適用于關(guān)鍵字長度不等的情況選取哈希函數(shù)，考

28、慮以下因素：計(jì)算哈希函數(shù)所需時(shí)間關(guān)鍵字長度哈希表長度（哈希地址范圍）關(guān)鍵字分布情況記錄的查找頻率2022/7/20處理沖突的方法開放定址法方法：當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中。 Hi = (H(key)+di) MOD m，i=1,2,k(km-1) 其中：H(key)哈希函數(shù) m哈希表表長 di增量序列分類線性探測再散列：di=1,2,3,m-1 H1 =H(key) Hj =(Hj-1+1) MOD m j=2,3,二次探測再散列：di=1,-1,2,-2,3,k(km/2) H1=H(key) H2j=

29、(H1+j2) MOD m H2j+1=(H1-j2) MOD m j=1,2,3,偽隨機(jī)探測再散：di=偽隨機(jī)數(shù)序列 H1=H(key) Hj= (H1+R) MOD m2022/7/20例 表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄， H(key)=key MOD 11,現(xiàn)有第4個(gè)記錄，其關(guān)鍵字為38， 按三種處理沖突的方法，將它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38

30、(2) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5-1) MOD 11=4 不沖突38(3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為9，則： H1=(5+9) MOD 11=3 不沖突382022/7/20再哈希法方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址。 Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函數(shù)特點(diǎn)：計(jì)算時(shí)間增加鏈地址法方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針2022/7/20例： 已知一組關(guān)鍵字 (19，14，23，1，68，20，84，27

31、，55，11，10，79) 哈希函數(shù)為： H(key)=key MOD 13 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 141277968551984202310112022/7/20哈希查找過程及分析哈希查找過程給定k值計(jì)算H(k)此地址為空關(guān)鍵字=k查找失敗查找成功按處理沖突方法計(jì)算HiYNYN2022/7/20哈希查找分析哈希查找過程仍是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過程評價(jià)哈希查找效率仍要用ASL哈希查找過程與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于：哈希函數(shù)處理沖突的方法哈希表的裝填因子=表中填入的記錄數(shù)/哈希表長度例 已知一組關(guān)鍵字(19,14,23,1,

32、68,20,84,27,55,11,10,79) 哈希函數(shù)為：H(key)=key MOD 13, 哈希表長為m=16， 設(shè)每個(gè)記錄的查找概率相等(1) 用線性探測再散列處理沖突，即Hi=(H(key)+di) MOD mH(55)=3 沖突，H1=(3+1)MOD16=4 沖突，H2=(3+2)MOD16=5H(79)=1 沖突，H1=(1+1)MOD16=2 沖突，H2=(1+2)MOD16=3 沖突，H3=(1+3)MOD16=4 沖突，H4=(1+4)MOD16=5 沖突，H5=(1+5)MOD16=6 沖突，H6=(1+6)MOD16=7 沖突，H7=(1+7)MOD16=8 沖突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2*1+3*3+4*1+1*9)/12 =2.514 168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1 沖突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 沖突，H1=(6+1)MOD16