# 一對一問題回答 ## 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](https://hackmd.io/@sysprog/linux-rbtree) ## AVL tree 的實作有何缺陷? (針對[ quiz3 -測驗 2 ](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-2)) 目前是認為 [avltree.h](https://gist.github.com/jserv/d03098d57fec03c89fdb2a449d7f6be2) 僅提供設置節點其 parent 的函式 `avl_set_parent_balance` 以及找出其 parent 的函式 `avl_parent` ,但沒有提供新插入的點是置於 parent 的右子節點或是左子結點的相關函式。而在實作 priority queue 的 insert 也沒有說明 `new_entry` 是在 AVL tree 中的位子。 ## 關於 Linux 核心原始程式碼 commit 65e8354ec13a45414045084166cb340c0d7ffe8a 關於以上的 commit 我找不到相關的資訊,需要老師提點。
×
Sign in
Email
Password
Forgot password
or
By clicking below, you agree to our
terms of service
.
Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Wallet (
)
Connect another wallet
New to HackMD?
Sign up