作者clonsey1314 (Clonsey)
看板Grad-ProbAsk
標題[理工] 演算法 台大103資演 計算幾何
時間Sat Dec 2 14:55:29 2017
https://imgur.com/a/2e0kn
解答上說要用"紅黑樹"製作T
請問為何要用紅黑樹?
只是因為要把時間壓在O(nlogn)嗎?
那這樣的話, 用AVL tree實作是不是也ok?
很少看到紅黑樹的實際應用所以第一次看到有點不知所措
另外, 解答上"query的接近值"指的又是甚麼?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.178.168
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512197732.A.2C3.html
※ 編輯: clonsey1314 (1.163.178.168), 12/02/2017 14:56:35
※ 編輯: clonsey1314 (1.163.178.168), 12/02/2017 15:01:29
推 djmez: 紅黑樹和AVL的時間複雜度一樣 但是因為犧牲平衡換較少的迴 12/02 15:46
→ djmez: 轉次數所以實際上會快一點點 12/02 15:46
對耶! 謝謝你喔!
※ 編輯: clonsey1314 (1.163.178.168), 12/02/2017 17:07:51
推 FRAXIS: 使用紅黑樹的好處是刪除的時候只有 O(1) 個旋轉 12/02 20:40
→ FRAXIS: 對於要設計 Augmented Search Trees 會比較容易些 12/02 20:41
→ FRAXIS: 但是對於這一題來說 因為只是要排序端點 其實用 AVL 也可 12/02 20:41
→ clonsey1314: 謝謝F大，長知識了！ 12/02 21:00
推 winiel559: 所以AVL不是O(1)個旋轉嗎，還以為是 12/02 21:13
推 FRAXIS: AVL 刪除時旋轉次數是 O(lg n) 12/03 06:26