[高等教育]數(shù)據(jù)結(jié)構(gòu)第9章查找(編輯修改稿)
2025-02-15 18:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 叉樹(shù)，嚴(yán)格的定義為： 平衡二叉樹(shù)或者是空樹(shù)，或者是任何結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度最多相差 1的的二叉樹(shù)。 結(jié)點(diǎn)的平衡因子 BF： 指該結(jié)點(diǎn)的左子樹(shù)高度和右子樹(shù)的高度之差。 平衡二叉樹(shù)的性質(zhì)：平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是 0、 1。 平衡二叉樹(shù)示例 非平衡二叉樹(shù)示例 B樹(shù)和 B+樹(shù) B樹(shù)是用于文件系統(tǒng)，它是一種平衡的多叉樹(shù)，其定義如下： 一棵 m階的 B樹(shù)滿足下列條件： ⑴ 樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子； ⑵ 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有m/2個(gè)孩子； ⑶ 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有 2個(gè)孩子； ⑷ 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息； ⑸ 有 k個(gè)孩子的非終端結(jié)點(diǎn)恰好包含有 k1個(gè)關(guān)鍵字。 哈希表 （ Hash Table） ? 什么是哈希表 ? 哈希函數(shù)的構(gòu)造方法 ? 處理沖突的方法 什么是哈希表 例子 1 線性索引 ? 有一個(gè)存放職工信息的數(shù)據(jù)表，每一個(gè)職工對(duì)象有近 40 字節(jié)的信息。 哈希表 （ 散列表 ） 的概念 ? 散列方法 ：在記錄的存儲(chǔ)位置 Address （在一個(gè)有限的連續(xù)的地址區(qū)間中）與它的關(guān)鍵字 key之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系 H(key)，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)： Address ＝ H (key) ? 在搜索時(shí)，首先對(duì)給定的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做記錄的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取記錄的關(guān)鍵字與該給定的關(guān)鍵字比較。若相等，則搜索成功。在存放記錄時(shí)，根據(jù)相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。這種方法就是 散列方法 。 ? 在散列方法中使用的轉(zhuǎn)換函數(shù)叫做 散列函數(shù) 。存儲(chǔ)位置 Address稱(chēng)為 哈希地址 或 散列地址 。 ? 而按此種想法構(gòu)造出來(lái)的表或結(jié)構(gòu)就叫做 散列表或哈希表 。 ? 使用散列方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵字的比較 ，搜索速度比較快 ， 可以直接到達(dá)或逼近具有此關(guān)鍵字的記錄的實(shí)際存放地址 。 ? 散列函數(shù)是一個(gè)壓縮映象函數(shù) 。 散列函數(shù)是從關(guān)鍵字集合到地址集合的影像 ， 關(guān)鍵字集合比散列地址集合大得多 。 因此有可能經(jīng)過(guò)散列函數(shù)的計(jì)算 ， 把不同的關(guān)鍵字映射到同一個(gè)散列地址上 ， 這就產(chǎn)生了 沖突 (Collision)。 ? 示例：有一組記錄 ， 其關(guān)鍵字分別是 12361, 07251, 03309, 30976 采用的散列函數(shù)是 hash(x) = x % 73 + 13420 其中 ， “ %”是除法取余操作 。 則有： hash(12361) = hash(07251) = hash(03309) = hash(30976) = 13444。 就是說(shuō) ， 對(duì)不同的關(guān)鍵字 ， 通過(guò)散列函數(shù)的計(jì)算 ， 得到了同一散列地址 。 我們稱(chēng)這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵字為 同義詞 。 ?構(gòu)造要求： ? 哈希 函數(shù)的定義域 (即關(guān)鍵字集合 )必須包括所有可能的關(guān)鍵字，如果散列表允許有 n個(gè)地址時(shí) , 其值域（即哈希地址集合）必須在 0 到 n1 之間。 ? 關(guān)鍵字經(jīng)過(guò) 哈希 函數(shù)計(jì)算出來(lái)的 “ 隨機(jī)地址 ”應(yīng)能均勻分布在整個(gè)地址空間中：若 key 是從關(guān)鍵字集合中隨機(jī)抽取的一個(gè)關(guān)鍵字， 哈希 函數(shù)應(yīng)能以同等概率 取 0 到 n1 中的每一個(gè)值。從而 盡量減少?zèng)_突。 哈希函數(shù)的構(gòu)造方法 ? 此類(lèi)函數(shù)取關(guān)鍵字的某個(gè)線性函數(shù)值作為散列地址： H ( key ) ＝ a * key + b { a, b
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1