## 測驗 $\alpha-1$

此程式為 S-tree 的 implementation，一種 self-balancing BST，試著用 hint (類似 AVL tree 的 height) 估計子樹高度以平衡。

S-tree 在 插入節點 (`st_insert`) 後會對該節點做 `st_update` 以平衡(左旋或右旋)以及更新 hint 值 (`max(left hint, right hint)+1`)。只要該節點不為 `root` 且該節點的 hint 值和平衡前一樣，就會對該節點的 parent 繼續做 update。

移除節點 (`st_remove`) 則會依照要移除的節點有不同行為:
- 有 right child: 和 right child subtree 的 first node (successor) 交換 value 並移除，再對 successor 的 right child 做 update
- 沒有 right child，有 left child: 和 left child subtree 的 last node (predecessor) 交換 value 並移除，再對 predecessor 的 left child 做 update
- 都沒有: 直接移除並對其 parent 做 update

`__treeint_dump` 中，填空位置為 `st_left(n)` 及 `st_right(n)`，即為走訪樹時先走訪左子樹，再走訪當前節點，再走訪右子樹。

## 測驗 $\alpha-2$

和 AVL tree 相比，S-tree在做完平衡後還是有可能左右子樹高度差 2 的情況 (AVL 最多為 1)，但確保每個節點 update 只會做一次左旋或右旋，不用像 AVL tree 判斷 4 種旋轉的狀況。
AVL tree 通常不需要維護 parent。

和 red-black tree 相比，S-tree 不會到樹高是 2 倍的情況，因此 lookup time 會比 red-black tree 快一些。

:::warning
討論設計和實作缺失。
:notes: jserv
:::

## 測驗 $\alpha-3$

---

## 測驗 $\beta-1$

此程式會將 sz 向上取成 alignment 的倍數。
如果 alignment 是 2 的次方，則可以用 `(sz + mask) & ~mask` 操作達到一樣的效果，不需要用到除法。

## 測驗 $\beta-2$
## 測驗 $\gamma-1$
## 測驗 $\gamma-2$
## 測驗 $\gamma-3$