【正文】 13, 用鏈地址法處理沖突^0 1 2 3 4 5 6 7 8 9 10 11 12 14^6819202311^^^^^1 27 79558410^^^^^^– 哈希查找過(guò)程及分析? 哈希查找過(guò)程給定 k值計(jì)算 H(k)此地址為空關(guān)鍵字 ==k查找失敗查找成功按處理沖突方法計(jì)算 HiYNYN? 哈希查找分析–哈希查找過(guò)程仍是一個(gè)給定值與關(guān)鍵字進(jìn)行比較的過(guò)程–評(píng)價(jià)哈希查找效率仍要用 ASL–哈希查找過(guò)程與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于：? 哈希函數(shù)? 處理沖突的方法? 哈希表的填滿因子 ?=表中填入的記錄數(shù) /哈希表長(zhǎng)度例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為： H(key)=key MOD 13, 哈希表長(zhǎng)為 m=16， 設(shè)每個(gè)記錄的查找概率相等 (1) 用線性探測(cè)再散列處理沖突，即Hi=(H(key)+di) MOD m0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 1 68 27 55 19 20 84 79 23 11 10H(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=9ASL=(1*6+2+3*3+4+9)/12=H(19)=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(19,14,23,1,68,20,84,27,55,11,10,79)H(key)=key MOD 13 Hi=(H(key)+di) MOD m(2) 用鏈地址法處理沖突0 1 2 3 4 5 6 7 8 9 10 11 12 14^1 27 7968 5519 842023 1011^^^^^^^^^^^^ASL=(1*6+2*4+3+4)/12=關(guān)鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)? 哈希查找算法實(shí)現(xiàn) – 用線性探測(cè)再散列法處理沖突? 實(shí)現(xiàn)–查找過(guò)程：同前–刪除：只能作標(biāo)記，不能真正刪除–插入：遇到空位置或有刪除標(biāo)記的位置就可以插入? 算法描述：– 用鏈表處理沖突算法? define M 100? int h(int k)? { return(k%97)。(k ?m/2)–偽隨機(jī)探測(cè)再散列： di=偽隨機(jī)數(shù)序列例 表長(zhǎng)為 11的哈希表中已填有關(guān)鍵字為 17， 60， 29的記錄， H(key)=key MOD 11,現(xiàn)有第 4個(gè)記錄，其關(guān)鍵字為 38， 按三種處理沖突的方法，將它填入表中(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 不沖突 (2) H(38)=38 MOD 11=5 沖突 H1=(5+1178。,……177。,2178。,1178。ki是 ai的關(guān)鍵字 關(guān)鍵字集合存儲(chǔ)地址集合hash哈希表 —— 應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 ~哈希查找 —— 又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過(guò)程叫 ~例 30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表編號(hào) 地區(qū)別 總?cè)丝? 漢族 回族 …...1 北京2 上?！?.. …...以編號(hào)作關(guān)鍵字，構(gòu)造 哈希函數(shù)： H(key)=keyH(1)=1H(2)=2以地區(qū)別作關(guān)鍵字，取地區(qū)名稱第一個(gè)拼音字母的在字母表中序號(hào)作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19從例子可見：–哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可–沖突 ： key1?key2， 但 H(key1)=H(key2)的現(xiàn)象叫 ~–同義詞 ：具有相同函數(shù)值的兩個(gè)關(guān)鍵字，叫該哈希函數(shù)的 ~–哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免 ，只能盡量減少；同時(shí)，沖突發(fā)生后，應(yīng)該有處理沖突的方法 哈希函數(shù)的構(gòu)造方法? 直接定址法–構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)作哈希地址，即 H(key)=key 或 H(key)=aai是表中的一個(gè)元素187。有可能進(jìn)行到根，使 B_ 樹的深度降低一層！167。 至少 1 個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。B_ 樹和 B+ 樹 例如： 3 階 B_ 樹的刪除操作。 則執(zhí)行合并結(jié)點(diǎn)的操作。處理結(jié)束。 而它們的左或右鄰居結(jié) 點(diǎn)的關(guān)鍵字的個(gè)數(shù) m/2 1 。則結(jié)束。從第 L 層開始進(jìn)行刪除。用 的右子樹中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即 處于第 L 層上的最小 關(guān)鍵字值取代 。3， 127 24 3024， 3045， 7053 9026 10039 50 61 85 345， 7053 9026 10039 50 61 851230324 45 7053 9026 10039 50 61 85127 3032453 9026 10039 50 61 85127 45 707插入B_ 樹和 B+ 樹 B_ 樹的刪除操作查找具有給定鍵值的關(guān)鍵字 Ki 如果 在 第 L 層，可直接刪除（注意：第 L+1 層為葉子結(jié)點(diǎn)），轉(zhuǎn) 4 。 m=3, m/2 1 = 1。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹可能長(zhǎng)高一層。否則不滿結(jié)束。若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) m1, 則該結(jié)點(diǎn)滿。故： L＝ log m/2 （（ N+1） /2） + 1設(shè) N ＝ 1000， 000 且 m＝ 256 ， 則 L = 3； 最多 3 次訪問(wèn)外存可找到所有的記錄。? 設(shè)關(guān)鍵字的總數(shù)為 N ， 求 m階 B_ 樹的最大層次 L。 查找 An指向的結(jié)點(diǎn) 若 找到葉子，則查找失敗。 查找 Ai 指向的結(jié)點(diǎn) 若 KEY K1。 從根開始查找，如果 Ki = KEY 則查找成功， Ri 為關(guān)鍵字為 KEY 的記錄的地址。1， 993， 47， 58， 641， 391， 271， 112， 43， 781， 181， 35F F F F F FF F F F F F第 1 層第 2 層第 3 層 (L層 )第 4 層 (L＋ 1層 )B_ 樹和 B+ 樹 B_ 樹的查找代價(jià)分析：? 查找過(guò)程，類似于二叉樹的查找。該 B_ 樹的深度為 4。例如： m = 4 階 B_ 樹。提高訪問(wèn)速度、減少時(shí)間。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。因此，要多次 訪問(wèn)外存。BC? 右改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的右子樹上進(jìn)行的調(diào)整）的情況分析： RR 情況：（ RR： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 右子樹 的 右子樹上 ） 處理圖形和 LL 鏡象相似 RL 情況：（ RL： 表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的 右子樹 的 左子樹上 ） A、 處理圖形和 LRA 鏡象相似 B、 處理圖形和 LRB 鏡象相似 C、 處理圖形和 LRC 鏡象相似? 刪除情況：略? 程序?qū)崿F(xiàn)：略、 B_ 樹和 B+ 樹 為什么采用 B_ 樹和 B+ 樹：大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。 插入之后仍應(yīng)保持平衡二叉排序樹的性質(zhì)不變。1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹的性質(zhì)不變？2 3 5 97 1223597 12不可以以結(jié)點(diǎn) 為子樹的根結(jié)點(diǎn)?。‰m然，對(duì)本例來(lái)說(shuō)是可以行得通的。93 5 9? 平衡二叉排序樹的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡樹中 插入 數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。新插入的結(jié)點(diǎn)和第一個(gè)平衡度不為 0 的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為 0?在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如： ），其它結(jié)點(diǎn)不予調(diào)整。原平衡度為 01412539 286353605017187 30+1+11110000000 02+1+1+2危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹的性質(zhì)不變？解決方案：?不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（左圖為 3 ）。1412539 286353605017187 30+1+11110000000 0平衡樹1412539 286353605017187 30+1+11110000000 02+1+1+2原平衡度為 0危機(jī)結(jié)點(diǎn)如何用最簡(jiǎn)單、最有效的辦法保持平衡二叉排序樹的性質(zhì)不變？? 平衡二叉排序樹的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡二叉排序樹中插入數(shù)據(jù)場(chǎng)為 2 的結(jié)點(diǎn)。? 平衡二叉排序樹的 Adelson 算法的本質(zhì)特點(diǎn)：? 以插入為例： 在左圖所示的平衡二叉排序樹中插入數(shù)據(jù)場(chǎng)為 2的結(jié)點(diǎn)。? 平衡二叉樹： 每個(gè)結(jié)點(diǎn)的平衡因子都為