【正文】 17187 30+1+1 1110000000120 0? 左改組（新插入結(jié)點出現(xiàn)在危機(jī)結(jié)點的左子樹上進(jìn)行的調(diào)整）的情況分析： LL 情況：（ LL： 表示新插入結(jié)點在危機(jī)結(jié)點的 左子樹 的 左子樹上 ）AB+1h10+2+1h h1h1 LL 改組BL BRARBA0h0h1h1BLBR AR危機(jī)結(jié)點改組前：高度為 h + 1 中序序列： ABBL BR AR改組后：高度為 h + 1 中序序列： ABBL BR AR注意：改組后 平衡度為 0AB? 左改組（新插入結(jié)點出現(xiàn)在危機(jī)結(jié)點的左子樹上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點在危機(jī)結(jié)點的 左子樹 的 右子樹上 ） 情況 A：AB+1h10+21h1 LR 改組BLAR危機(jī)結(jié)點改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 0,0,1CBCCL CR h2h2h10+1CB0h1 h1BL ARACR h2CLh110ABBL ARCCL CR改組后： 高度為 h + 1 中序序列：ABBL ARCCL CRA? 左改組（新插入結(jié)點出現(xiàn)在危機(jī)結(jié)點的左子樹上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點在危機(jī)結(jié)點的 左子樹 的 右子樹上 ） 情況 B：AB+1h10+21h1 LR 改組BLAR危機(jī)結(jié)點改組前： 高度為 h + 1 中序序列：注意：改組后 平衡度為 +1,0,0CBCCRCL h1h2h201CB0h1 h1BL ARACR h1CLh2+1 0ABBL ARC CRCL改組后： 高度為 h + 1 中序序列：AABBL ARC CRCL? 左改組（新插入結(jié)點出現(xiàn)在危機(jī)結(jié)點的左子樹上進(jìn)行的調(diào)整）的情況分析： LR 情況：（ LR： 表示新插入結(jié)點在危機(jī)結(jié)點的 左子樹 的 右子樹上 ） 情況 C：AB+10+21LR 改組危機(jī)結(jié)點改組前： 高度為 2 中序序列：注意：改組后 平衡度為 0,0,0CBC0AB CA新插入結(jié)點AB C改組后： 高度為 2 中序序列：CB0A0 0? 四種情況的區(qū)分： 如果 的平衡度為＋ 1 則為 LL型改組； 否則為 LR型改組：若 的平衡度為＋ － 1 、 0 ；則分別為 LRA、 LRB、 LRC型改組。但硬盤的驅(qū)動受機(jī)械運動的制約，速度慢。 內(nèi)存: 用二叉樹組織文件，當(dāng)文件的記錄個數(shù)為 100， 000時，要找到給定關(guān)鍵字的記錄，需訪問外存17次（ log100,000） ,太長了！5025107515 35 60 9020 30 40 55 70 80 95索引文件數(shù)據(jù)文件文件頭，可常駐內(nèi)存文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上 B_ 樹是一種多分支數(shù)，首先介紹 m 階 B_ 樹：? 定義： m 階 B_ 樹滿足或空，或：A、 根結(jié)點要么是葉子，要么至少有兩個兒子B、 除根結(jié)點和葉子結(jié)點之外，每個結(jié)點的兒子個數(shù)為 : m/2 = s = mC、 有 s 個兒子的非葉結(jié)點具有 n = s － 1 個關(guān)鍵字，即 : s = n + 1 這些結(jié)點的數(shù)據(jù)信息為： （ n, A0, K1, R1, A1, K2, R2, A2, ……… Kn, Rn, An） 這里： n: 關(guān)鍵字的個數(shù) A0： K1 的結(jié)點的地址（指在該 B_ 樹中） K1： 關(guān)鍵字 R1： 關(guān)鍵字 = K1 的數(shù)據(jù)記錄在硬盤中的地址 A2： K1 且 K2 的結(jié)點的地址（指在該 B_ 樹中） 余類推 ……… An： Kn 的結(jié)點的地址（指在該 B_ 樹中） 注意： K1 =K2 = …... = KnD、 所有的葉子結(jié)點都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點或失敗結(jié)點）。葉子結(jié)點都在第 4 層上。 若 Ki KEY Ki+1。注意：每次查找將去掉 （ s1） /s 個分支，比二分查找快得多。 B_ 樹的插入操作確定插入位置，將結(jié)點插入到第 L 層（注意：第 L+1 層為葉子結(jié)點）找到插入位置，將關(guān)鍵字和其它信息按 序 插入。如結(jié)點原為： （ m1, A0, (K1, A1), (K2, A2), ……… (K m1, Am1)）插入一個關(guān)鍵字之后變?yōu)椋? （ m, A0, (K1, A1), (K2, A2), ……… (K m, Am)）該結(jié)點將進(jìn)行分裂： …………... (K m/2 , p‘ ) …………...（ m/21, A0, (K1, A1), ……… (K m/2 , A m/2 )） （ m m/2 , A m/2 , ……… (K m, Am)） 生成新結(jié)點 p‘, 將原結(jié)點的后半部分復(fù)制過去。 至少 1 個關(guān)鍵字，二個兒子結(jié)點。然后，刪除第 L 層上的該關(guān)鍵字。 B、 借：若刪除關(guān)鍵字值的那個結(jié)點的關(guān)鍵字的個數(shù)原為 m/2 1 。 C、 并：若該結(jié)點的左或右鄰居結(jié)點的關(guān)鍵字的個數(shù)為 m/2 1 。 m=3, m/2 1 = 1。 哈希表– 基本思想： 在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法– 定義? 哈希函數(shù) —— 在記錄的 關(guān)鍵字 與記錄的 存儲地址 之間建立的一種對應(yīng)關(guān)系叫 ~–哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象–哈希函數(shù)可寫成： addr(ai)=H(ki)187。key+b–特點?直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突?實際中能用這種哈希函數(shù)的情況很少? 數(shù)字分析法–構(gòu)造：對關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或若干位組合作哈希地址–適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況例 有 80個記錄，關(guān)鍵字為 8位十進(jìn)制數(shù)，哈希地址為 2位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5…..…..?? ? ??? ??分析： ?只取 8 ?只取 1 ?只取 4 ?只取 5 ????數(shù)字分布近乎隨機(jī)所以：取 ????任意兩位或兩位 與另兩位的疊加作哈希地址? 平方取中法–構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址–適于不知道全部關(guān)鍵字情況? 折疊法– 構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址– 種類? 移位疊加：將分割后的幾部分低位對齊相加? 間界疊加：從一端沿分割界來回折送，然后對齊相加– 適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況例 關(guān)鍵字為 ： 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 9 2H(key)=6092間界疊加? 除留余數(shù)法– 構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長 m的數(shù) p除后所得余數(shù)作哈希地址，即 H(key)=key MOD p， p?m– 特點? 簡單、常用，可與上述幾種方法結(jié)合使用? p的選取很重要； p選的不好，容易產(chǎn)生同義詞? 隨機(jī)數(shù)法– 構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key)– 適于關(guān)鍵字長度不等的情況? 選取哈希函數(shù)，考慮以下因素：– 計算哈希函數(shù)所需時間– 關(guān)鍵字長度– 哈希表長度（哈希地址范圍）– 關(guān)鍵字分布情況– 記錄的查找頻率 處理沖突的方法? 開放定址法– 方法：當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k ?m1)其中： H(key)—— 哈希函數(shù) m—— 哈希表表長 di—— 增量序列? di—— 增量序列 (有三種取法 )–線性探測再散列： di=1,2,3,……m1–二次探測再散列： di=1178。,3178。) MOD 11=6 沖突 H2=(5 1178。? while((jM)amp。(t[(i+j}%M]!=0))? j++。? }int slbxxcr(int t[],int k){ int i,j=0。(t[(i+j)%M]!=k)amp。 i=(i+j)%M。}int slbxxsc(int t[],int k){ int i,j=0。(t[(i+j)%M]!=k)amp。 if(t[i]==k) { t[i]=1。這函數(shù)稱為 “哈希函數(shù) ”，能用散列技術(shù)進(jìn)行查找的表稱為散列表（ 哈希表）。 直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突187。 簡單、常用，可與上述幾種方法結(jié)合使用187。 else if (BSTdatax) //進(jìn)入左子樹查找 return find ( BSTleft,x)。平衡二叉樹查找若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕對值不超過 1，則稱這樣的二叉樹為平衡二叉樹。處理的原則應(yīng)該是處理與扦入點最近的、而平衡因子又比 1大或比 1小的結(jié)點。這是的平衡處理為：將 B變到 A與 C 之間，使之成為LL型，然后按第 (1)種情形 LL型處理。這時的平衡處理為：將 B變到 A與 C之間，使之成為 RR型，然后按第 (3) 種情形 RR型處理。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復(fù)雜度 O(n)， 它的時間復(fù)雜度與二叉排序樹的最好時間復(fù)雜相同，都為 O(log2n)。 從圖 815的二叉排序樹可知，查找 6需 4次，平均查找長度 ASL=(1+2+2+3+3+3+4)/7=18/7≈。熟練掌握二叉排序樹和平衡二叉排序樹的構(gòu)造方法和查找