[理工] 算法台大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资演计算几何