contributed by < kart81604 > 開發環境 $ gcc -version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual

Linux 核心為何替換 avl tree 為 rbtree? AVL tree 在大量執行 insert 、remove 的情況下，會大量執行 rotate 來維持平衡，相比於 AVL tree， rbtree僅維持住顏色限制，rotate 次數並沒有 AVL tree 來的頻繁，且 rotate 為代價較大的行為。因此在對於大量插入以及刪除，rbtree 是比起AVL tree 是更好的選擇。 在參考老師所著作的書，在空間方面，AVL tree 中的節點要額外的空間來記錄兩邊子樹的高度，要採用 int 型別的參數來記錄，而rbtree 只需要 1 bits 來記錄該點顏色就可以，因此 rbtree 又相比起來更省空間。 參考資料 : Linux 核心的紅黑樹 - HackMD AVL tree 的實作有何缺陷？ (針對 quiz3 -測驗 2 ) 目前是認為 avltree.h 僅提供設置節點其 parent 的函式 avl_set_parent_balance 以及找出其 parent 的函式 avl_parent ，但沒有提供新插入的點是置於 parent 的右子節點或是左子結點的相關函式。而在實作 priority queue 的 insert 也沒有說明 new_entry 是在 AVL tree 中的位子。 關於 Linux 核心原始程式碼 commit 65e8354ec13a45414045084166cb340c0d7ffe8a

contributed by <kart81604> 測驗1 :::success AAAA = 8 BBBB = 32 CCCC = x + 1 ::: 程式碼原理

contributed by < kart81604 > :::danger 注意細節！ :notes: jserv ::: 測驗一 :::success AAA = item