【正文】 作業(yè)： 。熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的區(qū)別。 學(xué)習(xí)要點(diǎn)熟練掌握順序表和有序表的查找方法，并能靈活應(yīng)用。從圖 814的平衡二叉樹可知，查找 6需 2次，平均查找長度ASL=(1+2+2+3+3+3+3)=17/7≈。得到的平衡二叉樹見圖 814，得到的二叉排序樹見圖 815。 對例 82給定的關(guān)鍵字序列 4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找 6的次數(shù)及成功的平均查找長度。平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。給定一個(gè)關(guān)鍵字序列 4,5,7,2 ,1,3,6，試生成一棵平衡二叉樹。（ 4） RL型的處理 (右左型 )在 A的右孩子 C上扦入一個(gè)左孩子 B，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。（ 3） RR型的處理 (右右型 )在 A的右孩子 B上扦入一個(gè)右孩子 C，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。 (注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子 )（ 2） LR型的處理 (左右型 )在 C的左孩子 A上扦入一個(gè)右孩子 B， 使的 C的平衡因子由 1變成了 2，成為不平衡的二叉排序樹。（ 1） LL型 的處理 (左左型 )在 C的左孩子 B上扦入一個(gè)左孩子結(jié)點(diǎn) A，使 C的平衡因子由 1變成了 2，成為不平衡的二叉樹序樹。非平衡二叉樹的平衡處理若一棵二叉排序樹是平衡二叉樹，扦入某個(gè)結(jié)點(diǎn)后，可能會(huì)變成非平衡二叉樹，這時(shí)，就可以對該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。將該結(jié)點(diǎn)的左子樹深度減去右子樹深度的值，稱為該結(jié)點(diǎn)的平衡因子 (balance factor)。 因此，二叉排序樹查找的最好時(shí)間復(fù)雜度為 O(log2n)， 最壞的時(shí)間復(fù)雜度為 O(n)， 一般情形下，其時(shí)間復(fù)雜度大致可看成 O(log2n)， 比順序查找效率要好，但比二分查找要差。 else //進(jìn)入右子樹查找 return find (BSTright,x)。 //查找失敗 else { if (BSTdata= =x) //查找成功 return BST。 p的選取很重要； p選的不好，容易產(chǎn)生同義詞? 隨機(jī)數(shù)法– 構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)– 適于關(guān)鍵字長度不等的情況? 選取哈希函數(shù)，考慮以下因素：– 計(jì)算哈希函數(shù)所需時(shí)間– 關(guān)鍵字長度– 哈希表長度（哈希地址范圍）– 關(guān)鍵字分布情況– 記錄的查找頻率– 處理沖突的方法? 開放定址法– 方法：當(dāng)沖突發(fā)生時(shí)，形成一個(gè)探查序列；沿此序列逐個(gè)地址探查，直到找到一個(gè)空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1)其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列– 線性探測再散列： di=1,2,3,……m1– 再哈希法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，即： Hi=Rhi(key) i=1,2,……k其中： Rhi—— 不同的哈希函數(shù)– 特點(diǎn)：計(jì)算時(shí)間增加例 表長為 11的哈希表中已填有關(guān)鍵字為 17， 60， 28的記錄， H(key)=key MOD 11,現(xiàn)有第 4個(gè)記錄，其關(guān)鍵字為 38， 按處理沖突的方法，將它填入表中0 1 2 3 4 5 6 7 8 8 1060 17 28 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? 鏈地址法 (外鏈法 )– 方法：將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針例 已知一組關(guān)鍵字 (18,14,23,1,68,20,84,27,55,11,10,78) 哈希函數(shù)為： H(key)=key MOD 13, 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 8 10 11 12 14^1 27 7868 5518 842023 1011^^^^^^^^^^^^例 已知一組關(guān)鍵字 (18,14,23,1,68,20,84,27,55,11,10,78) 哈希函數(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(78)=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=80 1 2 3 4 5 6 7 8 8 10 11 12 13 14 15ASL=(1*6+2+3*3+4+8)/12=14 1 68 27 55 18 20 84 78 23 11 10H(18)=6H(14)=1H(23)=10H(1)=1 沖突， H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 沖突， H1=(6+1)MOD16=7 沖突， H2=(6+2)MOD16=8H(27)=1 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 沖突， H3=(1+3)MOD16=4H(11)=11H(10)=10 沖突， H1=(10+1)MOD16=11 沖突， H2=(10+2)MOD16=12(2) 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 8 10 11 12 14^1 27 7868 5518 842023 1011^^^^^^^^^^^^ASL=(1*6+2*4+3+4)/12=關(guān)鍵字 (18,14,23,1,68,20,84,27,55,11,10,78) 二叉排序 樹上的查找 （ 1）二叉排序 樹的查找思想若二叉排樹為空，則查找 失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點(diǎn)時(shí)，還沒有找到待找結(jié)點(diǎn)，則查找不成功。 間界疊加：從一端沿分割界來回折送，然后對齊相加– 適于關(guān)鍵字位數(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 8 2H(key)=6082間界疊加? 除留余數(shù)法– 構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即 H(key)=key MOD p， p?m– 特點(diǎn)187。 實(shí)際中能用這種哈希函數(shù)的情況很少? 數(shù)字分析法– 構(gòu)造：對關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址– 適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(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 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 8 6 78 1 3 6 8 5 3 78 1 4 1 8 3 5 5…..…..?? ? ??? ??分析： ?只取 8 ?只取 1 ?只取 4 ?只取 5 ????數(shù)字分布近乎隨機(jī)所以：取 ????任意兩位或兩位 與另兩位的疊加作哈希地址? 平方取中法– 構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址– 適于不知道全部關(guān)鍵字情況? 折疊法– 構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址– 種類187。key+b– 特點(diǎn)187。? 哈希表技術(shù)的主要目標(biāo)是提高查找效率，即縮短查表和填表的時(shí)間。}? 哈希（ HSAE） 查找 散列查找– 基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法– 定義? 哈希函數(shù) —— 在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對應(yīng)關(guān)系叫 ~ 根據(jù)關(guān)鍵字的值，利用某個(gè)函數(shù)直接計(jì)算出元素所在的位置。 return(1)。 i=(i+j)%M。amp。amp。 i=h(k)。 } if(t[i]==k) return(1)。 if(t[i]=0) { t[i]=k。 if(j==M) return(0)。amp。amp。 i=h(k)。? else return(1)。? i=(i+j)%M。amp。amp。? i=h(k)。) MOD 11=4 不沖突(3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為 9，則： H1=(5+9) MOD 11=3 不沖突0 1 2 3 4 5 6 7 8 9 1060 17 29 383838? 再哈希法–方法：構(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)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，并用一維數(shù)組存放頭指針例 已知一組關(guān)鍵字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) 哈希函數(shù)為： H(key)=key MOD