contributed by < koty6069 > 2023q1 第 4 週測驗題 測驗 1 與 quiz3 的紅黑樹做比較 理解 Left-leaning Red-Black Trees 原先將 2-3-4 樹轉為紅黑樹時,會將 3-node 轉為一紅邊一黑邊的左右子樹,因為紅邊可以在左或右,會導致轉換後的紅黑樹有多種情況,使得實作時程式碼會變得非常複雜,因此提出左傾紅黑樹,將 3-node 固定轉換成左子樹為紅邊的情況,這樣可以把轉換後的紅黑樹限制為一種,2-3-4 樹和紅黑樹之間的關係變為 1-1 對應。
5/15/2023contributed by < koty6069 > 2023q1 第 3 週測驗題 測驗 1 程式碼解析 (incomplete treesort.c) 此程式主要是使用 C 實作紅黑樹來實現 C++ 中的 std::map。 typedef struct __node { uintptr_t color;
5/4/2023contributed by < koty6069 > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ uname -r 5.19.0-35-generic $ lscpu
3/21/2023contributed 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?〉
3/18/2023or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up