作者st945712 (st945712)
看板Grad-ProbAsk
標題[理工] 資結 R-B tree/AVL tree rotation次數
時間Sat Nov 17 20:33:59 2018
小弟有2個問題想請教各位
http://i.imgur.com/gSORaVw.jpg http://i.imgur.com/zki0Ro4.jpg
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就沒特別說，所以不知道是否一樣)
-----
Sent from JPTT on my Samsung SM-G950F.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.235.124
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1542458041.A.1AE.html
1F：推 jasoncph: 應該跟AVL一樣 11/17 21:03
2F：推 seika555: 在想是不是rotation完之後，因為又遇到紅紅因此要在rota 11/17 21:07
3F：→ seika555: tion就會超過兩次 11/17 21:07
6F：推 seika555: 啊我耍雷 上面那張圖的轉是錯的 11/17 21:59
7F：→ st945712: 有可能旋轉上去又遇到一次紅紅嗎@@? 我想不太出有什麼 11/17 22:36
8F：→ st945712: 例子 11/17 22:36
9F：推 seika555: 後來看j大提供的文 好像真的不會遇到 紅黑樹旋轉過後就 11/17 22:39
10F：→ seika555: 不會再動了 而且此題答案好像有誤？ 11/17 22:39
12F：推 jwlhs104: 兩種樹插入一個node都是最多兩次旋轉 應該是答案錯了 11/18 02:16