作者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/cn.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