# 2024q1 Homework4 (quiz 3 + 4)
contributed by < `rain20010126` >
## 第三週測驗
### 測驗一
使用 [Digit-by-digit calculation ](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 方法找出輸入 $N^2$ 的平方根 $N$
首先將 $N^2$ 分解成由 n 個整數之和:
$N^2 = (a_n + a_{n-1} + a_{n-2} + ... + a_0)^2,a_m=2^m\ or\ a_m=0$
接著根據 $(x + y)^2 = x^2 + 2xy + y^2$，將 $N^2$ 展開如以下:
\begin{split}
N^2 =&\ a_n^2+[2a_n+a_{n-1}]a_{n-1}+[2(a_n+a_{n-1})+a_{n-2}]a_{n-2}+...+[2(\displaystyle\sum_{i=1}^{n}a_i)+a_0]a_0 \\
=&\ a_n^2+[2P_n+a_{n-1}]a_{n-1}+[2P_{n-1}+a_{n-2}]a_{n-2}+...+[2P_1+a_0]a_0 \\
\end{split}
令 $P_m=\sum_{i=m}^n a_i$，則$P_0=a_n+a_{n-1}+ a_{n-2} + ... + a_0=N$，此時 $P_0$ 即為所求的平方根
接著我們需要找出每個 $a_m$ 的值，可以透過 $P_m$ ，其中 $m=n$ 慢慢試到 $m=1$， 透過檢查 ${P_m}^2 \leq N^2$ 是否成立來判斷 $a_m$ 為 $2^m$ 或是 $0$，但是此種方法的成本過高
若是定義 $X_m$ 和 $Y_m$ 為以下
\begin{align}
X_m &= N^2 - {P_m}^2
\end{align}
\begin{split}
Y_m &= {P_m}^2 - {P_{m+1}}^2 &
\end{split}
接著透過 $X_m - X_{m+1} = - {P_m}^2 + {P_{m+1}}^2 = -Y_m$ ，可將上述式子轉換成以下
\begin{split}
X_m = X_{m+1} - Y_m
\end{split}
\begin{split}
Y_m &= {P_m}^2 - {P_{m+1}}^2 = {(P_{m+1} + a_m)}^2 - {P_{m+1}}^2 = 2P_{m+1}a_m + {a_m}^2
\end{split}
可以發現這時只需要紀錄 $P_{m+1}$ 的值即可取代 ${P_m}^2$ 的計算，最後將 $Y_m$ 拆解成 $c_m$ 以及 $d_m$ ，詳細定義為以下
\begin{split}
c_m = 2P_{m+1}a_m = P_{m+1}2^{m+1}
\end{split}
\begin{split}
d_m = {a_m}^2
\end{split}
這時可以透過 $Y_m$ 來判斷 $a_m$ 為何
\begin{split}
Y_m=
\begin{cases}
c_m+d_m & \text{if } a_m=2^m \\
0 & \text{if } a_m=0
\end{cases}
\end{split}
接著藉由位元運算來進行下一輪的 $c_{m-1}$, $\ d_{m-1}$，如以下
\begin{split}
c_{m-1}=&\ P_m2^m=(P_{m+1}+a_m)2^m=P_{m+1}2^m+a_m2^m=\begin{cases}
c_m/2+d_m & \text{if }a_m=2^m \\
c_m/2 & \text{if }a_m=0
\end{cases}\\
d_{m-1}=&\ (2^{m-1})^2 = (\dfrac{2^m}{2})^2 = \dfrac{(2^m)^2}{4}= \dfrac{d_m}{4}
\end{split}
最後求得 $c_{-1}$ 即為最後的解 $P_0 = N$
**程式碼部分**
```c
int i_sqrt(int x)
{
if (x <= 1) /* Assume x is always positive */
return x;
int z = 0;
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
}
return z;
}
```
`int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL)` 使最小位元為 0 (確保其值為偶數，==不理解為何==)
由此可知程式碼中的 `b`, `z`, `m` 分別對應到 $Y_m$, $\ c_m$, $\ d_m$，迴圈中的 `AAAA` 應該填上 `2` ， `BBBB` 填上 `1`
### 測驗二
此題為進行 mod10 和 div10 操作時，如何改成使用 `Hacker's Delight` 的 bitwise operation 方式來做除法
因為 $10$ 沒辦法用 $2^n$ 所表示，因此使用 bitwise operation 的方式無法完全整除，此時只能找一個接近 $\large \frac{1}{10}$ 的數字 $\large \frac{a}{2^N}$
由以下程式碼可以判斷出 `tmp` 的範圍為 0~19
```c
int tmp = (b[i] - '0') + (a[i] - '0') + carry;
carry = tmp / 10;
tmp = tmp % 10;
```
這時透過 [證明](https://hackmd.io/@sysprog/linux2024-quiz3) 可以得知若是要找到一除數 $x$ ，使 $\large \frac{n}{x}$ 直到小數第一位都是精確的，則可列出 $a.b \leq \large \frac{n}{x} \normalsize\leq a.b9$ ， $n$ 代入 19， 其中 $n=ab$ ($a$是十位數， $b$ 為個位數)，則可得到以下
\begin{split}
1.9 \leq \frac{19}{x} \leq 1.99 \Rightarrow 9.55\leq x\leq 10
\end{split}
這時只要找到 $\large \frac{a}{2^N}$ 滿足此範圍的數即可，即 $\large \frac{128}{13} \normalsize\approx 9.84$，也就是說將 `x*1/10` 近似為 `x*13/128`
原程式碼中的`tmp/10` 分解成 $\large \frac{tmp*13}{8} \normalsize\times 8\times \large\frac{1}{128}$，此時$\large \frac{tmp*13}{8}$ 就會等於$\large \frac{tmp}{8} \normalsize+ \large\frac{tmp}{2} \normalsize+tmp$ 對應的程式碼為
```c
(tmp >> 3) + (tmp >> 1) + tmp
```
接著再乘以 8
```
(((tmp >> 3) + (tmp >> 1) + tmp) << 3)
```
此時可以發現在進行 right shift 時會遺失最低的 3 個位元(餘數部分)，所以需要預先保存最低的三個位元後加回去
```c
d0 = q & 0b1;
d1 = q & 0b11;
d2 = q & 0b111;
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2)
```
最後除以 128 即完成求出商數的部分
```c
q = ((((tmp >> 3) + (tmp >> 1) + tmp) << 3) + d0 + d1 + d2) >> 7;
```
求餘數的部分則簡單由 `tmp` 減去商數乘以 $10$ ，也就是 $(q\times4+q)\times2$
```c
r = tmp - (((q << 2) + q) << 1);
```
最後包裝成題目的程式碼如以下
```c
#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> 3);
*mod = in - ((q & ~0x7) + (*div << DDDD));
}
```
首先 `uint32_t x = (in | 1) - (in >> 2)` 部分，當 `in` 為**偶數**時會需要做 `+1` ，
\begin{split}
x = \frac{3(in+1)}{4}
\end{split}
當 `in` 為**奇數**時，
\begin{split}
x = \frac{3in}{4}
\end{split}
接著 `uint32_t q = (x >> 4) + x;`，當 `in` 為**偶數**時，
\begin{split}
q = \frac{3(in+1)}{4} + \frac{3(in+1)}{64} = \frac{51(in+1)}{64}
\end{split}
當 `in` 為**奇數**時，
\begin{split}
q = \frac{3in}{4} + \frac{3in}{64} = \frac{51\ in}{64}
\end{split}
此時若是 $q < 128$ ，則 `q = (q >> 8) + x;` 可以等價為 `q = x`，也就是 `q` 不變，假設 `in` 為奇數，`(q >> 3)` 會等價於 $\large\frac{51\times in}{64} \times \frac{1}{8}$ 即可取得商數
若是 $q > 128$ 則會透過 `q = (q >> 8) + x;` ，假設 `in` 為奇數，可以將 $\large\frac{51\ in}{64} \normalsize\approx 0.797in$ 逼近至 $0.8in$
最後取餘數程式碼 `*mod = in - ((q & ~0x7) + (*div << 1));` 即為 `*div * 10` ，其中 `q & ~0x7` 目的是保留最後三個 bits 以外的位元，等同於 `*div << 3`
### 測驗三
此題為計算 `log2` ，版本一即是將數字不斷右移來找到最高位元為 1 的位元，即為 `log2` 的答案，版本二則是透過二分搜尋法的方式找尋
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
或者直接使用 `__builtin_clz` 找到第一個 `set bit` 的位置，再由 31 減去他即可求得答案
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v));
}
```
### 測驗四
**EWMA** 實作，其為一種取平均的統計方法，獲取資料所經過的時間越久則權重越低，以下為其定義
$$
S_t = \left\{
\begin{array}{l}
Y_0& t = 0 \\
\alpha Y_t + (1 - \alpha)\cdot S_{t-1}& t > 0 \\
\end{array}
\right.
$$
首先程式碼的結構體部分如以下，`internal` 是用來記錄當前時間的 `ewma` ，`weight` 為 $\alpha$ ，由 [vax-r](https://hackmd.io/@vax-r/linux2024-homework4) 的說明讓我了解到 `factor` 的作用為定點數運算的縮放係數，用來控制小數點精度的，可以將原先為小數的數字放大
```c
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
接著以下
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
若略過定點數運算 `avg->factor` 的影響，使 `val` 直接對應到 $Y_t$，接著觀察程式碼可以得出以下，
$$
S_t = \cfrac{(S_{t-1}\cdot2^{weight}-S_{t-1}) + Y_t}{2^{weight}} = (1 - \cfrac{1}{2^{weight}})S_{t-1} + \cfrac{1}{2^{weight}}Y_t
$$
由上可知 $\alpha = \cfrac{1}{2^{weight}}$
### 測驗五
此題為計算 $\log_2(x)$ ，以下為程式碼
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
x--;
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
return (r | shift | x > 1) + 1;
}
```
程式碼目標是找到輸入 `x` 的第一個 set bit 的位置，使用的方法類似 [測驗三](https://hackmd.io/ykolfUApTJKPclk2rHE1kw?view#%E6%B8%AC%E9%A9%97%E4%B8%89) 透過依序檢查輸入 `x` ，先判斷 x 有無大於 $2^{16}$ ，若有則將 `x` 右移 16 個位元並紀錄 `r` 為最高位元的位置，其中因為 `r` 和 `shift` 都是 2 的指數，所以 `r | shift` 會等效為 `r + shift`
`(r | shift | x > 1)` 部分因為判斷 `x > 0x3` 時若是 `x` 為 `0x2` 或是 `0x3` 會少一，所以才需要 `x > 1` ，最前面需要執行 `x--` 是因為當 `x` 為 2 的冪次方時會比正確答案多一，所以需要先減一避免此情況發生
## 第四週測驗
### 測驗三
#### 程式碼原理
首先可以看到 XTree 的結構組成如下，`hint` 可由程式碼推測出其紀錄該節點的子樹高
```c
struct xt_node {
short hint;
struct xt_node *parent;
struct xt_node *left, *right;
};
```
`void xt_destroy(struct xt_tree *tree)` : 遞迴呼叫 `__xt_destroy()` 將整棵樹刪除
`struct xt_node *xt_first(struct xt_node *n)` : 尋找節點 n 子樹中最左側的節點
`struct xt_node *xt_last(struct xt_node *n)` : 尋找節點 n 子樹中最右側的節點
`static inline void xt_rotate_left(struct xt_node *n)` : 對節點 n 進行左旋，以下是左旋的說明
1. 假設對節點 n 進行**左旋**
```graphviz
digraph order
{
rankdir=TB
{rank=TB p}
{rank=TB n l}
{rank=same l r}
{rank=same rl rr}
p->n
n->l
n->r
r->rr
r->rl
}
```
2. 接著進行以下操作
```
xt_parent(r) = xt_parent(n);
xt_right(n) = xt_left(r);
```
```graphviz
digraph order
{
rankdir=TB;
{rank=TB p}
{rank=TB n l}
{rank=same ll lr}
p->n
l->ll
l->lr
p->l
n->r
n->lr
n->l [style=invis];
}
```
3. 接著進行以下操作
```
xt_parent(n) = l;
xt_right(l) = n;
```
並進行最後調整，如果 p 存在並且 n 是 p 的左子節點，則設定 l 為 p 的左子節點，反之則設定為右節點
```graphviz
digraph order
{
rankdir=TB;
{rank=TB p}
{rank=same ll lr}
l->ll
l->n
p->l
n->r
n->lr
}
```
`static inline void xt_rotate_right(struct xt_node *n)` : 對節點 n 進行右旋，以下是旋轉的方式
1. 假設對 n 節點進行**右旋**
```graphviz
digraph order
{
rankdir=TB
{rank=TB p}
{rank=TB n l}
{rank=same l r}
{rank=same rl rr}
p->n
n->l
n->r
r->rl
r->rr
}
```
2. 接著進行以下操作
```
xt_parent(r) = xt_parent(n);
xt_right(n) = xt_left(r);
```
```graphviz
digraph order
{
rankdir=TB
{rank=TB p}
{rank=TB n l}
{rank=same l r}
{rank=same rl rr}
p->n
n->l
p->r
n->rl
r->rl
r->rr
}
```
3. 接著進行以下操作
```
xt_parent(n) = r;
xt_left(r) = n;
```
並進行最後調整，如果 p 存在並且 n 是 p 的左子節點，則設定 l 為 p 的左子節點，反之則設定為右節點
```graphviz
digraph order
{
rankdir=TB
{rank=TB p}
{rank=TB n l}
{rank=same rl rr}
n->l
p->r
n->rl
r->n
r->rr
}
```
`static inline int xt_balance(struct xt_node *n)` : 計算節點 n 的左右子樹差值
`static inline void xt_update(struct xt_node **root, struct xt_node *n)` : 計算節點 n 的左右子樹的樹高差值 `hint` 後，當小於負一時對其進行右旋，大於一時進行左旋，最後當 `hint` 值有改變或是差值為 0 ，則繼續對 `n` 的親代節點執行 `xt_update`
`int xt_insert(struct xt_tree *tree,void *key)` : 建立一個新節點並賦值為 key ，首先利用 `__xt_find` 找尋是否已經有相同 key 的節點，若有則取消插入，若不存在，則繼續判斷樹是否為空，若非空可則由 `__xt_find` 回傳找到 `key` 應擺放的位置進行插入並使用 `xt_update` 進行更新，若樹為空則建立一個樹並將新節點設定為根節點
`int xt_remove(struct xt_tree *tree, void *key)` : 此為刪除值為 key 的節點，首先利用 `xt_find` 呼叫 `__xt_find2` 找出該節點位置，接著利用 `__xt_remove` 來移除該節點，以下為 `__xt_remove` 的說明
當要刪除的節點存在右子樹時，會先找到右子樹的最左節點，並使用 `xt_replace_right` 來替代 `del` 的位置，若右子樹不存且左子樹存在時，則找到左子樹中最右邊的節點，並使用 `xt_replace_left` 來替代 `del` ，若 `del` 為 leaf node 則直接刪除。
```c
static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
if (xt_right(del)) {
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, least);
xt_update(root, xt_right(least));
return;
}
if (xt_left(del)) {
struct xt_node *most = xt_last(xt_left(del));
if (del == *root)
*root = most;
xt_replace_left(del, most);
xt_update(root, xt_left(most));
return;
}
if (del == *root) {
*root = 0;
return;
}
/* empty node */
struct xt_node *parent = xt_parent(del);
if (xt_left(parent) == del)
xt_left(parent) = 0;
else
xt_right(parent) = 0;
xt_update(root, parent);
}
```
#### 原始 XTree 與紅黑樹及 AVL 樹比較
**AVl Tree** 的基本定義 : $|左子樹高度 - 右子樹高度| \leq 1$
AVL tree 保證左右子樹的高度差距不大於 1，與 Xtree 相同，不同的是 AVL tree 透過平衡因子（左子樹高度減去右子樹高度）判斷，而 Xtree 則是透過結構體中的 `hint` 儲存子樹高度，再分別利用左子樹及右子樹的 `hint` 來計算高度差，最後在高度差的絕對值大於一時對二元樹進行旋轉，恢復二元樹的平衡，而此兩種二元樹在插入並進行平衡時，至多皆不大於兩次旋轉，不同的地方是，AVL tree 在旋轉後只須更新受影響節點的平衡因子，而 Xtree 則須更新該節點的親代節點至根節點的樹高，AVL tree 在搜尋、插入以及刪除節點的時間複雜度皆為 $O(\log n)$
**紅黑樹**的基本定義如下
1. 所有節點非黑即紅
2. 根節點(root) 為黑色
3. 所有葉節點 (leaf) 一定要為黑色的空值 (NULL)
4. 紅色節點的子節點必須為黑色
5. 從任何節點出發，其下至葉節點所經過的黑色節點數目要相同
以上性質確保了從根節點到任何葉節點的最常路徑步超過最短路徑的兩倍，另外根據 [Red-Black Trees](https://www.usna.edu/Users/cs/crabbe/SI321/current/red-black/red-black.html) ，紅黑樹在插入的時間複雜度表現中，尋找、插入以及刪除節點的複雜度皆為 $O(\log n)$
由以上結果可以得知紅黑數和 AVL tree 平均時間複雜度都是 $O(\log n)$，其中 AVl tree（左右子樹的高度相差不超過 1）較紅黑樹（最長路徑$\leq$ 2 倍最短路徑）平衡，在搜尋以樹高作為上限的操作下，AVL 樹會比紅黑樹略快，但由於 AVL 樹比紅黑樹要平衡，因此在平衡自身所花費的時間上 AVL 樹所花費的時間較多，所以在插入以及移除的操作下紅黑數的表現較優，紅黑樹的優點在平衡自己時達到 $O(1)$（最多 3 次旋轉） 的複雜度
為了將 XTree 與紅黑樹以及 AVL 樹進行比較，我選擇先參考 [var-x](https://github.com/vax-r/bitwise_lab/tree/master/xtree) 完成的部份程式碼，包含新增 Linux 核心 red-black tree 以及修改測試程式碼 `treeeint.c`
> [commit ee87959](https://github.com/rain20010126/xtree/commit/ee87959f190f46848219f1f33ed2a328ded0fdd2)
接著我加入了以 [AVL Tree Program in C ](https://www.javatpoint.com/avl-tree-program-in-c) 作為 AVL tree 的實作程式，新增了判斷樹高的函式，修改其 `insert` 的方法，其中遇到已經存在的數值則放棄該次的插入，並新增搜尋和刪除節點的函式
> [commit 664f66d](https://github.com/rain20010126/xtree/commit/664f66dfe3d37c2382b56d087c512ca61a87e297)
Linux 核心 red-black tree 與原始 XTree 的比較結果如下，我做了 100 0個與100 個循序輸入以及亂序輸入進行較，但在 1000 個亂序輸入中，我實作的 AVL tree 會因為過多遞迴呼叫造成 segmentation fault ，因此沒有紀錄該項結果，以下為比較實驗結果的比較
```
$ ./treeint 100 0
Red-Black Tree
Average insertion time : 73.230000
Average find time : 25.210000
Average remove time : 23.460000
XTree
Average insertion time : 163.420000
xtree root hint: 7
Average find time : 67.720000
Average remove time : 93.920000
AVLTree
Average insertion time : 134.070000
AVL Tree height : 7
Average find time : 54.790000
Average remove time : 17.480000
$ ./treeint 100 1
Red-Black Tree
Average insertion time : 489.770000
Average find time : 179.150000
Average remove time : 182.860000
XTree
Average insertion time : 798.090000
xtree root hint: 7
Average find time : 397.570000
Average remove time : 568.260000
AVLTree
Average insertion time : 801.780000
AVL Tree height : 7
Average find time : 320.740000
Average remove time : 89.760000
$ ./treeint 1000 0
Red-Black Tree
Average insertion time : 56.809000
Average find time : 24.193000
Average remove time : 20.390000
XTree
Average insertion time : 170.880000
xtree root hint: 10
Average find time : 151.556000
Average remove time : 128.427000
AVLTree
Average insertion time : 199.649000
AVL Tree height : 10
Average find time : 99.862000
Average remove time : 15.601000
$ ./treeint 1000 1
Red-Black Tree
Average insertion time : 60.134000
Average find time : 56.318000
Average remove time : 38.448000
XTree
Average insertion time : 189.222000
xtree root hint: 11
Average find time : 178.042000
Average remove time : 152.549000
```
另外我新增了 `find_rbtree_height.c` 來判斷循序和亂序輸入 100 和 1000 個節點的最短路徑和最長路徑，其中亂序輸入所得到的輸入順序是藉由測試程式碼 `treeint.c` 所得到的，與其他二元樹的輸入相同
> [commit d044842](https://github.com/rain20010126/xtree/commit/d044842f77f20d052544c5cd043699647e764ca4)
```
Minimum depth of the red-black tree for sequential input 100 nodes: 6
Maximum depth of the red-black tree for sequential input 100 nodes: 11
Maximum depth of the red-black tree for random input 100 nodes: 7
Minimum depth of the red-black tree for random input 100 nodes: 5
Minimum depth of the red-black tree for sequential input 1000 nodes: 9
Maximum depth of the red-black tree for sequential input 1000 nodes: 17
Minimum depth of the red-black tree for random input 1000 nodes: 7
Maximum depth of the red-black tree for random input 1000 nodes: 11
```
可以觀察到結果與前面所提到的優缺點有衝突，我推測是因為 Linux 核心的紅黑樹較一般紅黑樹少了一層的間接操作，並擁有更好的 cache locality，而我簡單實作的 AVL tree 上有很大的改進空間，造成實際測試無法呈現出 AVL tree 的優勢
#### 改進 XTree
由結構上的相似度判斷，XTree 較接近 AVL tree，XTree 利用 hint 來評估樹是否要旋轉，在AVL tree 中，為了判斷二元樹的平衡程度，這時可以利用平衡因子判別是左傾或右傾 ，計算方式為左子樹高度減去右子樹高度(深度)，當平衡因子小於 -2 或大於 2 時，需要進行旋轉，共有四種旋轉方式分別為: LL、RR、LR、RL ，而我們可以觀察到在 XTree 中只有兩種旋轉方式，這時可以發現由節點 n 往上檢查左右子樹相差有無大於 1 ，檢查到節點 a 時發現其左子樹高較右子樹高 2，因此會對節點 a 進行右旋
```graphviz
digraph order
{
rankdir=TB;
{rank=TB a}
{rank=TB b c}
{rank=TB d e}
a->b
a->c
b->d
b->e
e->n
}
```
對節點 a 進行旋轉後如下，可以發現節點 a 的左右子樹差沒有減少
```graphviz
digraph order
{
rankdir=TB;
{rank=TB b}
{rank=TB d a}
{rank=TB d e}
b->d
b->a
a->e
e->h
a->c
}
```
因為 XTree 同樣是利用一個節點的左右子樹差來進行旋轉，使用 AVL Tree 的旋轉方式可以解決以上問題，也就是分成不平衡的類型 RR, RL, LR, LL 四種，並按照不同的情況進行相對應的旋轉，以下是修改的差異
```diff
if (b < -1)
{
/* leaning to the right */
+ if (xt_balance(xt_right(n)) > 0)
+ xt_rotate_left(xt_right(n));
if (n == *root)
*root = xt_right(n);
xt_rotate_right(n);
}
else if (b > 1)
{
/* leaning to the left */
+ if (xt_balance(xt_left(n)) < 0)
+ xt_rotate_right(xt_left(n));
if (n == *root)
*root = xt_left(n);
xt_rotate_left(n);
}
```
接著我使用與先前相同的實驗方式對修正後的 XTree 進行比較，以下是比較的結果呈現
```
$ ./treeint 100 0
XTree
Average insertion time : 481.930000
xtree root hint: 7
Average find time : 292.390000
Average remove time : 531.520000
$ ./treeint 100 1
XTree
Average insertion time : 182.860000
xtree root hint: 6
Average find time : 264.140000
Average remove time : 115.140000
$ ./treeint 1000 0
XTree
Average insertion time : 181.901000
xtree root hint: 10
Average find time : 89.020000
Average remove time : 99.623000
$ ./treeint 1000 1
XTree
Average insertion time : 199.487000
xtree root hint: 10
Average find time : 114.791000
Average remove time : 150.443000
```
從以上亂數輸入的實驗結果中可以發現，相比於修改前的結果，修改過後的 Xtree 在樹高部份（Xtree hint）都有減少，在亂序輸入 100 個節點中 hint 從 7 下降為 6 ，而在亂序輸入 1000 個節點中 hint 從 11 下降為 10 ，另外我實際建立一個 Xtree 來更好的比較修改前及修改後樹的自平衡能力，其中我依序插入以下節點 [1000, 500, 300, 0, 400, 350, 450, 425, 475, 460]後
修正前的 XTree 結構如下
```graphviz
digraph structs {
rankdir=TB;
node[shape=circle];
struct0 [label= "300"];
struct1 [label= "0"];
struct2 [label= "400"];
struct3 [label= "350"];
struct4 [label= "500"];
struct5 [label= "450"];
struct6 [label= "1000"];
struct7 [label= "425"];
struct8 [label= "475"];
struct9 [label= "460"];
struct10 [style=invis];
struct0->struct1;
struct0->struct2;
struct2->struct3;
struct2->struct4;
struct4->struct5;
struct4->struct6;
struct5->struct7;
struct5->struct8;
struct8->struct9;
struct8->struct10[style=invis];
}
```
修改後的結構如下
```graphviz
digraph order
{
400->300
400->475
300->0
300->350
475->450
475->500
450->425
450->460
500->1000
}
```
修改前的樹高：6
修改後的樹高：4
透過以上結果可以發現解決了先前我們所提到的無效旋轉的問題，使 XTree 更加平衡，同時因為樹高的減少，在搜尋所花費的時間上也有大幅下降
Sign in with Wallet
Connect another wallet