[理工] 107 清大計科 MOUOREO PTT批踢踢實業坊

作者: MOUOREO (毛毛) 2018-02-04 11:38:51

https://i.imgur.com/HECRgZu.jpg
想請問大家這兩題的做法，我跟他人討論的結果有點出入~想趁下一間還沒考之前釐清一
下觀念。
而下面那題應該是紅黑鏈結的轉換而不是轉成紅黑節點吧？還是兩種方式都可以呢？
謝謝大家

作者: taida (taida) 2018-02-04 12:07:00

這要用資結版的紅黑不能用演算法版的以link在234tree是否存在辨別是黑色還是紅色

作者: howard31622 (howard) 2018-02-04 12:11:00

下面那題就拉中間的旁邊就變紅色的看到我旁邊都空白心裡好開心

作者: MOUOREO (毛毛) 2018-02-04 12:28:00

我主要是想知道大家刪除後的答案啦～我也是link做

作者: taida (taida) 2018-02-04 12:40:00

我是把20和25合併變成leafRoot剩30 40其餘不變

作者: MOUOREO (毛毛) 2018-02-04 12:56:00

我問其他人是那樣做沒錯但筆記不是寫要跟sibling借嗎所以我是把35拉上去當root, 20,25,30當leaf可能我想太多，6分直接不見QQ

作者: Azlar911 (Azlar) 2018-02-04 13:00:00

好像是如果不能rotate才combine

作者: q1qip123 (wtlee) 2018-02-04 13:10:00

下面那題也是用上面題目給的圖吧？

作者: howard31622 (howard) 2018-02-04 13:18:00

對啊

作者: q1qip123 (wtlee) 2018-02-04 13:28:00

感謝看原po回文怕誤會題目意思～

作者: gary70812 (1) 2018-02-04 13:33:00

借問graph representation那題化成有向圖是不是就Ｇ了

作者: taida (taida) 2018-02-04 13:34:00

Rotate應該是要用在隔壁有多的才行我記得隔著一個的應該是不行？剛剛查過了只能跟隔壁的作rotate 所以這題應該是要combine

作者: MOUOREO (毛毛) 2018-02-04 14:28:00

可是不是隔壁也是sibling啊，這樣筆記描述好像有點不清楚

作者: taida (taida) 2018-02-04 16:22:00

這可能就是筆記沒寫清楚的問題了

作者: a020304888a (張小台) 2018-02-04 18:16:00

一定只能跟隔壁rotation 不然就不是BST了

作者: yangtz (æ“Ž) 2018-02-05 02:53:00

先借，發現不能借用合併，往上遞迴檢查

作者: nova06091 2018-02-06 07:49:00

只能康拜啦～

繼續閱讀