contributed by < koty6069 > 2023q1 第 4 週測驗題 測驗 1 與 quiz3 的紅黑樹做比較 理解 Left-leaning Red-Black Trees 原先將 2-3-4 樹轉為紅黑樹時，會將 3-node 轉為一紅邊一黑邊的左右子樹，因為紅邊可以在左或右，會導致轉換後的紅黑樹有多種情況，使得實作時程式碼會變得非常複雜，因此提出左傾紅黑樹，將 3-node 固定轉換成左子樹為紅邊的情況，這樣可以把轉換後的紅黑樹限制為一種，2-3-4 樹和紅黑樹之間的關係變為 1-1 對應。

contributed by < koty6069 > 2023q1 第 3 週測驗題 測驗 1 程式碼解析 (incomplete treesort.c) 此程式主要是使用 C 實作紅黑樹來實現 C++ 中的 std::map。 typedef struct __node { uintptr_t color;

contributed by < koty6069 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ uname -r 5.19.0-35-generic $ lscpu

contributed by < koty6069 > Reviewed by yanjiew1 q_insert_head 和 q_insert_tail 及 q_remove_head 和 q_remove_tail 均有重複的程式碼出現，可以思考如何重用這些程式，避免重複的程式碼。 可以再思考如何利用原有佇列是已排序的特性來實作 q_merge 。 Coding Style 和 commit message 均符合規範。 函式的實作過程和說明寫得清楚有條理。 仍有些作業要求未完成：新增洗牌的指令 shuffle 及分析亂度 研究亂數產生器 研讀論文〈Dude, is my code constant time?〉

contributed by < koty6069 > 2023q1 第 2 週測驗題 測驗 1 程式碼解析 原文有提到我們可改動原本數值 x ，從其原本有數值的最高位元至最低位元皆設成 1 。 最初 x 是 0010000000000000，經過一系列操作後，成為 0011111111111111，亦即設定 (set，即指派為 1) 自原本最高位元到最低位元中，所有的位元。