【正文】 5 8 11 1 34 67 910 12 23 45 56 78 89 1011 11 ② 折半查找的平均查找長度 假定有序表的長度 n＝ 2h－ 1（反之， h＝ log2(n+1)），則描述折半 查找的判定樹是深度為 h的滿二叉樹。假設(shè)表中每個記錄的查找概率相 等 (Pi = 1/n)，則查找成功時折半查找的平均查找長度： 1)1(l o g121 2111??????? ?????nnnjnCPA S L hjjniiibs對任意的 n，當(dāng) n較大 (n50)時，可有下列近似結(jié)果： 1)1(lo g 2 ??? nA S L bs（ 4）折半查找算法的特點 特點：只適用于有序表，且限于順序存儲結(jié)構(gòu)（對線性鏈表無法進行 折半查找）。 ￡ 索引順序表的查找 （ 1）分塊查找 分塊查找又稱索引順序查找，這是順序查找的一種改進方法。在此 查找法中，除表本身以外，尚需建立一個“索引表”。如下例所示。 查找過程： 將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找 適用條件： 分塊有序表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 索引表 查 38 最大關(guān)鍵字 起始地址 分塊有序 ：即后一個子表中的所有記錄的關(guān)鍵字均大于前一個子表中的最大關(guān)鍵字。 分塊查找的 算法思想 ： ① 確定待查記錄所在的塊（子表）； ② 在塊中順序查找 （ 2）性能分析 分塊查找的平均查找長度為： 其中： Lb為查找索引表確定所在塊的平均查找長度， Lw為在塊中查找元素的 平均查找長度。 1)(212 12 11111??????????? ????ssnsbisjbLLA S L sibjwbbsASLbs＝ Lb＋ Lw ① 用順序查找確定所在塊 ? ?snb /? ；又假定表中每個記錄的查找概率相等，則每 一般情況下，為進行分塊查找，可以將長度為 n的表均勻地分成 b塊，每 塊含有 s個記錄，即 塊查找的概率為 1/b，塊中每個記錄的查找概率為 1/s。則分塊查找的平均長 度為： ② 用折半查找確定所在塊 2)1(lo g 2 ssnLAS bs ????ASL（平均查找長度） 最大 最小 兩者之間 表結(jié)構(gòu) 有序表、無序表 有序表 分塊有序表 存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 順序存儲結(jié)構(gòu) 順序存儲結(jié)構(gòu) 線性鏈表 查找方法比較 順序查找 折半查找 分塊查找 特點 ：表結(jié)構(gòu)本身是在 查找過程中動態(tài)生成的 ，即對于給定值 key， 若表中存在其關(guān)鍵字等于 key的記錄，則查找成功返回，否則插入關(guān)鍵字 等于 key的記錄。 動態(tài)查找表的特點 ￡ 二叉排序樹和平衡二叉樹 （ 1）二叉排序樹 二叉排序樹 （ Binary Sort Tree）：它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹： 1．若它的左子樹不空，則左子樹上所有結(jié)點的值均 小于 它的根結(jié)點的值； 2．若它的右子樹不空，則右子樹上所有結(jié)點的值均 大于 它的根結(jié)點的值； 3．它的左、右子樹也分別為二叉排序樹。 ① 定義 ② 圖形表示 45 12 53 3 37 100 24 78 61 90 圖 二叉排序樹示例 (a) ③ 二叉排序樹的查找 算法思想 ：二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不空時，首 先將給定值和根結(jié)點的關(guān)鍵字比較，若相等，則查找成功，否則將依據(jù) 給定值和根結(jié)點的關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼 續(xù)進行查找。 算法實現(xiàn) ：取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)。 BiTree SearchBST (BiTree T, KeyType key) { //在根指針 T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素， //若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，否則返回空指針。 if ((!T) | | EQ(key, T－ )) //查找結(jié)束 return (T)。 else if (LT(key, T－ )) //在左子樹中繼續(xù)查找 return (SearchBST (T－ lchild, key))。 else return (SearchBST (T－ rchild, key))。 //在右子樹中繼續(xù)查找 } // SearchBST 算法 (a)如下： ④ 二叉排序樹的插入和刪除 1．插入算法 i． 算法思想 ：根據(jù)二叉排序樹的特點，易知，新插入的結(jié)點一定是一個新添加的葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。 ii． 算法實現(xiàn) ：為了在查找不成功時返回新結(jié)點的插入位置，將上述算法算法 (a)修改為 (b)。插入算法如算法 。 ④ 二叉排序樹的插入和刪除 1．插入算法 Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree amp。p) { //在根指針 T所指二叉排序樹中遞歸地查找某關(guān)鍵字等于 key的數(shù)據(jù)元素，若 //查找成功，則指針 p指向該數(shù)據(jù)元素結(jié)點，并返回 TRUE，否則指針 p指向 //查找路徑上訪問的最后一個結(jié)點并返回 FALSE，指針 f指向 T的雙親，其初 //始調(diào)用值為 NULL。 if (!T) { p = f。 return FALSE。} //查找不成功 else if EQ(key, T－ ) { p = T。 return TRUE。} //查找成功 else if LT(key, T－ ) //在左子樹中繼續(xù)查找 return (SearchBST (T－ lchild, key, T, p))。 else return (SearchBST (T－ rchild, key, T, p))。 //在右子樹中繼續(xù)查找 } // SearchBST 算法 (b)如下： Status InsertBST (BiTree T, ElemType e) { //當(dāng)二叉排序樹 T中不存在關(guān)鍵字等于 ，插入 e并 //返回 TRUE，否則返回 FALSE。 if (!SearchBST (T, , NULL, p)) { //查找不成功 s = (BiTree) malloc (sizeof (BiTree))。 s－ data = e。 s－ lchild = s－ rchild = NULL。 if (!p) T = s。 //被插結(jié)點 *s為新的根結(jié)點 else if LT(, p－ ) //被插結(jié)點 *s為左孩子 p－ lchild = s。 else p－ rchild = s。 //被插結(jié)點 *s為右孩子 return TRUE。 } else return FALSE。 //樹中已有關(guān)鍵字相同的結(jié)點 } // InsertBST 算法 ： iii．例子 例如，從空樹出發(fā)，經(jīng)過一系列的查找插入操作之后，可生成一棵二叉樹。設(shè)查找的關(guān)鍵字序列為 {45, 24, 53, 45, 12, 24, 90}，則刪除的二叉排序樹如圖 。 45 24 53 12 90 45 24 53 12 45 24 53 45 24 45 (a) (b) (c) (d) (e) (f) 圖 二叉排序樹的構(gòu)造過程 二叉排序樹查找的性能分析 在二叉排序樹查找中 ， 成功的查找次數(shù)不會超過二叉樹的深度 ， 而具有 n個結(jié)點的二叉排序樹的深度 ， 最好為log2n， 最壞為 n。 因此 ， 二叉排序樹查找的最好時間復(fù)雜度為 O(log2n)， 最壞的時間復(fù)雜度為 O(n)， 一般情形下 ， 其時間復(fù)雜度大致可看成 O(log2n)， 比順序查找效率要好 ， 但比二分查找要差 。 （ 2）平衡二叉樹 ① 定義 平衡二叉樹 （ Balanced Binary Tree 或 HeightBalanced Tree）又稱 AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子 樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不 超過 1。 平衡因子 BF（ Balance Factor）：二叉樹上結(jié)點的左子樹的深度減去它的右子樹的深度的值。 由平衡二叉樹的定義易知，平衡二叉樹上所有結(jié)點的平衡因子只可能 是－ 0和 1。 例如，圖 (a)所示為兩棵平衡二叉樹，而 圖 (b)為兩棵不平衡二叉樹，結(jié)點中的值為該結(jié)點 的平衡因子 ② 圖形表示 (a) 平衡二叉樹 1 1 0 0 1 1 1 0 1 0 0 ⑥ 平衡樹查找的分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復(fù)雜度 O(n)，它的時間復(fù)雜度與二叉排序樹的最好時間復(fù)雜相同，都為 O(log2n)。 ￡ 哈希表 ￡ 定義 哈希 （ Hash）函數(shù)：在記錄的存儲位置和它的關(guān)鍵字之間建立的一個確定的對應(yīng)關(guān)系 f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。稱這個對應(yīng)關(guān)系 f為哈希函數(shù)。 基本思想 ：在記錄的 存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 ；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法 關(guān)鍵字 集合 存儲地址 集合 hash ? 哈希表 —— 應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 ~ ? 哈希查找 —— 又叫散列查找，利用哈希函數(shù)進行查找的過程叫 ~ 例 30個地區(qū)的各民族人口統(tǒng)計表 編號 地區(qū)別 總?cè)丝? 漢族 回族 …... 1 北京 2 上海 …... …... 以 編號 作關(guān)鍵字， 構(gòu)造 哈希函數(shù)： H(key)=key H(1)=1 H(2)=2 以 地區(qū)別 作關(guān)鍵字，取地區(qū) 名稱第一個拼音字母的序號 作哈希函數(shù)： H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19 從例子可見： 哈希函數(shù) 只是一種 映象 ，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可 沖突： key1≠key2，但 H(key1)=H(key2)的現(xiàn)象叫 ~ 同義詞 ：具有相同函數(shù)值的兩個關(guān)鍵字，叫該哈希函數(shù)的 ~ 哈希函數(shù)通常是一種壓縮映象，所以 沖突不可避免 ，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法 ￡ 哈希函數(shù)的構(gòu)造 （ 1）直接定址法 取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。即： H(key) = key 或 H(key) = a * key + b 其中 a和 b為常數(shù)（這種哈希函數(shù)叫做 自身函數(shù) ）。 2．例子 例一，有一個從 1歲到 100歲的人口數(shù)字統(tǒng)計表。 地址 01 02 03 … 25 26 27 … 100 年齡 1 2 3 …