【正文】 p = rdirectory[in。 // key已存在 int index = hash(key, gdepth)。 key) { // 將新 // 記錄 r插入整個表中 pageType* p = find(key)。 } template class Type void insert(const recordTypeamp。 if (PageSearch(key, p) return p。找到返回該記錄所在頁面的地址， //否則返回 0 int index = hash(key, gdepth)。 JYP 142 template class Type pageType* find(const Typeamp。 key, const pageType* p)。 // 將新記錄 r //插入頁面 p，并執(zhí)行 p?NumRecords++。找到返回 TRUE，否則返回 // FALSE template class Type void enter(const recordamp。 key, const pageType* p)。 // 返回頁面 p中記錄個數(shù) template class Type void coalesce(const pageType* p, const pageType* buddy)。 // 用均勻散列將 key //轉換為二進制位序列，返回與 i個最低位對應 // 的整數(shù)，并作為目錄項下標 int buddy(const int index)。 // 局部深度達到全局深度的頁面數(shù) JYP 140 template class Type int hash(const Typeamp。 // 目錄，假設 MaxDir是已 // 定義的常數(shù) int gdepth。 // 注意這是用指針模擬頁面地址 }。 JYP 139 template class Type struct DirEntry { // 目錄項結構 int LocalDepth。 // 假設 PageSize是已定義的常數(shù) int NumRecords。 // 其它數(shù)據字段 }。 如果所有 p + 1個關鍵字被散列到兩頁面之一，則上述分裂過程還須繼續(xù)。 JYP 137 利用 i + 1個二進制位將 p + 1個關鍵字重新散列到這兩個頁面，并將這些頁面的局部深度設置為 i + 1。 當兩個伙伴頁面中的關鍵字個數(shù)不大于一個頁面的容量時，就將這兩個頁面 合并 ，釋放多余的頁面，并將結果頁面的局部深度減少 1。 JYP 136 當局部深度為 i的頁面溢出時，分配一個新頁面，并將關鍵字重新散列到這兩個頁面。 以下是一種解決方案： hashi: key ? {0, …, 2 i – 1}， 1≤i≤d 其中， hashi的結果只是簡單地在 hashi1的結果前端加上二進制位 0或 1。 為防止這種情況，不宜直接使用關鍵字的二進制位序列，而應通過均勻散列函數(shù)將這些二進制位轉換為隨機序列。 JYP 134 訪問任何頁面都需要兩個步驟： （ 1）通過散列函數(shù)確定目錄項，并得到頁面地址； （ 2）訪問該頁面。 JYP 133 在圖（ a）中，每個頁面只被 1個目錄項指向，全局深度為 2。 如果對于一個頁面內的關鍵字，實際只需要 i個最低位即可確定其所在頁面，則稱該頁面的 局部深度 為 i。 例如頁面 a被 2個目錄項指向，且我們實際只需要2個最低位即可確定其中關鍵字所在頁面。 這時新增加一個頁面 e，同時改用 3個最低位區(qū)分關鍵字，并使目錄的目錄項數(shù)擴大一倍，如右圖（ b）所示。由于 C5的 2個最低位是 01，因此應存入頁面 b。需用關鍵字的 2個最低位來確定目錄項。 JYP 130 假設初始時目錄有 4項。 假設關鍵字由2個字符組成，每個字符由 3個二進制位表示。 查找關鍵字 x時 ， 用與 x的最低 k個二進制位對應的整數(shù)定位目錄項 ， 再搜索該目錄項指向的頁面 。 目錄 實際上是一個散列表 ， 該表的每個目錄項存放一個頁面指針 。 JYP 128 帶目錄動態(tài)散列 每個關鍵字由一個二進制編碼表示 。 JYP 127 在設計算法時，應盡量減少對頁面的訪問次數(shù)，因為頁面通常存儲在磁盤上。每個記錄有一個關鍵字 key。 動態(tài)散列 又稱為 可擴展散列 ，其目的就是要既保持靜態(tài)散列的快速查找性能，又具備動態(tài)適應數(shù)據文件大小變化的能力。 JYP 126 動態(tài)散列 （ ） 靜態(tài)散列必須靜態(tài)分配散列表空間。 JYP 123 圖 B+樹中刪除 35的過程 ，注意 ， “ 路標 ” 28移到根結點 ， 35移到根結點的右子女 。 JYP 122 如果刪除后結點 p中只有 ?mleaf/2? – 2個關鍵字 ，且其最鄰近兄弟 q只有 ?mleaf/2? – 1個關鍵字 ， 則需要將結點 q的內容合并到結點 p， 并刪除整個結點 q。 此過程還需要改變雙親結點中的 “ 路標 ” ， 以反映結點 p或 q中第一個關鍵字的值 。 注意 ， 雖然元素 30已被刪除 ，但作為 “ 路標 ” 的 30不必從中間結點中刪除 。 如果刪除后結點 p中的關鍵字個數(shù)仍然大于等于 ?mleaf/2?–1， 則將修改后的結點 p寫到磁盤即可 。 JYP 115 圖 — 1 JYP 116 圖 — 2 JYP 117 從 B+樹中 刪除 關鍵字 x的方法也與 B樹的類似 。 JYP 114 這又可能使雙親結點分裂，直至使根結點分裂，整個 B+樹長高一層。 如果結點 p已滿，則將其分裂為 p和 q兩個結點，這兩個結點平均承載原來結點 p中的內容和新元素，且結點 q中元素的關鍵字大于結點 p中的。 首先，定位到關鍵字為 x的元素可插入的葉結點 p。由根結點的第 2棵子樹的第 1個分枝，可到達關鍵字為 35的元素所在的葉結點。 例如，在圖 35。 JYP 112 除了需要一直查到葉結點以外， B+樹的 查找 方法與 B樹的基本相同。 圖 B+樹的例子： 其中 ， m=3， mleaf=5。設 mleaf是葉結點可容納的最大失敗結點個數(shù)，則其中的實際關鍵字個數(shù) n應滿足： 1≤?mleaf/2? – 1≤n mleaf。 （ 6） 所有葉結點都處于同一個層次，包含了全部關鍵字以及相應的元素或元素地址，葉結點中的關鍵字從小到大排序，且互不相同。 JYP 110 （ 4） An中的所有關鍵字都大于等于 Kn， A0中的所有關鍵字都小于 K1。 （ 2） Ki Ki+1， 1≤i n，且所有中間結點的關鍵字互不相同。中間結點也存放關鍵字，但這些關鍵字只起引導查找的“路標”作用。 B+樹與 B樹的最大 區(qū)別是 ： B+樹的元素只存放在葉結點中。 為了滿足這種需求，需要改進 B樹。 } 顯然， build(a, 0, n)的計算時間是 O(n)。 p?RightChild = build(a, k, j)。 p?data = a[k]。 // 空樹 BstNodeType*p = new BstNodeType。 } root = build(a, 0, n)。} // 求 k } c[i][j] = w[i][j] + c[i][k1] + c[k][j]。 if (t s) {s = t。 u = r[i+1][ j]。 float s = MAX。 w[i][j] = w[i][j1] + p[j] + q[j]。 i = n m。 m = n。 c[n][n] = 0。 c[i][i+1] = w[i][i+1]。 // 初始化 w[i][i+1] = q[i] + q[i+1] + p[i+1]。 i++) { w[i][i] = q[i]。 for (int i = 0。 )12(2?????nmmnJYP 105 template class Type void BSTType::obst(float *p, float *q, ElementType*a, int n) { // 給定 n個標識符 a1 a2 … a n，和 pj（ 1 ? j ? n）和 // qi（ 0 ? i ? n），計算表示 ai+1,…, a j的 Tij的 cij，同時計算 // rij 和 wij。計算全部 cij和 rij的總時間改進為 n – m + 1 + = O(n2) 假設二維數(shù)組 w、 c和 r是類 BST的私有數(shù)據成員 。 JYP 103 計算全部 cij和 rij的總時間是 = O(n3) Knuth的研究成果表明， ()式中的最佳 u的選擇可限定在 ri,j1≤u≤ri+1,j的范圍。每計算一個 cij需要從 m個量中選擇最小的（ ()式），計算時間是 O(m)。 由上可得計算 cij和 rij（ 0≤i n， i j≤n）以及根據rij構造 T0n的方法：按（ j – i） = 1, 2, …, n 的順序計算cij。由此可以構造 T03，如右圖所示。 T13的根結點含標識符 a3，其左子樹是 T12，右子樹是 T33。 下一頁的圖 。利用 ()和 ()式，并注意到 wij = wi,j1 + pj + qj，可得 w01 = w00 + p1 + q1 = + + = c01 = w01 + min{c00 + c11} = r01 = 1 w12 = w11 + p2 + q2 = + + = c12 = w12 + min{c11 + c22} = r12 = 2 JYP 99 w23 = w22 + p3 + q3 = + + = c23 = w23 + min{c22 + c33} = r23 = 3 在 wi,i+1和 ci,i+1的基礎上（ 0≤i 3），再次利用 ()和 ()式，可計算出 wi,i+ ci,i+2和 ri,i+2， 0≤i 2。 }{m i n 1, ujuiijjuiccw ?? ???}{m i n 1, ujuijuicc ????JYP 98 例 設 n = 3， (a1, a2, a3) = (data, pipe, work)，(p1, p2, p3) = (, , )， (q0, q1, q2, q3) = (, , , )。 根據 ()， Tij的代價 cij = pk+L的代價 +R的代價 +L的權重 +R的權重 其中， L的權重 = wi,k1， R的權重 = wkj。 )(1kjikk pq ????JYP 95 如果 Tij是包含 ai+1, … , aj的最佳二叉查找樹 ， 且 rij = k， 則 i k≤j。由定義， wii = qi， 0≤i≤n。 設 rij為 Tij的根結點標識符的下標號 。 設 cij為 Tij的代價 。 通過利用最佳二叉查找樹的一些性質 ， 則可以得到相當高效的算法 。 JYP 93 采用例 雜性很高 。 )1)((0?????il e v e lqnii 失敗結點)1)(()(01???? ??????il e v e lqal e v e lpniiinii 失敗結點JYP 89 例 圖 a1, a2, a3 = (data, pipe, work)的所有可能的二叉查找樹： JYP 90 JYP 91 當 pi = qj = 1/7時， 1≤i≤3， 0≤j≤3，有 樹（ a）的代價 = 15/7 樹（ b）的代價 = 13/7 樹（ c）的代價 = 15/7 樹（ d）的代價 = 15/7 樹（ e）的代價 = 15/7 正如可以預料到的，樹（ b）是最佳的。 將失敗結點從