測驗

$\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 快一些。

討論設計和實作缺失。

jserv

測驗

$\alpha -3$

---

測驗

$\beta -1$

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

測驗

$\beta -2$

測驗

$\gamma -1$

測驗

$\gamma -2$

測驗

$\gamma -3$