【正文】 else if(a[mid] elem) low = mid + 1。 else high = mid 1。 } return 1。} 當(dāng)每個(gè)數(shù)據(jù)元素的查找概率相等時(shí)，二分查找算法查找成功時(shí)的平均查找長(zhǎng)度為： 二分查找算法查找失敗時(shí)的平均查找長(zhǎng)度為； 索引 把要在其上建立索引的數(shù)據(jù)元素序列（通常采用數(shù)組 保存）稱作主表。 主表中存放著數(shù)據(jù)元素的全部信息。 索引中只保存主表中要查找數(shù)據(jù)元素的關(guān)鍵字和索引信息。 下頁(yè)圖是一個(gè)主表和一個(gè)按關(guān)鍵字 key建立的索引的結(jié)構(gòu)圖。 把和主表項(xiàng)完全相同，但只包含索引關(guān)鍵字和該數(shù)據(jù)元素在主表中位置信息的索引稱作主表的 完全索引表。 下圖為帶完全索引表的索引表結(jié)構(gòu)圖 : 等長(zhǎng)索引 是指索引中的每個(gè)索引項(xiàng)對(duì)應(yīng)主表中的數(shù)據(jù)元素個(gè)數(shù)是相等的。 索引中的索引項(xiàng)對(duì)應(yīng)主表中的數(shù)據(jù)元素個(gè)數(shù)也可以是不相等的，這種索引結(jié)構(gòu)稱作 不等長(zhǎng)索引 結(jié)構(gòu)。 下圖為 不等長(zhǎng)索引表結(jié)構(gòu)圖： 帶索引結(jié)構(gòu)的數(shù)據(jù)元素查找算法的比較次數(shù)由兩部分組成： 一部分是在索引上查找的比較次數(shù) ； 一部分是在主表中的某個(gè)子表中進(jìn)行查找的比較次數(shù)。 假設(shè)索引的長(zhǎng)度為 m，主表中每個(gè)子表的長(zhǎng)度為 s，并假設(shè)在索引上和在主表上均采用順序查找算法，則整個(gè)查找算法的平均查找長(zhǎng)度為： 動(dòng)態(tài)查找 二叉排序樹也稱做二叉查找樹。二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： （ 1）若左子樹非空，則左子樹上所有結(jié)點(diǎn)的數(shù)據(jù)元素值均小于根結(jié)點(diǎn)的數(shù)據(jù)元素值； （ 2）若右子樹非空，則右子樹上所有結(jié)點(diǎn)的數(shù)據(jù)元素值均大于或等于根結(jié)點(diǎn)的數(shù)據(jù)元素值； （ 3）左右子樹也均為二叉排序樹。下圖為一棵二叉排序樹二叉排序樹的查找算法 ：public BiTreeNode find(int item){if(root != null){BiTreeNode temp = root。while(temp != null){if(() == item) return temp。 if(() item)temp = ()。 elsetemp = ()。 }}return null。 } }二叉排序樹的插入 二叉排序樹的刪除算法 ： 刪除操作的要求是：首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若不存在則結(jié)束；若存在則按下面四種情況分別進(jìn)行不同的刪除操作。這四種情況是 ： （ 1）要?jiǎng)h除結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)； （ 2）要?jiǎng)h除結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)； （ 3）要?jiǎng)h除結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)； （ 4）要?jiǎng)h除結(jié)點(diǎn)有左右孩子結(jié)點(diǎn)。對(duì)于上述四種不同情況，相應(yīng)的刪除方法是：（ 1）要?jiǎng)h除結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn)時(shí)，直接刪除該結(jié)點(diǎn)。（ 2）要?jiǎng)h除結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)時(shí)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。（ 3）要?jiǎng)h除結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)時(shí)，刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。（ 4）要?jiǎng)h除結(jié)點(diǎn)有左右孩子結(jié)點(diǎn)時(shí)，分如下三步完成：首先尋找數(shù)據(jù)元素值大于要?jiǎng)h除結(jié)點(diǎn)數(shù)據(jù)元素關(guān)鍵字的最小值，然后把右子樹的最左結(jié)點(diǎn)的數(shù)據(jù)元素值拷貝到要?jiǎng)h除的結(jié)點(diǎn)上；最后刪除右子樹的最左結(jié)點(diǎn)。 刪除結(jié)點(diǎn)無(wú)孩子結(jié)點(diǎn) 刪除結(jié)點(diǎn)只有左孩子結(jié)點(diǎn) :刪除結(jié)點(diǎn)只有右孩子結(jié)點(diǎn) :刪除孩子有左右結(jié)點(diǎn)的孩子 :二叉排序樹的性能分析 : 對(duì)有 n個(gè)結(jié)點(diǎn)的二叉排序樹來(lái)說(shuō)，若每個(gè)數(shù)據(jù)元素的查找概率相等，則二叉排序樹平均查找長(zhǎng)度是結(jié)點(diǎn)深度的函數(shù)，即： 若每個(gè)數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平均查找長(zhǎng)度為： 當(dāng)二叉排序樹是一棵單分支退化樹時(shí)，查找成功的平均查找長(zhǎng)度和有序數(shù)組的平均查找長(zhǎng)度相同，即為： B_樹 B_樹是一種平衡多叉排序樹。 B_樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)個(gè)數(shù)的最大值稱為 B_樹的階 . 一棵 m階的 B_樹或者是一棵空樹，或者是滿足下列要的 m階的 B_樹： （ 1）樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子結(jié)點(diǎn)。 （ 2）除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)至少有 [m/2]個(gè)孩子結(jié)點(diǎn)。 （ 3）若根結(jié)點(diǎn)不是葉結(jié)點(diǎn)，則根結(jié)點(diǎn)至少有兩個(gè)孩子結(jié)點(diǎn) （ 4）每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為： （ 5）所有葉結(jié)點(diǎn)都在二叉排序樹的同一層上。n P下圖是一棵 3階 B_樹的示例：1 B_樹的查找算法 在 B_樹上查找數(shù)據(jù)元素（確切說(shuō)是查找數(shù)據(jù)元素的關(guān)鍵字） key的方法為：將 key與根結(jié)點(diǎn)的 Ki逐個(gè)順序比較： （ 1）若 key=Ki則查找成功 ； （ 2）若 keyK1則沿著指針 P0所指的子樹繼續(xù)查找； （ 3）若 KikeyKi+1則沿著指針 Pi所指的子樹繼續(xù)查找 （ 4）若 keyKn則沿著指針 Pn所指的子樹繼續(xù)查找 。? B_樹的插入算法 將數(shù)據(jù)元素 key插入到 B_樹的過(guò)程分兩步完成： （ 1）利用 B_樹的查找算法找出該數(shù)據(jù)元素結(jié)點(diǎn)應(yīng)該插入的結(jié)點(diǎn)位置； （ 2）判斷要插入的結(jié)點(diǎn)是否還有空位置，即判斷該結(jié)點(diǎn)是否滿足 nm1，若該結(jié)點(diǎn)滿足 nm1，說(shuō)明該結(jié)點(diǎn)還有空位置，直接把數(shù)據(jù)元素 key插入到該結(jié)點(diǎn)的合適位置上；若該結(jié)點(diǎn)有 n=m1，說(shuō)明該結(jié)點(diǎn)已沒(méi)有空位置，要插入就要分裂該結(jié)點(diǎn)。 下圖是 3階 B_樹上進(jìn)行插入操作的示例 ： 初始狀態(tài)：插入 90后的狀態(tài) :插入 195后結(jié)點(diǎn)分裂前的狀態(tài)：插入 195后結(jié)點(diǎn)的分裂過(guò)程：? B_樹的刪除 在 B_樹上刪除數(shù)據(jù)元素 key的過(guò)程分兩步完成： （ 1）利用 B_樹的查找算法找出該數(shù)據(jù)元素所在的結(jié)點(diǎn)； （ 2）在結(jié)點(diǎn)上刪除數(shù)據(jù)元素 key分兩種情況：一種是在葉結(jié)點(diǎn)上刪除數(shù)據(jù)元素；另一種是在非葉結(jié)點(diǎn)上刪除數(shù)據(jù)元素。 在非葉結(jié)點(diǎn)上刪除數(shù)據(jù)元素的算法思想為：假設(shè)要?jiǎng)h除一個(gè)結(jié)點(diǎn)的數(shù)據(jù)元素 Ki（ 1≤i≤n），首先尋找該結(jié)點(diǎn) Pi所指子樹中的最小數(shù)據(jù)元素 Kmin，然后用 Kmin覆蓋要?jiǎng)h除的數(shù)據(jù)元素 Ki，最后再以指針 Pi所指結(jié)點(diǎn)為根結(jié)點(diǎn)查找并刪除 Kmin。 在 B_樹的葉結(jié)點(diǎn)上刪除數(shù)據(jù)元素共有以下三種情況：（ a）要?jiǎng)h除數(shù)據(jù)元素結(jié)點(diǎn)的數(shù)據(jù)元素個(gè)數(shù) n[m/2]1（ b）要?jiǎng)h除數(shù)據(jù)元素結(jié)點(diǎn)的數(shù)據(jù)元素個(gè)數(shù) n=[m/2]1 （ c）假如要?jiǎng)h除數(shù)據(jù)元素結(jié)點(diǎn)的數(shù)據(jù)元素個(gè)數(shù) n=[m/2]1并且該結(jié)點(diǎn)的左和右兄弟結(jié)點(diǎn)（如果存在的話）中數(shù)據(jù)元素個(gè)數(shù) n均等于 [m/2]1 下面幾幅圖是 在 3階 B_樹上進(jìn)行刪除操作的示例 初始狀態(tài)： 刪去 110后的狀態(tài) 刪去 80后的狀態(tài) 刪去 116后的狀態(tài) 刪去 180后的狀態(tài) 第 11章 哈希表 哈希表的基本概念 哈希函數(shù)的構(gòu)造方法 哈希沖突解決方法 哈希表設(shè)計(jì)類本章主要知識(shí)點(diǎn)：● 哈希表的基本概念● 建立哈希表的關(guān)鍵問(wèn)題● 哈希函數(shù)構(gòu)造方法和哈希沖突解決方法● 哈希表類設(shè)計(jì)方法 哈希表的基本概念 哈希表 主要是構(gòu)造一個(gè)映射函數(shù)，該函數(shù)以數(shù)據(jù)元素為自變量，函數(shù)值即為數(shù)據(jù)元素在內(nèi)存中的存儲(chǔ)位置。通常把這樣的映射函數(shù)稱為哈希函數(shù) h(x)。因此可以說(shuō)，哈希表是通過(guò)哈希函數(shù) h(x)來(lái)確定數(shù)據(jù)元素 x存放位置 h(x)的一種特殊存儲(chǔ)結(jié)構(gòu)。 哈希表的基本構(gòu)造方法 構(gòu)造哈希表 的方法是：設(shè)要存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)為 n，設(shè)置一個(gè)長(zhǎng)度為 m（ m≥n）的連續(xù)內(nèi)存單元（即數(shù)組），分別以每個(gè)數(shù)據(jù)元素的關(guān)鍵字 Ki（ 0≤i≤n1）為自變量，以哈希函數(shù) h(Ki)值為該數(shù)據(jù)元素在數(shù)組中的下標(biāo)值存儲(chǔ)該數(shù)據(jù)元素。 把構(gòu)造哈希表時(shí) Ki≠Kj（ i≠j） ,但 h(Ki)=h(Kj)的現(xiàn)象稱作 哈希沖突。 建立哈希表的關(guān)鍵問(wèn)題 設(shè)計(jì)一個(gè)好的哈希函數(shù)，使得盡量避免哈希沖突，以及哈希沖突發(fā)生后，如何解決哈希沖突，就成了建立哈希表的兩個(gè)關(guān)鍵問(wèn)題。 哈希沖突主要與三個(gè)因素有關(guān)： （ 1）與裝填因子 a有關(guān)。 （ 2）與所采用的哈希函數(shù)有關(guān)。 （ 3）與解決哈希沖突的哈希沖突函數(shù)有關(guān)。 哈希函數(shù)構(gòu)造方法 設(shè)要存放的數(shù)據(jù)元素有 n個(gè)，存放數(shù)據(jù)元素的數(shù)組個(gè)數(shù)為 m，哈希函數(shù)的設(shè)計(jì)目標(biāo)，就是要使通過(guò)哈希函數(shù)得到的 n個(gè)數(shù)據(jù)元素的哈希地址 。 1 除留余數(shù)法 除留余數(shù)法是用數(shù)據(jù)元素的關(guān)鍵字 K除以哈希表長(zhǎng)度 m所得的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù) h(K)為： h(K) = K mod m 2 直接定址法 直接定址法是以數(shù)據(jù)元素的關(guān)鍵字 K本身或關(guān)鍵字加上某個(gè)數(shù)值常量 C作為哈希函數(shù)的方法。直接定址法的哈希函數(shù) h(K)為： h(K) = K + C3 數(shù)字分析法 數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位構(gòu)造哈希函數(shù)的方法。它只適合于所有關(guān)鍵字值已知的情況。 哈希沖突解決方法解決哈希沖突的方法主要有 開放定址法 和 鏈表法 兩大類。 開放定址法 開放定址法是一類以發(fā)生哈希沖突的哈希地址為自變量、通過(guò)某種哈希沖突函數(shù)得到一個(gè)新的空閑的哈希地址的方法。開放定址法的哈希沖突函數(shù)通常是一組。1 線性探查法 線性探查法是從發(fā)生哈希沖突的地址 d開始，依次探查 d的下一個(gè)地址，直到找到一個(gè)空閑單元為止。線性探查法的數(shù)學(xué)遞推描述公式為：2 平方探查法 設(shè)發(fā)生哈希沖突的地址為 d，則平方探查法的探查序列為： d+2, d+21, d+22, … 。平方探查法的數(shù)學(xué)遞推描述公式為： 3 偽隨機(jī)數(shù)法 設(shè)發(fā)生哈希沖突的地址為 d，則偽隨機(jī)數(shù)法的探查序列為 d+Ri。 Ri為一偽隨機(jī)數(shù)序列的第 i個(gè)數(shù)值。偽隨機(jī)數(shù)法的數(shù)學(xué)遞推描述公式為： 鏈表法 鏈表法解決哈希沖突的基本思想是：如果沒(méi)有發(fā)生哈希沖突，則直接在該地址保存該數(shù)據(jù)元素；如果發(fā)生了哈希沖突，則把發(fā)生哈希沖突的數(shù)據(jù)元素保存在另外的單鏈表中。 用鏈表法解決哈希沖突通常有兩種方法： 第一種方法是為發(fā)生哈希沖突的不同的同義詞建立不同的單鏈表， 第二種方法是為所有發(fā)生哈希沖突的數(shù)據(jù)元素建立一個(gè)單鏈表。用鏈表法解決沖突的哈希表 示例