[理工] 資結 R-B tree/AVL tree rotation次數
作者: st945712 (st945712) 2018-11-17 20:33:59
小弟有2個問題想請教各位
![]()
![]()
1. 圖一的E選項跟圖二的D選項
這兩個選項都沒有在答案裡頭，難道insert一個new Node的rotation次數有可能會超過兩次嗎??
2.請問R-B tree跟AVL tree的rotation次數算法是一樣的嗎?
都是RL,LR記做兩次Rotation，而LL與RR只記一次Rotation?
(記得洪逸只有在AVL tree說過LR與RL要多記一次旋轉，R-B tree就沒特別說，所以不知道是否一樣)
1. 圖一的E選項跟圖二的D選項
這兩個選項都沒有在答案裡頭，難道insert一個new Node的rotation次數有可能會超過兩次嗎??
2.請問R-B tree跟AVL tree的rotation次數算法是一樣的嗎?
都是RL,LR記做兩次Rotation，而LL與RR只記一次Rotation?
(記得洪逸只有在AVL tree說過LR與RL要多記一次旋轉，R-B tree就沒特別說，所以不知道是否一樣)
作者: jasoncph (Ben) 2018-11-17 21:03:00
應該跟AVL一樣
作者: seika555 (kakkoii) 2018-11-17 21:07:00
在想是不是rotation完之後，因為又遇到紅紅因此要在rotation就會超過兩次https://i.imgur.com/okmel4o.jpg
作者: seika555 (kakkoii) 2018-11-17 21:59:00
啊我耍雷 上面那張圖的轉是錯的
作者: st945712 (st945712) 2018-11-17 22:36:00
有可能旋轉上去又遇到一次紅紅嗎@@? 我想不太出有什麼例子
作者: seika555 (kakkoii) 2018-11-17 22:39:00
後來看j大提供的文 好像真的不會遇到 紅黑樹旋轉過後就不會再動了 而且此題答案好像有誤？
作者: jasoncph (Ben) 2018-11-17 23:31:00
這個講得滿詳細的![]()
" target="_blank" rel="nofollow">
![]()
" target="_blank" rel="nofollow">作者: jwlhs104 (機智小字典) 2018-11-18 02:16:00
兩種樹插入一個node都是最多兩次旋轉 應該是答案錯了