申論題

第一題：

    假設已經存在 data1.dat、data2.dat、…data8.dat 等八個資料檔，每個檔案存放一萬筆資料，每筆資料有 個 Key 值，所有資料的 Key 值均不同，且在各個檔案中按照 Key 值由小而大排列。今欲運用 Selection Tree 將這八個排好序的檔案合併成擁有八萬筆資料且 Key 值由小而大排列的檔案 data.dat，且採用 Winner Tree (而非 Loser Tree)。初始化 Winner Tree 時依 data1.dat、data2.dat、…data8.dat 順序將每個來源資料檔案(run) 的第一筆資料讀入 Winner Tree 的對應葉節點(Leaf Node)，以建構 Winner Tree。

(一)請繪圖表示此 Winner Tree 的形狀(不須標示每個 Node 的 Key 值)。