【正文】 例如 ， 假設(shè)需要從圖 （ a） 的樹中刪除 30， 可以用其左子樹中的最大元素 5取代 30， 從而得到圖（ a） 所示的樹 。 JYP 136 ? 當需要刪除的元素處于有兩個子女的非葉結(jié)點中時 ， 可以用其左子樹中的最大元素或右子樹中的最小元素取代該元素 。結(jié)點 5的唯一子女是結(jié)點 2 。 例如，將 5從圖 （ a）中刪除。由此得到圖 （ a）的樹。 JYP 135 3 刪除 ? 刪除葉結(jié)點中的元素很容易。 return TRUE。 else if ( q?) q?LeftChild = p。 p?data = x。 } JYP 134 // 實施插入 p = new BstNodeType。 // if ( p?) p = p?LeftChild。 while (p) { q = p。x) { // 查找 ,， q是 p的雙親 BstNodeType*p = root。 JYP 132 新結(jié)點作為該結(jié)點的右子女插入 ， 從而得到圖（ a） 所示的二叉查找樹： JYP 133 將 35插入圖 （ a） 則得到圖 （ b） 的二叉查找樹 。 例如，在圖 （ b）中插入 80： 先查找 80。 2 插入 要插入新的元素 x，首先應(yīng)進行查找。 } } return 0。 else { k = LeftSize。 while (t) { if (k == t?LeftSize) return t。 JYP 130 如果需要 按位次 查找，可在每個結(jié)點增加一個新字段 LeftSize，其值為該結(jié)點的左子樹中的元素個數(shù)加 1。 } 其中，二叉查找樹是類 BST的對象，結(jié)點BstNode含字段 LeftChild， RightChild和 data。 else t = t?RightChild。 while (t) { if (k == t?) return t。 ? 子樹的查找也相同 。 如果相等則查找成功結(jié)束 。 如果樹根為 0， 則查找不成功 。 JYP 127 二叉樹的例子 : 其中，（ a）不是二叉查找樹，（ b）和（ c）是。 JYP 126 二叉查找樹 二叉查找樹定義 定義： 二叉查找樹是一棵二叉樹。 符號表的表示應(yīng)確保這三個基本操作的實現(xiàn)效率。 // 如果 name在符號表中，則從符 // 號表中刪除 (name, attr) }。 // 如果 name在符號表中，則返 // 回相應(yīng)屬性的指針，否則返回 0 void Insert(Name name, Attribute attr)。 // 建立一個容量為 size // 的空符號表 Boolean IsIn(Name name)。 例如 ，在詞典中 ， 名字是一個詞 ， 屬性是該詞的釋義；在編譯程序生成的符號表中 ， 名字是標識符 ， 屬性則可能包括該標識符的類型 、 初始值以及所有用到該標識符的程序行號 。 JYP 122 符號表 符號表的應(yīng)用： ? Word中的拼寫檢查 ? 數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)字典 ? 編譯程序生成的符號表等 符號表 定義為名字 ?? 屬性對集合 。 JYP 121 第 8章 查找結(jié)構(gòu) 符號表的最基本操作是查找、插入和刪除。 JYP 120 根據(jù)哈夫曼樹 ， 很容易獲得一組信息的最佳編碼 。 分析： 主循環(huán)執(zhí)行 n–1次。 JYP 116 ( )返回 list中權(quán)重最小的樹并將其從 list中刪除 ， ( )返回 list中元素個數(shù) ，(bt)將新二叉樹 bt加入表 list中 。 (bt)。 BinaryTree second = ( )。 i n – 1。 void huffman(ListBinaryTree list) { int n = ( )。 }。 root?weight = ?weight + ?weight。 root?LeftChild = 。 }。 int weight。 設(shè)二叉樹的類定義為： class BinaryTreeNode { friend class BinaryTree。 設(shè) qi是傳輸信息 Mi的相對頻率， di是 Mi對應(yīng)的外部結(jié)點到根結(jié)點的距離，則期望解碼時間是 iniidq???1 顯然，通過選擇具有最短加權(quán)外部路徑長度的解碼樹對應(yīng)的編碼，可使期望解碼時間最短。 例如，將 0解釋為左分枝，1為右分枝，右圖的解碼樹就對應(yīng)編碼 000， 001， 01和 1，分別表示信息 M1, M2, M3和 M4。 JYP 111 解碼樹是一棵二叉樹，其外部結(jié)點表示信息。每個編碼為二進制位串。 最短加權(quán)外部路徑長度二叉樹的另一個應(yīng)用是獲得最佳 信息編碼 。 JYP 110 如果采用具有最短加權(quán)外部路徑長度的 k叉歸并樹，則對 n個長度為 qi（ 1≤i≤n）的歸并段進行 k路歸并的代價最小。 此和又稱為 加權(quán)外部路徑長度 。 可用下列兩種方式給進行 2路歸并： JYP 109 一個記錄參與的歸并次數(shù)由其所在的外部結(jié)點到根的距離確定 。 這時前面所述的完整掃描所有歸并段的策略所導(dǎo)致的計算時間不是最少的 。由于每輸出一個記錄，重新調(diào)整敗者樹的時間是 O(log k)，所以對于 n個記錄的輸入表，生成所有歸并段的時間是 O(n log k)。 34} JYP 98 例 設(shè)輸入表為 (99, 48, 19, 65, 3, 74, 33, 17, 21, 20, 98, 53, 22)， k = 4，則 runs生成初始歸并段的過程如后面所示： JYP 99 JYP 100 JYP 101 JYP 102 JYP 103 JYP 104 JYP 105 JYP 106 分析： 當輸入記錄表已排好序，只生成一個歸并段。 delete [ ] rn。 30 rq = rn[q]。 q = l[t]。amp。 t。 // 新記錄仍然屬于當前歸并段 24 } 25 rq = rn[q]。 22 if ( r[q].key LastKey) rn[q] = rmax = rq + 1。 18 // 輸入新記錄 19 if (輸入結(jié)束 ) rn[q] = rmax + 1。 16 } 17 WriteRecord(r[q])。 14 if ( rq rmax ) break。 KeyType LastKey。 int rc = 1。 // 初始化敗者樹，可用類 // 似第 9 int q = l[0]。 rn[i] = 1。 i k。 int *l = new int[k]。 JYP 95 函數(shù) runs實現(xiàn)了上述采用敗者樹動態(tài)流動生成初始歸并段的方法： 1 template class KeyType 2 void runs(const int k) { 3 ElementKeyType *r = new Element[k]。 ? LastKey存放當前最后一個輸出記錄的關(guān)鍵字值。 ? rq存放 r[q]所屬的歸并段號。 ? l[0]和 q都存放整個比賽的勝者記錄下標。 敗者樹 是組織這些記錄的有效結(jié)構(gòu)： ? 每個非葉結(jié)點 i有一個字段 l[i]（ 1≤ik），表示在結(jié)點 i比賽的敗者。 從輸入表讀入下一個記錄到 r[q]，如果此記錄的關(guān)鍵字不小于當前歸并段的最后一個記錄的關(guān)鍵字，則該記錄也屬于當前歸并段，否則屬于下一個將生成的歸并段。 輸入 k個記錄后，這些記錄都屬于當前歸并段。 如果采用 動態(tài)流動 的方法 ， 即在生成歸并段的過程中不斷將記錄寫到磁盤 ， 同時從磁盤讀入新的記錄到內(nèi)存 ， 則可能生成比內(nèi)存容量大的歸并段 。 JYP 91 生成初始歸并段 用傳統(tǒng)的內(nèi)排序方法生成初始歸并段 ， 需要將內(nèi)存容納的所有記錄都排序好后再全部輸出到磁盤 。 因此，當 k超過一定值時，輸入輸出時間反而會隨著 k的增大而增加。 JYP 90 還應(yīng)該看到，當 k超過一定范圍時，輸入輸出時間并不隨著 k的增大而減少。 從敗者樹中每選一個最小記錄并重新調(diào)整需要 O(log2k)時間 ， 所以對 n個記錄歸并一遍需要的時間是 O(n log2k)。 但 k路歸并要求從 k個歸并段的前端記錄中選擇關(guān)鍵字最小的輸出 。 如下圖對 16個歸并段進行 4路歸并只需掃描數(shù)據(jù) 2遍： JYP 89 一般地 ， 采用 k路歸并需要對數(shù)據(jù)掃描 ?logkm?遍 。 JYP 88 k路歸并 按 2路歸并 ， 給定 m個歸并段 ， 相應(yīng)的歸并樹有?log2m?+1層 ， 需要對數(shù)據(jù)掃描 ?log2m?遍 。 但這些歸并段長短不一，對它們歸并的次序也會影響計算時間。 此外，初始歸并段應(yīng)盡可能長，從而減少初始歸并段個數(shù)。 322322322JYP 87 顯然， k路歸并 （ k 2）可以減少數(shù)據(jù)掃描遍數(shù)。 一遍掃描需要輸入輸出 2?18個 IO塊，總的輸入輸 出時間是 ( + 1) ?2?18tIO = 132tIO。按上述方法，排序步驟如下： JYP 83 JYP 84 分析用符號： tseek = 最長尋找時間 tlatency = 最長等待時間 trw = 讀寫一個 IO塊（ 250個記錄）所需時間 tIO = tseek + tlatency + trw tIS = 內(nèi)排序 750個記錄所需時間 ntm = 將 n個記錄從輸入緩沖區(qū)歸并到輸出緩沖區(qū)所 需時間 JYP 85 例 4500個記錄的操作時間： JYP 86 由于 tIO tIS， tIO tm，影響計算時間的主要因素是輸入輸出操作的次數(shù)，而后者又主要依賴于對數(shù)據(jù)掃描的遍數(shù)。 由于歸并算法只要求同一時刻兩個歸并段的前端記錄在內(nèi)存 ， 因此經(jīng)過歸并 ， 可以生成比內(nèi)存大的歸并段 。 這些已排序的段又稱為 歸并段 （ runs） 。為了提高傳輸效率， IO塊的容量一般都較大，通?？砂瑪?shù)千字節(jié)。 ? 傳輸 時間：將塊中數(shù)據(jù)讀入內(nèi)存或?qū)懙酱疟P所用時間。 JYP 80 影響磁盤讀寫時間的有以下三個因素： ? 尋找 時間：將讀寫頭定位于正確的柱面所用時間。 磁盤的讀、寫以 IO塊 為單位。 假設(shè)需要排序的記錄表存放在磁盤上。排序過程如后面兩頁所示。 例 設(shè)需要排序的 10個數(shù)的取值范圍是 [0, 999]。 i) 結(jié)束 return current。 } // for (i = d 1。 last = e[k]。 k r。 int last = e[j]。 j++)。 } for (j = 0。 else list[e[k]].link = current。current = list[current].link) { //分配記錄 int k = list[current].key[i]。 // 初始化所有箱子 for ( 。 j r。 i = 0。 int current = 0。 i++) list[i].link = i+1。 // radix個隊列的首、尾指針 for (int i = 0。 JYP 72 每個箱子中的記錄鏈接成隊列 ， f[i]和 e[i]（ 0≤i r） 分別指向第 i個箱子的首 、 尾記錄 。 // 關(guān)鍵字數(shù)組， d是常數(shù) // 其它字段 … int link。關(guān)鍵字用基數(shù) r分解，每個分解為 d位，每位的取值是 0到 r – 1，則需要 r個箱子。 基數(shù) r排序需要 r個箱子。 當 r = 10，則得到上述十進制分解。 JYP 70 可見，如果關(guān)鍵字是十進制數(shù)，可將其中的每個十進制位看成一個子關(guān)鍵字，并按 LSD策略用 10個箱子對每個子關(guān)鍵字進行箱排序。 ? 接著 ， 將 8號箱的卡片放在 9號箱的之前 ， … ， 將 0號箱的卡片放在 1號箱的之前 。