c# - 添加到 SortedSet 及其复杂性

Question

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

If Count is less than the capacity of the internal array, this method is an O(1) operation.

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

Answer 1

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

这个文档错误已经been submitted由你知道的人。