[理工] 算法台大103资演计算几何 clonsey1314 PTT批踢踢实业坊

楼主: clonsey1314 (Clonsey) 2017-12-02 14:55:29

解答上说要用"红黑树"制作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)

继续阅读