添加到SortedSet <T>及其复杂性

Question

MSDN声明以下SortedSet(T).Add方法:

如果Count小于内部阵列的容量,则此方法是O(1)操作.

有人可以解释"怎么样"？我的意思是在添加新值时,我们需要找到一个正确的位置来添加一个值(将其与另一个值进行比较),内部实现看起来像一个具有O(log N)插入复杂度的"红黑树".

Answer 1

评论完全错了.是的,它是一个红黑树,O(log(n))用于插入.看看Reflector看看这个,私有的AddIfNotPresent()方法包含一个while()循环来查找插入点,使用正常的红黑节点遍历.

这个doc bug已经由你知道谁提交了.