PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 资结 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就没特别说,所以不知道是否一样)
作者:
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
作者:
jasoncph
(Ben)
2018-11-17 21:24:00
#1KoZwfmg
作者:
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">
作者:
jwlhs104
(机智小字典)
2018-11-18 02:16:00
两种树插入一个node都是最多两次旋转 应该是答案错了
继续阅读
[理工] OS RR排班
AAQ8
[理工] 线代题库班p5!
Aa841018
[理工] 线代 第七章
AAQ8
[理工] 几题计组
decoder
算法 103交大资工 flow network
paralyzation
[理工] 离散 递回
sooge
[理工] 算法 substitution method
wilson50101
[理工] 104政大资科OS
bmpss92196
[理工] 103政大资科OS
bmpss92196
[理工] 计组浮点数&资结一题证明
wacheck
Links
booklink
Contact Us: admin [ a t ] ucptt.com