Re: [理工] [DS] 台大電機100

看板Grad-ProbAsk作者 (ekalteiuQ)時間12年前 (2012/02/14 11:01), 編輯推噓5(5推 0噓 15→)
留言20則, 6人參與, 最新討論串2/3 (看更多)
※ 引述《LADMCODS (我要上112)》之銘言： : http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100412.pdf : 我想問第10題的A選項 : the number of rotations per insert/delete operation in a red-black tree : is O(log n) : 毫無頭緒 不知道要不要選 @@ : 先謝過了! 看到推文的各位都是選CDE，想請教一下B選項， 不是很清楚二者的高度誰大誰小，因為都是balanced， 白痴的試了好幾串data，二個建出來的高度都一樣... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.169.183.107
→
02/14 11:31, , 1F
實際case我也想不到 不過AVL較嚴格 高度小於等於紅黑
02/14 11:31, 1F
→
02/14 11:32, , 2F
應該是在wiki看到的
02/14 11:32, 2F
→
02/14 11:35, , 3F
恩...高度可能有問題 待查
02/14 11:35, 3F
→
02/14 11:39, , 4F
我也有看到維基這段，但不是很確定，所以再來問看看
02/14 11:39, 4F
→
02/14 11:46, , 5F
HOROWITZ版 P508最上面 可以當作原因嗎?
02/14 11:46, 5F
→
02/14 14:52, , 6F
手上沒有這本書，可以簡單打一下內容嗎？
02/14 14:52, 6F
→
02/14 15:58, , 7F
the worst-case height of a red-black tree is more than
02/14 15:58, 7F
→
02/14 15:59, , 8F
the worst-case height of an AVL tree with the same
02/14 15:59, 8F
→
02/14 15:59, , 9F
number of (internal) nodes.
02/14 15:59, 9F
→
02/14 16:00, , 10F
可以當作可當作原因嗎? 因為這是worst-case的時候
02/14 16:00, 10F
→
02/14 16:05, , 11F
應該ok吧
02/14 16:05, 11F
→
02/14 16:06, , 12F
看到internal才想到 紅黑是extend 沒說只管internal
02/14 16:06, 12F
→
02/14 16:07, , 13F
隨便都比較高吧lol
02/14 16:07, 13F
推
02/14 16:10, , 14F
try this sequence: 1, 2, 3, 4, 5, 6
02/14 16:10, 14F
推
02/14 18:10, , 15F
紅黑樹可以弄出在AVL中是不屬於balance的情形
02/14 18:10, 15F
推
02/14 18:17, , 16F
用1 2 3 4 5 6就可以看出來了
02/14 18:17, 16F
推
02/14 18:20, , 17F
原來bbhands已經講了XDD
02/14 18:20, 17F
推
02/14 18:24, , 19F
對耶 囧 感謝
02/14 18:24, 19F
→
09/11 14:56, , 20F
原來bbhands已經 https://daxiv.com
09/11 14:56, 20F
‣ 更多 Quietlake 的文章
文章代碼(AID): #1FESwRVh (Grad-ProbAsk)
‣ 更多 Quietlake 的文章
文章代碼(AID): #1FESwRVh (Grad-ProbAsk)