# 2024q1 Homework4 (quiz3+4)
contributed by [< `HenryChaing` >](https://github.com/HenryChaing/quiz3-4)
## [第三週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
## 測驗二
> 參考： [CA2023-Lab02](https://hackmd.io/@sysprog/SJAR5XMmi), [rv32emu](https://github.com/sysprog21/rv32emu)
### CPU 週期數量
在測驗二當中共有兩種不使用除法及模數運算來得到商及餘數的方法，我們會針對這兩種方法進行分析，分別會分析他們的組譯結果以及執行時所需要的 CPU 週期。
在分析中我所使用到的工具為 [rv32emu](https://github.com/sysprog21/rv32emu) , GNU toolchain ，我們會分析經由跨平台編譯器組譯後的 RISC-V 組合語言程式，以及在 rv32emu 運行時程式在模擬器當中所使用的時脈週期數量。
#### riscv-none-elf-gcc , riscv-none-elf-objdump
首先 `riscv-none-elf-gcc` 是我們的跨平台編譯器，透過我們給定的 C 語言原始碼，它可以幫我們組譯成目標檔或是編譯成 `elf` 執行檔。為了分析編譯後的結果，我們會利用 `riscv-none-elf-objdump` 幫我們從執行檔中的機器碼還原顯示成 RISC-V 組合語言程式。
#### RISC-V 組合語言程式
- [ ] 運用除法運算的程式碼
```shell
$ riscv-none-elf-objdump -d mod3_v1.o
mod3_v1.o: file format elf32-littleriscv
Disassembly of section .text:
00000000 <divmod_10>:
0: ff010113 add sp,sp,-16
4: 00812423 sw s0,8(sp)
8: 00058413 mv s0,a1
c: 00a00593 li a1,10
10: 00112623 sw ra,12(sp)
14: 00912223 sw s1,4(sp)
18: 01212023 sw s2,0(sp)
1c: 00060493 mv s1,a2
20: 00050913 mv s2,a0
24: 00000097 auipc ra,0x0
28: 000080e7 jalr ra # 24 <divmod_10+0x24>
2c: 00a42023 sw a0,0(s0)
30: 00a00593 li a1,10
34: 00090513 mv a0,s2
38: 00000097 auipc ra,0x0
3c: 000080e7 jalr ra # 38 <divmod_10+0x38>
40: 00a4a023 sw a0,0(s1)
44: 00042583 lw a1,0(s0)
48: 00812403 lw s0,8(sp)
4c: 00c12083 lw ra,12(sp)
50: 00412483 lw s1,4(sp)
54: 00012903 lw s2,0(sp)
58: 00050613 mv a2,a0
5c: 00000537 lui a0,0x0
60: 00050513 mv a0,a0
64: 01010113 add sp,sp,16
68: 00000317 auipc t1,0x0
6c: 00030067 jr t1 # 68 <divmod_10+0x68>
Disassembly of section .text.startup:
00000000 <main>:
0: fe010113 add sp,sp,-32
4: 00812c23 sw s0,24(sp)
8: 01212823 sw s2,16(sp)
c: 01312623 sw s3,12(sp)
10: 00112e23 sw ra,28(sp)
14: 00912a23 sw s1,20(sp)
18: 00000413 li s0,0
1c: 000009b7 lui s3,0x0
20: 01300913 li s2,19
00000024 <.L5>:
24: 00a00593 li a1,10
28: 00040513 mv a0,s0
2c: 00000097 auipc ra,0x0
30: 000080e7 jalr ra # 2c <.L5+0x8>
34: 00050493 mv s1,a0
38: 00a00593 li a1,10
3c: 00040513 mv a0,s0
40: 00000097 auipc ra,0x0
44: 000080e7 jalr ra # 40 <.L5+0x1c>
48: 00050593 mv a1,a0
4c: 00048613 mv a2,s1
50: 00098513 mv a0,s3
54: 00140413 add s0,s0,1
58: 00000097 auipc ra,0x0
5c: 000080e7 jalr ra # 58 <.L5+0x34>
60: fd2412e3 bne s0,s2,24 <.L5>
64: 01c12083 lw ra,28(sp)
68: 01812403 lw s0,24(sp)
6c: 01412483 lw s1,20(sp)
70: 01012903 lw s2,16(sp)
74: 00c12983 lw s3,12(sp)
78: 00000513 li a0,0
7c: 02010113 add sp,sp,32
80: 00008067 ret
```
- [ ] 運用右移運算替代除法之程式
```shell
$ riscv-none-elf-objdump -d mod3_v2.o
mod3_v2.o: file format elf32-littleriscv
Disassembly of section .text.startup:
00000000 <main>:
0: ff010113 add sp,sp,-16
4: 00812423 sw s0,8(sp)
8: 00912223 sw s1,4(sp)
c: 01212023 sw s2,0(sp)
10: 00112623 sw ra,12(sp)
14: 00000413 li s0,0
18: 00000937 lui s2,0x0
1c: 01400493 li s1,20
00000020 <.L2>:
20: 40145793 sra a5,s0,0x1
24: 40345593 sra a1,s0,0x3
28: 00f585b3 add a1,a1,a5
2c: 008585b3 add a1,a1,s0
30: 00359593 sll a1,a1,0x3
34: 0075d593 srl a1,a1,0x7
38: 40b00633 neg a2,a1
3c: 00567613 and a2,a2,5
40: 00161613 sll a2,a2,0x1
44: 40c40633 sub a2,s0,a2
48: 00090513 mv a0,s2
4c: 00140413 add s0,s0,1
50: 00000097 auipc ra,0x0
54: 000080e7 jalr ra # 50 <.L2+0x30>
58: fc9414e3 bne s0,s1,20 <.L2>
5c: 00c12083 lw ra,12(sp)
60: 00812403 lw s0,8(sp)
64: 00412483 lw s1,4(sp)
68: 00012903 lw s2,0(sp)
6c: 00000513 li a0,0
70: 01010113 add sp,sp,16
74: 00008067 ret
```
這是還未經過連結器的目標檔還原成 RISC-V 程式碼的結果，這些程式的目的皆是處理 `0~19` 對整數十進行除法運算。以下方程式來說重點在位址 `0x20 ~ 0x48` ，這裡是處理除法的段落，因此可以推斷在進行一次除法運算需要這 11 個指令，會比上方除法運算要快上許多。
#### rv32emu
接著要看實際運行狀況，我們會讓可以運行 `elf` 執行檔的 rv32emu 來運行上方編譯完成的兩個執行檔。為了得到正確的時脈週期，這裡會加入由 `getcycle.S` 提供組合語言撰寫成的時間函式，得到各自進行 20 次除法運算後所使用到的時脈週期。
- [ ] 運用除法運算
```shell
cycle count: 26417
inferior exit code 0
```
- [ ] 運用右移運算替代除法
```
cycle count: 25892
inferior exit code 0
```
可能是二十次測驗效果還不夠顯著，但運用右移運算只須原本除法運算 ${\dfrac{98}{100}}$ 所使用的時脈週期。
### mod5 實作
> 參考： [Modulus without Division](https://homepage.cs.uiowa.edu/~dwjones/bcd/mod.shtml)
在這項實作中，我們會先處理模 15 的運算，再得到模 5 的結果。
在參考中有提到，針對 ${2^n -1}$ 的模數運算，我們可以將其改成這項對計算機友善的公式：
${a \mod (2^n-1) = ( \ (a/2^n) + (a \mod 2^n) \ ) \mod\ (2^n-1)}$
其中除以 $2^n$ 之運算可以替換為右移 $n$ ， $mod$ 運算也可以用 `&` 運算達成。但由於 ${(a/2^n) + (a \mod 2^n)}$ 並未必小於 ${2^n -1}$，因此這項運算須重複至原本 $a$ 可能之最大值也須小於 ${2^n -1}$ ，再者這項運算等同於計算 $a$ 以二進位表示時 1 的數量，因此我們也可以改變每次位移以及 and 運算的 $n$ 值。
```c
uint32_t mod15( uint32_t a ) {
a = (a >> 16) + (a & 0xFFFF); /* maximun value: 0x1FFFE */
a = (a >> 8) + (a & 0xFF); /* maximun value: 0x2FD */
a = (a >> 4) + (a & 0xF); /* maximun value: 0x3C */
return (a >> 4) + (a & 0xF); /* maximun value: 0xF */
}
```
以上是我在參考範例程式後改寫的版本，可以將模數的範圍縮至 `0~15` 。
```c
uint32_t mod5( uint32_t a ) {
a = (a >> 16) + (a & 0xFFFF); /* maximun value: 0x1FFFE */
a = (a >> 8) + (a & 0xFF); /* maximun value: 0x2FD */
a = (a >> 4) + (a & 0xF); /* maximun value: 0x3C */
a = (a >> 4) + (a & 0xF); /* maximun value: 0xF */
if(a<5)return a;
if(a<10)return a-5;
return a-10;
}
```
由於 ${(a \mod 15)\mod 5 \ \equiv \ a \mod 5}$ ，因此模 5 的函式即是將模 15 後的結果再模 5 ，並且在已知範圍為 `0~15` 之情形下利用簡單的減法減去商達到模數效果。
### mod9 實作
> 參考： [Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)
參考過 `Hacker's Delight` 對於 Remainder by Summing digits 的描述後，我透過它舉證出的公式，利用模同餘不斷減少數字的值，直到接近除數才用條件式判斷後減掉商數的方式得出餘數值。而這裡會著重在介紹模同餘的運算方式。
這次模同餘我主要運用到的是 ${2^6 \equiv 1 \ (mod\ 9)}$ 這項轉換完成。由於這項公式，我可以將 ${n \cdot 2^6 \ (mod\ 9)}$ 直接轉換成 ${n \ (mod\ 9)}$ 。因此 ${[(r \ \& \ 0x003F) + (r \gg 6)]\ (mod\ 9)}$ 會等價於 ${r\ (mod\ 9)}$ ，而經過這個方法的不斷簡化，我將數值縮小到了小於一千的正整數。
最後是透過查表法的方式找到結果，也就是將這近千個整數建立對應到的餘數的陣列，這樣可以大幅減少運算。
> [commit 70103d0](https://github.com/HenryChaing/quiz3-4/commit/70103d0bd5753a96aaf5076277b79cf7acc548c5)
```c
int remu9(unsigned n) {
int r;
static char table[510] = {0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5,6,7,8,
0,1,2,3,4,5,6,7,8, 0,1,2,3,4,5};
r = (n & 0x0FFF) + (n >> 12); // 0 to 1FFFFE.
r = (r & 0x0FFF) + (r >> 12); // 0 to 11FD.
r = (r & 0x0FFF) + (r >> 12); // 0 to 1FE.
return table[r];
}
```
## 測驗三
### 程式碼解說
這些函式的目的是要計算整數取 $\log_2$ 後所得到的數值（小數無條件捨去），因為計算以二為底的對數若只觀察二進位的第一個設定位元 (set bit) ，則對數值剛好會等於該數值以二進位表示的指數值。我們也使用這個特性估算出整數以二為底的對數值。
> [commit ffca224](https://github.com/HenryChaing/quiz3-4/commit/ffca22456f0f89b2d6f3c9405be3a4bcb2e0d36c)
- [ ] 方法一 (line 5)
透過不斷將數值除以二（右位移）的方式，找到二進位數值第一個設定位元的位置，並用變數 `log` 紀錄再回傳對數值。
- [ ] 方法二 (line 15)
假設輸入的數值不為零，則二進位數值可以表示成二的冪數列和，而這個函式會同樣將第一個設定位元移至 `LSB` 的位置，最後回傳對數值。
- [ ] 方法三 (line 41)
這裡直接使用 `GNU C` 中的擴充函式 `clz` ，這個函式可以計算在第一個設定位元前有幾個零，因此我們也用這個函式反推出對數值。
## 測驗四
### 程式碼解說
EWMA 公式： ${S_t = \begin{cases}
α\cdot Y_t\ + \ (1-α)\cdot S_{t-1}, & \text{t > 0} \\
Y_0, & \text{t = 0}
\end{cases}}$
#### 結構變數 ewma
```c
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
這個是用來計算指數加權移動平均所使用到的結構變數， `internal` 紀錄的是當下的平均值， 而 `weight` 是歷史資料加權降低的程度， 最後是公式沒有出現的 `factor` 變數，我認為是可以讓原始資料放大的參數。
#### 結構變數初始化
```c
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
}
```
為了解說接下來 EWMA 每一回合的處理，需要特別注意的是 `weight` 及 `factor` 的成員變數皆經過對數化，為的是方便待會每一回合的平移步驟，省去計算量龐大的乘除法。
#### EWMA 計算
```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;
}
```
這裡應用的就是 EWMA 的公式，函式由於 `weight` 及 `factor` 都經過對數化，所以平移可以視為乘除運算。其中較為特別的是每次資料點會先乘以 `factor` 倍才代入公式當中。還有指數權重較不直觀，但若只觀察資料點會發現指數權重是 $\dfrac{1}{weight}$ ，反之歷史資料的權重是 ${1 - \dfrac{1}{weight}}$ 。
---
### Linux 核心 EWMA 應用
> 部份節錄自 [linux/.../dynack.c](https://github.com/torvalds/linux/blob/master/drivers/net/wireless/ath/ath9k/dynack.c#L145)
我還未研究 git log 因此以下行為視同舉燭。
Linux 核心在 `ath_dynack_compute_to` 這個計算 `station ack time out` 的函式中，採用了 EWMA 的方式來更新 `station ack time out` 的值，而這個 `station` 是用來儲存連線裝置的狀態，每回合計算的 `ack_to` 是由 `ack_ts = ack_ts - st_ts->tstamp - st_ts->dur` 決定。
而 EWMA 更新的公式則是：
${S_t = \dfrac{1}{4} \cdot S_{t-1} \ + \ \dfrac{3}{4} \cdot ackto}$
其中 $S_t$ 代表 `station` 中儲存的 time out 時間。
## 測驗五
### 程式碼解說
```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;
}
```
這個與測驗三中的方法二實作上有相似之處，差別在於採用沒有分支的方式（即沒有 if , while 等組譯後會產生分支的指令），實作方式是會把位移量保留在 `r` 變數當中。
其中 `return` 的值很特別，首先 `r|shift` 是記錄上二行 `shift` 的結果，而 `(x > 1)` 則是再處理 ${x >= 2^0}$ 的案例。而最後的加一要與 `x--` 一同觀察，這裡是在處理對數值無條件進位的地方，加一就是無條件進位的動作，而 `x--` 則是要處理 2 的冪數字的例外。
---
### Linux 核心所應用的 ceil_log2
> 節錄自 [linux/.../thuge-gen.c](https://github.com/torvalds/linux/blob/master/tools/testing/selftests/mm/thuge-gen.c#L51)
```c
int ilog2(unsigned long v)
{
int l = 0;
while ((1UL << l) < v)
l++;
return l;
}
```
應用的場合是在計算任務的粒度 （granularity），因應可用處理器數目的變更而重新計算，因為粒度與可用處理器之間的關係並非線性，因此用 `ilog` 進行模擬。
這個函式功能與測驗五的 `ceil_ilog2` 相同，計算位移的方式同測驗三的方法一，差別在於無條件進位的處理位在進入迴圈的判斷式，除了 2 的冪外它會比方法一還要多算一位，由此來處理無條件進位。
---
## [第四週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)
## 測驗一
### 程式碼解說
```c
int total_hamming_distance(int* nums, int numsSize)
{
int total = 0;;
for (int i = 0;i < numsSize;i++)
for (int j = 0; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
return total >> 1;
}
```
首先兩個迴圈是為了計算每個配對之間的漢明距離，重點在於 `popcount` 以及互斥或， `popcount` 可以計算變數以二進位表示時有多少設置位元，而互斥或則是運用其特性會將對應位置相異的位元設為一，反之則為零。因此每個配對即是將對應位置相異的位元數量做計算，最後儲存到 `total` 變數中。而 `total` 之所以要右移一，則是要刪掉重複比較的配對。
### Total Hamming Distance 改進
> [commit 36ac28c](https://github.com/HenryChaing/quiz3-4/commit/36ac28c91eeebc5af127fa4163f85aae20d8b865)
```c
int hamming_distance_linear(int* nums, int nums_size){
int iteration = 0, distance = 0;
for (__uint32_t i = 1; iteration < 32; i<<=1)
{
int ones = 0;
for (int j = 0; j < nums_size; j++)
{
__uint32_t bin = nums[j];
if((bin & i) == i){
ones++;
}
}
distance += ones*(nums_size-ones);
iteration++;
}
return distance;
}
```
我使用了測驗一最後歸納的方法實作了線性時間複雜度的漢明距離函式。而這個作法的原理是所有整數一起作逐位元觀察，並且將觀察結果加入總和變數，當在觀察第 $n$ 個位元（ $n$ 屬於0到31）時，我們會統計所有整數中設置位元的數量（$s$），對每一個設置位元來說與其相異的位元共有 $size-s$ 個（$size$ 為陣列長度），因此對這個整數來說漢明距離共增加 $size-s$ ，並且這樣的整數共有 $s$ 個，因此這回合漢明距離共增加 ${s * (size-s)}$，而這樣的計數共要進行 $n$ 回合。
接著來計算時間複雜度，引用剛才的變數，時間複雜度可記為 $O(n \times size)$ ，其中 $n$ 為常數 32 ， 因此時間複雜度可簡化為 $O(size)$ ，所以這是個執行時間與整數陣列大小有關的函式。
## 測驗二
### 程式碼解說
#### 模 3 運算
```c
static inline int mod3(unsigned n)
{
static char table[33] = {
2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1,
};
n = __builtin_popcount(n ^ 0xAAAAAAAA);
return table[n];
}
```
這裡不解釋作者已經舉證出的模三可以透過 ${popcount(n \oplus 0xAAAAAAAA) -1}$ 來簡化數字成接近模數結果的值 ${\ result + 3t}$ ($t$ 屬於整數)， 為了直接得到 $result$ ，我們現在已知經過位元總和運算後， $n$ 會介於 `0~32` ，為了避免加入不必要的運算，我們透過查表法來解決找到 $result$ 的問題。
為了方便理解查表法以及作者的公式，我將程式碼改成如下等價表示：
```c
static inline int mod3(unsigned n)
{
static char table[33] = {
0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0,
1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2,
};
n = __builtin_popcount(n ^ 0xAAAAAAAA) -1;
return table[n];
}
```
透過作者的公式可知，經過位元總和的運算後 $n$ 為 ${\ result + 3t}$ ($t$ 屬於整數) 並且介於 `0~32` ，因此我們建立了對應這 33 個數字之餘數陣列，可以直接從陣列找到這個數字對應的餘數。
## 測驗三
### 程式碼解說
> [Xtree code](https://gist.github.com/jserv/7374b3e031ec3a81441b1b93b008c5d2)
首先這棵樹是一棵二元搜尋樹，也有樹基本的插入、刪除操作，也有相似於高等平衡樹的地方，例如紀錄平衡值的 `hint` 值，以及平衡樹的旋轉操作。其中旋轉操作在對樹進行插入及刪除等會變更樹結構的操作時會觸發。
### 程式碼改進
> [commit ce1067e](https://github.com/HenryChaing/quiz3-4/commit/ce1067e2a1c201e156eecb6229f4075a35947898)
我發現之問題如下，可能是我理解錯誤，但觀察程式碼時發現旋轉的操作並未減少樹高，也就是沒有達到平衡的目的。 Xtree 中的旋轉分成兩個案例，分別是左傾以及右傾，他們分別對應到 AVL Tree 中的 `LL` 以及 `RR` 案例。但是這樣會產生一個缺點，也就是 AVL Tree 中的 `LR` 以及 `RL` 案例發生時，旋轉也會執行但是對樹的平衡沒有幫助（高度不變且依舊不平衡）
- [ ] Xtree (初始狀態)
```graphviz
digraph BST {
node [fontname="Arial" ];
l1 [ label = "5" ];
l21 [ label = "2" ];
l22 [ label = "6" ];
l31 [ label = "1" ];
l32 [ label = "4" ];
l1 -> { l21 l22 };
l21 -> { l31 l32 };
}
```
- [ ] 插入值 3 節點
```graphviz
digraph BST {
node [fontname="Arial" ];
l1 [ label = "5" ];
l21 [ label = "2" ];
l22 [ label = "6" ];
l31 [ label = "1" ];
l32 [ label = "4" ];
l41 [ label = "3" ]
l42 [ shape = plain label = "null" ]
l1 -> { l21 l22 };
l21 -> { l31 l32 };
l32 -> { l42 l41 };
}
```
- [ ] 對 5 進行旋轉
```graphviz
digraph BST {
node [fontname= "Arial" ];
l1 [ label = "2" ];
l21 [ label = "1" ];
l22 [ label = "5" ];
l31 [ label = "4" ];
l32 [ label = "6" ];
l41 [ label = "3" ];
l42 [ shape = plain label = "null" ]
l1 -> { l21 l22 };
l22 -> { l31 l32 };
l31 -> { l41 l42 };
}
```
這項插入對 Xtree 造成左傾的不平衡，因此會進行旋轉調整，但是觀察結果會發現樹從左傾變成了右傾，並且高度也不變。而之所以會產生這個結果是因為 `LL` 所對應的旋轉方式無法解決 `LR` 案例的不平衡。
#### 解決方式-引入新的旋轉方式
於是我引入了 AVL Tree 使用的`LR` 及 `RL` 案例所對應的旋轉方式，這項改動雖然有助於樹的平衡，理想上讓插入、刪除、尋找的時間複雜度正比於二元完整樹樹高，也就是 $O(logn)$ 。但實際上插入以及刪除時間成本應該會上升，因為旋轉的操作變得更為複雜，這再接下來的結果分析會看出明顯結果，需要旋轉的插入以及刪除會比沒有旋轉發生的案例執行時間多上近 5 倍。
- [ ] 對 5 進行旋轉 （改善後）
```graphviz
digraph BST {
node [fontname= "Arial" ];
l1 [ label = "4" ];
l21 [ label = "2" ];
l22 [ label = "5" ];
l31 [ label = "1" ];
l32 [ label = "3" ];
l41 [ label = "6" ];
// l42 [ shape = plain label = "null" ]
l1 -> { l21 l22 };
l21 -> { l31 l32 };
l22 -> { l41 };
}
```
### XTree 對 AVL Tree 的效能評比
為了能與 XTree 進行效能比較，我親手實作了一棵 AVL Tree ，相對應的 git commit 有附上相關程式進行測試，包括基本的插入、刪除、搜尋操作，不過進行效能評比時也有發生過幾次刪除失誤，因此刪除操作尚有待加強。
- [ ] 亂序插入
我們先測試對兩棵樹亂序插入，以下測試結果符合我們對兩者的預測，其中（$\uparrow$ XTree, $\downarrow$ AVL Tree），因為 XTree 較不常發生旋轉，相對於經常需要旋轉調整的 AVL Tree ，插入及刪除的成本平均要低上許多。但是在搜尋方面， AVL Tree 由於樹高接近於 $logn$ （ $n$ 為節點數），所以平均的搜尋成本會比 XTree 要低。
```shell
$ ./build/treeint 10 3
----- Insert -----
320,286,132,110,52,48,46,89,34,31,
185,335,432,177,257,358,179,131,189,259,
----- Find -----
116, 51, 36, 42, 28, 33, 23, 40, 48, 32,
66, 41, 30, 21, 22, 26, 40, 28, 28, 31,
----- Remove -----
198, 63, 33, 23, 103, 22, 86, 51, 21, 22,
89, 497, 30, 148, 29, 61, 134, 43, 35, 29,
```
- [ ] 循序插入
其實效果與亂序插入看不出明顯的差別，但是循序插入的優點在於我們可以用紙筆追蹤樹的操作。例如對 AVL Tree 循序插入 1,2,3,4 則在插入3時會旋轉插入4時則因為平衡不會旋轉，也間接觀察到再不旋轉的情況下 XTree 以及 AVL Tree 的插入成本近乎相同。並且在此例中也觀察到搜尋成本 XTree 相對於 AVL Tree 要有更大的起伏。
```shell
$ ./build/treeint 10 0
----- Insert -----
630,368,171,108,170,134,101,103,113,154,
267,449,482,110,263,359,159,108,193,294,
----- Find -----
217, 99, 168, 53, 73, 44, 39, 38, 44, 42,
84, 52, 50, 42, 82, 39, 46, 33, 36, 45,
----- Remove -----
369, 98, 100, 157, 121, 70, 75, 124, 152, 83,
309, 717, 127, 143, 91, 79, 145, 85, 94, 118,
```
Sign in with Wallet
Connect another wallet