c***g 发帖数: 472 | 1 what's the downside of the sigleton?
what's the downside of the binary search tree compared to linked list? |
g**e 发帖数: 6127 | 2
1. development confusion
2. unite test difficulty
3. possible throughput problem with multithread program
4. slightly overhead for checking instance existance every time
1. worst case BST degenerates to a linked list
2. O(logn) insert/delete time
3. conding complexity
【在 c***g 的大作中提到】 : what's the downside of the sigleton? : what's the downside of the binary search tree compared to linked list?
|
c*********t 发帖数: 2921 | 3 我觉得对于linked list,
insert: 如果加到头,O(1); 如果要求加到某个有特定的key 的Node后的话,要从头
开始search到要加的位置,这时就是O(n)了。
delete: 如果给了那个node的指针,delete O(1); 可是如果只告诉你删除有某个给定
的key的那个Node,就是O(n).
【在 g**e 的大作中提到】 : : 1. development confusion : 2. unite test difficulty : 3. possible throughput problem with multithread program : 4. slightly overhead for checking instance existance every time : 1. worst case BST degenerates to a linked list : 2. O(logn) insert/delete time : 3. conding complexity
|
m**q 发帖数: 189 | 4 For BST, it uses more spaces than linked list - two pointers per entry
compared to one.
【在 g**e 的大作中提到】 : : 1. development confusion : 2. unite test difficulty : 3. possible throughput problem with multithread program : 4. slightly overhead for checking instance existance every time : 1. worst case BST degenerates to a linked list : 2. O(logn) insert/delete time : 3. conding complexity
|