數(shù)據(jù)結(jié)構(gòu)與算法作業(yè)題

1、第十章習(xí)題作業(yè)講解10.9關(guān)于23樹的創(chuàng)建與的應(yīng)用；10.11 關(guān)于BTree操作的應(yīng)用；+10.12 關(guān)于B Tree操作的應(yīng)用；+10.13關(guān)于B Tree刪除操作的應(yīng)用。10.9關(guān)于23樹的創(chuàng)建與的應(yīng)用題目：給定的一組字母： C, S, D, T, A, M, P, I, B, W, N,G, U, R, K, E, H, O,L, J，按照所給字母的順序創(chuàng)建23樹。求解：舉例：當(dāng)C、S、D時節(jié)點如下，此時不滿足23樹定義，需要分解；需要分解SCDC D ST、A、M后：需要分解TMA CD SM S TA CD最后：10.11 關(guān)于BTree操作的應(yīng)用題目：畫出在圖10.17 BTre

2、e中后的BTree圖。值55定義：一棵m階B-樹或者是一棵空樹,或者是滿足下列要求的m叉樹：(1) 樹中每個結(jié)點至多有m個孩子結(jié)點(即至多有m-1個關(guān)鍵字)；(2) 除根結(jié)點外,其他結(jié)點至少有m/2個孩子結(jié)點(即至少有m/2-1=(m-1)/2個關(guān)鍵字)；(3) 若根結(jié)點不是葉子結(jié)點,則根結(jié)點至少有結(jié)點；求解：當(dāng)值55后，圖最右邊的葉子的節(jié)點變?yōu)橄聢D，需要進(jìn)行分解，以下標(biāo)為m/2 （m為樹的階數(shù))的數(shù)值作為中心進(jìn)行分解，值55上移。不滿足條件須分解分解圖一圖二55334560505233454855244850525560最終：10.12 關(guān)于B+Tree操作的應(yīng)用題目：作出在圖10.18 B

3、+Tree圖。1，2，3，4，5，6之后的定義： B+Tree(1) 每個分支結(jié)點至多有m棵。(2) 除根結(jié)點外,其他每個分支結(jié)點至少有m/2 棵。(3) 根結(jié)點至少有兩棵,至多有m棵。(4)的指針,而所有葉子結(jié)點包含全部關(guān)鍵字及指向相應(yīng)且葉子結(jié)點按關(guān)鍵字大小順序。(5) 所有分支結(jié)點中僅包含它的各個子結(jié)點中最大關(guān)鍵字及指向子結(jié)點的指針。求解：當(dāng)值1、2、3后，圖最左邊的葉子的結(jié)點變?yōu)橄聢D，需要進(jìn)行分解，數(shù)值10上移。123101210 1823值4、5、6后，須分解為圖1 ，數(shù)值4上移，須分當(dāng)解分解為圖2；圖一圖二234101833456123123456410最終：10.13關(guān)于B+Tree刪除操作的應(yīng)用題目：畫出從10.24b圖中刪除值18、19和20之后的B+Tree圖。圖24求解：刪除18、19和20之后所在的結(jié)點為只能和它的兄弟結(jié)點合并合并為合并之后少了一個結(jié)點，也不能從兄弟結(jié)點借，這樣樹只能減少一層。：10 121521