[理工] 成大-資料結構

[showyoulovex (NONO)]

題目:http://ppt.cc/FVrj

我想請教C和D

C)

我想問 紅黑樹的旋轉時間複雜度是跟AVL樹一樣嗎?

       都是O(1)嗎?因為筆記和書都沒寫 所以不確定

       若考試考LL.RR與LR.RL 處理時間是否一樣該怎麼回答

       一個是single旋轉另一個是double旋轉 但就時間複雜度的角度好像是相同的


D)

關於題目指的compare keys是什麼呢?

我的想法是只指父點，因此才能分出左右

但若無法比較就沒辦法建樹，又該如何決定是否為孫子或是祖先



請各位資結高手幫忙 感謝~

--
→ startlequiet:1080的兩倍是3160好嗎..你數學實在...
推 alwaysOGC:1F的數學老斯請假了嗎?
推 storyf66014:一樓的數學讓我好shack  XD
你們的國文老師、英文老師跟數學老師都請假了嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.134.26.47
推 louis719:如果光指"rotate"這個動作 確實是O(1)，不管哪種都是
推 pikachu123:Single跟Double差別在說一個改1個Link一個要改2個
→ pikachu123:但是改Link指示改指標 一樣是O(1)
感謝樓上兩位大大，大家都唸好熟喔@@

第二題有人有想法嗎 感謝~
※ 編輯: showyoulovex    來自: 140.134.26.47        (01/03 01:11)
推 metalalive:sorry 可以借個題目請教一下red-black tree 每次
→ metalalive:insert node 的 rotation 次數, 至多兩次嗎?有沒有可能
→ metalalive:三次以上, 3q