添加到 SortedSet;及其复杂性
MSDN 声明以下 SortedSet(T).Add 方法：
如果 Count 小于内部数组的容量，则此方法的操作时间复杂度为 O(1)。
有人可以解释一下“怎么会这样”吗？我的意思是，当添加新值时，我们需要找到正确的位置来添加值（将其与其他值进行比较），并且内部实现看起来像具有 O (log N) 插入复杂度的“红黑树”。
MSDN states the following SortedSet(T).Add Method :
If Count is less than the capacity of the internal array, this method is an O(1) operation.
Could someone please explain "how so"? I mean when adding new value we need to find a correct place to add a value (comparing it with another values) and internal implementation looks like a "Red-Black tree" with O (log N) insertion complexity.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该评论根本就是错误的。是的，它是一棵红黑树，插入的时间复杂度为 O(log(n))。使用 Reflector 查看一下可以证明这一点，私有 AddIfNotPresent() 方法包含一个 while() 循环来查找插入点，使用正常的红黑节点遍历。
The comment is simply wrong. Yes, it is a red-black tree, O(log(n)) for inserts. Taking a look with Reflector bears this out, the private AddIfNotPresent() method contains a while() loop to find the insertion point, using normal red-black node traversal.