【正文】 else if(K = = Tkey) return(T)。 /*在左樹中查找 */ if(KTkey) return SearchBST(Trchild,K)。 if(T == NULL) { s=(BSTree*)malloc(sizeof(BSTNODE))。 slchild=NULL。 T=s。 else if(KTkey) InsertBST(Trchild,K)。每讀入一個(gè)元素 ， 就建立一個(gè)新的結(jié)點(diǎn)并插入到當(dāng)前已生成的二叉排序樹中 ， 即調(diào)用上述二叉排序樹的插入算法將新結(jié)點(diǎn)插入 。 T = NULL。K)。K)。K)。 ? 刪除操作首先要在二叉排序樹中查找被刪除的結(jié)點(diǎn)是否存在 ， 若不存在 ， 則不做任何操作 ， 否則 ， 刪除該結(jié)點(diǎn) 。 free(p)；當(dāng)結(jié)點(diǎn) p為其雙親的右孩子結(jié)點(diǎn)時(shí) ， 應(yīng)實(shí)現(xiàn) frchild = NULL。 free(p)。 free(p). 二叉排序樹 (8) ? 若 p既有左子樹 ， 又有右子樹 ， 此時(shí)有兩種處理方法： 方法 1： 首先找到結(jié)點(diǎn) p在中序遍歷序列中的直接前驅(qū) s， 然后將 p的左子樹作為結(jié)點(diǎn) f的左子樹 ， 而將 p的右子樹作為結(jié)點(diǎn) s的右子樹 ， 即： flchild=plchild。 free(p)。 qrchild=slchild。 結(jié)果如圖 (b)所示 。 若查找不成功 ， 則是從根結(jié)點(diǎn)出發(fā)走了一條從根到某個(gè)葉子結(jié)點(diǎn)的路徑 。 ? 在二叉排序樹上進(jìn)行查找時(shí)的平均查找長度和二叉排序樹的形態(tài)有關(guān) 。 ? 若考慮把 n個(gè)結(jié)點(diǎn)按各種可能的次序插入到二叉排序樹中 ， 則有 n！棵二叉排序樹 (其中有的形態(tài)相同 )， 可以證明 ， 對(duì)這些二叉排序樹的查找長度進(jìn)行平均 ， 在隨機(jī)情況下得到的平均查找長度與 log2n是等數(shù)量級(jí)的 。 在最壞情況下 ， 二叉排序樹是通過把一個(gè)有序表的 n個(gè)結(jié)點(diǎn)依次插入生成的 ， 由此得到的二叉排序樹蛻化為一棵深度為 n的單支樹 ， 它的平均查找長度和單鏈表上的順序查找相同 ， 也是 (n+1)/2。 平衡二叉樹 ? 平衡二叉樹又稱為 AVL樹 ， 它是一棵 “ 平衡化 ” 的二叉排序樹 。 ? 引入平衡二叉排序樹的目的是為了克服二叉排序樹中左右子樹深度不平衡的狀態(tài) ， 從而提高查找效率 ， 保持其平均查找長度為log2n。 如圖 。 可將調(diào)整方法歸納為以下四種情況 : ? LL型 ? LR型 ? RR型 ? RL型 參見教材各相應(yīng)圖形及算法！ 平衡二叉樹 (3) 圖 二叉排序樹 LL型平衡旋轉(zhuǎn) 平衡二叉樹 (4) 圖 二叉排序樹 LR型平衡旋轉(zhuǎn) 平衡二叉樹 (5) 圖 二叉排序樹 RR型平衡旋轉(zhuǎn) 平衡二叉樹 (6) 圖 二叉排序樹 RL型平衡旋轉(zhuǎn) 平衡二叉樹 (7) 圖 RL型不平衡二叉樹的調(diào)整 平衡二叉樹 (8) ? 2. 平衡二叉排序樹的插入 ， 主要包括以下三步操作： (1) 查找應(yīng)插位置 ， 并記錄離插入位置最近的可能失衡結(jié)點(diǎn) (該點(diǎn)的平衡因子不等于 0)； (2) 插入新結(jié)點(diǎn) ， 并修改插入路徑上各結(jié)點(diǎn)的平衡因子； (3) 根據(jù)各結(jié)點(diǎn)的平衡因子 ， 判斷是否失衡以及失衡類型 ， 做相應(yīng)處理 。 調(diào)整方法為： ? ① 當(dāng)出現(xiàn) LL型和 LR型失衡類型時(shí) ， 采用左平衡 LeftBalance的算法 ， 其中 LL型失衡類型 ， 僅執(zhí)行一次右旋轉(zhuǎn) (R_Rotate)；而 LR型失衡類型需先執(zhí)行一次左旋轉(zhuǎn) (L_Rotate)， 再執(zhí)行一次右旋轉(zhuǎn)(R_Rotate)， 以達(dá)到平衡 。 平衡二叉樹 (9) ? 算法 void R_Rotate(BSTree amp。 plchild=lcrchild。p=lc。p) { /*對(duì)以 *p為根的二叉排序樹作左旋處理*/ rc=prchild。 rclchild=p。 } 平衡二叉樹 (11) 算法 void LeftBalance(AVLTree T) /* 對(duì) T所指的結(jié)點(diǎn)為根的二叉樹作左平衡處理 ， 調(diào)整完成時(shí) ， T指向新的根結(jié)點(diǎn) */ { lc = Tlchild。 R_Rotate(T)。 case RH: rd = lcrchild。 lcbf = EH。 case RH: Tbf =EH。 } rdbf = EH。 R_Rotate(T)。 ? 1. B－樹及其查找 ? 一棵 m階 B－樹 ， 或者是一棵空樹或者是滿足如下性質(zhì)的 m叉樹： ? 1. 失衡二叉樹的調(diào)整 ? 在平衡二叉樹的實(shí)際操作中 ， 為了既要保證其二叉排序樹的特性不變 ， 又要平衡 ， 則必須對(duì)失去平衡的二叉排序樹進(jìn)行調(diào)整 ， 使其仍為平衡二叉樹 。 ? 樹中每個(gè)結(jié)點(diǎn)至多有 m棵子樹 ， m－ 1個(gè)關(guān)鍵字 ， 其結(jié)構(gòu)如下： parent N P0 K1 P1 K2 P2 … Kn Pn B－樹 (2) ? 除根之外的所有非終端至少有 棵子樹； ? 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層上 ， 并且不帶信息 (可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn) ， 實(shí)際上這些結(jié)點(diǎn)不存在 ， 指向這些結(jié)點(diǎn)的指針為空 ， 引入這些結(jié)點(diǎn)的目的是為了便于分析 B— 樹的查找性能 )。 圖 出一個(gè) B－樹的插入實(shí)例 。 ? 已知一棵 3階 B－樹 ， 如圖 (a)所示 ， 要求插入 5 49。 (2) 插入 20： 直接插入后如圖 (c)所示 。 B－樹 (3) ? 一般情況下 ， 結(jié)點(diǎn)可實(shí)現(xiàn) “ 分裂 ” 如下 。兩個(gè)結(jié)點(diǎn) ， 其中結(jié)點(diǎn) *p為： ? ? ? ? ? ? )12/P,12/K(,),P,K(,P,12/ 110 ??? mmm ?其中結(jié)點(diǎn) *p39。一起插入到 *p的雙親結(jié)點(diǎn)中。一起插入到 *p的雙親結(jié)點(diǎn)中。 B－樹 (4) 3. 在 B－樹中刪除一個(gè)關(guān)鍵字 在 B樹中刪除一個(gè)關(guān)鍵字時(shí) ， 首先應(yīng)找到該關(guān)鍵字所在的結(jié)點(diǎn) ， 然后 ， 考慮該結(jié)點(diǎn)是否為樹中的最下層非終端結(jié)點(diǎn) ， 若是 ， 且其中的關(guān)鍵字?jǐn)?shù) 。 (2) 被刪除關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目等于 － 1， 而與該結(jié)點(diǎn)相鄰的有兄弟 (或左兄弟 )結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目大于 － 1， 為了保持 B－樹的各分支等長 (平衡 )， 且有序 ， 則需將其兄弟結(jié)點(diǎn)中的最小 (或最大 )的關(guān)鍵字上移至雙親結(jié)點(diǎn)中 ， 而將雙親結(jié)點(diǎn)中小于(或大于 )且緊靠該上移關(guān)鍵字的關(guān)鍵字下移至被刪除關(guān)鍵字所在結(jié)點(diǎn)中 。 ? 注意： 一般情況下 ， 刪除非最下層結(jié)點(diǎn)中的關(guān)健字 ， 可轉(zhuǎn)化為刪除最下層結(jié)點(diǎn)中的關(guān)鍵字 。 這種對(duì)應(yīng)關(guān)系 H被稱為散列函數(shù) ， 或哈希函數(shù) ， 利用這種方法建立的表稱為散列表或哈希表 。 ? 構(gòu)造散列表主要包括以下兩方面的內(nèi)容： 構(gòu)造散列表主要包括以下兩方面的內(nèi)容： ? 如何構(gòu)造哈希函數(shù)； ? 如何處理沖突 。 ? 1. 數(shù)字分析法： 如果事先知道關(guān)鍵字集合 ， 并且每個(gè)關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多時(shí) ， 可以從關(guān)鍵字中選出分布較均勻的若干位 ， 構(gòu)成散列地址 。 取值的位數(shù)由表長決定 。 具體方法有折疊法與移位法 。 ? 5. 偽隨機(jī)數(shù)法： 采用一個(gè)偽隨機(jī)函數(shù)作散列函數(shù) ， 即 H(key)= random(key)。 在構(gòu)造散列函數(shù)時(shí) ， 通常應(yīng)考慮以下五個(gè)因素：計(jì)算散列函數(shù)所需的時(shí)間 ， 關(guān)鍵字的長度 ， 散列表的大小 ， 關(guān)鍵字的分布情況 ， 查找記錄的頻率 。 可以有以下三種增量序列的取值方法：線性探測再散列 ， 二次探測再散列 ， 偽隨機(jī)探測再散列 。 這種方法不易產(chǎn)生聚集 ， 但增加了計(jì)算時(shí)間 。 ? ： 這種方法的基本思想是將散列表分為基本表和溢出表兩部分 ， 凡是與基本表發(fā)生沖突的元素一律填入溢出表 。 散列表的查找 ? 散列表的查找過程與散列表的構(gòu)造過程是一致的 。 如果存儲(chǔ)單元 p0為空 ， 則待查找記錄不存在；如果存儲(chǔ)單元 p0中記錄的關(guān)鍵字為key， 則找到待查找記錄；如果存儲(chǔ)單元 p0中元素的關(guān)鍵字不等于 key， 則重復(fù)執(zhí)行下列解決沖突的過程：按處理沖突的方法 ， 找出下一個(gè)散列地址 p1， 如果存儲(chǔ)單元 p1為空 ， 則所查找記錄不存在：如果存儲(chǔ)單元 p1中元素的關(guān)鍵字為 key， 則找到待查找記錄 ， 否則繼續(xù)查找 p2， …… 直至找到關(guān)鍵字為 key的記錄 ， 或直至找遍整個(gè)表 ， 沒有找到 ， 則待查找記錄不存在 。 define m /* 散列表的長度 */ typedef int KeyType。 … }RecordType。 散列表的查找 下面以線性探測再散列為例 ， 給出散列表的查找算法 (算法 )。 typedef struct { KeyType key。 typedef RecordType HashTable[m]。 if(HT[P0].key = = NULL) return(－ 1)； else { for(i =1。 i++) { pi=(p0 + i) MOD m。 else if(HT[pi] == key) return(pi)。 } } 散列技術(shù)性能分析 ? 評(píng)價(jià)查找性能的 “ 優(yōu)劣 ” 時(shí) ， 首先要考慮其產(chǎn)生沖突的頻率是多少 。 ? 散列表的裝填因子的定義如下： α 可描述散列表的裝滿程度。 散列技術(shù)性能分析 (2) 散列技術(shù)性能分析 (3) 參見教材：例 84 上 機(jī) 實(shí) 習(xí) ? 實(shí)習(xí) 1 ? 實(shí)習(xí) 2 ? 實(shí)習(xí) 3 實(shí)習(xí) 1 ? 二叉排序樹的建立 。 typedef struct node { int key。 /*其他數(shù)據(jù)項(xiàng) */ struct node *lchild,*rchild /*左 、 右孩子指針 */ }bstnode。 printf(%4d,tkey)。 printf(%4d,tkey)。 p=t。 if(skey==pkey) return t。 else p=prchild。 if(skeyfkey) flchild=s。 return t。 int key,data。 scanf(%d,amp。 while (key!=0) { s=(bstnode*)malloc(sizeof(bstnode))。 slchild=null。 scanf(%d,amp。 sother=data。 scanf(%d,amp。 } return t。 root=creatord()。 }/*main*/ 實(shí)習(xí) 2 ? 掌握散列表對(duì)矩陣的散列存儲(chǔ)方法 。 ? 提示： 根據(jù)題目給定的 100*100的稀疏矩陣中 ， 非零元素個(gè)數(shù)應(yīng)在 100*100*1%=100以內(nèi) ， 且每個(gè)元素均以一個(gè)三元組 (i,j,val)形式存儲(chǔ) 。 實(shí)習(xí) 2（ 2） define smax 12。 /*行號(hào)，列號(hào) */ char v。 /*散列表 HT*/ create(node[] HT) { int k,h,i,j。 for(h=0。h++) { HT[h].i=0。 HT[h].v=/。k12。i,amp。val)。 while(HT[h].v!=/) h=(h+1)%12。 HT[h].j=j。 } }/*create*/ main() { node []H。 char val。h12。 ? 題目：設(shè)計(jì)一個(gè)從上題得到的散列表 HT中檢索下標(biāo)為 i， j的非零元素的算法 。 h=(3*i+2*j)%127。amp。 /*利用線性探測法檢索下標(biāo)為 i,j的元素 ， 若 HT[h].i=i,且 HT[h].j=j, 則 HT[h].v 就是所求元素值 ， 否則為零元素 ， 即 HT[h].v=0*/ return(HT[h].v)。 習(xí) 題 ? 1 填空題 ?