【正文】 * RR(AVLBinNode *p) { /*對(duì)以 p指向的結(jié)點(diǎn)為根的子樹(shù)，作 RR型調(diào)整，調(diào)整之后，返回子樹(shù)的新根 */ AVLBinNode *pr。 pr=prchild。 /*lp指向 *p右子樹(shù)根結(jié)點(diǎn) */ prchild=prlchild。 /*lp的左子樹(shù)掛接 *p的右子樹(shù) */ prlchild=p。 /* *p指向新的根結(jié)點(diǎn) */ pbf=0。 prbf=0。 return pr。 } 第 8章 查找 AVLBinNode *LR(AVLBinNode * p) { /*對(duì)以 p指向的結(jié)點(diǎn)為根的子樹(shù)，作 LR型調(diào)整，調(diào)整之后，返回子樹(shù)的新根 */ AVLBinNode *pl,*plr。 pl=plchild。plr=plrchild。 plrchild=plrlchild。 plchild=plrrchild。 plrlchild=pl。 plrrchild=p。 plbf=1。pbf=0。plrbf=0。 return plr。 ? } 第 8章 查找 ? AVLBinNode * RL (AVLBinNode * p) { /*對(duì)以 p指向的結(jié)點(diǎn)為根的子樹(shù)，作 RL型調(diào)整，調(diào)整之后，返回子樹(shù)的新根 */ AVLBinNode *pr,*prl。 pr=prchild。prl=prlchild。 prlchild=plrrchild。 prchild=plrlchild。 plrlchild=p。 plrrchild=pr。 prbf=1。pbf=0。plrbf=0。 return prl。 ? } 第 8章 查找 ? AVLBinTree InsertAVL(AVLBinTree bt, KeyType kx) { /*對(duì)以 bt根的平衡二叉樹(shù)插入關(guān)鍵碼值為 kx的結(jié)點(diǎn)，并調(diào)整，調(diào)整之后，返回樹(shù)的根結(jié)點(diǎn) */ s=((AVLBinNode *)malloc(AVLBinNode)。 s=kx。 slchild=NULL。s rchild=NULL。 sbf=0。 if(bt==NULL) { bt=s。return bt。} p=bt。 a=bt。 af=NULL。 pf=NULL。 /* *pf結(jié)點(diǎn)為 *p結(jié)點(diǎn)的雙親， *af結(jié)點(diǎn)為 *a結(jié)點(diǎn)的雙親 */ while(p) {if(pbf!=0) {a=p。af=pf； }/*a記錄平衡因子非 0的結(jié)點(diǎn)，其終值指向離插入位置最近的結(jié)點(diǎn) */ pf=p。 if(kxp) p=plchild。 else p=prchild。 } 第 8章 查找 if(kxpf) pflchld=s。 else pfrchild=s。 if(kxa) {p=alchild。b=p。d=1。} else {p=archild。b=p。d=1。} while(p!=s) /*修改 *a的孩子至 *s路徑上各結(jié)點(diǎn)的平衡因子 */ if(kxp) {pbf=1。p=plchild。} else {pbf=1。 p=prchild。} 第 8章 查找 switch(abf) { case 0:{ abf=d。break。} case 1:{if(d==1) abf=0。 else if(bbf==1) if(aflchild==a) aflchild=LR(bt,a)。 else afrchild=LR(bt,a)。 else if(aflchild==a) aflchild=LL(bt,a)。 else afrchild=LL(bt,a)。 break。 } 第 8章 查找 case 1: { if(d==1) abf=0。 else if(bbf==1) if(aflchild==a) aflchild=RR(bt,a)。 else afrchild=RR(bt,a)。 else if(aflchild==a) aflchild=RL(bt,a)。 else afrchild=RL(bt,a)。 break。 } } return bt。 ? } 第 8章 查找 B樹(shù)和 B+樹(shù) ? B樹(shù)又稱 平衡多路查找樹(shù) ，或 外部查找樹(shù)， 是一種組織和維護(hù) 外存文件系統(tǒng) 的非常有效的數(shù)據(jù)結(jié)構(gòu)，它以高效、易變、平衡和對(duì)硬件相對(duì)獨(dú)立等特點(diǎn)而成為數(shù)據(jù)庫(kù)系統(tǒng)中索引的標(biāo)準(zhǔn)組織形式 。 第 8章 查找 B樹(shù)的定義 一棵 m階的 B樹(shù) ，或者為空樹(shù)，或?yàn)闈M足下列特性的 m叉樹(shù) ： ⑴樹(shù)中每個(gè)結(jié)點(diǎn) 至多有 m棵子樹(shù) ，從查找效率考慮，一般m=3； ⑵若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少 有兩棵子樹(shù) ； ⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有 ?m/2? 棵子樹(shù) ； 第 8章 查找 ⑷所有的非終端結(jié)點(diǎn)中包含以下信息數(shù)據(jù)即每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為： （ n， A0， K1， A1， K2， … ， Kn， An） 其中： Ki（ i=1,2,…,n ）為關(guān)鍵碼 ，且 KiKi+1， Ai為指向子樹(shù)根結(jié)點(diǎn)的指針 (i=0,1,…,n) ，且指針 Ai1所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均小于 Ki (i=1,2,…,n)， An所指子樹(shù)中所有結(jié)點(diǎn)的關(guān)鍵碼均大于 Kn， ?m/2? ?1≤n≤m ?1 ， n為關(guān)鍵碼的個(gè)數(shù) 。 ⑸ 所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上 ，并且 不帶信息（ 可以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。 第 8章 查找 1 62 1 ∧ 8 ∧ 1 80 2 15 38 1 ∧ 54 ∧ 3 ∧ 20 ∧ 25 ∧ 32 ∧ 2 ∧ 65 ∧ 73 ∧ 2 ∧ 87 ∧ 96 ∧ mt 一棵由 13個(gè)關(guān)鍵字組成的四階的 B樹(shù) 每個(gè) 結(jié)點(diǎn)關(guān)鍵字 最少 = ?m/2? 1=21=1； 最多 =m1=3，每個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目最少為 ?m/2? =2， 最多為 m=4。 不管每個(gè)結(jié)點(diǎn)實(shí)際使用了多少個(gè)關(guān)鍵字域和指針域，它都包含 4個(gè)關(guān)鍵字域、 4個(gè)指向記錄存儲(chǔ)位置的指針域、 5個(gè)指向孩子結(jié)點(diǎn)的指針域、一個(gè)指向父親結(jié)點(diǎn)的指針域和一個(gè)保存關(guān)鍵字個(gè)數(shù)的 n域。 F 第 8章 查找 ? B樹(shù)的查找類(lèi)似二叉排序樹(shù)的查找，所不同的是 B樹(shù)每個(gè)結(jié)點(diǎn)上是 多關(guān)鍵碼的有序表 ，在到達(dá)某個(gè)結(jié)點(diǎn)時(shí)，先在有序表中查找，若找到，則查找成功；否則，沿指針信息指向的子樹(shù)中去查找，如果到達(dá)葉子結(jié)點(diǎn)，那么說(shuō)明樹(shù)中沒(méi)有對(duì)應(yīng)的關(guān)鍵碼，查找失敗。 第 8章 查找 ? 1）插入 在 B樹(shù)上插入關(guān)鍵碼與在二叉排序樹(shù)上 插入結(jié)點(diǎn)不同 ，關(guān)鍵碼的插入不是在葉子結(jié)點(diǎn)上進(jìn)行的，而是在 最底層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵碼，若該結(jié)點(diǎn)上關(guān)鍵碼個(gè)數(shù)不超過(guò) m1個(gè)，則可直接插入到該結(jié)點(diǎn)上；否則，該結(jié)點(diǎn)上關(guān)鍵碼個(gè)數(shù)達(dá)到 m個(gè)，使該結(jié)點(diǎn)的子樹(shù)超過(guò)了 m棵，這與 B樹(shù)定義不符，要進(jìn)行調(diào)整，稱之 為結(jié)點(diǎn)的“分裂”。 分裂的方法為： 第 8章 查找 ⑴關(guān)鍵碼加入結(jié)點(diǎn)后，將結(jié)點(diǎn)中的所有關(guān)鍵碼分成三部分，使得前后兩部分關(guān)鍵碼個(gè)數(shù)均大于等于（ ?m/2?1），而中間部分只有一個(gè)結(jié)點(diǎn)。前后兩部分分別成為兩個(gè)結(jié)點(diǎn)，中間的一個(gè)結(jié)點(diǎn)將其插入到其父結(jié)點(diǎn)中； ⑵若插入父結(jié)點(diǎn)而使父結(jié)點(diǎn)中關(guān)鍵碼個(gè)數(shù)超過(guò) m1，則父結(jié)點(diǎn)繼續(xù)分裂，直到插入某個(gè)父結(jié)點(diǎn)，其關(guān)鍵碼個(gè)數(shù)小于 m。 第 8章 查找 ? 2） 刪除 設(shè)某 m階 B樹(shù)的深度為 k+1，則在該 B樹(shù)的刪除分以下幾種情況： (1)刪除第 k層結(jié)點(diǎn)中的關(guān)鍵碼，并且該結(jié)點(diǎn)中原關(guān)鍵碼個(gè)數(shù)大于 ?m/2?1，則直接刪去該結(jié)點(diǎn)。 (2)刪除第 k層結(jié)點(diǎn)中的關(guān)鍵碼，并且該結(jié)點(diǎn)中原關(guān)鍵碼個(gè)數(shù)等于 ?m/2?1，此時(shí)考慮兩種情況： 第 8章 查找 其左兄弟（或右兄弟）結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)大于 (?m/2? 1)，則把左兄弟結(jié)點(diǎn)中最大（或右兄弟中最小）的關(guān)鍵碼上移到其父結(jié)點(diǎn)中，同時(shí)把其父結(jié)點(diǎn)中大于（或小于）上移關(guān)鍵碼的關(guān)鍵碼下移替換被刪的結(jié)點(diǎn)。 其左兄弟（或右兄弟）結(jié)點(diǎn)關(guān)鍵碼個(gè)數(shù)均等于 (?m/2? 1)，此時(shí)該結(jié)點(diǎn)剩余項(xiàng)與左兄弟（或右兄弟）進(jìn)行合并。由于合并后其父結(jié)點(diǎn)的相關(guān)項(xiàng)不能保持，因此把其父結(jié)點(diǎn)的相關(guān)項(xiàng)也并入合并項(xiàng)。若此時(shí)其父結(jié)點(diǎn)被破壞，則繼續(xù)調(diào)整，直到根結(jié)點(diǎn)。 第 8章 查找 ? (3)刪除第 1~k1層中的關(guān)鍵碼，假設(shè)被刪關(guān)鍵碼為所在結(jié)點(diǎn)的第 i個(gè)關(guān)鍵碼 Ki，那么可以將指針 Ai所指子樹(shù)中的最小關(guān)鍵碼 X替代 Ki，然后，再刪除關(guān)鍵碼 X，直到這個(gè) X在最 k層結(jié)點(diǎn)上，即轉(zhuǎn)為 (1)的情形。 第 8章 查找 +樹(shù) B+樹(shù)是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種 B樹(shù)的變形樹(shù)。一棵 m階的 B+樹(shù)和 m階的 B樹(shù)的差異在于： ⑴有 n棵子樹(shù)的 結(jié)點(diǎn)中含有 n個(gè)關(guān)鍵碼 ； ⑵ 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵碼的信息 ，及指向含有這些關(guān)鍵碼記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵碼的大小自小而大的順序鏈接。 ⑶ 所有的非終端結(jié)點(diǎn)可以看成是索引部分 ，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵碼。 第 8章 查找 ? 在 B+樹(shù)上進(jìn)行隨機(jī)查找、插入和刪除的過(guò)程基本上與 B樹(shù)類(lèi)似。只是在查找時(shí)，若非終端結(jié)點(diǎn)上的關(guān)鍵碼等于給定值，并不終止，而是繼續(xù)向下直到葉子結(jié)點(diǎn)。因此，在 B+樹(shù)，不管查找成功與否，每次查找都是走了一條從根到葉子結(jié)點(diǎn)的路徑。 B+樹(shù)的插入僅在葉子結(jié)點(diǎn)上進(jìn)行，當(dāng)結(jié)點(diǎn)中的關(guān)鍵碼個(gè)數(shù)大于 m時(shí)要分裂成兩個(gè)結(jié)點(diǎn)，他們所含關(guān)鍵碼的個(gè)數(shù)均為 ?m/2?。 第 8章 查找 ? 并且，他們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)中的最大關(guān)鍵碼。 B+樹(shù)的刪除也僅在葉子結(jié)點(diǎn)進(jìn)行，當(dāng)葉子結(jié)點(diǎn)中的最大關(guān)鍵碼被刪除時(shí)，其在非終端結(jié)點(diǎn)中的值可以作為一個(gè)“分界關(guān)鍵碼”存在。若因刪除而使結(jié)點(diǎn)中關(guān)鍵碼的個(gè)數(shù)少于 ?m/2?時(shí)，其和兄弟結(jié)點(diǎn)的合并過(guò)程亦和 B樹(shù)類(lèi)似。