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