【正文】 Y和 Z。 delete Y。 delete Z。 當(dāng) n = 0， E = I = 0，引理 。由此可得： Sn = 1 + nUUU n 110 . . . ????JYP 80 同時， Sn = ， Un = ， E = I + 2n，所以， Sn = = 即 Sn = Un – 1 () 1?nI 1?nE)1( 1n?12)1( ??? n nUn n12 ??n nEJYP 81 又由 Sn = 和 Sn = 1 + 可得 I = U0 + U1 + …+ U n1 再由 Un = = 可得 1?nInUUU n 110 . . . ????1?nE12??nnIJYP 82 (n + 1)Un = 2n + U0 + U1 + …+ U n1 為解此遞歸式，用 n – 1替換 n： n Un1 = 2(n – 1) + U0 + U1 + …+ U n2 兩式相減，得： Un = Un1 + 12?nJYP 83 由于 U0 = 0，所以， Un = 2 = 2 Hn+1 – 2 其中， Hn+1是第 n + 1個 調(diào)和數(shù) ，即 Hn+1 = 根據(jù)調(diào)和數(shù)理論， Hn ? ln n + ， Un ? 2ln n。 JYP 92 當(dāng) p1 = ， p2 = ， p3 = ， q0 = ， q1 = ， q2 = ，和 q3 = ，有 樹（ a）的代價 = 樹（ b）的代價 = 樹（ c）的代價 = 樹（ d）的代價 = 樹（ e）的代價 = 樹（ e）是最佳的。 初始時， wii = qi， cii = 0， 0≤i≤3。算法 obst實(shí)現(xiàn)了上述方法 ， 并根據(jù)計算結(jié)果調(diào)用函數(shù) build構(gòu)造最佳二叉查找樹 。 i++) { int j = i + m。 p?LeftChild = build(a, i, k1)。 （ 7） 葉結(jié)點(diǎn)中存放的關(guān)鍵字個數(shù)可以大于或小于m。 圖 ，其中，中間結(jié)點(diǎn)的粗體字表示新插入的“路標(biāo)”，葉結(jié)點(diǎn)的粗體字表示新插入的關(guān)鍵字。 假設(shè)文件 F是記錄 R的集合。 將關(guān)鍵字 A0, B0, C2, A1, B1和 C3加入表中后的結(jié)果如下圖（ a）所示： JYP 131 再將 C5加入表中。 因此，散列函數(shù) hash(key, i) 根據(jù)關(guān)鍵字 key生成一個與 i個二進(jìn)制位對應(yīng)的隨機(jī)數(shù)。 template class Type DirEntry rdirectory[MaxDir]。 // 從 // 頁面 p中刪除關(guān)鍵字為 key的記錄，并執(zhí)行 p?NumRecords。 JYP 143 Boolean StillFull = FALSE。 r, const pageType* p)。 // 本頁面的記錄個數(shù) }。 如果關(guān)鍵字在頁面中的分布不均勻，目錄增長可能過大，而大多數(shù)目錄項都指向同一頁面。 右圖是一些關(guān)鍵字及其二進(jìn)制表示。 圖 — 1 JYP 124 圖 — 2 JYP 125 實(shí)驗(yàn)作業(yè) ： 設(shè)計一個磁盤資源管理系統(tǒng) ， 實(shí)現(xiàn) B+樹的查詢 、插入和刪除操作 ， 并生成測試數(shù)據(jù)集 ， 驗(yàn)證這些操作的正確性 。 如果結(jié)點(diǎn) p不滿，則加入新元素，并將修改后的結(jié)點(diǎn) p寫到磁盤即可。 （ 3） Ai中的所有關(guān)鍵字都 大于等于 Ki并小于 Ki+1，0 i n。 } // obst結(jié)束 JYP 107 template class Type BstNodeType* BSTType::build(ElementType*a, int i, int j) { // 根據(jù) rij構(gòu)造最佳二叉查找樹 if (i == j) return 0。 JYP 106 for (int m = 2。計算所有 cij的總時間為 O(nm – m2)。 Tij有左 、 右兩棵子樹 ， 如下圖所示： JYP 96 L是左子樹 ， 包含標(biāo)識符 ai+1, … , ak1； R是右子樹 ，包含標(biāo)識符 ak+1, … , aj。 對于 Ei中的所有標(biāo)識符 ， 查找都會在同一個失敗結(jié)點(diǎn)結(jié)束 ， 且對于不同類中的標(biāo)識符 ， 查找會在不同的失敗結(jié)點(diǎn)結(jié)束 。在與根結(jié)點(diǎn)的距離為 1處最多可有 2個結(jié)點(diǎn)，距離為 2處最多可有 4個結(jié)點(diǎn)，一般地，最小的 I是 0 + 2 ? 1 + 4 ? 2 + 8 ? 3 + … + 完全二叉樹就是一種具有最小內(nèi)部路徑長度的樹。 二叉樹的 外部路徑長度 E定義為所有外部結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度之和。 } R?RightChild = L?LeftChild = 0。 L?LeftChild = t?RightChild。 若 i t?， 則結(jié)點(diǎn) t及其右子樹應(yīng)加入 C中 。最后將 A和 B設(shè)置為空。 } } JYP 53 例 一個根據(jù)映射表 t對記錄順序化的例子： JYP 54 對 table的分析： 設(shè)每個記錄占用 m個存儲單元，則所需輔助空間為 O(m)個存儲單元。含記錄 i的環(huán)路由 i, t[i], t2[i], …, t k[i]構(gòu)成，且 tk[i] = i。 list[i].link = first。 如果能夠修改 Rx的link字段 ， 使其指向原位于 R0的記錄的新位置 first，則剩余記錄 R1, … , Rn1也是按關(guān)鍵字非遞減次序鏈接的 。 即使采用鄰接表，第 10到 12行的總時間可減少到O(e)（因?yàn)橹挥朽徑幼?u的頂點(diǎn)的 dist可能變化），第 8行的總時間仍然是 O(n2)。 else path[i] = – 1。 這對應(yīng)于 上的關(guān)鍵字減少操作 。 if (不存在這樣的邊 ) break。 cout x , y endl。 i++ ) { dfn[i] = low[i] = 0。 // min2(x,y)返回 x和 y的 // 較小者 } else if (w != v) low[u] = min2 ( low[u], dfn[w] )。 JYP 12 假設(shè)頂點(diǎn) w的祖先包括 w本身。 定義： 一個連通圖 G的 雙連分量 是 G的最大雙連通子圖。 JYP 6 圖 G6包含四個雙連分量，如下所示： JYP 7 不難發(fā)現(xiàn)，同一個圖的兩個雙連分量最多有一個共同頂點(diǎn)。 為了表示一個頂點(diǎn)經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先，對于圖 G的每個頂點(diǎn) w，定義low(w) 為從 w經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先的 dfn。 // 回邊。 } Biconnected (0, 1)。 } while ( (x, y)與 (u, w)不相同 )。 將 v加入 TV。 TVTV ]}[{m in xd is tTVx ?TVTVTVJYP 32 關(guān)鍵字減少操作的總次數(shù)最多是圖中邊的條數(shù) 。 5 } 6 s[v] = TRUE。 JYP 36 S 應(yīng)用斐波納契堆 和鄰接表，可使算法的時間復(fù)雜性減少為 O(n log n + e)。 JYP 39 但在單鏈表中 ， 我們無法快速確定結(jié)點(diǎn) R0的前驅(qū)Rx。 } first = q。 例如，上一頁的置換由兩個環(huán)路組成，第一個包含記錄 R0和 R4，第二個包含記錄 R1， R3和 R2。 for循環(huán)執(zhí)行了 n–1次。 JYP 59 （ 3） (i, B, x, C)： 分裂為三部分： B包含 A中所有關(guān)鍵字小于 i的元素；如果 A含關(guān)鍵字為 i的元素，則將該元素復(fù)制到x，并返回 x的指針，否則返回 0； C包含 A中所有關(guān)鍵字大于 i的元素。 若 i t?， 則結(jié)點(diǎn) t及其左子樹應(yīng)加入 B中 。 x = t?data。 // 注意這是必要的 = Y?RightChild。 內(nèi)部路徑長度 I是所有內(nèi)部結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度之和。采用完全二叉樹的結(jié)點(diǎn)編號，結(jié)點(diǎn) i到根結(jié)點(diǎn)的距離是 ?log2i?。 將失敗結(jié)點(diǎn)從 0到 n編號 ， 編號 i的失敗結(jié)點(diǎn)對應(yīng) Ei，0≤i≤n。 根據(jù) ()， Tij的代價 cij = pk+L的代價 +R的代價 +L的權(quán)重 +R的權(quán)重 其中， L的權(quán)重 = wi,k1， R的權(quán)重 = wkj。 JYP 103 計算全部 cij和 rij的總時間是 = O(n3) Knuth的研究成果表明， ()式中的最佳 u的選擇可限定在 ri,j1≤u≤ri+1,j的范圍。 m = n。 // 空樹 BstNodeType*p = new BstNodeType。 JYP 110 （ 4） An中的所有關(guān)鍵字都大于等于 Kn， A0中的所有關(guān)鍵字都小于 K1。 如果結(jié)點(diǎn) p已滿，則將其分裂為 p和 q兩個結(jié)點(diǎn)，這兩個結(jié)點(diǎn)平均承載原來結(jié)點(diǎn) p中的內(nèi)容和新元素，且結(jié)點(diǎn) q中元素的關(guān)鍵字大于結(jié)點(diǎn) p中的。 JYP 126 動態(tài)散列 （ ） 靜態(tài)散列必須靜態(tài)分配散列表空間。 JYP 130 假設(shè)初始時目錄有 4項。 為防止這種情況，不宜直接使用關(guān)鍵字的二進(jìn)制位序列，而應(yīng)通過均勻散列函數(shù)將這些二進(jìn)制位轉(zhuǎn)換為隨機(jī)序列。 JYP 139 template class Type struct DirEntry { // 目錄項結(jié)構(gòu) int LocalDepth。 // 將新記錄 r //插入頁面 p，并執(zhí)行 p?NumRecords++。 p = rdirectory[in。 key, const pageType* p)。 // 注意這是用指針模擬頁面地址 }。 以下是一種解決方案： hashi: key ? {0, …, 2 i – 1}， 1≤i≤d 其中， hashi的結(jié)果只是簡單地在 hashi1的結(jié)果前端加上二進(jìn)制位 0或 1。需用關(guān)鍵字的 2個最低位來確定目錄項。 動態(tài)散列 又稱為 可擴(kuò)展散列 ，其目的就是要既保持靜態(tài)散列的快速查找性能，又具備動態(tài)適應(yīng)數(shù)據(jù)文件大小變化的能力。 JYP 114 這又可能使雙親結(jié)點(diǎn)分裂，直至使根結(jié)點(diǎn)分裂，整個 B+樹長高一層。 （ 6） 所有葉結(jié)點(diǎn)都處于同一個層次，包含了全部關(guān)鍵字以及相應(yīng)的元素或元素地址，葉結(jié)點(diǎn)中的關(guān)鍵字從小到大排序，且互不相同。 p?data = a[k]。 i = n m。計算全部 cij和 rij的總時間改進(jìn)為 n – m + 1 + = O(n2) 假設(shè)二維數(shù)組 w、 c和 r是類 BST的私有數(shù)據(jù)成員 。 }{m i n 1, ujuiijjuiccw ?? ???}{m i n 1, ujuijuicc ????JYP 98 例 設(shè) n = 3， (a1, a2, a3) = (data, pipe, work)，(p1, p2, p3) = (, , )， (q0, q1, q2, q3) = (, , , )。 )1)((0?????il e v e lqnii 失敗結(jié)點(diǎn))1)(()(01???? ??????il e v e lqal e v e lpniiinii 失敗結(jié)點(diǎn)JYP 89 例 圖 a1, a2, a3 = (data, pipe, work)的所有可能的二叉查找樹： JYP 90 JYP 91 當(dāng) pi = qj = 1/7時， 1≤i≤3， 0≤j≤3，有 樹（ a）的代價 = 15/7 樹（ b）的代價 = 13/7