# 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` 函數處理刪除操作,包括選擇適當的替代節點並更新樹以維持平衡。
```graphviz
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
以下是左旋操作的圖示,紅色虛線表示旋轉後的新連接:
```graphviz
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"];
}
```
左旋轉前後對比圖(白色是之前,藍色之後):
```graphviz
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
以下是右旋操作的圖示,紅色虛線表示旋轉後的新連接:
```graphviz
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` 函數的操作示意圖:
```graphviz
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
```graphviz
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 ,紅色虛線表示旋轉後的新連接:
```graphviz
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 需要在快速插入/刪除與維持樹平衡之間找到適當的平衡點。
#### 代做事項