# 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 -->

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 -->