大概是昨天我又發現自己忘記寫 WebWork 的微積分作業了。雖然那份作業占的分數不高，但看到自己就這樣白白錯過，心裡還是很痛。也因為這件事，我開始認真覺得自己需要一個專門拿來提醒 deadline 的系統。
現在常見的日曆 app 對我來說比較像是拿來記錄大事件，例如考試、活動、開會或重要行程。但如果把作業、報告、測驗、申請期限這些東西全部混在一起，畫面會變得很亂，反而更難注意到真正快到期的小任務。
另外，像 NTU COOL 這類課程平台的通知很多，有時候會夾雜公告、課程資訊、教材更新與作業提醒。當資訊太雜時，真正重要的 deadline 反而容易被淹沒。
因此，我想做一個「作業截止日管理系統」，重點不是做一個完整日曆，而是專注在 deadline 的管理、排序與查詢。這個系統希望能讓使用者新增、刪除、修改與查詢任務，並且依照截止時間自動排序，幫助使用者更清楚掌握近期要完成的事情。
本專題的目標是建立一個以 deadline 為核心的任務管理系統，並使用 Red-Black Tree 作為主要資料結構來維護任務的排序。
預計達成以下目標：
- 建立一個可新增、刪除、查詢與修改任務的截止日管理系統。
- 使用 Red-Black Tree 維持任務依 deadline 排序。
- 提供查詢最近到期任務的功能。
- 提供依照 deadline 由近到遠列出所有任務的功能。
- 比較 Red-Black Tree 與其他資料結構在 deadline 管理上的效能差異。
- 透過實作過程理解 self-balancing binary search tree 在動態資料管理中的應用。
| 項目 | Google Calendar / Apple Calendar | NTU COOL / 課程平台通知 | 一般 To-do List App | 本專題：作業忘記寫了 |
|---|---|---|---|---|
| 主要用途 | 管理行程、活動與會議 | 課程公告、教材與作業通知 | 管理待辦事項 | 專注管理作業與 deadline |
| Deadline 排序 | 可以，但通常需要手動整理 | 資訊較分散，且未被建立在課程平台中的作業不一定會顯示 | 通常可以，但多以當天待辦事項為主 | 以 deadline 為核心自動排序 |
| 最近到期任務查詢 | 不一定直覺 | 容易被公告淹沒 | 視 app 而定 | 可直接查詢最近到期任務 |
| 資料結構效能分析 | 無 | 無 | 無 | 可比較不同資料結構效率 |
| 是否適合學生作業情境 | 普通 | 是，但通知較雜 | 普通 | 專門針對學生 deadline 設計 |
和一般日曆 app 相比，本專題不以完整月曆或活動安排為主，而是專注在「近期快到期的任務」。一般日曆雖然可以記錄 deadline，但作業、考試、活動和會議混在一起時，畫面容易變得雜亂。
和課程平台通知相比，本專題的資訊更集中。課程平台常會混合公告、教材、討論區與作業提醒，而且未被老師建立在系統中的作業不一定會顯示。本系統則讓使用者可以主動新增所有任務。
和一般 To-do List App 相比，本專題更強調學生 deadline 情境與資料結構實作。除了基本任務管理，也會比較普通陣列、排序陣列、AVL Tree、Splay Tree 與 Red-Black Tree 在 deadline 管理上的效率差異。
-
新增任務
- 使用者可輸入任務名稱、課程名稱、deadline、優先級與備註。
- 系統會將任務插入 Red-Black Tree 中，並依 deadline 維持排序。
-
刪除任務
- 使用者可刪除已完成或不需要的任務。
- 系統需正確更新資料結構。
-
修改任務
- 使用者可修改任務名稱、課程名稱、deadline、優先級與備註。
- 若 deadline 被修改，系統會重新調整任務在資料結構中的位置。
-
查詢最近到期任務
- 系統可快速顯示目前最接近截止時間的任務。
- 此功能會透過 Red-Black Tree 中最小 deadline 的節點完成。
-
列出所有任務
- 系統可依 deadline 由近到遠顯示所有任務。
- 透過 in-order traversal 輸出排序結果。
-
標記完成狀態
- 使用者可將任務標記為已完成或未完成。
- 已完成任務可以選擇保留或刪除。
-
使用說明
- 程式啟動後會顯示基本操作方式。
- 使用者可以查看 deadline 格式、優先級輸入方式與範例任務。
-
效能比較
- 使用相同任務資料，先比較普通陣列、排序陣列與 Red-Black Tree。
- 若時間允許，後續再加入 AVL Tree 與 Splay Tree 作為延伸比較對象。
- 預計比較新增任務、查詢最近 deadline、刪除任務與列出所有任務等操作。
- 記錄操作時間，並整理成輸出結果。
- 程式語言： C++
- 開發工具： Visual Studio Code、g++
- 版本控制： Git、GitHub
- 核心資料結構： Red-Black Tree
- 比較用資料結構：
- 普通陣列
- 排序陣列
- AVL Tree
- Splay Tree
- Red-Black Tree
其中 Red-Black Tree 會作為本專題的主要資料結構，AVL Tree 與 Splay Tree 則作為效能比較對象。透過比較不同資料結構在新增任務、查詢最近 deadline、刪除任務與列出所有任務上的表現，可以觀察不同 self-balancing binary search tree 在實際應用情境中的差異。
其他使用到的技術與觀念包含：
- class 與物件導向設計
- struct 資料封裝
- 模組化程式設計
- 終端機 CLI 介面
- 時間複雜度分析
std::vectorstd::chronostd::lower_boundstd::min_element
系統預計會拆成幾個主要部分：
Task：儲存任務名稱、課程名稱、deadline、優先級、備註與完成狀態。RedBlackTree：負責 Red-Black Tree 的插入、搜尋、旋轉、重新著色與走訪。TaskManager：負責管理使用者操作，例如新增、刪除、修改、查詢與列出任務。benchmark：負責測試不同資料結構在相同操作下的效能。
Prototype 階段預計完成一個可以在終端機操作的基本版本，重點是先驗證核心資料結構與 deadline 管理流程是否可行。
預計可驗證的內容包含：
-
任務資料格式是否能正常建立
- 可以建立任務名稱、課程名稱、deadline、優先級與備註。
- 可以正確顯示任務內容。
- 可以標記任務是否完成。
-
Red-Black Tree 基本操作是否正常
- 可以插入任務。
- 插入後能維持依 deadline 排序。
- 可以透過 in-order traversal 依 deadline 由近到遠輸出任務。
-
最近到期任務查詢是否可行
- 可以找到目前 deadline 最早的任務。
- 新增任務後，最近到期任務可以正確更新。
- 若任務被刪除，也可以重新整理資料並找到下一個最近到期任務。
-
基本任務管理功能是否完成
- 新增任務。
- 刪除任務。
- 修改任務。
- 查詢最近到期任務。
- 列出所有任務。
- 標記任務完成。
-
初步效能比較是否可執行
- 使用相同任務資料，先比較普通陣列、排序陣列與 Red-Black Tree。
- 若時間允許，後續再加入 AVL Tree 與 Splay Tree 作為延伸比較對象。
- 測試新增任務所需時間。
- 測試查詢最近 deadline 所需時間。
- 初步觀察不同資料結構在 deadline 管理情境下的差異。
Prototype 階段不一定完成完整 UI，但會先完成核心功能，也就是 Red-Black Tree 的任務管理與初步效能比較。Final 階段再補上更完整的測試資料、效能分析與使用介面優化。
目前已完成一個可以在終端機操作的 Prototype 版本，主要功能已經可以初步驗證本專題的核心想法：使用 Red-Black Tree 來管理作業 deadline，並依照截止時間自動排序。
目前完成的內容包含：
-
任務資料格式
- 已建立
Task結構，儲存任務 ID、任務名稱、課程名稱、deadline、優先級、備註與完成狀態。 - deadline 目前使用
YYYY-MM-DD HH:MM的字串格式儲存。 - 任務可以透過 ID 進行刪除、修改與標記完成。
- 已建立
-
Red-Black Tree 基本功能
- 已建立 Red-Black Tree 節點結構。
- 已完成插入功能。
- 插入後會透過 rotation 與 recoloring 維持 Red-Black Tree 的平衡性。
- 已完成 in-order traversal，可以依照 deadline 由近到遠列出所有任務。
-
Deadline 管理功能
- 可以新增任務。
- 可以列出所有任務。
- 可以查詢最近到期的任務。
- 可以刪除指定 ID 的任務。
- 可以修改指定 ID 的任務。
- 可以標記任務為已完成。
-
使用者操作介面
- 目前採用終端機選單介面。
- 程式一開始會顯示使用說明。
- 使用者可以依照選單輸入數字操作功能。
- 有提供 deadline 輸入格式與範例，降低使用時輸入錯誤的機率。
-
初步效能比較
- 已加入簡單 benchmark 功能。
- 目前會產生大量測試任務資料。
- 目前已完成普通陣列、排序陣列與 Red-Black Tree 的初步效能比較。
- 後續預計加入 AVL Tree 與 Splay Tree，進一步比較不同 self-balancing binary search tree 在 deadline 管理上的差異。
目前 Prototype 已經可以展示本專題的主要流程：新增任務後，系統會依照 deadline 維持排序，並且可以查詢最近到期的任務。
目前遇到的主要困難有以下幾點：
-
Red-Black Tree 刪除操作較複雜
Red-Black Tree 的插入需要處理 rotation 與 recoloring，而刪除節點後還需要處理更多修正情況，例如黑色高度不一致等問題。
因此在 Prototype 階段，刪除功能先採用比較簡化的方式：先把所有任務取出，移除指定 ID 的任務後，再重新建立 Red-Black Tree。
這個做法雖然不是最有效率的 Red-Black Tree 刪除方式，但可以先確保系統功能完整，讓新增、刪除、修改與查詢流程都能被驗證。後續若時間允許，會再補上標準的 Red-Black Tree deletion fix-up。
-
修改 deadline 時需要重新維持排序
因為任務在 Red-Black Tree 中的位置是根據 deadline 決定的，所以如果使用者修改 deadline，原本節點所在的位置可能就不正確。
目前的處理方式是先找到原本的任務，再從樹中移除該任務，修改資料後重新插入 Red-Black Tree。這樣可以確保修改 deadline 後，任務仍然會依照新的 deadline 排序。
-
相同 deadline 的任務需要額外排序規則
如果兩個任務有相同 deadline，單純使用 deadline 當 key 會無法明確決定排序順序。
目前的排序規則是：
- 先比較 deadline。
- deadline 相同時，比較 priority，數字越大越優先。
- 如果 deadline 和 priority 都相同，最後用任務 ID 作為排序依據。
-
效能比較需要公平
要比較不同資料結構的效率，必須讓它們使用相同的測試資料，否則結果會不公平。
目前 benchmark 會先產生一組固定的隨機任務資料，再分別插入普通陣列、排序陣列與 Red-Black Tree。這樣可以確保三種資料結構面對的是同一批資料。
-
中文顯示可能出現編碼問題
在 Windows PowerShell 或 VS Code Terminal 中，中文有時候會變成亂碼。這主要是終端機編碼不是 UTF-8 的問題。
目前透過在程式中加入 Windows console 的 UTF-8 設定來改善。
接下來預計完成以下內容：
-
改善 Red-Black Tree 刪除功能
- 目前刪除是 Prototype 簡化版。
- 後續希望補上完整 Red-Black Tree deletion fix-up。
- 讓刪除操作也能更接近標準的
O(log n)複雜度。
-
改善 deadline 格式檢查
- 目前 deadline 主要依賴使用者輸入正確格式。
- 後續可以加入格式檢查，避免輸入錯誤造成排序異常。
- 例如檢查是否符合
YYYY-MM-DD HH:MM。
-
增加檔案儲存功能
- 目前任務資料只存在程式執行期間。
- 後續希望加入檔案輸入輸出。
- 讓使用者關閉程式後，下次仍然可以讀取之前建立的任務。
-
讓 benchmark 更完整
- 目前 benchmark 已經可以比較新增與查詢最近 deadline。
- 後續可以加入刪除任務、修改 deadline、列出所有任務等操作的比較。
- 可以測試不同資料量，例如 100、1,000、10,000 筆任務。
-
整理效能分析結果
- 將 benchmark 結果整理成表格。
- 比較普通陣列、排序陣列與 Red-Black Tree 在不同操作下的優缺點。
- 說明為什麼 Red-Black Tree 適合用在動態 deadline 管理系統中。
-
改善操作介面
- 目前是基本 CLI 選單。
- 後續可以讓輸出格式更清楚。
- 若時間允許，可以嘗試加入簡單 UI。
-
加入 AVL Tree 與 Splay Tree 作為比較對象
- AVL Tree 會透過高度差維持更嚴格的平衡。
- Splay Tree 會在每次存取後將節點旋轉到根節點附近。
- 後續會比較 AVL Tree、Splay Tree 與 Red-Black Tree 在新增、查詢最近 deadline、刪除與列出所有任務時的效能差異。