公職◆資料結構題庫

五、若處理的資料，其數值均不同且已知均為 1 到 100 之間的整數或小數。若 K≦X＜

K+1，集合 Lx 代表數值在[K,K-1]間全部資料，1≦K≦99, K 為整數，資料結構支援

下列功能。

Insert(X)：增加 X，若 X 不存在 Lx 中。

Delete(X)：移除 X，若 X 存在 Lx 中。

List(X)：將 Lx 中的資料全部依序印出。

設計一資料結構滿足在最差情況的條件分析（Worst Case Analysis），每個功能的執

行時間要求為：Insert(X) and Delete(X)須在 O(log |Lx |)時間內完成，List(X)則須在

O(|Lx |)時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？

（15 分）