c# - 添加到排序集及其复杂性

Question

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

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

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

Answer 1

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

You -know-who已经提交了这个文档错误。