【正文】 3 5 5…..…..?? ? ??? ??分析： ?只取 8 ?只取 1 ?只取 4 ?只取 5 ????數(shù)字分布近乎隨機所以：取 ????任意兩位或兩位 與另兩位的疊加作哈希地址? 平方取中法– 構造：取關鍵字平方后中間幾位作哈希地址– 適于不知道全部關鍵字情況? 折疊法– 構造：將關鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址– 種類187。 移位疊加：將分割后的幾部分低位對齊相加187。 間界疊加：從一端沿分割界來回折送，然后對齊相加– 適于關鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例 關鍵字為 ： 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ù)法– 構造：取關鍵字被某個不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即 H(key)=key MOD p， p?m– 特點187。 簡單、常用，可與上述幾種方法結合使用187。 p的選取很重要； p選的不好，容易產(chǎn)生同義詞? 隨機數(shù)法– 構造：取關鍵字的隨機函數(shù)值作哈希地址，即H(key)=random(key)– 適于關鍵字長度不等的情況? 選取哈希函數(shù)，考慮以下因素：– 計算哈希函數(shù)所需時間– 關鍵字長度– 哈希表長度（哈希地址范圍）– 關鍵字分布情況– 記錄的查找頻率– 處理沖突的方法? 開放定址法– 方法：當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1)其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列– 線性探測再散列： di=1,2,3,……m1– 再哈希法：構造若干個哈希函數(shù)，當發(fā)生沖突時，計算下一個哈希地址，即： Hi=Rhi(key) i=1,2,……k其中： Rhi—— 不同的哈希函數(shù)– 特點：計算時間增加例 表長為 11的哈希表中已填有關鍵字為 17， 60， 28的記錄， H(key)=key MOD 11,現(xiàn)有第 4個記錄，其關鍵字為 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? 鏈地址法 (外鏈法 )– 方法：將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針例 已知一組關鍵字 (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^^^^^^^^^^^^例 已知一組關鍵字 (18,14,23,1,68,20,84,27,55,11,10,78) 哈希函數(shù)為： H(key)=key MOD 13, 哈希表長為 m=16， 設每個記錄的查找概率相等(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=關鍵字 (18,14,23,1,68,20,84,27,55,11,10,78) 二叉排序 樹上的查找 （ 1）二叉排序 樹的查找思想若二叉排樹為空，則查找 失敗，否則，先拿根結點值與待查值進行比較，若相等，則查找成功，若根結點值大于待查值，則進入左子樹重復此步驟，否則，進入右子樹重復此步驟，若在查找過程中遇到二叉排序樹的葉子結點時，還沒有找到待找結點，則查找不成功。（ 2）二叉排序樹查找的算法實現(xiàn)Btreenode * find( Btreenode *BST,elentype x) //在以 BST為根指針的二叉排隊 樹中查找值為 x的結點{ if ( BST= =NULL) return NULL。 //查找失敗 else { if (BSTdata= =x) //查找成功 return BST。 else if (BSTdatax) //進入左子樹查找 return find ( BSTleft,x)。 else //進入右子樹查找 return find (BSTright,x)。} }二叉排序樹查找的性能分析在二叉排序樹查找中，成功的查找次數(shù)不會超過二叉樹的深度，而具有 n個結點的二叉排序樹的深度，最好為log2n， 最壞為 n。 因此，二叉排序樹查找的最好時間復雜度為 O(log2n)， 最壞的時間復雜度為 O(n)， 一般情形下，其時間復雜度大致可看成 O(log2n)， 比順序查找效率要好，但比二分查找要差。平衡二叉樹查找若一棵二叉樹中每個結點的左、右子樹的深度之差的絕對值不超過 1，則稱這樣的二叉樹為平衡二叉樹。將該結點的左子樹深度減去右子樹深度的值，稱為該結點的平衡因子 (balance factor)。 也就是說，一棵二叉排序樹中，所有結點的平衡因子只能為 0、 1時，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹。非平衡二叉樹的平衡處理若一棵二叉排序樹是平衡二叉樹，扦入某個結點后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進行平衡處理，使其變成一棵平衡二叉樹。處理的原則應該是處理與扦入點最近的、而平衡因子又比 1大或比 1小的結點。（ 1） LL型 的處理 (左左型 )在 C的左孩子 B上扦入一個左孩子結點 A，使 C的平衡因子由 1變成了 2，成為不平衡的二叉樹序樹。這時的平衡處理為：將 C順時針旋轉，成為 B的右子樹，而原來 B的右子樹則變成 C的左子樹，待扦入結點 A作為 B的左子樹。 (注：圖中結點旁邊的數(shù)字表示該 結點的平衡因子 )（ 2） LR型的處理 (左右型 )在 C的左孩子 A上扦入一個右孩子 B， 使的 C的平衡因子由 1變成了 2，成為不平衡的二叉排序樹。這是的平衡處理為：將 B變到 A與 C 之間，使之成為LL型，然后按第 (1)種情形 LL型處理。（ 3） RR型的處理 (右右型 )在 A的右孩子 B上扦入一個右孩子 C，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。這時的平衡處理為：將 A逆時針旋轉，成為 B的左子樹，而原來 B的左子樹則變成 A的右子樹，待扦入結點 C成為 B的右子樹。（ 4） RL型的處理 (右左型 )在 A的右孩子 C上扦入一個左孩子 B，使 A的平衡因子由 1變成 2，成為不平衡的二叉排序樹。這時的平衡處理為：將 B變到 A與 C之間，使之成為 RR型，然后按第 (3) 種情形 RR型處理。給定一個關鍵字序列 4,5,7,2 ,1,3,6，試生成一棵平衡二叉樹。分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應平衡處理，最后就可以建成一棵平衡二叉樹。平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復雜度 O(n)， 它的時間復雜度與二叉排序樹的最好時間復雜相同，都為 O(log2n)。 對例 82給定的關鍵字序列 4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找 6的次數(shù)及成功的平均查找長度。分析：由于關鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹和平衡二叉樹都是唯一的。得到的平衡二叉樹見圖 814，得到的二叉排序樹見圖 815。 從圖 815的二叉排序樹可知，查找 6需 4次，平均查找長度 ASL=(1+2+2+3+3+3+4)/7=18/7≈。從圖 814的平衡二叉樹可知，查找 6需 2次，平均查找長度ASL=(1+2+2+3+3+3+3)=17/7≈。從結果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。 學習要點熟練掌握順序表和有序表的查找方法，并能靈活應用。熟練掌握二叉排序樹和平衡二叉排序樹的構造方法和查找方法。熟練掌握哈希表的構造方法，深刻理解哈希表與其它結構的表的實質性的區(qū)別。掌握計算各種查找方法在等概率情況下查找成功時的平均查找長度。作業(yè)：