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

Question

MSDN 声明了以下 SortedSet(T).Add Method :

如果 Count 小于内部数组的容量，则此方法是 O(1) 操作。

有人可以解释一下“怎么会这样”吗？我的意思是，当添加新值时，我们需要找到一个正确的位置来添加值（将其与另一个值进行比较），并且内部实现看起来像一个具有 O (log N) 插入复杂度的“红黑树”。

Answer 1

这个评论根本就是错误的。是的，它是一棵红黑树，插入的时间复杂度为 O(log(n))。用 Reflector 看一下就可以证明这一点，私有的 AddIfNotPresent() 方法包含一个 while() 循环来使用正常的红黑节点遍历来查找插入点。