# 2024q1 Homework4 (quiz3+4)
contributed by < [`Ken-LuWeiRu`](https://github.com/Ken-LuWeiRu) >

## [2024q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)

XTree 是自平衡二元搜尋樹，它結合了 AVL 樹和紅黑樹的特點，旨在提供快速插入和刪除操作同時保持相對優良的平衡性。

- `xt_create` 函數初始化一棵空樹。
- `xt_destroy` 和 `__xt_destroy` 函數負責遞迴銷毀樹及其節點。
- `xt_first` 和 `xt_last` 函數分別找到子樹中最小和最大的節點。
- `xt_rotate_left` 和 `xt_rotate_right` 函數執行基本的樹旋轉操作以幫助維持或恢復平衡。
- `xt_balance` 和 `xt_max_hint` 函數計算樹的平衡因子和更新節點的平衡提示。
- `xt_update` 函數根據節點的平衡情況進行調整以維護整體樹的平衡。
- `__xt_find` 和 `__xt_find2` 函數用於在樹中查找特定鍵值的節點。
- `__xt_insert` 和 `xt_insert` 函數實現節點的插入操作。
- `xt_replace_right` 和 `xt_replace_left` 函數在刪除操作中用來替換節點。
- `__xt_remove` 和 `xt_remove` 函數處理刪除操作，包括選擇適當的替代節點並更新樹以維持平衡。

digraph XTree {
    node [shape=record];
    struct1 [label="XTree | <root> root | cmp | create_node | destroy_node"];
    struct2 [label="xt_node | <left> left | <right> right | hint | <parent> parent"];

    struct3 [label="xt_node | <left> left | <right> right | hint | <parent> parent"];

    struct4 [label="xt_node | <left> left | <right> right | hint | <parent> parent"];

    struct1:root -> struct2 [label="root"];
    struct2:left -> struct3:parent //[label="parent", color="blue"];
    struct2:right -> struct4:parent //[label="parent", color="red"];
    //struct2:parent -> struct2 [label="parent", color="grey"];
}

這張圖顯示了 XTree 的基本結構，包括根節點和其他節點之間的關係。每個節點可以有左右子節點和一個父節點。

### 程式碼解釋

#### xt_rotate_left

以下是左旋操作的圖示，紅色虛線表示旋轉後的新連接：

digraph G {
    node [shape=record, style=filled, fillcolor=gray95];

    N [label="n"];
    L [label="l"];
    P [label="p"];
    LR [label="l's right"];

    // Before rotation
    P -> N [label="Parent"];
    N -> L [label="Left child"];
    L -> LR [label="Right child"];

    // After rotation, shown with dashed lines
    edge [color=red, style=dashed];
    P -> L [label="New Parent",color=red];
    L -> N [label="New Right child"];
    N -> LR [label="New Left child"];
}

左旋轉前後對比圖(白色是之前，藍色之後):

digraph G {
    node [shape=record, style=filled, fillcolor=gray95];

    // Nodes before rotation
    P [label="p (Parent)"];
    N [label="n (Node to rotate)"];
    L [label="l (Left child of n)"];
    LL [label="ll (Left child of l)"];
    LR [label="lr (Right child of l)"];

    // Nodes after rotation
    P2 [label="p", color="blue"];
    N2 [label="n", color="blue"];
    L2 [label="l", color="blue"];
    LL2 [label="ll", color="blue"];
    LR2 [label="lr", color="blue"];

    // Edges before rotation
    P -> N;
    N -> L;
    L -> LL;
    L -> LR;

    // Edges after rotation
    P2 -> L2 [color="blue", style=dashed];
    L2 -> N2 [color="blue", style=dashed];
    N2 -> LL2 [color="blue", style=dashed];
    L2 -> LR2 [color="blue", style=dashed];

    // Invisible edges for layout
    edge [style=invis];
    P -> P2;
    N -> L2;
    L -> N2;
    LL -> LL2;
    LR -> LR2;
}

#### xt_rotate_right

以下是右旋操作的圖示，紅色虛線表示旋轉後的新連接：

digraph G {
    node [shape=record, style=filled, fillcolor=gray95];

    N [label="n"];
    R [label="r"];
    P [label="p"];
    RL [label="r's left"];

    // Before rotation
    P -> N [label="Parent"];
    N -> R [label="Right child before rotation"];
    R -> RL [label="Left child of r"];

    // After rotation, shown with dashed lines
    edge [color=red, style=dashed];
    P -> R [label="New Parent"];
    R -> N [label="New Left child"];
    N -> RL [label="New Right child", color="red"];
}

#### xt_update

這是 `xt_update` 函數的操作示意圖：

digraph {
    node [shape=box];
    subgraph cluster_0 {
        label = "xt_update";
        Start [shape=oval, label="Start xt_update"];
        CheckNull [label="Is node NULL?"];
        CalcBalance [label="Calculate balance factor"];
        RotateRight [label="Rotate right"];
        RotateLeft [label="Rotate left"];
        UpdateHint [label="Update hint"];
        End [shape=oval, label="End xt_update"];
    }

    Start -> CheckNull;
    CheckNull -> CalcBalance [label="No"];
    CheckNull -> End [label="Yes"];
    CalcBalance -> RotateRight [label="balance < -1"];
    CalcBalance -> RotateLeft [label="balance > 1"];
    CalcBalance -> UpdateHint [label="balance is ok"];
    RotateRight -> UpdateHint;
    RotateLeft -> UpdateHint;
    UpdateHint -> End;
}

#### xt_insert & __xt_insert

digraph xt_insert {
    node [shape=record, fontname=Helvetica];

    start [label="開始插入", shape=ellipse];
    find [label="使用 __xt_find\n尋找插入位置"];
    check [label="節點是否已存在?", shape=diamond];
    create [label="創建新節點"];
    insert [label="調用 __xt_insert\n進行實際插入"];
    update [label="調用 xt_update\n平衡樹", shape=box, style=filled, fillcolor=lightgrey];
    end [label="結束插入", shape=ellipse];

    start -> find -> check;
    check -> create [label="否"];
    create -> insert -> update;
    check -> end [label="是"];
    update -> end;
}

#### __xt_remove xt_replace_right xt_replace_left

__xt_remove 使用 xt_replace_right 或 xt_replace_left 來替換節點，在使用 xt_update 來平衡 xtree

以下是 xt_replace_right ，紅色虛線表示旋轉後的新連接：

digraph {
    node [shape=record];

    // Defining nodes
    n [label="{Node n|key: n_key}"];
    r [label="{Replacement Node r|key: r_key}"];
    p [label="{Parent Node p|key: p_key}"];
    rp [label="{Parent of Replacement Node rp|key: rp_key}"];
    nr [label="{Right Child of n|key: nr_key}"];
    rr [label="{Right Child of r|key: rr_key}"];

    // Connecting nodes
    p -> n [label="left or right child"];
    n -> r [label="right child"];
    n -> nr [label="right child", style=dashed];
    rp -> r [label="left or right child"];
    r -> rr [label="right child", style=dashed];

    // After replacement
    p -> r [label="new child", color="red", style=dashed];
    r -> n [label="left child (after rotation)", color="red", style=dashed];
    rp -> rr [label="new child", color="red", style=dashed];
}

### 可改進之處

與 AVL 樹和紅黑樹相比，XTree 在插入和刪除操作中尋求更快的執行速度，但可能在保持完美平衡方面稍遜色。改進的方向包括：

1. **平衡策略的優化：** 目前的平衡操作是在插入或刪除後立即執行。考慮引入更智能的策略，例如僅在必要時進行平衡操作，可以減少總體平衡次數，提升效率。
2. **動態調整策略：** 根據樹的大小和操作的特性（如連續插入或刪除），動態調整平衡策略，可能會提高效率。
3. **記憶體管理：** 樹的節點操作經常伴隨記憶體分配和釋放，可以考慮使用記憶體池來管理節點的分配和釋放，以減少記憶體分配的開銷。

#### 循序輸入和亂序輸入的狀況

- **循序輸入：** 在連續插入排序資料時，某些二元搜尋樹（如未平衡的 BST）可能退化成鏈表，導致性能下降。對於 XTree，即使在面對循序輸入時，也應保持一定程度的平衡，避免退化成鏈表。
- **亂序輸入：** 亂序輸入一般有助於保持樹的平衡，但過度的平衡操作可能會導致不必要的性能損耗

XTree 需要在快速插入/刪除與維持樹平衡之間找到適當的平衡點。

#### 代做事項