[理工] 演算法台大103資演計算幾何 clonsey1314 PTT批踢踢實業坊

[理工] 演算法台大103資演計算幾何

作者: clonsey1314 (Clonsey) 2017-12-02 14:55:29

https://imgur.com/a/2e0kn
解答上說要用"紅黑樹"製作T
請問為何要用紅黑樹?
只是因為要把時間壓在O(nlogn)嗎?
那這樣的話, 用AVL tree實作是不是也ok?
很少看到紅黑樹的實際應用所以第一次看到有點不知所措
另外, 解答上"query的接近值"指的又是甚麼?
謝謝

作者: djmez 2017-12-02 15:46:00

紅黑樹和AVL的時間複雜度一樣但是因為犧牲平衡換較少的迴轉次數所以實際上會快一點點

作者: FRAXIS (喔喔) 2017-12-02 20:40:00

使用紅黑樹的好處是刪除的時候只有 O(1) 個旋轉對於要設計 Augmented Search Trees 會比較容易些但是對於這一題來說因為只是要排序端點其實用 AVL 也可

作者: clonsey1314 (Clonsey) 2017-12-02 21:00:00

謝謝F大，長知識了！

作者: winiel559 (大漢天威) 2017-12-02 21:13:00

所以AVL不是O(1)個旋轉嗎，還以為是

作者: FRAXIS (喔喔) 2017-12-03 06:26:00

AVL 刪除時旋轉次數是 O(lg n)

繼續閱讀

[理工] OS blocking/non-blocking/send/receiveclonsey1314 [商管] 清大統研azazazaz [理工] 資結程式執行次數追蹤qwer911 [理工] 高成工程機率題庫下冊p.144danny0108 [理工] 101 台大線代TampaBayRays [理工] 自控時域設計pttrzong [理工] 資結題庫-時間複雜度magic83v [理工] 演算法 P/NP/NPCclonsey1314 [理工] 離散無理數證明clonsey1314 [請益] 補數基本概念wayneshiau

[理工] 演算法 台大103資演 計算幾何

[理工] 演算法台大103資演計算幾何