大家好，我想分享一個我最近做的筆記，主題是把第三周測驗題的第一題 `treesort` 整合進第一周作業的 `lab0-c`，目前主要的修改有:
* 參考 `linux` 在 `Linked list` 的實作，將紅黑數節點的資訊從原本的結構體 `node_t` 移出到 `rb_node` 結構體，好處在於只要將 `rb_node` 納入到新的結構體的成員即可操作，不必另外維護一顆紅黑樹。
* 加入印出 `level order` 的功能方便除錯，選擇 `level order` 的原因是因為比起前、中、後序它可以決定唯一的二元樹。
* 利用 `lab0-c` 提供的 `list.h` 標頭檔改寫 `treesort` 函式，並將其加入 `qtest` 中。
* 引入 `memory pool`，參考 [rv32emu 在 memory pool 的實作](https://github.com/sysprog21/rv32emu/blob/master/src/mpool.c)，用於執行 `treesort` 前預先配置好記憶體，之後重用該空間，從而縮減動態記憶體配置的成本。

筆記: https://hackmd.io/@willwillhi/treesort