contributed by <doodoodog> 題目: 2023_sumer_quiz1 Homework2 quiz 1-1 :::success 解釋上述程式碼運作原理，應該涵蓋測試方法、futex 使用方式、Linux 核心開發者針對 POSIX Threads 強化哪些相關 futex 實作機制等等 ::: 程式碼運作原理 此程式碼的目的是在 Multi-Thread 的情況下能滿足所有 Task 能夠按順序完成。(範例 : 如果要執行 Task 3 就必須先執行 Task 2，如果要執行 Task 2 就必須先執行 Task 1 以此類推)。

:pencil:α − 1 :::success 解釋上述程式碼運作原理 ::: S-Tree 繼承了 AVL Tree 的特性，透過 Insert & Rotation 來平衡樹高，此目的可以保證在 Search Node 的時間複雜度維持在 O(log n)，但因為 AVL Tree 存在著過度 Balance 的問題導致在做 Insert or Delete Node 的時候會帶來較大的開銷，此時設計者加入 red-black tree 的特性，也就是不會過度執行 Balance 進而可以平衡掉 AVL Tree 執行 Balance 帶來的開銷。 這邊設計者利用 hint 來追蹤數高，hint 只有在 st_update Node 情況下才會更新 在 Delete Node 會先選擇右子樹最小的 Node 來 replace 如果不存在右節點，則會從左子樹最大的 Node 來 replace 在 st_update() 時候會檢查 balance 如果左右子樹的樹高差距大於 1 則會進行 st_rotate_right() or st_rotate_left()