# 2024q1 Homework4 (quiz3+4) contributed by < `yutingshih` > ## 第三週測驗題 ### 測驗 1 ### 測驗 2 ### 測驗 3 ### 測驗 4 ### 測驗 5 ## 第四週測驗題 ### 測驗 1 ### 測驗 2 ### 測驗 3 <!-- 1. 解釋上述程式碼運作原理 2. 指出上述程式碼可改進之處,特別跟 AVL tree 和 red-black tree 相比,並予以實作 (考慮到循序輸入和亂序輸入的狀況) 3. 設計效能評比程式,探討上述程式碼和 Linux 核心 red-black tree 效能落差 --> #### 程式碼運作原理 <!-- 解釋 hint --> <!-- 解釋 __xt_remote --> ```c static void __xt_remove(struct xt_node **root, struct xt_node *del); ``` 函式 `__xt_remove` 用於在 XTree 中移除一個節點,有兩個參數,分別是 XTree 的根節點 `struct xt_node **root` 和欲移除的節點 `struct xt_node *del`,需要分別對三種狀況做處理: 1. 如果 `del` 有右子樹,以右子樹中最小節點替換 `del`,然後呼叫 `xt_update` 維護 XTree。 2. 如果 `del` 有左子樹,以左子樹中最大節點替換 `del`,然後呼叫 `xt_update` 維護 XTree。 3. 如果 `del` 是唯一的節點 (即根節點),則直接把根設為 `NULL`,,最後一樣呼叫 `xt_update` 維護 XTree。 <!-- 指出用詞不精準 --> <!-- treeint_xt 只支援整數的型態 --> <!-- update 的條件和 AVL tree 一樣,解釋一下 --> <!-- 紅黑樹 --> <!-- Linux v6.8 以後沒有 AVL tree,以前才有,為什麼? --> <!-- AVL tree 和 rbtree 適用在不同場景 --> <!-- xt_update --> <!-- xt_balance -->
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up